матожидание количества бросков до выпадения двух 6 подряд
Добавлено: 06 окт 2021, 10:19
В сети ходит такая задача - найти матожидание количества бросков кубика до выпадения двух 6 подряд. Ответ - 42, надо только доказать.
Есть даже такие чудные решения, как https://phys-math.ru/_media/conf2020/sp ... bornik.pdf (страница 169, кфмн написал).
Хочу своё решение через цепи Маркова написать, по аналогии как мы уже решали другую задачу viewtopic.php?p=2661#p2661
Т.к. метод очень мощный, работает для многих задач - как для той старой (и разных её модификаций), так и для этой задачи, даже если внести в условие значительные модификации. Кстати, если есть идеи, как модифицировать задачу, чтобы значительно усложнить, пишите сюда. Имеется ввиду не тривиальное усложнение, когда просто размер условия большой (например встретить 10 шестёрок подряд, потом встретить 7 пятёрок, но не встречая 8 четвёрок).
Для начала можно заметить, что вместо кубика можно рассматривать кривую монету, у которой одна сторона выпадает с вероятностью , а другая сторона с вероятностью . Хотя принципиально это ничего не меняет.
Рассмотрим автомат с 3 состояниями.
1 - только что встретили "не 6", ещё не встречали "две 6 подряд".
2 - только что встретили "6", ещё не встречали "две 6 подряд".
3 - где-то ранее (или только что) встретили "две 6 подряд".
Из 1 переходим в 1 с вероятность или в 2 с вероятность .
Из 2 переходим в 1 с вероятность или в 3 с вероятность .
Из 3 всегда переходим в 3.
После первого броска автомат будет в состоянии 1 с вероятностью или в состоянии 2 с вероятностью .
Можно было бы добавить ещё одно состояние, гда был автомат до первого броска и куда никогда не вернётся, но ради простоты не будем это делать.
Матрица трансформации вероятностей будет , вектор вероятностей после первого броска .
Вектор вероятностей по трём состояниям после бросков будет .
Для нахождения нужного матожидания нам интересна вероятность состояния номер 2.
Если автомат находится в состоянии номер 2, то с вероятность после следующего броска наступит событие.
Значит матожидание равно .
Осталось только посчитать его.
Можно было бы вынести умножение на вектор за скобки, но сумма матриц внутри расходится.
Но можно заметить, что при умножении на вектор нам нужны только первые два столбца матрицы внутри суммы. А для ответа нужна только вторая строка. Т.е. от матрицы нужны только элементы и . А при возведении матрицы в степень элементы подматрицы 2x2 слева вверху зависят только от этой подматрицы (т.к. в столбце 3 первые два элемента нулевые).
Т.е. можно рассмотреть матрицу и вектор .
Тогда обозначим матрицу .
И ответ будет - второй элемент вектора .
Сумма для матриц считается так же как и для чисел.
Например если для числа сумма равна , то , значит .
Аналогично для матрицы .
Будет .
Тогда для
.
Значит и .
Получаем, что нужное матожидание равно 42.
Есть даже такие чудные решения, как https://phys-math.ru/_media/conf2020/sp ... bornik.pdf (страница 169, кфмн написал).
Хочу своё решение через цепи Маркова написать, по аналогии как мы уже решали другую задачу viewtopic.php?p=2661#p2661
Т.к. метод очень мощный, работает для многих задач - как для той старой (и разных её модификаций), так и для этой задачи, даже если внести в условие значительные модификации. Кстати, если есть идеи, как модифицировать задачу, чтобы значительно усложнить, пишите сюда. Имеется ввиду не тривиальное усложнение, когда просто размер условия большой (например встретить 10 шестёрок подряд, потом встретить 7 пятёрок, но не встречая 8 четвёрок).
Для начала можно заметить, что вместо кубика можно рассматривать кривую монету, у которой одна сторона выпадает с вероятностью , а другая сторона с вероятностью . Хотя принципиально это ничего не меняет.
Рассмотрим автомат с 3 состояниями.
1 - только что встретили "не 6", ещё не встречали "две 6 подряд".
2 - только что встретили "6", ещё не встречали "две 6 подряд".
3 - где-то ранее (или только что) встретили "две 6 подряд".
Из 1 переходим в 1 с вероятность или в 2 с вероятность .
Из 2 переходим в 1 с вероятность или в 3 с вероятность .
Из 3 всегда переходим в 3.
После первого броска автомат будет в состоянии 1 с вероятностью или в состоянии 2 с вероятностью .
Можно было бы добавить ещё одно состояние, гда был автомат до первого броска и куда никогда не вернётся, но ради простоты не будем это делать.
Матрица трансформации вероятностей будет , вектор вероятностей после первого броска .
Вектор вероятностей по трём состояниям после бросков будет .
Для нахождения нужного матожидания нам интересна вероятность состояния номер 2.
Если автомат находится в состоянии номер 2, то с вероятность после следующего броска наступит событие.
Значит матожидание равно .
Осталось только посчитать его.
Можно было бы вынести умножение на вектор за скобки, но сумма матриц внутри расходится.
Но можно заметить, что при умножении на вектор нам нужны только первые два столбца матрицы внутри суммы. А для ответа нужна только вторая строка. Т.е. от матрицы нужны только элементы и . А при возведении матрицы в степень элементы подматрицы 2x2 слева вверху зависят только от этой подматрицы (т.к. в столбце 3 первые два элемента нулевые).
Т.е. можно рассмотреть матрицу и вектор .
Тогда обозначим матрицу .
И ответ будет - второй элемент вектора .
Сумма для матриц считается так же как и для чисел.
Например если для числа сумма равна , то , значит .
Аналогично для матрицы .
Будет .
Тогда для
.
Значит и .
Получаем, что нужное матожидание равно 42.