Задача про подбрасывание монеты

[oxid]

Привет!
Подскажите пожалуйста:
Найти вероятность того, что при пяти подбрасываниях монеты герб выпадет по крайней мере 3 раза подряд.

Решаю по формуле включений-исключений
C_3^1 \cdot 4/2^5 - C_2^1*1/16+1/2^5

Ответ неправильный. Если выкинуть послднее слагаемое, то вроде бы верно.

[Aarnikotka]

разбейте лучше на несовместные события, потом сложите, и все получится

[oxid]

Это я уже пробовал.
Но есть еще другая задача, где подбрасываний 10.
И кажется что метод включений-исключений все равно должен работать 8(

[Aarnikotka]

опять же через сумму несовместных - 3 герба по 10 ячейкам лягут 7-ю вариантами (то есть 10-k, k=3:10, сочетания из 10-к по 1 суммируете и умножаете на $1/1024 $) а как вы здесь представляете включение-исключение. в чем совместность?

-- 05.07.2014, 22:55 --

хотя неправ, надо еще считать варианты три герба встретятся два раза на 10 подбрасываниях, например

[arseniiv]

Рассмотрите такие вероятности:
• $p_3(n)$ того, что три герба подряд встретились в каких-нибудь предыдущих $n$ подбрасываниях;
• $p_2(n)$ того, что последними в серии предыдущих $n$ подбрасываний были, с сохранением порядка, не-герб, герб, герб;
• $p_1(n)$ того, что последними в серии предыдущих $n$ подбрасываний были, с сохранением порядка, не-герб и герб;
• $p_0(n)$ того, что последним подбрасыванием из предыдущих $n$ был не герб
и выразите $p_i(n)$ через $p_i(n-1)$. Получатся рекуррентные соотношения, из которых можно будет найти $p_3(n)$ для любого $n$, зная, что $p_0(0) = 1$ и $p_1(0) = p_2(0) = p_3(0) = 0$.

[oxid]

Спасибо, попробую. А не подскажите где ошибка в моей формуле? Я рассуждал так - вероятность что есть три герба подряд, минус вероятность четыре герба подряд плюс пять подряд.. Кажется классическая формула...

[arseniiv]

oxid в сообщении #884364 писал(а):

А не подскажите где ошибка в моей формуле?

Ошибка — это вещь не всегда локализуемая.

Хотя вот странно, у вас в формуле есть и $\cdot$ и $*$ — к чему бы это… Но ведь это не та ошибка, которую вы бы хотели?

[oxid]

Локализовал ошибку. В число всех комбинаций с тремя орлами входит 3 комбинации когда выпали только орлы. А в число комбинаций с 4 орлами входит 2 таких. Т.е нужно только два члена это суммы. И обычная формула тут видимо не действует.


Правда не получается как то обобщить.

[arseniiv]

Обобщить можно рекуррентную последовательность $(p_0, p_1, p_2, p_3)$. Точнее, она уже и так обобщена — какое нужно $n$, то и берите. То, что она рекуррентно задана здесь, не значит, что её нельзя задать нерекуррентно. А если вы увидите там матрицу — вообще хорошо.

Может, попробуете составить соотношения?

[oxid]

Попробовал, но как-то не очень продвинулся

p_3(n) = p_3(n-3) \cdot 7/8 + (1-p_3(n-3))\cdot1/8 + ((1-p_3(n-3))\cdot7/8 )(p_2(n-3)/2 + p_2(n-3)/4 + p_1(n-3)/4 ) + p_3(n-3)/8

Т.е разбиваем пространство на 4 непресекающихся события -
либо 3 орла это три последних подбрасывания, либо они лежат среди n-3 первых подбрасываний. Либо они лежат "между", либо одновременно и там и там.
Между могут лежать вот такими способами - poo|о..., роо|оо..., ро|оо...

[Lia]

Aarnikotka
Замечание за неиспользование тега math. post884357.html#p884357

[arseniiv]

oxid в сообщении #884604 писал(а):

Попробовал, но как-то не очень продвинулся

$$p_3(n) = p_3(n-3) \cdot 7/8 + (1-p_3(n-3))\cdot1/8 + ((1-p_3(n-3))\cdot7/8 )(p_2(n-3)/2 + p_2(n-3)/4 + p_1(n-3)/4 ) + p_3(n-3)/8$$

Не-не-не, никаких $n-3$! Только $n-1$.

Думаю, я плохо объяснил, в чём соль способа и что вообще надо делать.

Для каждой последовательности бросков известно, есть в ней три герба подряд или нет. Бросание монеты переводит одну последовательность в другую, но при этом трёхгербовость появляется или не появляется у новой последовательности не как попало, а довольно по простому закону.

Когда мы получим трёхгербовую последовательность? Если она уже была такая и выпало что угодно, или если она не была трёхгербовая, но в конце у неё было два герба, и выпал герб. Ага, а последовательность такого вида как может получиться? Единственным образом — если была не трёхгербовая последовательность с не-гербом и гербом в конце и выпал герб. Ну а такая как может получиться? Если была не трёхгербовая последовательность, у которой в конце не герб, и выпал герб. Под конец, последовательность последнего вида может получиться из любой не трёхгербовой последовательности выпадением не-герба.

В самом начале у нас пустая последовательность, которую логично отнести к последнему типу; и назовём эти типы соответственно 3, 2, 1 и 0. Заметьте, что последовательность обязательно одного из этих типов, так что ничего не пропущено в описании.

Теперь представим, что мы что-то там набросали $n$ раз и не знаем, что это за последовательность, но можем знать, например, пару-другую вероятностей. К сожалению, выше в

arseniiv в сообщении #884363 писал(а):

• $p_3(n)$ того, что три герба подряд встретились в каких-нибудь предыдущих $n$ подбрасываниях;
• $p_2(n)$ того, что последними в серии предыдущих $n$ подбрасываний были, с сохранением порядка, не-герб, герб, герб;
• $p_1(n)$ того, что последними в серии предыдущих $n$ подбрасываний были, с сохранением порядка, не-герб и герб;
• $p_0(n)$ того, что последним подбрасыванием из предыдущих $n$ был не герб

я выразился неточно, и это могло вас запутать. $p_0, p_1, p_2$ относятся именно к не трёхгербовым последовательностям. (Тогда $p_0(n)+p_1(n)+p_2(n)+p_3(n) = 1$ для любого $n$, это потом можно использовать для проверки.)

Зная, как последовательности типов 3, 2, 1 и 0 получаются друг из друга, мы можем записать аналогичные соотношения для вероятностей $p_i(n)$ (каждой, иначе ответ не получится) через (все) $p_j(n-1)$. В меньшие длины уходить не надо, потому что это избыточно и всё только усложнит.

Попробуйте теперь снова.

-- Вс июл 06, 2014 23:39:36 --

Можно разбить последовательности на большее число классов, но это опять только усложнит дорогу к ответу.

Подобным способом можно строить ДКА, распознающий во входной строке вхождения какого-то заданного множества подстрок. В нашем случае — последовательности (герб, герб, герб). По построенному конечному автомату можно, если вероятности появления символов (у нас это результаты бросания монеты), получить цепь Маркова и вот этот метод вычисления вероятности того, что в последовательности есть какая-то подпоследовательность (или какая-то из нескольких!). Если вы знаете про конечные автоматы в достаточной мере, это может помочь в понимании манипуляций выше, мне кажется.

[oxid]

Получились такие соотношения
$p_3(n) = p_3(n-1) + p_2(n-1)/2$
$p_2(n) = p_1(n-1)/2$
$p_1(n) = p_0(n-1)/2$
$p_0(n) = n > 0 ? 1/2 : 1$

В таком варианте выдает верный ответ.
Но, при больших n он переваливает через 1 ;)

