Discrete-time Markov chain: Difference between revisions

Revision as of 21:55, 13 June 2024

Latest revision as of 10:19, 28 August 2025

(4 intermediate revisions by 4 users not shown)

Line 87:

==={{anchor|Transience}}{{anchor|Recurrence}}Transience and recurrence===

A state ''i'' is said to be transient if, given that we start in state ''i'', there is a non-zero probability that we will never return to ''i''. Formally, let the [[random variable]] ''T_i'' be the first return time to state ''i'' (the "[[hitting time]]"):

:<math> T_i = \inf \{ n\ge1: X_n = i\}.</math>

Line 159:

:<math>\pi_i \Pr(X_{n+1} = j \mid X_{n} = i) = \pi_j \Pr(X_{n+1} = i \mid X_{n} = j)</math>

for all times ''n'' and all states ''i'' and ''j''. This condition is known as the [[detailed balance]] condition (or local [[balance equation]]).

Considering a fixed arbitrary time ''n'' and using the shorthand

Line 185:

[[Kolmogorov's criterion]] gives a necessary and sufficient condition for a Markov chain to be reversible directly from the transition matrix probabilities. The criterion requires that the products of probabilities around every closed loop are the same in both directions around the loop.

Reversible Markov chains are common in [[Markov chain Monte Carlo]] (MCMC) approaches because the detailed balance equation for a desired distribution '''{{pi}}''' necessarily implies that the Markov chain has been constructed so that '''{{pi}}''' is a steady-state distribution. Even with time-inhomogeneous Markov chains, where multiple transition matrices are used, if each such transition matrix exhibits detailed balance with the desired '''{{pi}}''' distribution, this necessarily implies that '''{{pi}}''' is a steady-state distribution of the Markov chain.

==== Closest reversible Markov chain ====

For any time-homogeneous Markov chain given by a transition matrix <math>P \in \mathbb{R}^{n \times n}</math>, any norm <math>||\cdot ||</math> on <math> \mathbb{R}^{n \times n}</math> which is induced by a [[Inner product space |scalar product]], and any probability vector <math>\pi</math>, there exists a unique transition matrix <math>P^*</math> which is reversible according to <math>\pi</math>

and which is closest to <math>P</math> according to the norm <math>||\cdot ||.</math> The matrix <math>P^*</math> can be computed by solving a quadratic-convex [[optimization problem]].<ref>A. Nielsen, M. Weber. Online publication in Numerical Linear Algebra with Applications, DOI:10.1002/nla.1967, 2015.</ref>

For example, consider the following Markov chain:

Line 195:

This Markov chain is not reversible. According to the [[Matrix norm#Frobenius norm | Frobenius Norm ]] the closest reversible Markov chain according to <math>\pi = \left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)</math> can be computed as

[[File:Mchain simple corrected C1.png|frameless|center]]

If we choose the [[probability vector]] randomly as <math>\pi=\left( \frac{1}{4}, \frac{1}{4}, \frac{1}{2} \right)</math>, then the closest reversible Markov chain according to the Frobenius norm is approximately given by

[[File:Mvchain approx C2.png|400px|frameless|center]]

Line 218:

|archive-url= https://web.archive.org/web/20150319050311/https://books.google.com/books?id=JBBRiuxTN0QC&pg=PA35

|archive-date= 2015-03-19

|url-access= subscription

}}</ref> in which case the unique such distribution is given by <math>\pi_i=\frac{1}{M_i}</math> where <math>M_i=\mathbb{E}(T_i)</math> is the mean recurrence time of ''i''.<ref name="PRS"/>

Line 266 ⟶ 267:

* [[John G. Kemeny]] & [[J. Laurie Snell]] (1960) ''Finite Markov Chains'', D. van Nostrand Company {{ISBN|0-442-04328-7}}

* E. Nummelin. "General irreducible Markov chains and non-negative operators". Cambridge University Press, 1984, 2004. {{ISBN|0-521-60494-X}}

* [[Eugene Seneta|Seneta, E.]] ''Non-negative matrices and Markov chains''. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Originally published by Allen & Unwin Ltd., London, 1973) {{ISBN|978-0-387-29765-1}}

{{refend}}

[[zh-yue:離散時間馬可夫鏈]]