Вероятность вернуться домой за n шагов (случайное блуждание)

[Aether]

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



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

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

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

[wrest]

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

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

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

[Aether]

wrest в сообщении #1235708 писал(а):

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

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

[svv]

Пусть $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$ это даёт явные формулы.

[iou]

Пусть $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}$, после чего по линейной рекурренте написать формулу общего члена.

[Aether]

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 пути?

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

[Dmitriy40]

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

Вероятность вернуться домой:

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$ далее вероятность остаётся такой же.

[svv]

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

[Dmitriy40]

Количество "правильных" путей (с возвратом домой) есть в A014113.

[Aether]

svv,Dmitriy40,iou,wrest

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

-- 24.07.2017, 21:33 --

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

[svv]

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

[Aether]

svv в сообщении #1235729 писал(а):

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

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

-- 24.07.2017, 23:59 --

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

[Dmitriy40]

Aether в сообщении #1235733 писал(а):

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

Да я условия не понимаю. Если раньше было просто, количество единиц в двоичной записи числа и всё, то здесь, что такое эквивалентные пути, да ещё и непрерывные - вообще неясно.

[wrest]

Dmitriy40 в сообщении #1235715 писал(а):

Для всех $n$ далее вероятность остаётся такой же.

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

[svv]

Неотрицательные целые числа $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)$, удовлетворяющих всем условиям.