Невыпадение четырех одинаковых значений кубика подряд

[manul91]

Человек кидает кубик пока у него не выпадет одно и то же значение 4 раза подряд.
Какова вероятность, что ему потребуется 1000 бросков или меньше?

Я рассуждал так. Пусть
$Q(n)$: вероятность что не упало одно и то же значение 4 раза подряд, вплоть до $n$-того броска включительно.
$P(n)$: вероятность что как раз на $n$-том броске, ВПЕРВыЕ попались 4 одинаковых значения (очевидно, последние четыре).

Имеем очевидную зависимость:
$A$) $Q(n) = 1 - (P(1) + P(2) + P(3) + .... + P(n))$

Далее, чтобы впервые попались 4 одинаковых значения на n-том броске, нужно чтобы:
- вплоть до $n$-4том не попадались одинаковых значения
- либо последние два одинаковы (вероятность 1/2), тогда мы должны швырнуть отличное от них, и потом еще три раза такое же
- либо последние два разные (вероятность 1/2), тогда мы должны швырнуть отличное от последнего, и потом еще три раза такое же
Или:
$B$) $P(n) = Q(n-4)( \frac{1}{2}\cdot \frac{5}{6} \cdot \frac{1}{6^3} + \frac{1}{2}\cdot \frac{5}{6}\frac{1}{6^3}) = \frac{5}{6^4}Q(n-4)$

Еще, для начальных значений знаем, что
$P(1), P(2), P(3) = 0, P(4) = \frac{1}{6^3}$
$Q(1), Q(2), Q(3) = 1$

Из $A$ и $B$ выше можно рекуррентно вычислить как $Q(n)$ так и $P(n)$ для любого $n$.

Например, для $n=5$ получаем из $B$ и $A$ соответно:
$P(5)=\frac{5}{6^4}Q(1) = \frac{5}{6^4} = P(6)=P(7)$
$Q(5) = 1 - (P(5) + P(4) + 0 + 0 + 0) = 1 - \frac{5}{6^4} - \frac{1}{6^3}$

Искомая вероятность, это
$1 - Q(1000)$
(неверно, что вплоть до 1000-ного броска ни разу не попались 4 одинаковых)

Вместо $A$ можно пользоваться эквивалентным соотношением (выводится если расписать $A$ для двух последовательных $n$ и вычесть друг от друга):
$Q(n) = Q(n-1) - P(n)$
или в итоге используя $B$, свести к единственном рекуррентном соотношении для $Q(n)$
$Q(n) = Q(n-1) - \frac{5}{6^4}Q(n-4)$

Вопросы:
- Верно ли решение, и рассуждения выше?
- Имеется ли более простое решение
- Можно ли (и как) получить $Q(n)$ например, в явном (не рекурсивном) виде..?

[venco]

manul91 в сообщении #1668371 писал(а):

либо последние два одинаковы (вероятность 1/2)

..., либо не встречу.

Почему, собственно, 1/2?

Вам надо разделить $P(n)$ на $P_1(n), P_2(n), P_3(n)$, по количеству одинаковых в конце. Они все разные.

[manul91]

venco в сообщении #1668374 писал(а):

..., либо не встречу.
Почему, собственно, 1/2?

Это из "соображений симметрии" но да, несколько глупо получилось (решил не исправлять однако в оригинальном сообщении).
Тем не менее, то же самое можно переформулировать (лучше) так:

Чтобы впервые попались 4 одинаковых значения на n-том броске, нужно чтобы:

- вплоть до $n$-4том не попадались одинаковых значения (вероятность $Q(n-4)$, по определению)
- паттерн для $n$ должен быть вида: ...****X|YYYY ; здесь прежде вертикальной черты это последовательность $n-4$ для которой точно знаем что нет четыре последовательных, суть в том что первая $Y$ должна отличаться от последней в последовательности (вероятность $\frac{5}{6}$), потом еще три раза должно выпасть то же $Y$ (вероятность $\frac{1}{6}$ каждый раз)
И опять выходит то же самое:
$B$) $P(n) = Q(n-4)(\frac{5}{6}\frac{1}{6^3}) = \frac{5}{6^4}Q(n-4)$

venco в сообщении #1668374 писал(а):

Вам надо разделить $P(n)$ на $P_1(n), P_2(n), P_3(n)$, по количеству одинаковых в конце. Они все разные.

