Марковские цепи дискретного времени: свойства и вероятностные характеристики

Введение

Концепция вероятности: математические свойства дискретных цепей Маркова

В теории вероятностей дискретная цепь Маркова (DTMC) представляет собой последовательность случайных величин, известных как стохастический процесс, в которой значение следующей величины зависит только от значения текущей величины и не зависит от каких-либо предыдущих величин. Например, машина может находиться в двух состояниях: A и E. Когда она находится в состоянии A, существует вероятность 40% перейти в состояние E и 60% остаться в состоянии A. Когда она находится в состоянии E, существует вероятность 70% перейти в состояние A и 30% остаться в состоянии E. Последовательность состояний машины представляет собой цепь Маркова. Если мы обозначаем цепь как , то – это состояние, в котором машина начинается, а – случайная величина, описывающая ее состояние после 10 переходов. Процесс продолжается бесконечно, индексируясь натуральными числами. Примером стохастического процесса, который не является цепью Маркова, является модель машины, которая имеет состояния A и E и переходит в состояние A из любого состояния с вероятностью 50%, если она когда-либо посещала состояние A ранее, и с вероятностью 20%, если она никогда не посещала состояние A ранее (что оставляет вероятность 50% или 80% для перехода машины в состояние E). Это происходит потому, что поведение машины зависит от всей истории: если машина находится в состоянии E, вероятность перехода в состояние A может быть 50% или 20%, в зависимости от ее предыдущих значений. Следовательно, она не обладает свойством Маркова. Цепь Маркова может быть описана стохастической матрицей, которая перечисляет вероятности перехода из каждого состояния в любое другое состояние. На основе этой матрицы можно вычислить вероятность нахождения в определенном состоянии через n шагов. Пространство состояний цепи Маркова можно разделить на коммуникационные классы, которые описывают, какие состояния достижимы из других состояний (за один или несколько переходов). Каждое состояние можно охарактеризовать как преходящее или рекуррентное, в зависимости от вероятности того, что цепь когда-либо вернется в это состояние. Цепи Маркова могут обладать свойствами, такими как периодичность, обратимость и стационарность. Непрерывная цепь Маркова во времени аналогична дискретной цепи Маркова во времени, но переходит между состояниями непрерывно во времени, а не дискретными шагами. Другие стохастические процессы также могут удовлетворять свойству Маркова, которое заключается в том, что прошлое поведение не влияет на процесс, а только текущее состояние.

In probability, a discrete time Markov chain (DTMC) is a sequence of random variables, known as a stochastic process, in which the value of the next variable depends only on the value of the current variable, and not any variables in the past. For instance, a machine may have two states, A and E. When it is in state A, there is a 40% chance of it moving to state E and a 60% chance of it remaining in state A. When it is in state E, there is a 70% chance of it moving to A and a 30% chance of it staying in E. The sequence of states of the machine is a Markov chain. If we denote the chain by then is the state which the machine starts in and is the random variable describing its state after 10 transitions. The process continues forever, indexed by the natural numbers. An example of a stochastic process which is not a Markov chain is the model of a machine which has states A and E and moves to A from either state with 50% chance if it has ever visited A before, and 20% chance if it has never visited A before (leaving a 50% or 80% chance that the machine moves to E). This is because the behavior of the machine depends on the whole history—if the machine is in E, it may have a 50% or 20% chance of moving to A, depending on its past values. Hence, it does not have the Markov property. A Markov chain can be described by a stochastic matrix, which lists the probabilities of moving to each state from any individual state. From this matrix, the probability of being in a particular state n steps in the future can be calculated. A Markov chain's state space can be partitioned into communicating classes that describe which states are reachable from each other (in one transition or in many). Each state can be described as transient or recurrent, depending on the probability of the chain ever returning to that state. Markov chains can have properties including periodicity, reversibility and stationarity. A continuous time Markov chain is like a discrete time Markov chain, but it moves states continuously through time rather than as discrete time steps. Other stochastic processes can satisfy the Markov property, the property that past behavior does not affect the process, only the present state.

Стационарные распределения

Распределение является стационарным распределением цепи Маркова со стохастической матрицей тогда и только тогда, когда . Это можно записать следующим образом: в этом случае единственное такое распределение задается формулой , где – среднее время возврата в состояние i.