Помогите решить задачу по теории вероятности!
Вы попали в лабиринт, состоящий из нескольких комнат, соединенных системой двусторонних порталов. Каждый портал соединяет только одну пару комнат лабиринта. Порталом можно пользоваться неограниченное число раз. Вы появляетесь в комнате v1 и прыжками перемещаетесь между комнатами. В комнате v6 находится выход из лабиринта. Предположим, что каждый следующий портал для прыжка вы выбираете случайно и равновероятно среди всех порталов в этой комнате, включая портал до предыдущей комнаты. Найдите математическое ожидание количества прыжков до первого попадания в v6.
Так как мы спавнимся в точке 1, минимальное количество шагов до точке 6 - это 2 (1-2-6, 1-3-6). Соответственно случайная величина может принимать значения от 2 и до какого-то N. Дальше я читал всевозможные вероятности для каждого числа шагов( например для того, что X=2, вероятность равна (0.5 * 0.25 + 0.5 * 0.25) - (1 - 2 - 6, 1 - 3 - 6). Но уже для 4 считать оказывается проблематично, так как с увеличением числа шагов на 1, способов добраться до вершины 6 увеличивается в 2 раза.(Например для 3 шагов: 1 - 2 - 4 - 6, 1 - 2 - 3 - 6 и.т.д). И вот я не понимаю одного, как дальше считать матожидание, если вероятности отличаются! Пробовал еще подогнать под экспоненциальный закон, но понял, что СВ дискретная.
Ответы (1 шт):
Подойдем к решению, как настоящие программисты - рекурсивно :) От математиков воспользуемся симметрией - понятно, что узлы 2 и 3 равнозначны, как и узлы 4 и 5.
Пусть Среднее количество шагов из узла 1 до узла 6 - K, от узлов 2 и 3 - N, а от узлов 4 и 5 - M.
Из узла 1 мы можем попасть одним ходом в узлы 2 или 3, т.е.
K = (1/2)*(1+N) + (1/2)*(1+N)
- два равновероятных хода в узлы 2 и 3, а оттуда - за N шагов из каждого.
Для узлов 2 и 3 есть по 4 равновероятных хода - т.е.
N = (1/4)*(1+N) + (1/4)*(1+M) + (1/4)*(1+K) + (1/4)*(1+0)
(попадание в узлы 3 (или 2, для узла 3), 4 (или 5 для узла 3), 1 и 6 соответственно), так что
N = 1 + (M+N+K)/4
Для узлов 4 и 5 точно так же получаем
M = (1/3)*(1+M) + (1/3)*(1+N) + (1/3)*(1+0)
Итого - имеем систему уравнений
K = 1 + N
N = 1 + (N+M+K)/4
M = 1 + (M+N)/3
Решая ее, находим K = 16/3.
Экспериментальная проверка - программа, которая много-много раз имитирует случайные блуждания - находится здесь.