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

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

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

Сообщение Ian » 24 дек 2018, 17:44

Определения.

Распределение вероятностей среди n состояний системы - матрица- строка [math]

Марковская цепь- случайный процесс с дискретным временем такой, что вероятность перехода в момент времени (m+1) зависит только от состояния в момент m, и ни от какой информации о предшествовавших состояниях.То есть заданы [math]

Процесс стационарный, если [math] не зависит также от ноиера шага m , с такими и будем иметь дело

Матрица [math] называется матрицей марковской цепи.[math], что в матричной форме значит [math]-распределение вероятности в момент m получается из любого предшествующего умножением его строки на нужную степень квадратной матрицы [math]. Сумма элементов любой строки матрицы А равна 1 -матрица марковской цепи всегда вырождена.

Пусть [math] то есть система на нулевом шаге с определенностью находится в состоянии k. Вероятность, что система придет в состояние j на m-м шаге, находится в j-м столбце k-й строки матрицы [math]. Процесс называется эргодическим, если из любого состояния достижимо любое за достаточно большое число шагов, то есть для любых [math] от 1 до n найдется M, что при всех m>M в строке k столбце j матрицы [math] будет стоять не ноль. У эргодического процесса всегда имеется предельное распределение [math], так что независимо от начального распределения р p[math] в смысле сходимости последовательности n- мерных векторов. [math] является собственным вектором матрицы А с собственным значением 1. Каждая строка матрицы [math]сходится к строке [math].

Рассмотрим [math]-матожидание числа шагов , необходимых для попадания из состояния k до первого появления состояния j. Естественно [math] , и конечно составим из [math] матрицу М. Доказательство, что для эргодической матрицы все [math] конечны, существует, но не приводим. [math] действительно, из состояния k либо с вероятностью [math]попадем сразу в j, либо попадем в состояние i и потратим в среднем [math] шагов, включая один сделанный. Приходим к равенству [math] или в матричном виде [math]
[math],(1)
где Е- матрица, состоящая из [math] единиц, в отличие от I -единичной матрицы, где единицы только на диагонали. Далее применить [math] нельзя из-за вырожденности, но уравнений для определения М по А хватает, мы знаем что [math]

Для решения задачи о среднем числе шагов до “встречи” (первого совпадения состояний), при начальных состояниях k и l, обозначим ответ этой задачи через [math] Ясно, что [math], а матрица S симметрична [math] действительно, из состояний k и l либо с вероятностью [math] попадем в какое-то одно i, либо попадем в разные состояния i и j и потратим в среднем [math] шагов, включая один сделанный. Преобразуем [math]
[math] (2)
[math]-транспонированная матрица А. Эта система дает [math] линейно независимых уравнений, если А эргодическая, для определения стольких же переменных [math]
---
Уважаемые участники, вот что мне требуется. Решить для какого-нибудь блуждания по графу матричные уравнения (1) и (2). Если ответы будут неправдоподобны, буду искать ошибку в приведенном рассуждуеннии.

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

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

Сообщение peregoudov » 26 дек 2018, 15:45

Уравнение $(I-A)M=E$ вроде как несовместное. Пусть $m$ --- столбец матрицы $M$, а $e$ --- столбец матрицы $E$. Уравнение для $M$ распадается на отдельные уравнения для $m$, $(I-A)m=e$. В силу $\sum_j A_{ij}=1$ столбец $e$ является собственным вектором $A$ с собственным значением 1, $Ae=e$. Пусть $\Pi_1$ --- проектор на этот вектор. Тогда $\Pi_1(I-A)m=0$, но $\Pi_1e=e\neq0$.

По-другому: если все собственные значения A различны, то собственные векторы образуют базис, а в левой части стоит линейная комбинация векторов с неединичными собственными значениями, тогда как в правой, наоборот, стоит вектор с единичным собственным значением.

P. S. Мне кажется, вы вообще что-то не то считаете. Если $A_{ij}$ ($i\neq j$) отлична от нуля, то $M_{ij}=1$ сразу, ничего там суммировать уже не надо.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 26 дек 2018, 23:25

Да.
Вот например двумерный случай: [math].
Тут нам [math] даёт:
[math]
[math]

