Вероятность достижения состояния

Сложность
Средний 50%

Вероятность достижения состояния

Вероятность достижения состояния и, в более широком смысле, время достижения состояния обозначает количество раз до достижения состояния цепи Маркова.

(ИКСнет)нет означает цепь маркова однородного конечного или счетного пространства состояний X матрицы перехода Q: мы можем интерпретировать Xнет как моделирование состояния системы в момент времени n.

Исходный закон цепи (Xнет) были зафиксированы, только состояния, которые могут быть достигнуты, вмешиваются в изучение эволюции цепи. Ставим Хв = {x ∈ X, существует n ⩾ 0, P(Xнет = х) > 0}.

Для состояния e ∈ Xв, обозначим T(нет)е время, за которое цепочка достигает состояния e строго через время n:

  • Т(нет)е поэтому обозначает наименьшее целое число k > 0 такое, что Xп+к = e, если строка проходит через e через время n
  • Т(нет)е = +∞, если цепь не проходит через состояние e через время n.
  • Для упрощения обозначений T(0)е также будет обозначаться просто Tе.

Пусть i, e ∈ Xв.

  • Для всех n ∈ N и k ∈ N* , вероятность достижения состояния e в момент времени n+k впервые после времени n, зная, что Xнет = i не зависит от n, обозначим его fто есть(к) = Р(Т(нет)е = к | Хнет = я). Он проверяет следующее уравнение: fто есть(1) = Q(i, e) и fто есть(к) = ∑j∈X\{e} Q(i,j)fя(k − 1) для всех k ≥ 2.

Уравнение для fто есть(k) просто переводит тот факт, что для того, чтобы впервые прийти в состояние e за k шагов, начиная с состояния i, необходимо перейти из состояния i в состояние j≠e, затем, начиная с j, прийти за первый время в e за k − 1 шагов.

  • Вероятность достижения состояния e через время n, зная, что Xнет = i не зависит от n, обозначим его fто естьто есть = Р(Т(нет)е < +∞|Хнет = я). Он проверяет: fто есть = Q(т.е.) + ∑j∈X\{e} Q(i,j)fя.

Уравнение для fто есть переводит тот факт, что цепочка достигает e из состояния i либо напрямую, либо переходит из состояния i в состояние j≠e, а затем достигает e из состояния j.

Обратите внимание, что фто есть=1 тогда и только тогда, когда fя=1 для любого состояния j≠e такого, что Q(i,j)>0.

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

вероятность достижения состояния

Пример вероятности достижения состояния

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

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

Напомним, что p обозначает вероятность того, что он выиграет игру и, следовательно, выиграет 1 евро, а 1−p — это вероятность того, что он проиграет игру и, следовательно, потеряет 1 евро.

Мы ищем вероятность того, что таким образом ему удастся получить 3 евро, т. е. f1,3. Уравнение с i=1 и e=3 записывается f1,3 = пф2,3 + (1 - р)f0,3. Мы0,3 = 0, так как игрок не может играть, если изначально у него нет денег (0 — поглощающее состояние). Осталось написать уравнение для f2,3 это вероятность того, что игроку удастся получить 3 евро, если у него на старте было 2 евро. Получаем: ф2,3 = 1 - р + (1 - р)f1,3. Таким образом, мы должны решить систему из 2 уравнений с 2 неизвестными: {f1,3 = пф2,3; ф2,3 = р + (1 - р)f1,3}.

Эта система имеет только одно решение — f2,3 =p/(1−p(1−p) и f1,3 =p²/1−p(1−p).

В частности, если игра честная, т. е. если p = 1/2, то1,3 = 1/3, что означает, что если у игрока изначально есть 1 евро, у него есть шанс один к трем получить 3 евро. Вероятность того, что игра остановится из-за того, что игрок разорился, вычисляется аналогично, записывая уравнения, которым удовлетворяет f1,0, ф2,0 и Ф3,0 и решение полученной системы. Этот расчет показывает, что f1,0 + ф1,3 = 1, что означает, что игрок обязательно остановится после конечного числа игр либо потому, что ему удалось получить 3 евро, либо потому, что он разорился.

Среднее время выхода из конфигурации

Помимо вероятности достижения состояния можно рассчитать среднее время достижения этого состояния.

Среднее время попадания — это наименьшее положительное решение системы:

вероятность достижения состояния

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

Пример среднего времени достижения

Здесь вероятность достижения состояния не рассчитывается. На самом деле вероятность достижения состояния и среднее время достижения состояния должны изучаться вместе.

Фишка прыгает по треугольнику с вероятностью 2/3 по часовой стрелке и 1/3 против часовой стрелки.

  • Вершины пронумерованы: 1,2,3.
  • Давайте посмотрим на время хитов. Начнем с вершины 1. Имеем
    для я = 1: х1=0
  • Для i = 2, 3 необходимо решить следующие системы:
    • Икс2=1+ 1/3x1 + 0x2+ 2/3x3
    • Икс3=1+ 2/3x1+ 1/3x2+ 0x3

Что дает в качестве решения вектор (0, 15/7, 12/7)

Делиться
ru_RURU