2014 dxdy logo

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

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




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

Изображение

Пусть мы находимся в точке $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 
Aether
Я бы шел примерно так.
Обозначим единице ход по часовой стрелке, нулем -- против часовой стрелки.
Составим всевозможные $n$-разрядные числа в двоичной системе счисления.
Таких чисел будет всего $2^n$

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

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

 
 
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 19:28 
wrest в сообщении #1235708 писал(а):
Числа которые ведут к дому, это те, у которых модуль разности количества нулей и количества единиц равен нулю или делится на $3$.


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

 
 
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 19:40 
Аватара пользователя
Пусть $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 
Аватара пользователя
Пусть $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 
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 

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

Вероятность вернуться домой:
Код:
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 
Аватара пользователя
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 
Количество "правильных" путей (с возвратом домой) есть в A014113.

 
 
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 20:23 
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 
Аватара пользователя
А пути ABCA и ACBA считаются эквивалентными или нет? Важно ли направление прохождения отрезка?

 
 
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение24.07.2017, 22:54 
svv в сообщении #1235729 писал(а):
А пути ABCA и ACBA считаются эквивалентными или нет? Важно ли направление прохождения отрезка?


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

-- 24.07.2017, 23:59 --

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

 
 
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 00:04 
Aether в сообщении #1235733 писал(а):
Численный эксперимент применительно к данной задаче тоже очень приветствуется )))
Да я условия не понимаю. Если раньше было просто, количество единиц в двоичной записи числа и всё, то здесь, что такое эквивалентные пути, да ещё и непрерывные - вообще неясно.

 
 
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 00:47 
Dmitriy40 в сообщении #1235715 писал(а):
Для всех $n$ далее вероятность остаётся такой же.

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

 
 
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 00:55 
Аватара пользователя
Изображение
Неотрицательные целые числа $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  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group