Видимо ошибка в [math].

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 27 дек 2018, 00:04

Ian писал(а):Source of the post [math]

Думаю, это просто не верно.

Взять например [math]. Т.е. [math] равен [math] плюс неотрицательное число.

Думаю, это уравнение не учитывает тот факт, что процесс идет до достижения целевого состояния и потом процесс прекращается.

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

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

Сообщение Ian » 27 дек 2018, 00:20

Действительно, я что-то путаюсь. Вот модель "блуждание среди трех сосен"Вероятности перехода от любой сосны к любой другой 1/2. Из симметрии обозначим М среднее число шагов до первого достижения от данной одной сосны данной другой. Аналогично[math] отсюда М=2 а вовсе не 1. И была попытка свернуть этот метод в матрицу.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 27 дек 2018, 00:21

Например для того же двумерного случая получим [math], что просто не верно.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 27 дек 2018, 00:26

На этом примере видно, что хотя [math], т.е. "из 1 мы попадаем в 1" за 0 шагов, но это не важно для [math]. Мы можем оставатся в 1 несколько шагов (каждый раз с вероятность [math]), и только потом перескочить в 2 (каждый раз вероятность этого [math]).

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

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

Сообщение Ian » 27 дек 2018, 09:15

Рассмотрим [math]-матожидание числа шагов , необходимых для попадания из состояния k до первого появления состояния j. Естественно [math] , и конечно составим из [math] матрицу М. Доказательство, что для эргодической матрицы все [math] конечны, существует, но не приводим. [math] действительно, из состояния k либо с вероятностью [math]попадем сразу в j, либо попадем в состояние i и потратим в среднем [math] шагов, включая один сделанный. Приходим к равенству [math] или в матричном виде [math] (1'),
где Е- матрица, состоящая из [math] единиц, в отличие от I -единичной матрицы, где единицы только на диагонали. P за скобкой это не умножение матриц. Р это проектор в пространстве матриц, обнуляюший всю диагональ. Далее применить итерации, уравнение 1' этому способствует, из-за малости элементов матрицы А они должны сойтись, но искусственно обнулять диагональ на каждом шаге итерации [math]
Вот исправил абзац поста 1 с учетом всех замечаний. При выводе уравнения 2 тоже будет небольшое исправление, связанное с нулями на диагонали.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 27 дек 2018, 12:53

Ian писал(а):Source of the post Вот исправил абзац поста 1 с учетом всех замечаний
Думаю, что [math] в принципе не верно.
Ian писал(а):Source of the post И была попытка свернуть этот метод в матрицу.

Мне кажется, так просто это не получится.

У меня вот так получается для вычисления [math] (где [math]):
Обозначим подматрицу от [math] в которой выбросили строку [math] и столбец [math], как [math] (или просто [math]). Столбец матрицы [math] с индексом [math], из которого выбросили элемент [math], как [math] (или просто [math]). Строка [math] (или просто [math]) размера [math] получается из нулевой строки размера [math] заменой 0 на 1 в элементе [math] и затем выбрасыванием элемента [math].

Тогда [math].
Пусть [math], тогда [math]
[math].
Так же [math].

Отсюда получаем [math] и [math].
Поскольку [math] эргодична, то имеет место ненулевое утекание в состояние [math] (матрица [math] отвечает за внутренние переходы между всеми состояниями кроме [math], а столбец [math] отвечает за утекание из всех этих состояний в состояние [math]), то [math] стремится к нулевой матрице по мере роста [math].
Значит [math]
[math]
[math].

В итоге получаем [math].

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 27 дек 2018, 13:06

Пример для двух измерений:
Для матрицы [math] получим по формуле
[math], что соответствует элементарному анализу двумерной ситуации.

(Как известно, [math].)

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

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

Сообщение Ian » 27 дек 2018, 13:42

Ну знаете , писать " в принципе не верно" на утверждение доказанное в одну строчку. не указав ошибку...
Матрица вероятностей переходов для трех состояний А=

Код: Выбрать все

0              1/3        2/3 
   3/4     0              1/4 
   1/2        1/2     0       
За 13 итераций из матрицы Е получилась матрица средних М

Код: Выбрать все

0       2 1/2   1 7/9
1 3/7   0       2 1/3
1 5/7   2 1/4   0   
с ошибкой 0,001.Формат Excel дробный.То есть правильный ответ, удовлетворяющий уравнению 1'

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

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

Сообщение peregoudov » 27 дек 2018, 14:06

Скажите, а зачем вообще полагать $M_{ii}=0$? Пусть это будет среднее число шагов до возврата в исходное состояние. Тогда уравнение в матричном виде запишется как $M'=AP(M')+E$. Если теперь подействовать проектором, то получим $P(M')=P(AP(M')+E)$, то есть ваше уравнение с $M=P(M')$.

Например, для "блуждания в трех соснах", если я правильно понимаю, $A=(E-I)/2$ (1/2 всюду, кроме диагонали), тогда уравнения для определения $M'$ в явной записи выглядят так

$$ \begin{pmatrix} m_{11}&m_{12}&m_{13}\\ m_{21}&m_{22}&m_{23}\\ m_{31}&m_{32}&m_{33} \end{pmatrix}= \begin{pmatrix} 0&1/2&1/2\\ 1/2&0&1/2\\ 1/2&1/2&0 \end{pmatrix} \begin{pmatrix} 0&m_{12}&m_{13}\\ m_{21}&0&m_{23}\\ m_{31}&m_{32}&0 \end{pmatrix}+ \begin{pmatrix} 1&1&1\\ 1&1&1\\ 1&1&1 \end{pmatrix} $$

и приводят к ожидаемому результату $m_{11}=3$, $m_{12}=2$.
Последний раз редактировалось peregoudov 27 дек 2018, 14:06, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 27 дек 2018, 14:06

Ian писал(а):Source of the post не указав ошибку...

Я приводил пример ранее:
zykov писал(а):Source of the post Например для того же двумерного случая получим [math], что просто не верно.

Но там у меня ошибка. Извиняюсь!

Возьмем для примера матрицу [math].
По Вашей формуле будет [math], т.е. [math].
Значит [math] - всё сходится.

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

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

Сообщение Ian » 27 дек 2018, 16:22

В том, что я уравнение 1 заменил на 1' велика и роль peregoudov, строго доказал неверность 1), и роль zykov, указал, что именно для k=j ошибка. А я только сидел и чесал репу. Но теперь уравнение 1' из цитаты считаю верным и даже подтвержденным расчетами. Метод итераций медленно сходится для больших матриц, конечно,хорошо бы заранее иметь оценку числа итераций, имея матрицу А для числа состояний порядка нескольких десятков, там и элементы М порядка сотни

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

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

Сообщение Ian » 28 дек 2018, 00:36

Обсчитал и итерации по уравнению 1', и итерации по уравнению 2' [math]для реальной задачи с 31 вершиной.Граф на картинке, из каждой вершины переходы по любому ребру равновероятны между собой и равновероятны остановке на месте.
gr31.jpg
gr31.jpg (54.66 KiB) 31752 просмотра

Результаты итераций по уравнению 1', пока не добились [math]

Код: Выбрать все

ответ задачи после числа итераций N=3777                  Макс.среднее время 454,74 в столбце 5 строках 19-23
Уравнение 2' лучше обусловлено,для точности 0,0005 хватило 1002 итерации

Код: Выбрать все

Здесь копия ответа задачи после числа итераций N=1002                  Макс.среднее время 159,999 в столбцах 10-14 строках26-30                        Наибольшее отклонение матрицы последней итерации от предпоследней =                        0,000492066                        
Расчетный файл весом 119мег по ссылке https://dropmefiles.com/FYBc5 пролежит там дней 5 потом автоудалится
peregoudov, Вы изменили формулу 1' на эквивалентную, это уже вопрос программистский кто на чем и в чем считает. Середина цикла моей итерации это начало цикла Вашей итерации, а действия в сумме за цикл одни и те же. Какие-то формулы видел в книгах, но кажется они сложнее для расчета. Если 1)я 2)за час,3)в экселе обсчитал реальную модель, то спец с программами будет их как орешки щелкать

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

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

Сообщение peregoudov » 28 дек 2018, 14:28

А зачем итерации-то? Ведь решается линейная система уравнений. Ну вот, например, в моем варианте $M'=AP(M')+E$. Матрицы $M$ и $E$ разделим на столбцы и поставим их друг на друга. Вместо $A$ рассмотрим блочно-диагональную матрицу, на диагонали которой стоят матрицы $A$ с обнуленным 1-ым, 2-ым ... столбцом. Тогда, сохраняя буквенные обозначения для преобразованных матриц, получаем систему уравнений $M=AM+E$. И решаем ее каким-нибудь методом для ленточных матриц!

