в ряде из n событий встретится m подряд идущих 1

Zag2t

Есть 2 исхода 0,1. С вероятностью p выпадает 1.
С какой вероятностью в ряде из n событий встретится m подряд идущих 1?

seregaohota

при m>n.
Ровно m или больше или равно? Или точно m, ограничена 0-ми и началом-концом n серии?

Zag2t

Ограничивать 0-ми не надо. Можно и больше m.

Zag2t

из коментов к http://plakhov.livejournal.com/45868.html зы гугл все найдет.
посчитать можно из комбинаторных соображений.
начнем с простого случая.
допустим, нам нужно узнать сколько всего последовательностей из нулей и единиц длины n содержат подпоследовательность из двух, скажем, единиц.
Пусть A_n - число таких последовательностей. разделим их на три группы: те у которых на первом месте стоит 0, те у которых на двух первых местах стоят 11 и те, у которых на 2х первых местах стоят 10. Из такого разделения очевидно можно получить, что
A_n = A_{n-1} + 2^{n-2} + A_{n-2}
Вычтем из обоих частей 2^n и обозначим B_n = A_n - 2^n. Тогда получим
B_n = B_{n-1}+B_{n-2}
Т.к. очевидно А_2 = 1 и A_3 = 3, то B_2 = -3 и B_3 = -5.
следовательно B_n = -Fib_{n+2}, где Fib_n - числа Фибоначчи. Тогда вероятность что в случайной последовательности нулей и единиц длинны n мы встретим последовательность содержащую 2 подряд единицы будет p^(2)_n = 1 - Fib_{n+2}/2^n
аналогично можно показать что для последовательности из k единиц, вероятоность будет
p^(k)_n = 1 - Fib^(k)_{n+2}/2^n.
Где Fib^(k)_n есть k-step Fibonacci numbers http://mathworld.wolfram.com/Fibonaccin-StepNumber.html
Вероятность не встретить 7 подряд нулей (или единиц) в последовательности из 100 символов будет примерно 0.7 как мне программка говорит. Посчитать вероятность что не встретится 7 одинаковых цифр времени уже нет, надо убегать

а теперь вопрос: Я правильно помню, что нет формул для вычислений чисел фибоначчи?

svetik5623190

Стандартная задача, решение наверняка можно найти в любом учебнике по теории вероятности.
а теперь вопрос: Я правильно помню, что нет формул для вычислений чисел фибоначчи?
Да вроде бы есть Нужно решить конечно-разностное уравнение
a_{n+2} - a_{n+1} - a_n = 0, \forall n = 1,2, 3....
с начальными условиями
a_1 = 1
a_2 = 1

Zag2t

апгрейд не получается сделать из p=0.5 до общего.

svetik5623190

Методика решения примерно такая: членим на элементарные события, из них составляем сложное.
Сейчас попробую что-то придумать, если не усну: очень спать хочу.

svetik5623190

Посмотри кстати книжку какую-нибудь по дискретной математике, там вполне может быть. Например книжку Чашкина.

kira-kulikova

События независимы?
Тогда, P(1..10...0)=p^n(1-p)^(m-n)
теперь "сдвигаем" единицы в векторе: (01..10..0)..(0..01..1)
итого: (m-n)*p^n*(1-p)^(m-n)

Zag2t

Я раньше на Дискре учился. А щас нет ни знаний, ни литературы. Все улетучилось в некуда.

Zag2t

Мне актуально, когда p=0.6 а 15>m>5

z-helenium

 Производящая функция.

seregaohota

А n какие?

stm7543347

Да вроде бы есть Нужно решить конечно-разностное уравнение
a_{n+2} - a_{n+1} - a_n = 0, \forall n = 1,2, 3....
с начальными условиями
a_1 = 1
a_2 = 1
+1. Получается сумма двух экспонент. Если учесть, что одна из них быстро стремится к нулю, можно вычислять только вторую и округлять результат. ^_^

Zag2t

А n какие?

это ваще любое....

seregaohota

Пусть p вероятность выпадения единички, q=1-p вероятность выпадения нуля.
Обозначим P_n = P_n(>=m) - вероятность в n серии встретить >= m единичек подряд.
Кстати, P_n(=m) = P_n(>=m) - P_n(>=m+1) есть вероятность, что в n-последовательности встретилась подпоследовательность ровно из m единичек, но нет ни одной более длинной подпоследовательности из m+1 единички.
Итак, тогда полная группа независимых событий когда последовательность начинается с заданной и соответствующие вероятности встретить в исходной последовательности m единичек подряд

0 q * P_{n-1}
10 q*p * P_{n-2}
110 q*p^2 * P_{n-3}
1110 q*p^3 * P_{n-4}

111..110 q*p^{m-1} * P_{n-m}
11111111 p^m * 1

Откуда рекурентная формула

P_n = q*(
P_{n-1}
+ p *P_{n-2}
+ p^2*P_{n-3}
+ p^3*P_{n-4}
+ ...
+ p^{m-1}*P_{n-m}
)
+
p^m

при начальных условиях

P_0 = P_1 = ... = P_{m-1} = 0.

Начиная с n=m до нужного тебе значения считается численно.
Аналитически можно вывести как полином от p, но затруднительно.
По индукции легко проверить заменяя все P_k в правой части рекурентной формулы 1, что P_n < 1 при p<1.
Очевидно P_n стремится к 1 при n стремящемся к бесконечности и p>0.
Можно получить аналитическую формулу скажем при m=7 и p=0.6 как решение неоднородного разностного уравнения с начальными данными, но лениво, тем более всё равно характеристические числа как корни полинома 7 степени численно только вычислятся и будут комплексными вообще говоря. Не мне же это надо.

Zag2t

Всем спасибо…
Дальше я сам

seregaohota

Там ошибка была P_{n-(m-1)} вместо P_{n-m}. Я исправил.
Численно считается легко, так как при P_k в правой части сумма модулей коэффициентов <1 и ошибки не растут, то есть счёт в лоб устойчив.
Оставить комментарий
Имя или ник:
Комментарий: