2014 dxdy logo

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

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





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


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

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


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

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


13/02/17
295
Varanasi
На ум приходит лишь, что первый прыжок однозначно сокращает минимальное расстояние до исходной точки с 4-х прыжков до 3-х, а до противоположной точки - с 5-ти до 4-х прыжков. Второй прыжок однозначно сокращает растояние до первой точки с 3-х до 2-х прыжков и расстояние до противоположной точки с 4-х до 3-х прыжков. Третий прыжок может уже как увеличивать минимальное расстояние до исходной точки с 2-х до 3-х прыжков и сокращать его до противоположной с 3-х до 2-х, так и наоборот - уменьшать минимальное расстояние до исходной точки с 2-х до 1 и увеличивать его до противоположной с 3-х до 4-х.

Предполагаю, что начинать расчет необходимо с точек, в которых гиперблоха может оказаться после второго прыжка, потому, что при движении до этих точек она однозначно приближается к обеим конечным точкам.

Зацикливаниями следует пренебречь, поскольку можно считать, что они ни приближают, ни удаляют блоху к конечной точке, т.к. внутри цикла всегда можно произвести взаимоуничтожение удаляющих и приближающих путей.

Дальше похоже надо считать варианты.

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


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

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

-- 12.03.2017, 14:01 --

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

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

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


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

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


13/02/17
295
Varanasi
Может быть уважаемый топикстартер выложит под спойлер правильный ответ?

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


02/09/10
56

(Оффтоп)

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

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

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

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


13/02/17
295
Varanasi
staric в сообщении #1199598 писал(а):
Верный ответ был дан Iam достаточно быстро


Я попытался решить задачу в лоб, начал строить дерево событий, оно должно иметь бесконечное количество уровней ветвей, но некоторые ветви прерываются, чем раньше прерывается ветвь, тем выше вероятность события. Тенденция такова, что при перемещении по дереву, вероятность попадания в противоположную точку на начальной ступени выше и растет быстрее чем вероятность попадания в исходную точку. Т.е. попасть в противоположную точку более вероятно. Конечно я не рассмотрел всё бесконечное дерево и даже не рассмотрел достаточное количество ветвей, чтобы утверждать это однозначно. Но такова тенденция. Возможно я где-то ошибся.

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


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


Также непонятно, почему рассматривается лишь четное число шагов? Ищется только вероятность попасть в исходную точку?

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


23/08/07
4589
Нов-ск
В лоб можно вот так. Обозначим $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, 11:24 


13/02/17
295
Varanasi
Там могут возникать бесконечные циклы, поэтому определить вероятность попадания в исходную точку из любой будет проблематично, но можно без проблем определить вероятность её перехода в любую соседнюю или даже на соседний уровень.

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


23/08/07
4589
Нов-ск
Aether в сообщении #1199810 писал(а):
Там могут возникать бесконечные циклы, поэтому определить вероятность попадания в исходную точку из любой будет проблематично

Требуется найти вероятность попадания в исходную точку, а не в противоположную. Сумма этих вероятностей равна $1$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

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



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

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


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

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