матожидание количества бросков до выпадения двух 6 подряд

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 06 окт 2021, 10:19

В сети ходит такая задача - найти матожидание количества бросков кубика до выпадения двух 6 подряд. Ответ - 42, надо только доказать.
Есть даже такие чудные решения, как https://phys-math.ru/_media/conf2020/sp ... bornik.pdf (страница 169, кфмн написал).

Хочу своё решение через цепи Маркова написать, по аналогии как мы уже решали другую задачу viewtopic.php?p=2661#p2661
Т.к. метод очень мощный, работает для многих задач - как для той старой (и разных её модификаций), так и для этой задачи, даже если внести в условие значительные модификации. Кстати, если есть идеи, как модифицировать задачу, чтобы значительно усложнить, пишите сюда. Имеется ввиду не тривиальное усложнение, когда просто размер условия большой (например встретить 10 шестёрок подряд, потом встретить 7 пятёрок, но не встречая 8 четвёрок).

Для начала можно заметить, что вместо кубика можно рассматривать кривую монету, у которой одна сторона выпадает с вероятностью $\frac16$, а другая сторона с вероятностью $\frac56$. Хотя принципиально это ничего не меняет.
Рассмотрим автомат с 3 состояниями.
1 - только что встретили "не 6", ещё не встречали "две 6 подряд".
2 - только что встретили "6", ещё не встречали "две 6 подряд".
3 - где-то ранее (или только что) встретили "две 6 подряд".
Из 1 переходим в 1 с вероятность $\frac56$ или в 2 с вероятность $\frac16$.
Из 2 переходим в 1 с вероятность $\frac56$ или в 3 с вероятность $\frac16$.
Из 3 всегда переходим в 3.
После первого броска автомат будет в состоянии 1 с вероятностью $\frac56$ или в состоянии 2 с вероятностью $\frac16$.
Можно было бы добавить ещё одно состояние, гда был автомат до первого броска и куда никогда не вернётся, но ради простоты не будем это делать.
Матрица трансформации вероятностей будет $$M_0 = \begin{pmatrix} \frac56 &  \frac56 & 0 \\ \frac16 &  0 & 0 \\ 0 & \frac16  & 1 \end{pmatrix}$$, вектор вероятностей после первого броска $$v_1=\begin{pmatrix} \frac56 \\ \frac16\\ 0 \end{pmatrix}$$.
Вектор вероятностей по трём состояниям после $k+1$ бросков будет $v_{k+1} = M_0^k v_1$.

Для нахождения нужного матожидания нам интересна вероятность состояния номер 2.
Если автомат находится в состоянии номер 2, то с вероятность $\frac16$ после следующего броска наступит событие.
Значит матожидание равно $$\sum_{k=0}^{\infty} \frac{k+2}{6} v_{k+1}[2]$$.
Осталось только посчитать его.

Можно было бы вынести умножение на вектор за скобки, но сумма матриц внутри расходится.
Но можно заметить, что при умножении на вектор нам нужны только первые два столбца матрицы внутри суммы. А для ответа нужна только вторая строка. Т.е. от матрицы нужны только элементы $[2,1]$ и $[2,2]$. А при возведении матрицы в степень элементы подматрицы 2x2 слева вверху зависят только от этой подматрицы (т.к. в столбце 3 первые два элемента нулевые).
Т.е. можно рассмотреть матрицу $$N_0 = \begin{pmatrix} \frac56 &  \frac56 \\ \frac16 &  0 \end{pmatrix}$$ и вектор $$u_1=\begin{pmatrix} \frac56 \\ \frac16 \end{pmatrix}$$.
Тогда обозначим матрицу $N=\sum_{k=0}^{\infty} (k+2) N_0^k$.
И ответ будет - второй элемент вектора $\frac16 N u_1$.

