Двумерная решетка (случайные блуждания)

[Oddy]

Здравствуйте,
помогите, пожалуйста, найти решение задачи: движение точки на плоскости описывается как случайное блуждание по двумерной решетке (вероятности переходов в соседние состояния - вверх, вниз, вправо, влево - равны 1/4). Надо найти в каждый момент времени вероятноть нахождения точки в каждом возможном состоянии (в условии n возможных состояний - узлов решетки). Причем при достижении границ точка отражается внутрь решетки.

Спасибо.

[G^a]

А Вы с цепями Маркова знакомы? Если да - то применяйте, если нет - то почитайте; и покажите свои первые шаги в решение задачи. А мы подскажем далее, если что.

[Oddy]

Да, про цепи Маркова я читала. Есть решение для одномерного блуждания, но в двумерном случае могут меняться обе координаты как цепи Маркова (это вызывает у меня трудности).
Вопрос: матрица переходов имеет размерность nxn (n - количество возможных состояний)?
Если я не ошиблась, то матрица вероятностей переходов для n=9(для общего случая nxn не выходит):

Вопрос: как происходит отражение в углах области? Я посчитала, что с вер-тью 1/2 осуществляется переход в соседнюю точку (2 варианта перехода). Забыла упомянуть, отражение от границы происходит с вер-тью 1, переходы по диагонали невозможны.
Вопрос: далее, чтобы узнать распределение вероятностей в каждый k-ый момент времени, нужно вычислить матрицу вероятностей переходов в степени k и умножить результат на вектор начальных вероятностей (nx1)?

[G^a]

Oddy писал(а):

Вопрос: матрица переходов имеет размерность nxn (n - количество возможных состояний)?

Да, это самый логичный вариант.

Oddy писал(а):

Если я не ошиблась, то матрица вероятностей переходов для n=9(для общего случая nxn не выходит):

Для порождения матрицы в случае произвольного $n$ можно использовать ленточное правило: записать матрицу построчно в виде одной строки. Если таким образом просмотрите варианты различных размерностей, должны будете увидеть закономерности. Подсказка: "ширина" и "длина" области Вам известны.

Oddy писал(а):

Вопрос: как происходит отражение в углах области? Я посчитала, что с вер-тью 1/2 осуществляется переход в соседнюю точку (2 варианта перехода). Забыла упомянуть, отражение от границы происходит с вер-тью 1, переходы по диагонали невозможны.

Правильно! Движение по диагонали у Вас запрещено условием задачи, следовательно: на углах - два разрешённых перехода, на линейной границе - три.

Oddy писал(а):

Вопрос: далее, чтобы узнать распределение вероятностей в каждый k-ый момент времени, нужно вычислить матрицу вероятностей переходов в степени k и умножить результат на вектор начальных вероятностей (nx1)?

Да! Ибо матрица переходов у Вас стационарна.

[Oddy]

G^a писал(а):

Движение по диагонали у Вас запрещено условием задачи, следовательно: на углах - два разрешённых перехода, на линейной границе - три.

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

[Macavity]

Извините, давно не решал такие задачи...

Я думаю, а нельзя ли рассмотреть независимо координаты x и y.
Предположим матрица 5*5, начальное положение центр.
Рассмотрим координату x -
вероятность того, что точка сдвинется влево 1/4, вправо - 1/4,
останется на месте (по x, то есть уйдет вверх или вниз) - 1/2.
В результате, для каждой координаты получим такого типа матрицу.

\left(\begin{array}{ccccc} 1/2&1/2&0&0&0\\ 1/4&1/2&1/4&0&0\\ 0&1/4&1/2&1/4&0\\ 0&0&1/4&1/2&1/4\\ 0&0&0&1/2&1/2\end{array} \right)

Дальше считается вероятность расположения точки по координате x в момент t и отдельно по координате y.
Оба вектора перемножаются в квадратную матрицу, с вероятностями уже в решетке (x,y).

Насколько это верно? Независимы ли события, можно ли так делать?

[G^a]

Oddy писал(а):

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

Всё зависит от того, имеет ли граница нулевую толщину, или нет. Это зависит от условия задачи, но в общем случае необходимо рассматривать и движение вдоль крайнего ряда ячеек тоже.

Macavity писал(а):

Я думаю, а нельзя ли рассмотреть независимо координаты x и y.
...
Насколько это верно? Независимы ли события, можно ли так делать?

В общем случае нет! Но в данной задаче (независимость вероятностей по x и по y) - подход работает.

[Someone]

Macavity писал(а):

Насколько это верно? Независимы ли события, можно ли так делать?

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

А при предложенном Oddy правиле отражения нужно исключить из рассмотрения угловые вершины, поскольку они недостижимы. Точнее, их, может быть, следует оставить, чтобы матрица была покрасивее (это может быть и удобнее), но вероятности нахождения в этих вершинах равны нулю после первого же шага.

[Oddy]

G^a писал(а):

Всё зависит от того, имеет ли граница нулевую толщину, или нет. Это зависит от условия задачи, но в общем случае необходимо рассматривать и движение вдоль крайнего ряда ячеек тоже.

Но если рассматривать возможность движения вдоль линейных границ (3 возможных направления движения), то чему равны вероятности переходов - 1/3?
Что означает "граница имеет нулевую толщину"?

Постановка Macavity предполагает возможность отстаться в текущем положении. Этот вариант тоже надо учитывать?

[Someone]

Oddy писал(а):

Постановка Macavity предполагает возможность отстаться в текущем положении. Этот вариант тоже надо учитывать?

Постановка Macavity преполагает не только возможность остаться на месте, но и возможность диагональных переходов. Она слишком не похожа на Вашу.

