Content deleted Content added
Re-Adding section "Closest reversible Markov chain" this got lost when discrecte Markov Chains where extracted from global Markov Chain article. It used to be there, see https://en.wikipedia.org/w/index.php?title=Markov_chain&oldid=689230061#Reversible_Markov_chain |
m Maximal set is a (now redirect) page about an unrelated concept in computability theory |
||
| (15 intermediate revisions by 11 users not shown) | |||
Line 13:
:<math>\Pr(X_{n+1}=x\mid X_1=x_1, X_2=x_2, \ldots, X_n=x_n) = \Pr(X_{n+1}=x\mid X_n=x_n),</math> if both [[conditional probability|conditional probabilities]] are well defined, that is, if <math>\Pr(X_1=x_1,\ldots,X_n=x_n)>0.</math>
The possible values of ''X''<sub>''i''</sub> form a [[countable set]] ''S'' called the state space of the chain.<ref name="PRS">{{cite book | title=Probability and Random Processes | first2=D. R. | last2=Stirzaker | first1=G. R. | last1=Grimmett | author-link=Geoffrey Grimmett | year=1992 |edition=second | publisher=Oxford University Press|
Markov chains are often described by a sequence of [[directed graph]]s, where the edges of graph ''n'' are labeled by the probabilities of going from one state at time ''n'' to the other states at time ''n'' + 1, <math>\Pr(X_{n+1}=x\mid X_n=x_n).</math> The same information is represented by the transition matrix from time ''n'' to time ''n'' + 1. However, Markov chains are frequently assumed to be time-homogeneous (see variations below), in which case the graph and matrix are independent of ''n'' and are thus not presented as sequences.
Line 75:
A state ''i'' is said to be essential or final if for all ''j'' such that ''i'' → ''j'' it is also true that ''j'' → ''i''. A state ''i'' is inessential if it is not essential.<ref>{{cite book|last=Asher Levin|first=David|title=Markov chains and mixing times|page=[https://archive.org/details/markovchainsmixi00levi_364/page/n31 16]|title-link= Markov Chains and Mixing Times |isbn=978-0-8218-4739-8|year=2009}}</ref> A state is final if and only if its communicating class is closed.
A Markov chain is said to be irreducible if its state space is a single communicating class; in other words, if it is possible to get to any state from any state.<ref name="PRS"/><ref name="
===Periodicity===
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<sub>i</sub>'' be the first return time to state ''i'' (the "[[hitting time]]"):
:<math> T_i = \inf \{ n\ge1: X_n = i\}.</math>
Line 107:
====Positive recurrence====
Even if the hitting time is finite with probability
:<math> M_i = E[T_i]=\sum_{n=1}^\infty n\cdot f_{ii}^{(n)}.</math>
Line 118:
:<math> p_{ii} = 1\text{ and }p_{ij} = 0\text{ for }i \not= j.</math>
If every state can reach an absorbing state, then the Markov chain is an [[absorbing Markov chain]].<ref name=
| first = Charles M.
| last = Grinstead
| first2 = J. Laurie
| last2 = Snell
| author-link2 = J. Laurie Snell
| title = Introduction to Probability
|date=July 1997
| publisher = American Mathematical Society
| isbn = 978-0-8218-0749-1
| chapter = Ch. 11: Markov Chains
| chapter-url = https://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf}}</ref><ref name=Kem>
{{cite book
| first = John G.
| last = Kemeny
| author-link = John G. Kemeny
| first2 = J. Laurie
| last2 = Snell
| author-link2 = J. Laurie Snell
| editor-first = F. W.
| editor-last = Gehring
| editor2-first = P. R.
| editor2-last = Halmos
| title = Finite Markov Chains
| url = https://archive.org/details/finitemarkovchai00keme_792
| url-access = limited
| edition = Second
| orig-year = 1960
|date=July 1976
| publisher = Springer-Verlag
| ___location = New York Berlin Heidelberg Tokyo
| isbn = 978-0-387-90192-3
| pages = [https://archive.org/details/finitemarkovchai00keme_792/page/n235 224]
| chapter = Ch. 3: Absorbing Markov Chains
}}</ref>
===Reversible Markov chain{{Anchor|detailed balance}}===
Line 125 ⟶ 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 151 ⟶ 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 161 ⟶ 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]]
==Stationary distributions==
A distribution <math>\pi</math> is a stationary distribution of the Markov chain with stochastic matrix <math>P</math> if and only if <math>\pi P = \pi</math>. This can be written as:<ref name="PRS"/>
:<math>\forall j\in \mathbb{S}: \sum_{i\in \mathbb{S}} \pi_i p_{ij} = \pi_j</math>.
This condition implies that <math>\pi P^n=\pi</math> and hence if the Markov chain <math>(X_n, n\in \mathbb{N})</math> has initial distribution <math>X_0 = \pi</math> then <math>X_n = \pi</math> (in distribution) for any <math>n\in\mathbb{N}</math>.<ref name="PRS"/>
Line 184 ⟶ 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"/>
If a chain has more than one closed communicating class, its stationary distributions will not be unique (consider any [[#
<math>\lim\nolimits_{n \rightarrow \infty} p_{jj}^{(n)} = \tfrac{C}{M_j}</math>
and for any other state ''i'', let ''f<sub>ij</sub>'' be the probability that the chain ever visits state ''j'' if it starts at ''i'',
Line 216 ⟶ 251:
==Ergodic theorem==
An instance of [[ergodic theory]], the ergodic theorem for states that for an irreducible aperiodic Markov chain,
:<math>p_{i,j}^{(n)}\rightarrow \frac{1}{M_j}</math> as <math>n\rightarrow \infty</math>.
==Notes==
Line 225 ⟶ 260:
{{refbegin}}
* A. A. Markov (1971). "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. ''Dynamic Probabilistic Systems, volume 1: Markov Chains''. John Wiley and Sons.
* {{cite journal |last = Markov |first = A. A. |year = 2006 |title = An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains |translator-first = David |translator-last = Link |journal = Science in Context |volume = 19 |issue = 4 |pages = 591–600 |doi = 10.1017/s0269889706001074 |
* Leo Breiman (1992) [1968] ''Probability''. Original edition published by Addison-Wesley; reprinted by [[Society for Industrial and Applied Mathematics]] {{ISBN|0-89871-296-3}}. (See Chapter 7)
* [[J. L. Doob]] (1953) ''Stochastic Processes''. New York: John Wiley and Sons {{ISBN|0-471-52369-0}}.
Line 232 ⟶ 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:離散時間馬可夫鏈]]
| |||