Сумма для матриц считается так же как и для чисел.
Например если для числа $q$ сумма равна $s=1+q+q^2+q^3+...$, то $s=1+q(1+q+q^2+...)=1+qs$, значит $s=\frac{1}{1-q}$.
Аналогично для матрицы $S=\sum_{k=0}^{\infty} N_0^k = (E-N_0)^{-1}$.
Будет $$S=\begin{pmatrix} 36 &  30 \\ 6 &  6 \end{pmatrix}$$.
Тогда для $$N=S+\sum_{k=0}^{\infty} (k+1) N_0^k=S+\sum_{k=0}^{\infty} (\sum_{m=0}^k 1) N_0^k=S+\sum_{m=0}^{\infty}\sum_{k=m}^{\infty} N_0^k=$$
$$=S+\sum_{m=0}^{\infty} N_0^m (\sum_{k=0}^{\infty} N_0^k)=S+\sum_{m=0}^{\infty} N_0^m (S)=S+S^2$$.
Значит $$N=S+S^2=\begin{pmatrix} 1512 &  1290 \\ 258 & 222 \end{pmatrix}$$ и $$\frac16 N u_1 = \begin{pmatrix} \frac{1475}{6} \\ 42 \end{pmatrix}$$.
Получаем, что нужное матожидание равно 42.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 06 окт 2021, 12:00

Например совершенно аналогично можно получить, что для 3 шестёрок матожидание бросков будет 258, а для 4 будет 1554.
OEIS A105281
$a(0)=0;\;a(n)=6 a(n-1)+6$
Или явно $a(n)=\frac65 (6^n-1)$.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 06 окт 2021, 18:34

zykov писал(а):Source of the post Значит $$N=S+S^2=\begin{pmatrix} 1512 & 1290 \\ 258 & 222 \end{pmatrix}$$ и $$\frac16 N u_1 = \begin{pmatrix} \frac{1475}{6} \\ 42 \end{pmatrix}$$.

Аналогично можно оценить матожидание квадрата числа шагов: $\frac16 (S+S^2+2 S^3) u_1$.
Второй компонент вектора будет $3414$. Если из него вычесть $42^2$, то будет среднеквадратичное отклонение $1650\approx40.62^2$.
Последний раз редактировалось zykov 07 окт 2021, 07:58, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 07 окт 2021, 07:56

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

Обозначим искомое матожидание $n$. Если автомат находится в состоянии 1 после $k$ шагов, то при этом условии матожидание события будет $k+n$.
Обозначим матожидание дополнительного количества бросков $q$, если автомат находится в состоянии 2, так что полное количество бросков при этом условии имеет матожидание $k+q$.
Это две разные величины. Если автомат в состоянии 2, то с вероятность $\frac16$ наступит событие после следующего броска. Если автомат в состоянии 1, то после следующего броска событие точно не наступит.

Если мы в самом начале или в состоянии 1, то после одного броска с вероятность $\frac56$ мы окажемся в аналогичной ситуации и при этом условии матожидание будет $n+1$. С вероятность $\frac16$ мы попадаем в состояние 2 и при этом условии матожидание будет $1+q$.
Т.е. получим $n=\frac56 (n+1) + \frac16 (q+1)$.
Если мы в состоянии 2, то после одного броска с вероятность $\frac56$ мы окажемся в состоянии 1 и при этом условии матожидание будет $n+1$. С вероятность $\frac16$ событие происходит и при этом условии матожидание будет $1$.
Т.е. получим $q=\frac56 (n+1) + \frac16 1$.

Отсюда легко получаем $n=42$ и $q=36$.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 07 окт 2021, 10:16

Этот метод с уравнениями легко обобщить на произвольное количество шестёрок.
Например для 3 шестёрок будет:
$n=\frac56 (n+1) + \frac16 (q_1+1)$
$q_1=\frac56 (n+1) + \frac16 (q_2+1)$
$q_2=\frac56 (n+1) + \frac16$
Результат $n=258,\;q_1=252,\;q_2=216$.

Albus
Сообщений: 59
Зарегистрирован: 11 июн 2019, 10:46

матожидание количества бросков до выпадения двух 6 подряд

Сообщение Albus » 08 окт 2021, 22:51