P. S. Я правильно понимаю, что у вас в примере в 7-вершинных кластерах переходы есть между любыми вершинами? Просто там линий не разберешь. С отдельно стоящими вершинами все понятно.

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

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

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

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

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

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

Сообщение peregoudov » 28 дек 2018, 15:43

Ну, я написал процедуру на Maple. Она довольно быстро считает без всяких оптимизаций с ленточными матрицами. Например, среднее число шагов для перехода 1->2 получается 108.711. Что-то многовато... Сам код для Maple под катом

Код: Выбрать все

with(LinearAlgebra);

Ablock := proc (A) local i, j, k, N, Abl; N := ColumnDimension(A); Abl := Matrix(N*N, N*N, fill = 0); for i to N do for j to N do if j <> i then for k to N do Abl((i-1)*N+k, (i-1)*N+j) := A(k, j) end do end if end do end do; return Abl end proc;

Msteps := proc (A) local i, j, N, E, Abl, Id, M; N := ColumnDimension(A); Id := IdentityMatrix(N*N); E := Vector(N*N, fill = 1); Abl := Ablock(A); E := LinearSolve(Id-Abl, E); M := Matrix(N, N); for i to N do for j to N do M(i, j) := E(i+(j-1)*N) end do end do; return M end proc

makeA := proc (G) local i, j, N, A, p; N := nops(G); A := Matrix(N, N, fill = 0); for i to N do p := 1/nops(G[i]); for j to nops(G[i]) do A(i, G[i][j]) := p end do end do; return A end proc

