2014 dxdy logo

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

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





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


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

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


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

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


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

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

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


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

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

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


01/11/14
110
Постараюсь пояснить. Все позиции блохи можно представить множеством последовательностей длины 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
1429
Iam в сообщении #1199406 писал(а):
Дальнейшее решение сложности уже не составит.

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

-- 12.03.2017, 14:01 --

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

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

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


08/08/14
963
Москва
Какие центральные точки?

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


02/09/10
56

(Оффтоп)

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

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

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

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


23/08/07
4593
Нов-ск
В лоб можно вот так. Обозначим $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
1429
staric в сообщении #1199598 писал(а):
Я даже пожалел, что не заставил блоху прыгать по 7-кубу... (бонусный вопрос №1)

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

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

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



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

Сейчас этот форум просматривают: Мастак


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

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