Я об этом думал, но это означало бы что мы вовлекаемся в рассмотрение ситуаций когда четверка выпала бы раньше чем $n$-того броска, нас интересует случай когда четверка выпала впервые ровно на $n$-том броске (и не раньше).... это по определению $P(n)$?

P.S.
Для $P(5)$ например можно проверить независимым образом, из всех 6^5 последовательностей, 6*5 = 30 имеют паттерн XYYYY (первая отличается, последние четыре одинаковы), отношение выходит то же самое (подобным образом для $P(6), P(7)$)...

[venco]

Пардон, я перепутал у вас P и Q. Разбивать нужно Q.
В любом случае симметрии тут нет.
В принципе, можно и не разбивать, а построить рекуррентное соотношение Q от трёх предыдущих значений. из него - кубическое уравнение, из его корней можно получить выражение для Q в явной форме. Оно будет ужасным в точном виде. А если разбить Q на три - по количеству одинаковых в конце, то можно вывести матричную формулу, которая, на мой взгляд, гораздо красивее, и её легче использовать.

[manul91]

Проверим для $Q(5)$ независимым образом, перечисляя всех выходов.
- Он должен бросать минимум 4 раз.
- Из возможных 6^4 последовательностей, в 6 случаев выпадет паттерн XXXX, в остальных 6^4-6 он должен бросать пятый раз.
- из этих 6^4-6, 30 имеют потенциально выигрывающий паттерн XYYY, и 6^4-6-30 не имеют такой паттерн (сугубо проигравшие, что бы он не бросил на пятом разе).
- Он бросает пятый раз: в первом случае в 30 из 30x6 выигрывает, и в 30x6 - 30 проигрывает; во втором случае проигрывает во всех (6^4-6-30)*6 случаев.
Итого после пятого броска, проигрывает в суммарно 30x6 - 30 + (6^4-6-30)*6 случаев; если поделить это на 6^5 получаем то же $Q(5) = 1 - \frac{5}{6^4} - \frac{1}{6^3}$.

Однако, тут все же не все в порядке....
Посчитаем всех независимых развилок до пятого броска.
Имеется 6 развилок в которых он выигрывает на 4-том броске (и больше не бросает). И (6^4 - 6)*6 развилок в которых он бросает пятый раз (в некоторых выигрывает, в других нет).
Выходит, все независимые варианты 6 + (6^4 - 6)*6 = 6 + 6^5 - 6^2, а вовсе не 6^5 как я ставил выше в знаменателе.
Похоже ошибка на самом деле в "очевидном" выражении $A$, вероятности $P(n)$ не независимы.... Нужно бы $A$ подправить чтобы это учесть, да не соображу как...
venco
Все вышесказанное верно?

venco в сообщении #1668379 писал(а):

В принципе, можно и не разбивать, а построить рекуррентное соотношение Q от трёх предыдущих значений.

Как именно, и почему..?

[venco]

manul91 в сообщении #1668380 писал(а):

venco в сообщении #1668379 писал(а):

В принципе, можно и не разбивать, а построить рекуррентное соотношение Q от трёх предыдущих значений.

Как именно, и почему..?

Так же, как и для P - в конце могут быть 1, 2 или 3 одинаковых.

[manul91]

venco в сообщении #1668381 писал(а):

Так же, как и для P - в конце могут быть 1, 2 или 3 одинаковых.

Кажется понял.
$Q(n)$: вероятность что не упало одно и то же значение 4 раза подряд, вплоть до $n$-того броска включительно, И последние два значения - разные
$Q_2(n)$: вероятность что не упало одно и то же значение 4 раза подряд, вплоть до $n$-того броска включительно, И последние два значения - одинаковы (но отличаются от предыдущем)
$Q_3(n)$: вероятность что не упало одно и то же значение 4 раза подряд, вплоть до $n$-того броска включительно, И последние три значения - одинаковы (но отличаются от предыдущем, очевидно, по смыслу Q)
Связи:
$Q_2(n+1)= \frac{1}{6}Q(n)$
$Q_3(n+1)= \frac{1}{6}Q_2(n) = \frac{1}{6^2}Q(n-1)$

