распределение серии успехов заданной длины в схеме Бернулли

[rus33]

Помогите, pls, с задачей:
Проводится n испытаний по схеме Бернулли с вероятностью успеха р. Какова вероятность того, что серия из k успехов выпадет ровно m раз?

[Dan_Te]

Не понял условие. Что такое "серия из k успехов"? Это k успехов подряд?

[Someone]

rus33 писал(а):

Помогите, pls, с задачей:
Проводится n испытаний по схеме Бернулли с вероятностью успеха р. Какова вероятность того, что серия из k успехов выпадет ровно m раз?

Ещё вопросы. Если у нас было подряд (k+1) успехов и k>1, то как считать число серий по k успехов: 2, 1 или 0? А если успехов было 2k, то число серий равно 0, 1, 2 или k+1?

[Гость]

Да, имелось ввиду k успехов подряд

[rus33]

Someone писал(а):

Если у нас было подряд (k+1) успехов и k>1, то как считать число серий по k успехов: 2, 1 или 0? А если успехов было 2k, то число серий равно 0, 1, 2 или k+1?

Если подряд (k+1) успехов и k>1, то число серий по k успехов равно 0.
Если успехов подряд было 2k, то число серий тоже равно 0.
В серии должно быть ровно k успехов подряд, т.е. напр.
...0111110... - есть одна серия из 5 успехов подряд.

[незваный гость]

Начнем, пожалуй... Не уверен, что успею закончить за раз, ибо велика работа сия, а лучина догорает...

Итак, нам надо найти вероятность $k$ серий из $m$ успехов в последовательности из $n$ испытаний.

1) Обозначим $p_{ins}(n, x)$ вероятность того, что последовательность из $n$ испытаний имеет ровно $x$ мест, куда можно вставить успехи так, что образуются ровно нужные нам серии. Всякому ясно, что место сие либо между двумя неуспехами, либо в начале коли последовательность неуспехом начинается, либо в конце, коли последовательность кончается на неуспех. Сразу запишем $p_{ins}(0, 0)=0$, $p_{ins}(0, 1)=1$, $p_{ins}(1, 0)=p$, $p_{ins}(1, 1)=0$, $p_{ins}(1, 2)=1-p \leftrightharpoons q$.

Пусть $p_{ins;w}(n, x)$ - вероятность что последовательн ость кончается успехом, a $p_{ins;l}(n, x)$ - неуспехом. Тогда $p_{ins}(n, x) = $ $p_{ins;w}(n, x) + p_{ins;l}(n, x) $. Теперича, испытамши еще раз:

• $p_{ins;l}(n, x)$ с вероятностью $p$ переходит в $p_{ins;w}(n+1, x-1)$ (сократилось одно место вставки на конце);
• $p_{ins;l}(n, x)$ с вероятностью $q$ переходит в $p_{ins;l}(n+1, x+1)$ (добавилось одно место вставки на конце);
• $p_{ins;w}(n, x)$ с вероятностью $p$ переходит в $p_{ins;w}(n+1, x)$ (ничего не изменилось);
• $p_{ins;w}(n, x)$ с вероятностью $q$ переходит в $p_{ins;l}(n+1, x+1)$ (добавилось место вставки в конце).

Итого:

• $p_{ins;l}(n, x) = q (p_{ins;l}(n-1, x-1) + p_{ins;w}(n-1, x-1)) = $ $ q\, p_{ins}(n-1, x-1)$;
• $p_{ins;w}(n, x) = p \, p_{ins;w}(n-1, x) + q \, p_{ins;l}(n-1, x+1)$.

Используя первое из этих уравнений, и выражая $p_{ins;w}(n, x)$ из предшевствуещего как $p_{ins;w}(n, x) = p_{ins}(n, x) -$p_{ins;l}(n, x) $, изымаем рекурентное соотношение: $p_{ins}(n,x) = p \, p_{ins}(n-1,x) + q \, p_{ins}(n-1,x-1) +$ $ p\,q(p_{ins}(n-2,x)-p_{ins}(n-2,x-1))$. Ну, теперича засучиваем рукава и доказываем методом математической (а не на базаре купленой!) индукции, что p_{ins}(n,n+1)=q^n и $p_{ins}(n,x)=\sum\limits_{y=x}^{n-1}C_{y+1}^{k}C_{n-1-y}^{y-k}p^{n-y}q^{y}$ при $0 \le x \le n$.