$p_3(n) = p_3(n-1) + (1- p_3(n-1)) p_2(n-1)/2$
Тут ответ выдается неверный, но при больших n работает корректно.

Проверял программой на python

[arseniiv]

Вот верный:

$$\mathbf p(n) \equiv \begin{bmatrix} p_3(n) \\ p_2(n) \\ p_1(n) \\ p_0(n) \end{bmatrix} = \begin{bmatrix} 1 & 1/2 & 0 & 0 \\ 0 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 1/2 \\ 0 & 1/2 & 1/2 & 1/2 \end{bmatrix} \begin{bmatrix} p_3(n-1) \\ p_2(n-1) \\ p_1(n-1) \\ p_0(n-1) \end{bmatrix} \equiv A\mathbf p(n-1).$$

(В таком виде удобнее смотреть на вероятности переходов.)

Видно, что вы только в одном уравнении — для $p_0$ — забыли, что трёхгербовая последовательность никак уже «назад» не вернётся, и вид у него будет $p_0(n) = (p_2(n-1) + p_1(n-1) + p_0(n-1))/2$. (Проверку можно не писать, потому что здесь достаточно, чтобы эти соотношения были верны даже только при $n>0$.)

А теперь — магия. С пустой последовательностью всё ясно: как я выше уже писал, в ней нет гербов (да, поиграю КО ), т. е.

$$\mathbf p(0) = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}.$$

Чтобы получить $p_3(1)$, получим все вероятности $\mathbf p(1)$, умножив слева на матрицу вероятностей переходов:

$$\mathbf p(1) = A\mathbf p(0).$$

Чтобыполучить $p_3(2)$, получим все вероятности $\mathbf p(2)$, умножив снова:

$$\mathbf p(2) = A\mathbf p(1) = A^2\mathbf p(0).$$

Можно увидеть (и при желании строго доказать матиндукцией), что

$$\mathbf p(n) = A^n\mathbf p(0).$$

Это, в сущности, решение, потому что в конце надо взять первую компоненту, а это тоже оформляемо умножением на матрицу. Возвести $A$ в натуральную степень можно «за одно действие» разными способами, напр., с помощью жордановой нормальной формы (слова страшные, а так-то всё несложно; можете, например, в этой теме посмотреть, хотя лучше почитать).

[oxid]

Спасибо, это очень интересный метод!

Но может ли кто про формулу прояснить?