Теперь для $P(n)$ будем иметь (полагаем $Q(n), Q_2(n), Q_3(n)$ независимыми)
$P(n)=\frac{1}{6}Q_3(n-1) + \frac{1}{6^2}Q_2(n-2) + \frac{1}{6^3}Q(n-3)$
Так правильно?
То что "ищется" это $1 - (Q(1000) + Q_2(1000) + Q_3(1000))$
Но тут нужна еще связь для $Q$ через $P$....

[Null]

$Q(n)=\frac{5}{6}(Q(n-1)+Q_1(n-1)+Q_2(n-1))$ - что то вроде такого

[manul91]

Нет, $P$ похоже вообще ненужно.
Связи:
$Q_2(n+1)= \frac{1}{6}Q(n)$
$Q_3(n+1)= \frac{1}{6}Q_2(n) = \frac{1}{6^2}Q(n-1)$
Поскольку считаем $Q(n), Q_2(n), Q_3(n)$ независимыми, можно написать еще рекуррентное выражение для $Q(n)$
$Q(n)= \frac{5}{6}Q_2(n-1) + \frac{5}{6}Q_3(n-1) + \frac{5}{6}Q(n-1)$
Отсюда
$Q(n)= \frac{5}{6}\frac{1}{6}Q(n-2) + \frac{5}{6}\frac{1}{6^2}Q(n-3) + \frac{5}{6}Q(n-1)$
Для начальных значений берем например $Q(1)=1$, $Q(2)=\frac{1}{2}$, $Q(3)=(6^3 - 30)/(6^3) = \frac{31}{36}$
Для $Q(4)$ получим $\frac{175}{216}$
Для $Q(5)$ получим $\frac{1045}{1296}$
Вероятность неудачи для 5 бросков выходит $Q(5) + Q_2(5) + Q_3(5)$ получается $Q(5) + \frac{1}{6}Q(4) + \frac{1}{6^2}Q(3)$ или $\frac{139}{144}$
Независимый подсчет по всех развилках пути двумя сообщениями ранее, вроде получил что вероятность неудачи для вплоть для пяти бросков должна быть $(30\cdot 6 - 30 + (6^4-6-30)\cdot 6)/(6 + (6^4 - 6)\cdot 6)=\frac{1285}{1291}$, что отличается.
Что-то не так в датском королевстве...
Null
Спасибо но увы не сходится с подсчетом "на палочках" в начале этого сообщения (у меня $Q$ либо без индекса, либо индекс 2 либо 3, по количеству повторов). Ложусь пока спать а то уже на соображаю что именно считаю...

-- 04.01.2025, 11:22 --

Возможно, ошибся здесь

manul91 в сообщении #1668387 писал(а):

Для начальных значений берем например $Q(1)=1$, $Q(2)=\frac{1}{2}$, $Q(3)=(6^3 - 30)/(6^3) = \frac{31}{36}$

Все $Q$ вроде определенны только для $n \ge 3$, и для них и надо их рассчитать; $Q(1)=1$ вообще наверно бессмыслица

-- 04.01.2025, 11:41 --