На смутные мысли наводит формула сия. Что могёт существовать способ найти ее без индукции, правильно посчитамши разбиения и их вероятности...

2. Пусть теперь $p^*(n,m,k)$ суть вероятность что последовательность из $n$ испытаний содержит по крайней мере $k$ серий по $m$ успехов. Вероятность того, что у нас есть $x$ мест вставки среди $n - m k $ есмь $p_{ins}(n -m k,x)$, из $x$ мест вставки можно выбрать $k$ $C_x^k$ способами, итого имеем $p^*(n,m,k) =p^{m k} \sum\limits_{x=k}^{n-m k +1}C_x^k p_{ins}(n - m k, x) = $ $p^{m k} \left(\sum\limits_{x=k}^{n-m k}C_x^k p_{ins}(n - m k, x) + q^{n - m k} C_{n - m k +1}^{k} \right)$.

3. Ну и наконец, $p(n,m,k) = p^*(n,m,k) - p^*(n,m,k+1)$.

~~~

Есть, однако, одно место, которое и самому мне подозрительно - особливо при чтение его. А именно, в пункте два, не посчитали ли мы некоторые варианты дважды, а то и вовсе - многократно. Ну-ка содержит $n - m k$-последовательность серии искомые. Еще думать надо. А может, найдется добрый человек, поправит али подтвердит.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Feci, quod potui

[незваный гость]

незванный гость писал(а):

Есть, однако, одно место, которое и самому мне подозрительно - особливо при чтение его. А именно, в пункте два, не посчитали ли мы некоторые варианты дважды, а то и вовсе - многократно.

К сожалению, я был прав в своих подозрениях, и не прав в решении.

[rus33]

незванный гость писал(а):

К сожалению, я был прав в своих подозрениях, и не прав в решении.

Может ли незванный гость или кто другой поправить?

[Evgeni_1003]

Будем рассматривать строки из букв p,q (вероятности буквы p в разных позициях независимы и равны p).
Пусть $P_{s,i,L}$ - вероятность для строки длины L заканчиваться на $qp^i$ и содержать ровно S фрагментов вида $qp^kq$.
В этом определении мы считаем, что перед строкой записана буква q.
Тогда
$P_{s,0,l+1} = q(P_{s,o,l}+...+P_{s,k-1,l}+{\mathbf P_{s-1,k,l}} + P_{s, k+1,l}+...)$\par $P_{s, i+1,l+1} = pP_{s,i,l}$\par
Запишем формулы для мат. ожидания $E_{i,l} = \Sum_{s=0}^{\infty}sP_{s,i,l}$ (абсолютного, а не относительного) тогда если обозначить $S_l = \sum_{i=0}^{\infty}E_{i,l}$ и $P_{i,l} = \sum_{s=0}^{\infty}P_{s,i,l}$
можно показать что $E_{0,l+1} = qS_l + qP_{k,l}$ \par $E_{i+1,l+1} = pE_{i,l}$
следовательно $S_{l+1} = S_l + qP_{k,l}$
где $P_{i,l}$-вероятность для строки заканчиваться на $qp^i$.

Легко видеть, что $P_{i,l} = 0$, при $i<l,$\par $P_{i,i} = p^i,$\par $P_{i,l} = qp^i$, при $i>l$ \par

Так как в рассмотренных формулах не учитывается k успехов в конце (т.е. без ограничивающей q сзади), то полный ответ будет $\frac{E_{0,l+1}}{q} = S_l + P_{k,l}$.
Итоговый ответ: $0$, при $l<k$ \par $p^k$, при $l=k$\par $qp^k(2+q(l-k-1))$, при $l>k$\par

[Гость]

Evgeni_1003 писал(а):

Итоговый ответ: $0$, при $l<k$ \par $p^k$, при $l=k$\par $qp^k(2+q(l-k-1))$, при $l>k$\par

