2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5  След.
 
 Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 18:58 


13/02/17

317
Varanasi
Здравствуйте. Придумал задачу, а решить не получается:

Изображение

Пусть мы находимся в точке $A$- это дом. Можно совершать непрерывное движение по стрелкам. Переход от одной точки к другой по стрелке назовем шагом. В каждой точке мы имеем равновероятную возможность сделать шаг по одной из 2-х стрелок, выходящих из этой точки, с вероятностью $p=\frac{1}{2}$ для шага по часовой стрелке и с вероятностью $1-p=\frac{1}{2}$ для шага против часовой стрелки. Сделав $n\geq 2$ шагов мы можем оказаться в любой из точек.

Какова вероятность после совершения ровно $n\geq2$ шагов оказаться дома?
По пути можно неоднократно заходить домой.

Собственно попытки решения: необходимо определить сколько существует вариантов путей длины n, приводящих из дома домой(с этим как раз проблема) и разделить на количество всех путей длины n, выходящих из дома, которое равно $2^n$.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 19:22 


05/09/16
11467
Aether
Я бы шел примерно так.
Обозначим единице ход по часовой стрелке, нулем -- против часовой стрелки.
Составим всевозможные $n$-разрядные числа в двоичной системе счисления.
Таких чисел будет всего $2^n$

Числа которые ведут к дому, это те, у которых модуль разности количества нулей и количества единиц равен нулю или делится на $3$.

Для $n=3$ к дому ведут только два числа из восьми: $111$ и $000$, так что вероятность оказаться дома равна $0,25$

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 19:28 


13/02/17

317
Varanasi
wrest в сообщении #1235708 писал(а):
Числа которые ведут к дому, это те, у которых модуль разности количества нулей и количества единиц равен нулю или делится на $3$.


Спасибо, а как определить количество n-разрядных чисел, удовлетворяющих этому условию? ведь n может быть и очень большим, должна же быть какая-то общая формула?

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 19:40 
Заслуженный участник


23/07/08
10626
Crna Gora
Пусть $a_n, b_n, c_n$ — количество способов после $n$ ходов оказаться в точках $A, B, C$ соответственно. Из симметрии имеем $b_n=c_n$. В начале $a_0=1, b_0=0$, затем $a_{n+1}=2b_n,\; b_{n+1}=a_n+b_n$.

Решение рекуррентных соотношений облегчается, если доказать по индукции $a_n-b_n=(-1)^n$. Вместе с уравнением $a_n+2b_n=2^n$ это даёт явные формулы.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 19:44 
Аватара пользователя


04/10/15
291
Пусть $T_n$ количество путей из точки $A$ в точку $A$ за $n$ шагов, а $M_n$, соответственно, множество этих путей.
Лемма. $T_{2n+1}=T_{2n}+2T_{2n-1}$
Доказательство.
Сопоставим каждому пути из $M_{2n}$ путь из $M_{2n+1}.$ Если мы возвращаемся домой за $2n$ шагов, то на $(2n-1)$-ом шаге мы в точке $B$ или в точке $C$, но тогда такой путь единственным образом продолжается до пути за $(2n+1)$ шагов, мы просто шагаем в точку, отличную от точки $A$ за один шаг, а за второй шаг в точку $A$. Теперь возьмём произвольный путь из $M_{2n-1}$ и сопоставим ему два элемента из $M_{2n}$. Поскольку мы возвращаемся домой за $(2n-1)$ шаг, то мы можем сделать один шаг в любую из точек $B, ~C$, а потом вернуться в точку $A$. Легко видеть, что разным путям мы сопоставили разные пути, при этом для каждого пути из $M_{2n+1}$ мы нашли путь, который продолжается до искомого пути.

Аналогичными рассуждениями можно получить выражение $T_{2n}=T_{2n-1}+2T_{2n-2}$, после чего по линейной рекурренте написать формулу общего члена.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 20:04 


13/02/17

317
Varanasi
svv в сообщении #1235710 писал(а):
Из симметрии имеем $b_n=c_n$.

Спасибо, это понятно, а откуда следует это:
svv в сообщении #1235710 писал(а):
$a_{n+1}=2b_n,\; b_{n+1}=a_n+b_n$
?

Например количество путей длины 4, приводящих из дома домой равно 6, а количество путей длины 3, приводящих из дома в точку b должно быть равно 3, но я нахожу только 2 пути?

Прошу прощения, нашел третий.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 20:11 
Заслуженный участник


20/08/14
11065
Россия, Москва

(Численный эксперимент)

