Блуждания гиперблохи

[staric]

Блоха скачет по вершинам пятимерного куба. С каждой очередной вершины своего маршрута она случайно прыгает на любую из соседних (по ребрам) вершин, кроме предыдущей (той, с которой она попала на текущую). Заканчивает путешествие блоха сразу, как только возвращается в вершину, с которой стартовала, либо при попадании в противоположную вершину. Какова вероятность попадания в противоположную вершину?

[levtsn]

Гиперкуб можно урезать до цепи из 6 точек со случайным блужданием и разной вероятностью вправо, влево.

[Iam]

levtsn в сообщении #1199282 писал(а):

Гиперкуб можно урезать до цепи из 6 точек...,

которая для четного числа шагов редуцируется в цепь из 3-х точек, для которой получим P=1/2.

[staric]

Iam в сообщении #1199362 писал(а):

которая для четного числа шагов редуцируется в цепь из 3-х точек, для которой получим P=1/2.

Лаконичненько. Хотелось бы чуть-чуть подробностей. Или это случай поразительной интуиции?

[Iam]

Постараюсь пояснить. Все позиции блохи можно представить множеством последовательностей длины 5 над алфавитом $\{0,1\}$ или, более содержательно, пространством Хэмминга $E_2^5. $ Тогда ее прыжки можно описать марковской цепью с 32 состояниями. Если бы переход из состояния веса $i $ в состояние веса $ j $ ($0\le i, j $ и $ i, j \le 5$ ) зависел только от веса предыдущего состояния, то для решения задачи достаточно было бы использовать цепь с 6-ю состояниями, соответствующими их хэмминговым весам. А учитывая, что вероятность попадания в крайние $ (i=0, j=5) $ однозначно определяется вероятностями нахождения на предыдущем шаге в соседних (соответственно $i’=1$ и $j’=4$), то достаточно было бы проанализировать цепь с 4-мя состояниями. Ан нет: переход $i \to j $ зависит от того, из какого состояния (веса) она попала до этого в $i$.
levtsn подсказал, что для учета этой зависимости достаточно рассмотреть цепь с 6-ю состояниями. Обозначим их так: 1, 12, 23, 32, 43, 4. Если состояние обозначено одной цифрой, то эта цифра говорит о его весе, а если двумя, то вторая цифра есть его вес, а первая – вес предыдущего состояния.
Далее составляем матрицу переходов: $P_{t+1}(1)=P_t(12)/4+P_t (32)/2, P(12)=3P_t (1)/4... $ и полагаем $P_0(12)=1$.
Затем, заметив, что при четном числе прыжков блоха может оказаться лишь в состояниях $S=\{12, 32, 4\}$, строим цепь для этих состояний с подсчетом вероятностей: $P_{t}(u|v); u,v \in S, t=0, 2,... $
Дальнейшее решение сложности уже не составит.

[Geen]

Iam в сообщении #1199406 писал(а):

Дальнейшее решение сложности уже не составит.

А для бесконечномерного куба?

-- 12.03.2017, 14:01 --

levtsn в сообщении #1199282 писал(а):

Гиперкуб можно урезать до цепи из 6 точек со случайным блужданием и разной вероятностью вправо, влево.

А центральные точки не надо удвоить (что бы явно выразить зависимость от того откуда пришли)?

[levtsn]

Какие центральные точки?

[staric]

(Оффтоп)

Верный ответ был дан Iam достаточно быстро. Вопросы были по методу решения. По "думательной" части все разъяснено, нет "технической", там могут быть загвоздки с получением точного ответа, но в целом

Iam в сообщении #1199406 писал(а):

Дальнейшее решение сложности уже не составит.

Я даже пожалел, что не заставил блоху прыгать по 7-кубу... (бонусный вопрос №1)

Кстати, нетрудно понять, к чему стремится результат с ростом числа измерений - для этого не обязательно даже строить полную цепь (бонусный вопрос №2).

[TOTAL]

В лоб можно вот так. Обозначим $P_m^+$ и $P_m^-$ вероятность попадания в исходную точку с расстояния $m$ от неё, если на предыдущем ходе это расстояние соответственно увеличилось или уменьшилось. Тогда находим $P_1^+$ из

$P_1^+ = P_2^+$
$4P_1^- = 1 + 3P_2^+$
$4P_2^+ = P_1^- + 3(1-P_2^-)$
$4P_2^- =2 P_1^- + 2(1-P_2^-)$

[Geen]

staric в сообщении #1199598 писал(а):

Я даже пожалел, что не заставил блоху прыгать по 7-кубу... (бонусный вопрос №1)

Да, интересно, почему тут минимум... "случайность"?