Среднее время встречи при случайном блуждании

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Среднее время встречи при случайном блуждании

Сообщение Ian » 28 дек 2018, 20:06

peregoudov писал(а): получается 108.711.
У меня 108,708 просто формат вывода такой

Albus
Сообщений: 59
Зарегистрирован: 11 июн 2019, 10:46

Среднее время встречи при случайном блуждании

Сообщение Albus » 28 май 2021, 00:23

Господа, вроде бы очевидно, что среднее число шагов шагов до возвращения в исходную точку будет равно $\frac{1}{p_i}$, где $p_i$ - вероятность попасть в данную вершину через очень большое время, т.е. установившееся состояние марковской цепи, когда $Mp=p$, где $M$ - матрица переходов, $p$- вектор вероятности нахождения в узлах цепи.
Например для трех сосен стационарное состояние будет $(0.(3),0.(3),0.(3))$, поэтому среднее число шагов будет равно трем :)

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Среднее время встречи при случайном блуждании

Сообщение Ian » 28 май 2021, 08:05

Albus писал(а):Господа, вроде бы очевидно, что среднее число шагов шагов до возвращения в исходную точку будет равно $\frac{1}{p_i}$, где $p_i$ - вероятность попасть в данную вершину через очень большое время, т.е. установившееся состояние марковской цепи, когда $Mp=p$, где $M$ - матрица переходов, $p$- вектор вероятности нахождения в узлах цепи.
Например для трех сосен стационарное состояние будет $(0.(3),0.(3),0.(3))$, поэтому среднее число шагов будет равно трем :)
Это среднее число шагов по всем начальным состояниям, если они равновероятны. Как средняя температура по больнице. А решена задача выразить среднее время встречи как функцию начального и конечного состояния формулой. Причем такие формулы в подробных книгах по марковским цепям я видел, они разные но надо было ту, по которой удобно считать, в громоздких задачах

Albus
Сообщений: 59
Зарегистрирован: 11 июн 2019, 10:46

Среднее время встречи при случайном блуждании

Сообщение Albus » 28 май 2021, 15:59

Ian писал(а):Source of the post Это среднее число шагов по всем начальным состояниям, если они равновероятны. Как средняя температура по больнице.

Не очень понятно, разве это не среднее число шагов, которое нам понадобится, чтобы вернуться в вершину $1$, откуда мы и стартовали? Тогда какое оно будет?
Ian писал(а):Source of the post А решена задача выразить среднее время встречи как функцию начального и конечного состояния формулой.

А можно поподробнее? Я понимаю задачу так - вот мы стартуем из вершины $a$, и нужно найти матожидание число шагов, которое необходимо для возвращения в эту вершину. Какое еще конечное состояние как параметр?

Albus
Сообщений: 59
Зарегистрирован: 11 июн 2019, 10:46

Среднее время встречи при случайном блуждании

Сообщение Albus » 28 май 2021, 17:05

Для случая трех сосен среднее число шагов можно легко посчитать вручную $\sum_{i=1}^{\infty} \frac{1+i}{2^i}=3$

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Среднее время встречи при случайном блуждании

Сообщение Ian » 29 май 2021, 08:12

Albus писал(а):Для случая трех сосен среднее число шагов можно легко посчитать вручную $\sum_{i=1}^{\infty} \frac{1+i}{2^i}=3$
Да Вы правильно все считаете, но случай трех сосен и сколько шагов в среднем сделает человек до следующего возвращения на исходную позицию -
он особенный, так как из трех состояний можно сделать два: "он уже там" или "он еще не там" и из второго в первое вероятность перехода 1/2, а из первого во второе 1 в начальный момент, 0 во все остальные (когда это посещение уже считается за возвращение). Теряется, из-за симметрии, цель задачи - найти состояние самое удаленное от данного (в вероятностном смысле), что может не совпадать с геометрически наиболее удаленным (при детерминированном движении по кратчайшему пути).

Albus
Сообщений: 59
Зарегистрирован: 11 июн 2019, 10:46

Среднее время встречи при случайном блуждании

Сообщение Albus » 05 июн 2021, 08:00

Ian
Ошибаетесь, моя формула работает всегда :)
Ian писал(а):Source of the post он особенный, так как из трех состояний можно сделать два

Ок, вот вам другой случай, менее симметричный. Пусть из сосны 1 вероятности будут по $0.5$, а вот для сосны 2 вероятность перехода в сосну 1 будет $0.75$, а вероятность перехода в сосну 3 $0.25$, тоже самое для сосны 3, т.е. присутствует осевая симметрия.
Тогда предельная вероятность для сосны 1 будет $\frac{3}{7}$, а среднее число шагов будет $2.(3)$
Посчитаем среднее число шагов в лоб $\sum_{i=0}^{\infty} \frac{3}{4} \frac{(i+2)}{4^i}=2.(3)$
Можете рассмотреть другую цепь, посчитать для нее среднее число шагов в лоб (по программе), и сравнить с моим способом :)

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Среднее время встречи при случайном блуждании

Сообщение Ian » 05 июн 2021, 10:25

Наоборот я подтвердил, что ошибок у вас нет. Я про пользу ответа.

Albus
Сообщений: 59
Зарегистрирован: 11 июн 2019, 10:46

Среднее время встречи при случайном блуждании

Сообщение Albus » 05 июн 2021, 19:16

Ian писал(а):Source of the post Наоборот я подтвердил, что ошибок у вас нет. Я про пользу ответа.

А, наверно я не так понял :) Т.е. вы согласны с
Albus писал(а):Source of the post среднее число шагов шагов до возвращения в исходную точку будет равно $\frac{1}{p_i}$
?
Просто я думал что вы думаете что это не ответ на конкретный вопрос
Ian писал(а):Source of the post среднее время встречи как функцию начального состояния
, а какое то усреднение, работающее только в симметричных случаях. Или все норм?
У меня кстати не получилось в общем случае найти среднее число шагов, когда конечная точка не совпадает с начальной

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Среднее время встречи при случайном блуждании

Сообщение Ian » 06 июн 2021, 12:34

Есть марковская матрица [math] -вероятность перехода из i в j. В задачах о блужданиях традиционно [math]. В Вашей последней модели
[math]
Обозначали [math] -среднее время перехода из i в j. Для единообразия считали [math] , то есть если мы уже там , время 0. То есть именно поставленную вами задачу (не считать его нулем, а считать следующий возврат) мы пока не решали явно.

По уравнению 1' на странице 1 темы [math] ,Е это не путать с I-единичной, матрица где все элементы единицы, P -проектор зануляющий диагональ матрицы

Это уравнение расписываем поэлементно в общем виде
[math]
, и еще 2 аналогичных решаемых системы. Вывести это можно и не ссылаясь на уравнение 1'. Действительно, из 2 можно либо попасть в 1 за 1 шаг, либо с вероятностью [math] через 3 попасть туда же за [math] шагов.

Тогда у поставленной Вами задачи о среднем времени [math] возвращения из 1 в 1 придется усреднять по двум возможным путям отхода в 1-й момент
[math]
,при Ваших вероятностях получается 7/3.. И действительно, при установившемся режиме [math]

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


Вернуться в «Математика»

Кто сейчас на форуме

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