То есть ответ не зависит от либо $m$ - количество элементов в серии, либо $k$ - число серий по $m$ элементов?!? Не верю!

[Evgeni_1003]

Я совсем забыл, что именно требовалось в задаче.
То, что написано в качестве ответа - математическое ожидание количества серий (там так все замечательно упрощалось, если проинтегрировать по кол-ву серий).

А про исходную задачу:
Опять будем рассматривать подстроки вида $qp^pq$, т.е. опять приписываем q перед строкой и временно забудем про возможную последнюю группу из k успехов без q в конце.

Рассмотрим строки вида $(qp^k)^lq$. Для каждого разбиения числа $m$ на $s$ упорядоченных сомножителей $m = l_1+l_2+...+l_s$ построим строки длины $L$ с подстроками $(qp^k)^{l_i}q$ в указанном порядке. А именно выберем начальное положение для каждой группы - это можно сделать $C_{L-m(k+1)}^{s}$ способами. Остальные буквы расставим произвольно.
Рассмотрим наборы $T_m$строк полученные таким образом для всех разбиений числа $m$ на слагаемые. Суммарная вероятность строк в наборе будет $X_m = \sum_{s=1}^{s=m}C_{L-m(k+1)}^{s}p^{km}q^{m+s}V_{m,s}$ где $V_{m,s} = C_{m-s}^{s-1}$ - количество способов разбить число $m$ на $s$ слогаемых (с учетом порядка).
Рассмотрим теперь строку с $m$ сериями. В наборе $T_k$ ($k\le m$) она встречается $C_m^k$ раз. Таким образои получаем

$X_k = \sum_{i=s}^{\infty}C_i^kP_i$, где $P_i$ - искомые вероятности строк с $i$ сериями успехов.
И обращаем ее жуткими формулами
$P_m = k_{m,0}X_m+...+k{m,i}X_{m+i}$ где
$k_{m,0} = 1 = C_{m}^{m}$\par $k_{m,1} = -C_{m+1}^{m}$\par $k_{m,2} = -C_{m+2}^{m}+C_{m+2}^{m+1}C_{m+1}^{m} = C_{m+2}^m$\par $k_{m,3} = -C_{m+3}^{m}+C_{m+3}^{m+1}C_{m+1}^{m}+C_{m+3}^{m+2}C_{m+2}^{m} - C_{m+3}^{m+2}C_{m+2}^{m+1}C_{m+1}^{m} = -C_{m+3}^m$\par ...
Итого
$P_m = \sum_{i=0}^{\infty}(-1)^iC_{m+i}^mX_{m+i}$\par $X_m = (qp^{k})^{m}\sum_{s=1}^{s=m}C_{L-m(k+1)}^{s}C_{m-s}^{s-1}q^s}$
Примерно так
Хотя в верность ВСЕХ сразу формул я и сам не верю, навеняка где-то ошибка

[незваный гость]

Evgeni_1003 писал(а):

Хотя в верность ВСЕХ сразу формул я и сам не верю, навеняка где-то ошибка

Evgeni_1003, скажите, пожалуйста, где?

[Evgeni_1003]

Во-первых, описка в формуле для $V_{m,s} = C_{m-1}^{s-1}$ - количества разбиения на слагаемые.
Во-вторых, это все относится к подстрокам $qp^kq$. Т.е. дополнительно надо учесть k успехов в начале и в конце.
В остальном ошибок вроде нет (я проверил эти формулы и реальные вероятности для l=1..100, k = 1,2,3,4,5, p = 0.3 и p=0.6).
Ответ строка длина $L$ содержит $m$ подстрок $qp^kq$ с вероятностью

$P_{m,L} = (-1)^m\sum_{i=m}^{\infty} (-qp^k)^{i} C_i^m \sum_{s=1}^{i}C^s_{L-i(k+1)}C^{s-1}_{i-1}q^s$

Вероятности в исходной задаче легко получаются из приведенных.
Кстати, мат ожинаие, которое я подсчитал другим способом, здесь присутствует в виде
$\sum_{i=0}iP_i = \sum_{i=1} C_i^1P_i = X_1 = qp^kC^1_{L-(k+1)}q = q^2p^k(L-k-1)$