У меня вышло так. Пусть есть строка длины $n$ (очень большое число) чисел от $1$ до $6$, рассмотрим пары чисел, их число будет $\frac{n}{2}$. Число пар с двумя шестерками равно $\frac{n}{2\cdot 36}$, также две шестерки подряд могут быть на стыке пар вида $a6$ и $6a$, где $a$ - любые не шестерки, их число равно $\frac{25n}{2\cdot 36^2}$. Есть еще один нюанс - если перед сетом из пар с двумя шестерками будет пара вида $a6$, а после сета пара вида $6a$, то число пар шестерок увеличится на одну, поэтому надо сначала надо найти число таких сетов с одной парой с двумя шестерками, потом с двумя и т.д., просуммировав получим ряд $\frac{n}{2}(\frac{5}{36} \cdot \frac{1}{36} \cdot \frac{5}{36}+\frac{5}{36} \cdot \frac{1}{36^2} \cdot \frac{5}{36}+..).=\frac{25n}{2\cdot 36^2 \cdot 35}$. Сложив все это, получим число двух шестерок подряд, которые мы насчитаем походу движения, и теперь если мы разделим наше $n$ на это число, получим среднюю длину цепочки, которую замыкают две шестерки, т.е. $\frac{1}{\frac{1}{2\cdot 36}+\frac{25}{2\cdot 36^2}+\frac{25}{2\cdot 36^2 \cdot 35}}=42$

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 10 окт 2021, 14:07

Интересно, ответ сошелся.
Но как-то путанно. Пока не разобрался.
Мне кажется, что конечное $n$ и бесконечный ряд не вяжутся друг с другом. Но видимо в пределе бесконечных $n$ сходится.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

матожидание количества бросков до выпадения двух 6 подряд

Сообщение Ian » 10 окт 2021, 20:42

Ну я же показывал, какой ответ ищем тот и обозначаем буквой. Пусть a матожидание длины при условии что нулевой элемент последовательности 6 (и допускается, что уже на 1м шаге можно окончить игру). Пусть b матожидание длины при условии что нулевой элемент не 6 (то есть ответ нашей задачи). Тогда по формулам полного матожидания [math] (с гипотезами, 1я 6ка или нет, когда нулевая не 6ка), [math] аналогично. Решая систему получаем b=42.
Обосновывать, что а и b конечны, действительно придется через теорию марковских матриц, но это можно в общем случае, для одного поглощающего состояния и эргодичности остального графа

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 10 окт 2021, 22:07

Ian, да, я выше писал. Ещё дисперсию без Маркова не найти.
А статью не смотрели? Там кфмн делает практически тоже самое, но ни слова про Маркова или матрицы. Решает через последовательности.

Вот ещё, не совсем в тему (видео на английском): https://www.youtube.com/watch?v=4AuV93LOPcE
Мужик интересно про последовательности рассказывает, про Newton-Gregory interpolation. Начинает он медленно, зато ближе к концу мне было интересно - не знал такого.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

матожидание количества бросков до выпадения двух 6 подряд

Сообщение Ian » 11 окт 2021, 08:21

1)ну я же говорю, вечер был, не вижу почти ни фига
2)кфмн оправдывает то, что он нашел дисперсию и значит нельзя как у нас в 2 строчки
3) а я знаю за что вам понравилась лекция. Там формулы и таблицы не нарастают в простыню, как в статьях и классических лекциях, а анимированы. То что я предлагал лет 5 назад как "новый метод преподавания математики". Стало живее. А по теме - интерполяционная формула Ньютона входит в госпрограмму для всех студентов кроме юристов; доказывается еще проще -только заметить что формула для точек 1...n+1 обязана иметь вид: формула для 1...n + довесок, обращающийся в 0 в точках 1...n, и должна быть точна для f(n)- полином степени n. Обозначение " показатель n с подчеркиванием" введен в "Конкретной математике". Так что это толковая популяризация.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 11 окт 2021, 09:33

Не помню, чтобы я такое проходил.
Мне там больше понравился случай про бесконечные суммы, например корень из двух в случае ряда $2^n$. И про отрицательные. Время 26:30.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 11 окт 2021, 09:43

Ian писал(а):Source of the post кфмн оправдывает то, что он нашел дисперсию и значит нельзя как у нас в 2 строчки

С кфмн мне не понятно, зачем он вообще всё это городил? Про цепи Маркова никогда не слышал?

Albus
Сообщений: 59
Зарегистрирован: 11 июн 2019, 10:46

матожидание количества бросков до выпадения двух 6 подряд

Сообщение Albus » 13 окт 2021, 02:05

zykov писал(а):Source of the post Мне кажется, что конечное $n$ и бесконечный ряд не вяжутся друг с другом. Но видимо в пределе бесконечных $n$ сходится.

