Цепи Маркова с дискретным временем

Цепь Маркова с дискретным временем представляет собой последовательность случайных состояний, развивающихся в целочисленном времени таким образом, что распределение следующего состояния зависит только от текущего состояния, а не от всей предшествующей истории.

Definition

Цепь Маркова с дискретным временем — это стохастический процесс на счётном пространстве состояний, индексированный неотрицательными целыми числами, у которого условное распределение следующего состояния, при условии всей предшествующей истории, зависит только от текущего состояния, что кодируется матрицей вероятностей одношаговых переходов.

Scope

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

Sub-topics

• Hidden Markov Models
• Markov Chain Classification and Recurrence
• Markov Chain Monte Carlo
• Stationary Distributions and Convergence

Core questions

• Что означает свойство Маркова и как оно выражается с помощью матрицы переходов?
• Как состояния классифицируются на возвратные, переходные и периодические классы?
• Когда цепь обладает единственным стационарным распределением и сходится к нему?
• Как быстро цепь приближается к равновесию и как это используется в моделировании?

Key theories

Свойство Маркова и уравнения Чепмена-Колмогорова

Будущее условно независимо от прошлого при условии настоящего, поэтому многошаговые вероятности перехода получаются путём умножения матриц переходов, что позволяет вычислить поведение за n шагов из одношаговой матрицы.

Эргодическая теорема для цепей Маркова

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

Clinical relevance

Цепи Маркова с дискретным временем моделируют случайные блуждания, снимки очередей, популяционную генетику, алгоритмы ранжирования, такие как PageRank, и переходы экономических состояний; их теория сходимости лежит в основе метода Монте-Карло на основе цепей Маркова, доминирующего вычислительного метода для выборки из сложных распределений вероятностей в статистике, физике и машинном обучении.

History

Андрей Марков ввёл цепи с зависимыми, но не имеющими памяти переходами в 1906 году, чтобы расширить закон больших чисел за пределы независимости, иллюстрируя их последовательностями букв в поэзии Пушкина. Колмогоров и Дёблин заложили строгие теоретико-мерные основы теории сходимости в 1930-х годах.

Key figures

• Andrey Markov
• Andrey Kolmogorov
• Wolfgang Doeblin

Seminal works

• norris1997

Frequently asked questions

Что делает процесс цепью Маркова?

Свойство Маркова: при заданном текущем состоянии будущее развитие не зависит от того, как цепь достигла этого состояния, поэтому вся динамика описывается одношаговыми вероятностями перехода.

Когда цепь Маркова сходится к единственному долгосрочному распределению?

Когда она неприводима, апериодична и положительно возвратна; тогда существует единственное стационарное распределение, к которому цепь сходится независимо от её начального состояния.