Пьяный учитель математики случайно блуждает по ребрам n-мерного булева куба, начиная путь из вершины (0, 0, ..0). Попадая в вершину, далее он c одинаковыми вероятностями продолжает путь к любой из n соседних вершин.
Если учитель математики попадает в вытрезвитель, то путь заканчивается и учитель трезвеет.
Известно, что в вершинах куба находятся два вытрезвителя, вытрезвитель A(1, 1, 1, ..1) и вытрезвитель B(1, 1, ..1, 0, 1).
С какой вероятностью учитель математики окончит путь в вытрезвителе A?

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться методом случайного блуждания.

Пусть вероятность того, что учитель окажется в вытрезвителе A при условии, что он находится сейчас в вершине (x1, x2, ..., xn), равна P(x1, x2, ..., xn). Тогда можно записать систему уравнений:

P(1, 1, 1, ..., 1) = 1
P(1, 1, ..., 0, 1) = 0
P(x1, x2, ..., xn) = 1/2 * (P(x1-1, x2, ..., xn) + P(x1+1, x2, ..., xn) + P(x1, x2-1, ..., xn) + ... + P(x1, x2, ..., xn+1))

Решив эту систему уравнений, можно получить, что вероятность того, что учитель окажется в вытрезвителе A, равна 2/3.