Да, там в пределе :)
zykov писал(а):Source of the post Этот метод с уравнениями легко обобщить на произвольное количество шестёрок.
Например для 3 шестёрок будет:
$n=\frac56 (n+1) + \frac16 (q_1+1)$
$q_1=\frac56 (n+1) + \frac16 (q_2+1)$
$q_2=\frac56 (n+1) + \frac16$
Результат $n=258,\;q_1=252,\;q_2=216$

Для трех шестерок у меня вышло так. Пусть так же есть строка длины $n$ (очень большое число) чисел от $1$ до $6$, рассмотрим тройки чисел, их число будет $\frac{n}{3}$. Число пар с тремя шестерками равно $\frac{n}{3\cdot 6^3}$, также три шестерки подряд могут быть на стыке пар вида $xa6$ - $66a$, $a66$ - $6ax$, и $a66$ - $66a$ где $a$ - любые не шестерки (а $x$-любое число), их число равно $2\cdot\frac{25n}{3\cdot 6^5}+\frac{25n}{3\cdot 6^6}=\frac{325n}{3\cdot 6^6}$. Есть еще один нюанс - если перед сетом из триплета с тремя шестерками будет триплет вида $xa6$, а после сета триплет вида $66a$, то число триплетов шестерок увеличится на один, поэтому надо сначала надо найти число таких сетов с одним триплетом шестерок, потом с двумя и т.д., просуммировав получим ряд $\frac{n}{3}(\frac{5}{36} \cdot \frac{1}{6^3} \cdot \frac{5}{6^3}+\frac{5}{36} \cdot \frac{1}{6^6} \cdot \frac{5}{6^3}+..)=\frac{25n}{3\cdot 6^5 \cdot (6^3-1)}$. Также если перед этими триплетами будет триплет вида $a66$, а после сета из триплетов будет триплет вида $6ax$ или $66a$, то тогда число триплетов тоже увеличивается на один, и соответствующий ряд $\frac{n}{3}(\frac{5}{6^3} \cdot \frac{1}{6^3} \cdot (\frac{5}{36}+\frac{5}{6^3})+\frac{5}{6^3} \cdot \frac{1}{6^6} \cdot (\frac{5}{36}+\frac{5}{6^3})+..)= \frac{5\cdot 35n}{3\cdot 6^6 \cdot (6^3-1)}$ Сложив все это, получим число трех шестерок подряд, которые мы насчитаем походу движения, и теперь если мы разделим наше $n$ на это число, получим среднюю длину цепочки, которую замыкают три шестерки, т.е. $\frac{1}{\frac{1}{3\cdot 6^3}+\frac{325}{3\cdot 6^6}+\frac{25}{3\cdot 6^5 \cdot (6^3-1)}+\frac{5\cdot 35}{3\cdot 6^6 \cdot (6^3-1)}}=258$
Также это легко обобщается на случай $n$-шестерок (а у вас тут получается система $n$ на $n$?)
P.S. Также можно по другому считать сеты шестерок, например для случая $n=2$ сначала находим всевозможные пары шестерок, что тривиально $\frac{n}{36}$, потом из них некоторые выбраковываем, т.к. если они идут рядом с друг другом, то мы насчитаем меньше последовательных пар шестерок, например в $a666a$ две пары, а последовательных одна, и т.д., и там возникают ряды вида $\sum_ {i} i\frac{1}{6^i}$, как в той статье

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

матожидание количества бросков до выпадения двух 6 подряд

Сообщение zykov » 15 окт 2021, 19:23

Albus писал(а):Source of the post а у вас тут получается система $n$ на $n$?

Да, но она имеет простую форму.
Последнее равенство выражает $q_i$ через $n$ линейно.
Предпоследнее равенство выражает $q_{i-1}$ линейно через $n$ и $q_i$, т.е. учитывая предыдущее - через $n$.
И т.д. - из первого получим что $n=x n + y$. Где легко найти $x$ и $y$.
Каждый раз у нас один и тот же переход $q_{i-1}=(\frac56 n + 1) + \frac16 q_i$.
Так что в итоге первое равенство превращается в $n = \frac65 (1 - 6^{-k}) (\frac56 n + 1)$, что даёт $n=\frac65 (6^k - 1)$.
(Здесь $k$ - это количество шестёрок подряд.)


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 14 гостей