# 31-вершинный граф Ian'а
G := [[1, 2, 31], [1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 7], [6, 7, 8], [7, 8, 9, 10, 11, 12, 13, 14], [8, 9, 10, 11, 12, 13, 14], [8, 9, 10, 11, 12, 13, 14], [8, 9, 10, 11, 12, 13, 14], [8, 9, 10, 11, 12, 13, 14], [8, 9, 10, 11, 12, 13, 14], [8, 9, 10, 11, 12, 13, 14, 15], [14, 15, 16], [15, 16, 17], [16, 17, 18, 19, 20, 21, 22, 23], [17, 18, 19, 20, 21, 22, 23], [17, 18, 19, 20, 21, 22, 23], [17, 18, 19, 20, 21, 22, 23], [17, 18, 19, 20, 21, 22, 23], [17, 18, 19, 20, 21, 22, 23], [17, 18, 19, 20, 21, 22, 23, 24], [23, 24, 25, 26, 27, 28, 29, 30], [24, 25, 26, 27, 28, 29, 30], [24, 25, 26, 27, 28, 29, 30], [24, 25, 26, 27, 28, 29, 30], [24, 25, 26, 27, 28, 29, 30], [24, 25, 26, 27, 28, 29, 30], [24, 25, 26, 27, 28, 29, 30, 31], [30, 31, 1]];

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

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

Сообщение Ian » 28 дек 2018, 17:47

peregoudov писал(а): среднее число шагов для перехода 1->2 получается 108.711. Что-то многовато...
Слишком большое расхождение с моим, у меня 119. Сверим исходные данные;
A.png
A.png (20.6 KiB) 31719 просмотра

Ответы :М
M.png
M.png (44.07 KiB) 31719 просмотра

Матрица средних времен первой встречи S
S.png
S.png (44.21 KiB) 31719 просмотра

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

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

Сообщение peregoudov » 28 дек 2018, 19:05

Нету расхождения. Просто у вас нумерация узлов с нуля, а у меня --- с единицы, ваш узел 0 у меня 31-й. Так что надо сравнивать ваш переход 2-3, а он как раз 109.


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

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

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