2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Блуждания гиперблохи
Сообщение11.03.2017, 19:28 


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

 Профиль  
                  
 
 Re: Блуждания гиперблохи
Сообщение11.03.2017, 23:13 
Аватара пользователя


08/08/14

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

 Профиль  
                  
 
 Re: Блуждания гиперблохи
Сообщение12.03.2017, 10:50 


01/11/14
195
levtsn в сообщении #1199282 писал(а):
Гиперкуб можно урезать до цепи из 6 точек...,

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

 Профиль  
                  
 
 Re: Блуждания гиперблохи
Сообщение12.03.2017, 11:04 


02/09/10
76
Iam в сообщении #1199362 писал(а):
которая для четного числа шагов редуцируется в цепь из 3-х точек, для которой получим P=1/2.

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

 Профиль  
                  
 
 Re: Блуждания гиперблохи
Сообщение12.03.2017, 12:34 


01/11/14
195
Постараюсь пояснить. Все позиции блохи можно представить множеством последовательностей длины 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,... $
Дальнейшее решение сложности уже не составит.

 Профиль  
                  
 
 Re: Блуждания гиперблохи
Сообщение12.03.2017, 13:58 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Iam в сообщении #1199406 писал(а):
Дальнейшее решение сложности уже не составит.

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

-- 12.03.2017, 14:01 --

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

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

 Профиль  
                  
 
 Re: Блуждания гиперблохи
Сообщение12.03.2017, 17:57 
Аватара пользователя


08/08/14

991
Москва
Какие центральные точки?

 Профиль  
                  
 
 Re: Блуждания гиперблохи
Сообщение12.03.2017, 21:25 


02/09/10
76

(Оффтоп)

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

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

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

 Профиль  
                  
 
 Re: Блуждания гиперблохи
Сообщение13.03.2017, 11:07 
Заслуженный участник
Аватара пользователя


23/08/07
5419
Нов-ск
В лоб можно вот так. Обозначим $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^-)$

 Профиль  
                  
 
 Re: Блуждания гиперблохи
Сообщение13.03.2017, 13:09 
Заслуженный участник
Аватара пользователя


01/09/13
4318
staric в сообщении #1199598 писал(а):
Я даже пожалел, что не заставил блоху прыгать по 7-кубу... (бонусный вопрос №1)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group