Среднее время встречи при случайном блуждании
Среднее время встречи при случайном блуждании
Определения.
Распределение вероятностей среди 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). Если ответы будут неправдоподобны, буду искать ошибку в приведенном рассуждуеннии.
Распределение вероятностей среди 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). Если ответы будут неправдоподобны, буду искать ошибку в приведенном рассуждуеннии.
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Среднее время встречи при случайном блуждании
Уравнение вроде как несовместное. Пусть --- столбец матрицы , а --- столбец матрицы . Уравнение для распадается на отдельные уравнения для , . В силу столбец является собственным вектором с собственным значением 1, . Пусть --- проектор на этот вектор. Тогда , но .
По-другому: если все собственные значения A различны, то собственные векторы образуют базис, а в левой части стоит линейная комбинация векторов с неединичными собственными значениями, тогда как в правой, наоборот, стоит вектор с единичным собственным значением.
P. S. Мне кажется, вы вообще что-то не то считаете. Если () отлична от нуля, то сразу, ничего там суммировать уже не надо.
По-другому: если все собственные значения A различны, то собственные векторы образуют базис, а в левой части стоит линейная комбинация векторов с неединичными собственными значениями, тогда как в правой, наоборот, стоит вектор с единичным собственным значением.
P. S. Мне кажется, вы вообще что-то не то считаете. Если () отлична от нуля, то сразу, ничего там суммировать уже не надо.
Среднее время встречи при случайном блуждании
Да.
Вот например двумерный случай: [math].
Тут нам [math] даёт:
[math]
[math]
Видимо ошибка в [math].
Вот например двумерный случай: [math].
Тут нам [math] даёт:
[math]
[math]
Видимо ошибка в [math].
Среднее время встречи при случайном блуждании
Ian писал(а):Source of the post [math]
Думаю, это просто не верно.
Взять например [math]. Т.е. [math] равен [math] плюс неотрицательное число.
Думаю, это уравнение не учитывает тот факт, что процесс идет до достижения целевого состояния и потом процесс прекращается.
Среднее время встречи при случайном блуждании
Действительно, я что-то путаюсь. Вот модель "блуждание среди трех сосен"Вероятности перехода от любой сосны к любой другой 1/2. Из симметрии обозначим М среднее число шагов до первого достижения от данной одной сосны данной другой. Аналогично[math] отсюда М=2 а вовсе не 1. И была попытка свернуть этот метод в матрицу.
Среднее время встречи при случайном блуждании
Например для того же двумерного случая получим [math], что просто не верно.
Среднее время встречи при случайном блуждании
На этом примере видно, что хотя [math], т.е. "из 1 мы попадаем в 1" за 0 шагов, но это не важно для [math]. Мы можем оставатся в 1 несколько шагов (каждый раз с вероятность [math]), и только потом перескочить в 2 (каждый раз вероятность этого [math]).
Среднее время встречи при случайном блуждании
Вот исправил абзац поста 1 с учетом всех замечаний. При выводе уравнения 2 тоже будет небольшое исправление, связанное с нулями на диагонали.Рассмотрим [math]-матожидание числа шагов , необходимых для попадания из состояния k до первого появления состояния j. Естественно [math] , и конечно составим из [math] матрицу М. Доказательство, что для эргодической матрицы все [math] конечны, существует, но не приводим. [math] действительно, из состояния k либо с вероятностью [math]попадем сразу в j, либо попадем в состояние i и потратим в среднем [math] шагов, включая один сделанный. Приходим к равенству [math] или в матричном виде [math] (1'),
где Е- матрица, состоящая из [math] единиц, в отличие от I -единичной матрицы, где единицы только на диагонали. P за скобкой это не умножение матриц. Р это проектор в пространстве матриц, обнуляюший всю диагональ. Далее применить итерации, уравнение 1' этому способствует, из-за малости элементов матрицы А они должны сойтись, но искусственно обнулять диагональ на каждом шаге итерации [math]
Среднее время встречи при случайном блуждании
Думаю, что [math] в принципе не верно.Ian писал(а):Source of the post Вот исправил абзац поста 1 с учетом всех замечаний
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].
Среднее время встречи при случайном блуждании
Пример для двух измерений:
Для матрицы [math] получим по формуле
[math], что соответствует элементарному анализу двумерной ситуации.
(Как известно, [math].)
Для матрицы [math] получим по формуле
[math], что соответствует элементарному анализу двумерной ситуации.
(Как известно, [math].)
Среднее время встречи при случайном блуждании
Ну знаете , писать " в принципе не верно" на утверждение доказанное в одну строчку. не указав ошибку...
Матрица вероятностей переходов для трех состояний А=
За 13 итераций из матрицы Е получилась матрица средних М
с ошибкой 0,001.Формат Excel дробный.То есть правильный ответ, удовлетворяющий уравнению 1'
Матрица вероятностей переходов для трех состояний А=
Код: Выбрать все
0 1/3 2/3
3/4 0 1/4
1/2 1/2 0
Код: Выбрать все
0 2 1/2 1 7/9
1 3/7 0 2 1/3
1 5/7 2 1/4 0
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Среднее время встречи при случайном блуждании
Скажите, а зачем вообще полагать ? Пусть это будет среднее число шагов до возврата в исходное состояние. Тогда уравнение в матричном виде запишется как . Если теперь подействовать проектором, то получим , то есть ваше уравнение с .
Например, для "блуждания в трех соснах", если я правильно понимаю, (1/2 всюду, кроме диагонали), тогда уравнения для определения в явной записи выглядят так
и приводят к ожидаемому результату , .
Например, для "блуждания в трех соснах", если я правильно понимаю, (1/2 всюду, кроме диагонали), тогда уравнения для определения в явной записи выглядят так
и приводят к ожидаемому результату , .
Последний раз редактировалось peregoudov 27 дек 2018, 14:06, всего редактировалось 1 раз.
Среднее время встречи при случайном блуждании
Ian писал(а):Source of the post не указав ошибку...
Я приводил пример ранее:
zykov писал(а):Source of the post Например для того же двумерного случая получим [math], что просто не верно.
Но там у меня ошибка. Извиняюсь!
Возьмем для примера матрицу [math].
По Вашей формуле будет [math], т.е. [math].
Значит [math] - всё сходится.
Среднее время встречи при случайном блуждании
В том, что я уравнение 1 заменил на 1' велика и роль peregoudov, строго доказал неверность 1), и роль zykov, указал, что именно для k=j ошибка. А я только сидел и чесал репу. Но теперь уравнение 1' из цитаты считаю верным и даже подтвержденным расчетами. Метод итераций медленно сходится для больших матриц, конечно,хорошо бы заранее иметь оценку числа итераций, имея матрицу А для числа состояний порядка нескольких десятков, там и элементы М порядка сотни
Среднее время встречи при случайном блуждании
Обсчитал и итерации по уравнению 1', и итерации по уравнению 2' [math]для реальной задачи с 31 вершиной.Граф на картинке, из каждой вершины переходы по любому ребру равновероятны между собой и равновероятны остановке на месте.
Результаты итераций по уравнению 1', пока не добились [math]Уравнение 2' лучше обусловлено,для точности 0,0005 хватило 1002 итерации
Расчетный файл весом 119мег по ссылке https://dropmefiles.com/FYBc5 пролежит там дней 5 потом автоудалится
peregoudov, Вы изменили формулу 1' на эквивалентную, это уже вопрос программистский кто на чем и в чем считает. Середина цикла моей итерации это начало цикла Вашей итерации, а действия в сумме за цикл одни и те же. Какие-то формулы видел в книгах, но кажется они сложнее для расчета. Если 1)я 2)за час,3)в экселе обсчитал реальную модель, то спец с программами будет их как орешки щелкать
Результаты итераций по уравнению 1', пока не добились [math]
Код: Выбрать все
ответ задачи после числа итераций N=3777 Макс.среднее время 454,74 в столбце 5 строках 19-23
Код: Выбрать все
Здесь копия ответа задачи после числа итераций N=1002 Макс.среднее время 159,999 в столбцах 10-14 строках26-30 Наибольшее отклонение матрицы последней итерации от предпоследней = 0,000492066
peregoudov, Вы изменили формулу 1' на эквивалентную, это уже вопрос программистский кто на чем и в чем считает. Середина цикла моей итерации это начало цикла Вашей итерации, а действия в сумме за цикл одни и те же. Какие-то формулы видел в книгах, но кажется они сложнее для расчета. Если 1)я 2)за час,3)в экселе обсчитал реальную модель, то спец с программами будет их как орешки щелкать
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Среднее время встречи при случайном блуждании
А зачем итерации-то? Ведь решается линейная система уравнений. Ну вот, например, в моем варианте . Матрицы и разделим на столбцы и поставим их друг на друга. Вместо рассмотрим блочно-диагональную матрицу, на диагонали которой стоят матрицы с обнуленным 1-ым, 2-ым ... столбцом. Тогда, сохраняя буквенные обозначения для преобразованных матриц, получаем систему уравнений . И решаем ее каким-нибудь методом для ленточных матриц!
P. S. Я правильно понимаю, что у вас в примере в 7-вершинных кластерах переходы есть между любыми вершинами? Просто там линий не разберешь. С отдельно стоящими вершинами все понятно.
P. S. Я правильно понимаю, что у вас в примере в 7-вершинных кластерах переходы есть между любыми вершинами? Просто там линий не разберешь. С отдельно стоящими вершинами все понятно.
Среднее время встречи при случайном блуждании
Да , происхождение примера я не знаю, возможно робот-пылесос мечется по неочистимому кольцевому коридору, на котором три больших зала. А у двух роботов -пылесосов встреча наиболее отдалена, если они начинают из двух удаленных залов, проверил
Возможность решения формулой для каких-то графов очень будет кстати. Для линейного графа есть формула вроде очень сложная.
Возможность решения формулой для каких-то графов очень будет кстати. Для линейного графа есть формула вроде очень сложная.
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Среднее время встречи при случайном блуждании
Ну, я написал процедуру на Maple. Она довольно быстро считает без всяких оптимизаций с ленточными матрицами. Например, среднее число шагов для перехода 1->2 получается 108.711. Что-то многовато... Сам код для Maple под катом
Среднее время встречи при случайном блуждании
Слишком большое расхождение с моим, у меня 119. Сверим исходные данные;peregoudov писал(а): среднее число шагов для перехода 1->2 получается 108.711. Что-то многовато...
Ответы :М
Матрица средних времен первой встречи S
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Среднее время встречи при случайном блуждании
Нету расхождения. Просто у вас нумерация узлов с нуля, а у меня --- с единицы, ваш узел 0 у меня 31-й. Так что надо сравнивать ваш переход 2-3, а он как раз 109.
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 7 гостей