Слова "при достижении границ точка отражается внутрь решётки" можно понимать немного по-разному.

1) Как у Вас: граница проходит прямо по решётке; при достижении граничного узла следующим шагом частица с вероятностью 1 переходит во внутренний (не граничный) узел. В этом случае угловые узлы являются несущественными, частица может находиться в них только в начальный момент (её "положили туда руками"), а потом она из угла выходит и больше никогда туда не возвращается.

2) Представляем себе, что граница проходит от узлов сетки на расстоянии полушага. Из каждого узла частица может двинуться с вероятностью 1/4 в любую сторону. Если она натыкается (на полпути) на границу, она отражается назад и возвращается в ту точку, из которой вышла. В этом случае при шаге из углового узла частица с вероятностями 1/4 оказывается в одном из двух соседних узлов, а с вероятностью 1/2 возвращается в тот же узел. Для других граничных узлов частица с вероятностями 1/4 переходит в один из трёх соседних узлов, и с той же вероятностью возвращается в тот узел, из которого вышла.

Случаи 1) и 2) отличаются только вероятностями переходов из граничных точек.

В случае 1) цепь Маркова оказывается периодической: если раскрасить узлы в шахматном порядке в чёрный и белый цвета, то из чёрного узла частица может попасть только в белый, а из белого - только в чёрный. Из-за этого предельные вероятности будут разными для четных и для нечётных шагов.

В случае 2) цепь Маркова непериодическая, и предельные вероятности существуют в обычном смысле.

[Oddy]

Someone писал(а):

Постановка Macavity преполагает не только возможность остаться на месте, но и возможность диагональных переходов.

А если мне предложат ввести возможность диагональных переходов, это отразится только на матрице переходов (например, вер-ти переходов вверх, вниз, вправо, влево будут равны p, а вер-ти переходов по диагонали будут равны q, где 4*p+4*q=1)?

PS Тогда и углы будут достижимы - проверено расчетами.

[G^a]

Добречко!

Someone писал(а):

Слова "при достижении границ точка отражается внутрь решётки" можно понимать немного по-разному.

Да, Вы правы, и к указанным Вами двум вариантам, следует в том числе добавить и вариант с так называемой границей с нулевой толщиной.

Ведь

Oddy писал(а):

Причем при достижении границ точка отражается внутрь решетки.

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

При такой постановке, угловые узлы - достижимы.

На самом деле, вариантов отражений масса, для корректного решения задачи следует всё же доопределить понятия : граница и правило отражения. Тогда автоматически определяются понятия: внутренняя область и достижимые ячейки.

Macavity писал(а):

Насколько это верно? Независимы ли события, можно ли так делать?

Поправлюсь - нет, в постановке Oddy нельзя! Someone правильно указал на диагональные отражения, которые запрещены. Я этого к сожалению под конец рабочего дня уже на заметил.

[Oddy]

Пожалуйста, ответьте на этот вопрос:

Oddy писал(а):

А если мне предложат ввести возможность диагональных переходов, это отразится только на матрице переходов (например, вер-ти переходов вверх, вниз, вправо, влево будут равны p, а вер-ти переходов по диагонали будут равны q, где 4*p+4*q=1)?

Видимо, у меня случай с границей нулевой толщины:

[G^a]

Добрый день!

Oddy писал(а):

А если мне предложат ввести возможность диагональных переходов, это отразится только на матрице переходов (например, вер-ти переходов вверх, вниз, вправо, влево будут равны p, а вер-ти переходов по диагонали будут равны q, где 4*p+4*q=1)?

Давайте считать: Вашу клетку (текущее состояние) окружает в решётке с квадратными ячейками - 8 клеток: 4 граничат рёбрами, 4 - углами (диагональные). У вас за один шаг частица может переходить либо только к соседям, либо оставаться на месте, всего 9 возможных исходов на одном шаге эволюции системы. Вероятность должна быть нормирована на 1. Отсюда и считайте.

При учёте диагональных переходов необходимо помимо изменения матрицы переходов, доопределить правило отражения от угловых ячеек и и от линейной границы.

Oddy писал(а):

Видимо, у меня случай с границей нулевой толщины:

То, как Вы начертили, скорее смахивает на случай 1 по Someone. Ибо граница проходит непосредственно по внешним ячейкам, и они фактически недоступны частице. Граница нулевой толщины - она проходит сразу же за внешними ячейками, и они доступны частице, но в отличии от случая 2 по Someone - частица не может двинуться в направлении к внешней среде (т.е. переход в 1/2 шага - запрещен). Но зато частица может скользить по стенке.

У Вас это абстрактная задача (просто решётка и просто частица), или задача имеет некий физический смысл? Это важно, чтобы закрыть вопросы по правилам достижимости и отражения от линейных границ и узлов.

[Oddy]

G^a писал(а):

У Вас это абстрактная задача (просто решётка и просто частица), или задача имеет некий физический смысл?

Вообще-то у этой задачи есть физический смысл: точка - это небесное тело (или некое техническое средство - спутник), перемещающееся на плоскости (принятое допущение), которое при движении не выходит за известные границы. Область аппроксимируется прямоугольником. Требуется найти подвижный объект.
В той области знаний, в которой я работаю, для поиска цели прямоугольник, где она может находиться, разбивается на ячейки. Каждая ячейка - состояние координат цели, описываемое цепью Маркова.

Так как задача поиска вероятностная, я пытаюсь вычислить вер-ти обнаружения цели, движение которой описывается цепью Маркова, в каждой ячейке в любой момент времени.

Подозреваю, что все-таки надо учесть возможность перемещения по диагонали.