Вероятность вернуться домой:
Код:
n=1,  p=0.0
n=2,  p=0.5
n=3,  p=0.25
n=4,  p=0.375
n=5,  p=0.3125
n=6,  p=0.34375
n=7,  p=0.328125
n=8,  p=0.335938
n=9,  p=0.332031
n=10, p=0.333984
n=11, p=0.333008
n=12, p=0.333496
n=13, p=0.333252
n=14, p=0.333374
n=15, p=0.333313
n=16, p=0.333344
n=17, p=0.333328
n=18, p=0.333336
n=19, p=0.333332
n=20, p=0.333334
n=21, p=0.333333
Для всех $n$ далее вероятность остаётся такой же.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 20:12 
Заслуженный участник


23/07/08
10626
Crna Gora
Aether в сообщении #1235713 писал(а):
откуда следует это
Из соотношений
$a_{n+1}=b_n+c_n$
$b_{n+1}=c_n+a_n$
$c_{n+1}=a_n+b_n$
с учетом $\forall n, \;b_n=c_n$.
Aether в сообщении #1235713 писал(а):
я нахожу только 2 пути
ABAB, ABCB, ACAB

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 20:19 
Заслуженный участник


20/08/14
11065
Россия, Москва
Количество "правильных" путей (с возвратом домой) есть в A014113.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 20:23 


13/02/17

317
Varanasi
svv,Dmitriy40,iou,wrest

Всем спасибо.

-- 24.07.2017, 21:33 --

И кстати, я ещё пытался решить эту же задачу, но только пути приводящие домой и состоящие из одинаковых шагов считаются эквивалентными. Например путь A,B,A,C,A эквивалентен A,C,A,B,A. Т.е. последовательность прохождения отрезков пути неважна, главное, чтобы путь был непрерывным. Это несколько усложняет задачу ))).
Прошу высказывать идеи ))).

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 22:18 
Заслуженный участник


23/07/08
10626
Crna Gora
А пути ABCA и ACBA считаются эквивалентными или нет? Важно ли направление прохождения отрезка?

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 22:54 


13/02/17

317
Varanasi
svv в сообщении #1235729 писал(а):
А пути ABCA и ACBA считаются эквивалентными или нет? Важно ли направление прохождения отрезка?


Важно, чтобы эквивалентные пути состояли из тех-же шагов, и, соответственно тех же рёбер графа со стрелочками, в приведенном Вами примере в путях различные рёбра, следовательно они не эквивалентны.

-- 24.07.2017, 23:59 --

Dmitriy40
Численный эксперимент применительно к данной задаче тоже очень приветствуется )))

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 00:04 
Заслуженный участник


20/08/14
11065
Россия, Москва
Aether в сообщении #1235733 писал(а):
Численный эксперимент применительно к данной задаче тоже очень приветствуется )))
Да я условия не понимаю. Если раньше было просто, количество единиц в двоичной записи числа и всё, то здесь, что такое эквивалентные пути, да ещё и непрерывные - вообще неясно.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 00:47 


05/09/16
11467
Dmitriy40 в сообщении #1235715 писал(а):
Для всех $n$ далее вероятность остаётся такой же.

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

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 00:55 
Заслуженный участник


23/07/08
10626
Crna Gora
Изображение
Неотрицательные целые числа $a,b,c,d,e,f$ показывают, сколько раз в данном маршруте пройдено каждое ребро. Два маршрута считаются эквивалентными, если для них наборы $(a,b,c,d,e,f)$ совпадают.

Числа эти не могут быть произвольными. Если маршрут начинается и заканчивается в $A$, выполняются соотношения, аналогичные закону Кирхгофа для токов:
$a+e=b+d$
$b+f=c+e$
$c+d=a+f$
(тут любое из уравнений следует из двух других). В другой форме:
$d-a=e-b=f-c=p$
Здесь $p$ — обозначение для общего значения всех трёх разностей. Числа $a, b, c, p$ можно считать базисными контурными токами, через которые выражаются $d, e, f$. При этом
$a$ соответствует контуру $BCB$,
$b$ соответствует контуру $CAC$,
$c$ соответствует контуру $ABA$,
$p$ соответствует контуру $ACBA$.
Положительное $p$ говорит о том, что в маршруте больше рёбер, направленных против часовой стрелки, чем по.

Кроме того, выполняется $a+b+c+d+e+f=n$. И ещё одно условие: исключается случай, когда ненулевые только $a$ и $d$.

Если все перечисленные условия выполнены, маршрут реализуем (обычно многими способами, которые мы считаем эквивалентными), его длина $n$, он начинается и заканчивается в $A$. Значит, надо сосчитать количество наборов $(a,b,c,d,e,f)$, удовлетворяющих всем условиям.

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

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



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

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


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

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