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

[Aether]

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

Если все перечисленные условия выполнены, маршрут реализуем, его длина $n$, он начинается и заканчивается в $A$. Значит, надо сосчитать все такие.

Спасибо, это Вы Dmitriy40 объяснили? Задача состоит в том, чтобы найти общую формулу, а не посчитать, но посчитать тоже было бы неплохо.

[svv]

Это я произношу мысли вслух. Можно сказать, обозначаю те объекты, которые надо пересчитывать.

Мы сейчас уже свободны от детального рассмотрения каждого маршрута. Каждый класс эквивалентности (множество эквивалентных маршрутов) определяется четырьмя числами.

-- Вт июл 25, 2017 02:04:11 --

Фиксируем $m=a+b+c$, чтобы $n-2m=3p$ было положительным числом, кратным $3$. Для фиксированного $m$ число неэквивалентных маршрутов равно количеству композиций числа $m$ длиной $3$ с нулевыми частями, то есть $\frac{(m+1)(m+2)}{2}$.
Остаётся просуммировать это для допустимых $m$.

[Aether]

svv
Спасибо.
Итого, имеем одно уравнение с четырьмя неизвестными:
$2(a+b+c)+3p=n$, необходимо найти выражение через $n$ для количества его решений.

[svv]

Я там чуть подредактировал. В итоге: случай отрицательных $p$ сводится к случаю положительных $p$ (в силу симметрии). Случай $p=0$ потом рассмотрим отдельно. А для положительных надо просуммировать $\frac{(m+1)(m+2)}2$ по всем таким $m\geqslant 0$, для которых $n-2m$ — положительное число, кратное $3$.

[Aether]

Это работает только для нечетных $n$(решается только перебором похоже), нужна ещё часть, работающая для четных.

[svv]

Имеете в виду, что не рассмотрен случай $p=0$, а без него можно обойтись только для нечётных $n$?

[Aether]

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

Имеете в виду, что не рассмотрен случай $p=0$, а без него можно обойтись только для нечётных $n$?

По крайней мере мне так кажется.

[NDP]

Как один из способов, для вычисления вероятности попасть домой за $n$ шагов можно использовать цепи Маркова. Матрица переходных вероятностей $P$ очевидно, как составляется, ее собственные значения ищутся без труда, матрица переходных вероятностей $P^n$ за $n$ шагов в качестве собственных значений имеет $n$-е степени собственных значений матрицы $P$. Из соображений симметрии ясно, что на ее диагонали стоят равные между собой элементы, поэтому искомая вероятность равна $1/3 \operatorname{tr} P^n$, то есть трети суммы $n$-х степеней собственных значений $P$.

Чтобы совсем тоскливо не было, ответ не пишу.

[Aether]

Ну это видимо тоже будет количество композиций длины 3 с нулями числа $\frac{n}{2}$

[slu4ayniyProcess]

Условие задачи можно выразить через однородную цепь маркова.
Начальное распределение вероятностей будет П: (1, 0, 0)
Матрица вероятностей переходов P:
(0, 0.5, 0.5)
(0.5, 0, 0.5)
(0.5, 0.5, 0)

При этом P в квадрате будет:
(0.5, 0.25, 0.25)
(0.25, 0.5, 0.25)
(0.25, 0.25, 0.5)

Откуда в соответствии с эргодической теоремой (на втором шаге минимальный элемент больше нуля) получаем, что задача имеет решение (матрица переходных вероятностей имеет предел).
Нужно лишь найти предел, и умножить на П.
С пределом тут легко, если заметить, что сумма элементов в каждой строке и в каждом столбце равны единице. И что в соответствии с той самой эргодической теоремой в пределе мы получим одинаковые значения элементов внутри каждого столбца. А учитывая, что в сумме они должны дать единицу(доказывается элементарно), то этому удовлетворяет только 1/3.
Далее умножаем предельную матрицу состоящую из элементов равных 1/3 на вектор П и получаем вектор (1/3, 1/3, 1/3).
Где первый элемент является вероятностью вернуться домой, то есть ответом.

PS: Опередили xD

[NDP]

slu4ayniyProcess
Это, конечно, хорошо, но о другом. Предельных вероятностей не требовалось, требовалась, в соответствии с буквой задачи, вероятность ровно за $n$ шагов. Это никогда не $1/3$, хотя, естественно, начиная с некоторого номера $n$, и очень быстро, поскольку зависимость экспоненциальная, значение вероятности отличается от $1/3$ незначительно. Здесь post1235715.html#p1235715 это хорошо видно. Видимость, что далее - всегда треть - это только видимость, вызванная погрешностью округления.

[svv]

slu4ayniyProcess, NDP
Вероятности, о которых спрашивалось в исходной задаче, мы уже посчитали. Теперь вычисляется количество замкнутых маршрутов с началом в $A$ длиной $n$, с точностью до описанной здесь эквивалентности.

[Aether]

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

Я там чуть подредактировал. В итоге: случай отрицательных $p$ сводится к случаю положительных $p$ (в силу симметрии). Случай $p=0$ потом рассмотрим отдельно. А для положительных надо просуммировать $\frac{(m+1)(m+2)}2$ по всем таким $m\geqslant 0$, для которых $n-2m$ — положительное число, кратное $3$.

А как быть с невозможными случаями? Они учтены в данной редакции? И ещё, у меня что-то не получается применить практически всё это (

[svv]

С какими невозможными?

[Aether]

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

С какими невозможными?

Рассмотрим случай $n=4$, m в данном случае может быть равно только 2. Число указанных Вами композиций равно 6-ти, в реальности же для n=4 существует 5, учитывающих "описанную эквивалентность" случаев. Т.е. Ваш метод не учитывает эту эквивалентность(дает решение задачи в стартовой постановке), либо я неправильно им пользуюсь, тогда поправьте пожалуйста меня.