Нет, $Q(3)=(6^3 - 30 - 6)/(6^3) = \frac{5}{6}$, забыл вычесть одинаковых троек; нужно теперь все через этого пересчитать : (

[manul91]

В последний раз.
$Q(3) = \frac{5}{6}$ (доля троек, у которых последние две значения разные)
$Q_2(3) = \frac{30}{6^3}$ (доля троек, у которых последние две значения одинаковы, но отличаются от первом)
$Q_3(3) = \frac{1}{6^2}$ (доля троек, у которых все значения одинаковы)
Теперь
$Q(4) = \frac{5}{6}(Q(3) + Q_2(3) + Q_3(3)) = \frac{5}{6}$
$Q(5) = \frac{5}{6}(Q(4) + Q_2(4) + Q_3(4)) = \frac{5}{6}(\frac{5}{6} + \frac{1}{6}\frac{5}{6} + \frac{1}{6}\frac{30}{6^3}) = \frac{1075}{1296}$
Итоговая вероятность неудачи, для вплоть до 5 бросков $Q(5) + Q_2(5) + Q_3(5) = \frac{1075}{1296} + \frac{1}{6}\frac{5}{6} + \frac{1}{6^2}\frac{5}{6} = \frac{1285}{1296}$

Это совпадает с самым первым рассчетом (наверно случайно), но не совпадает с контрольным пересчетом "на палочках" если учесть что количество всех развилок не $6^5$, а $6 + (6^4 - 6)6$ (если считать что развилок $6^5$ что вроде ошибочно, то результат правилен).

Непонятно что ставить в знаменателе для вероятности для вплоть до пяти бросков - $6^5$, или $6 + (6^4 - 6)6$ (в числителе понятно, количество неудачных последовательностей пятерок в которых нет четыре одинаковых).

[mihaild]

manul91 в сообщении #1668392 писал(а):

если считать что развилок $6^5$ что вроде ошибочно

Так а почему ошибочно? У нас на кубике может выпасть вообще что угодно, мы считаем число хороших результатов делить на вообще все.

[manul91]

mihaild в сообщении #1668396 писал(а):

Так а почему ошибочно? У нас на кубике может выпасть вообще что угодно, мы считаем число хороших результатов делить на вообще все.

Так "все результаты" это не все последовательности из пяти бросков. В шесть случаев из этих начальных $6^4$ мы бросаем только 4 раза и останавливаемся; пятый раз бросаем только в остальных $6^4-6$ случаев.
Тем не менее похоже здесь все-таки все в порядке.
Поскольку из полной исходной единичной вероятности этим 6-ти случаям соответствует доля $6/6^4$, а для всех остальных когда мы бросаем до пяти соответствует доля $(6^4-6)/6^4$ (которая при последующем пятом броске разбивается на $6(6^4-6)$ равновероятных частей).

Теперь из-за численного совпадения вероятности неуспеха вплоть до пяти бросков, меня мучает мысль что возможно мой рассчет в самом первом сообщении (там я обозначал как $Q(n)$ то, что теперь мы обозначаем как $Q(n) + Q_2(n) + Q_3(n)$, переобозначим поэтому далее $Q$ из первом сообщении как $QQ$ чтобы не путаться) - возможно все-таки эквивалентен этим усложненным рассчетом через разбиений.
Тоесть не эквивалентна ли рекурсивная формула

manul91 в сообщении #1668371 писал(а):

$QQ(n) = QQ(n-1) - \frac{5}{6^4}QQ(n-4)$

тем же $Q(n) + Q_2(n) + Q_3(n)$ что мы теперь рассчитываем через три разных переменных.
Ведь $QQ(5)$ и $Q(5) + Q_2(5) + Q_3(5)$ выходят оба равными $\frac{1285}{1296}$
Это будет так, если окажется что события $P(1), P(2), P(3)....$ из первом сообщении на самом деле независимы (а мне теперь снова кажется, что так и есть - ведь они принадлежат разными развилками, см. рассчет с перебором для вплоть до пяти бросков).

-- 04.01.2025, 13:37 --

И да, меня советовали перейти к разным переменным для разных случаев - но никто не указал логическую ошибку в первом (точнее во втором где я формулировал более прецизно) сообщении из темы.
Ведь для паттерна вида

manul91 в сообщении #1668376 писал(а):

- паттерн для $n$ должен быть вида: ...****X|YYYY ; здесь прежде вертикальной черты это последовательность $n-4$ для которой точно знаем что нет четыре последовательных, суть в том что первая $Y$ должна отличаться от последней в последовательности (вероятность $\frac{5}{6}$), потом еще три раза должно выпасть то же $Y$ (вероятность $\frac{1}{6}$ каждый раз)

совершенно неважно сколько раз повторяются $X$-ов прежде черточкой (только бы не четыре раза, что есть так по самому определению QQ(n-4) - это вероятность что в $n$-4 последовательности нет повторяющихся подпоследовательностей из 4-ех одинаковых значений)

[venco]

Мне немножко лень всё проверять, но

$$QQ(n) = QQ(n-1) - \frac{5}{6^4}QQ(n-4)$$

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

Ладно, формула с матрицей. Составим рекурсию для $Q, Q_2, Q_3$:

$Q(k) = \frac56Q(k-1)+\frac56Q_2(k-1)+\frac56Q_3(k-1)$
$Q_2(k) = \frac16Q(k-1)$
$Q_3(k) = \frac16Q_2(k-1)$
В матричном виде:

$$M=\begin{pmatrix} \frac56 & \frac56 & \frac56 \\ \frac16 & 0 & 0 \\ 0 & \frac16 & 0 \end{pmatrix}$$

$$\begin{bmatrix}Q(k) \\ Q_2(k) \\ Q_3(k)\end{bmatrix}=M^{k-1}\begin{bmatrix}Q(1) \\ Q_2(1) \\ Q_3(1)\end{bmatrix}=M^{k-1}\begin{bmatrix}1 \\ 0 \\ 0\end{bmatrix}$$

$P(k)$ получается из $Q_3(k-1)$, поэтому:
$P(k)=\frac16M^{k-2}[3,1]$

[mihaild]

manul91 в сообщении #1668398 писал(а):

Так "все результаты" это не все последовательности из пяти бросков. В шесть случаев из этих начальных $6^4$ мы бросаем только 4 раза и останавливаемся; пятый раз бросаем только в остальных $6^4-6$ случаев.

Тогда результаты не равновероятны: получить конкретный провал из 4 бросков более вероятно, чем из 5. Стандартный подход для упрощения - всегда бросаем кубик нужное число раз, даже если уже по первым броскам понятно, что не получилось.

manul91 в сообщении #1668398 писал(а):

Теперь из-за численного совпадения вероятности неуспеха вплоть до пяти бросков, меня мучает мысль что возможно мой рассчет в самом первом сообщении (там я обозначал как $Q(n)$ то, что теперь мы обозначаем как $Q(n) + Q_2(n) + Q_3(n)$, переобозначим поэтому далее $Q$ из первом сообщении как $QQ$ чтобы не путаться) - возможно все-таки эквивалентен этим усложненным рассчетом через разбиений

Да вроде эквивалентно. Только я бы сказал, что через разбиения проще, там совсем думать не надо, что куда переходит.

[manul91]

venco в сообщении #1668443 писал(а):

Мне немножко лень всё проверять, но

$$QQ(n) = QQ(n-1) - \frac{5}{6^4}QQ(n-4)$$

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

Спасибо что проверили, отлегло. А то я тоже бы пытался показать что $QQ(n) \equiv Q(n) + Q_2(n) + Q_3(n)$ неуклюже вращая их всякими суммами и подстановками.

venco в сообщении #1668379 писал(а):

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

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

mihaild в сообщении #1668447 писал(а):

Тогда результаты не равновероятны: получить конкретный провал из 4 бросков более вероятно, чем из 5. Стандартный подход для упрощения - всегда бросаем кубик нужное число раз, даже если уже по первым броскам понятно, что не получилось.

Совершенно верно но в задаче говорилось "бросает пока не выпадут четыре одинаковы", да и я ошибочно заподозрил что мое решение неверно и вот искал черной кошки там где ее нет; пришлось самому докумекать "рассчитывая на пальцев" до того что результаты тогда неравновероятны и поэтому все-таки все нормально со знаменателем $6^5$.

mihaild в сообщении #1668447 писал(а):

Да вроде эквивалентно. Только я бы сказал, что через разбиения проще, там совсем думать не надо, что куда переходит.

Ну не знаю, для конкретной задачи мне мой подход все же кажется проще (я сам думал вначале что возможно нужно будет рассматривать разбиения, отсюда и дурацкий артефакт про "либо $\frac{1}{2}$ либо $\frac{1}{2}$" в первом сообщении (это ошметки из упрощенного варианта с монетки тольку с двумя выходами которого я обдумывал, где у всех цепочек длиной $n$ у которых отсутствуют 4 одинаковых последовательных, там половина оканчивается на разных и половина на одинаковых значений); но увидел что они не нужны и поэтому забил).

venco в сообщении #1668443 писал(а):

$$\begin{bmatrix}Q(k) \\ Q_2(k) \\ Q_3(k)\end{bmatrix}=M^{k-1}\begin{bmatrix}Q(1) \\ Q_2(1) \\ Q_3(1)\end{bmatrix}=M^{k-1}\begin{bmatrix}1 \\ 0 \\ 0\end{bmatrix}$$

Выходит все же можно определить $Q(1), Q_2(1), Q_3(1)$ правильным образом, мне такое казалось подозрительным (из-за их определений которые как бы при $n<3$ возможно потеряют смысл, вот и для верности начинал рекурсию с $n=3$ считая их для этого случая комбинаторно)