Editing Markov chain (section)

===Ergodicity===
A state ''i'' is said to be ''ergodic'' if it is aperiodic and positive recurrent. In other words, a state ''i'' is ergodic if it is recurrent, has a period of 1, and has finite mean recurrence time.

If all states in an irreducible Markov chain are ergodic, then the chain is said to be ergodic. Equivalently, there exists some integer <math>k</math> such that all entries of <math>M^k</math> are positive.

It can be shown that a finite state irreducible Markov chain is ergodic if it has an aperiodic state. More generally, a Markov chain is ergodic if there is a number ''N'' such that any state can be reached from any other state in any number of steps less or equal to a number ''N''. In case of a fully connected transition matrix, where all transitions have a non-zero probability, this condition is fulfilled with&nbsp;''N''&nbsp;=&nbsp;1.

A Markov chain with more than one state and just one out-going transition per state is either not irreducible or not aperiodic, hence cannot be ergodic.

==== Terminology ====
Some authors call any irreducible, positive recurrent Markov chains ergodic, even periodic ones.<ref>{{cite book |last1=Parzen |first1=Emanuel |title=Stochastic Processes |date=1962 |publisher=Holden-Day |isbn=0-8162-6664-6 |location=San Francisco |page=145}}</ref> In fact, merely irreducible Markov chains correspond to [[ergodicity|ergodic processes]], defined according to [[ergodic theory]].<ref name=":2" />

Some authors call a matrix ''primitive'' if there exists some integer <math>k</math> such that all entries of <math>M^k</math> are positive.<ref>{{Cite book |last=Seneta |first=E. (Eugene) |url=http://archive.org/details/nonnegativematri00esen_0 |title=Non-negative matrices; an introduction to theory and applications |date=1973 |publisher=New York, Wiley |others=Internet Archive |isbn=978-0-470-77605-6}}</ref> Some authors call it ''regular''.<ref>{{Cite web |date=2020-03-22 |title=10.3: Regular Markov Chains |url=https://math.libretexts.org/Bookshelves/Applied_Mathematics/Applied_Finite_Mathematics_(Sekhon_and_Bloom)/10%3A_Markov_Chains/10.03%3A_Regular_Markov_Chains |access-date=2024-02-01 |website=Mathematics LibreTexts |language=en}}</ref>

==== Index of primitivity ====
The ''index of primitivity'', or ''exponent'', of a regular matrix, is the smallest <math>k</math> such that all entries of <math>M^k</math> are positive. The exponent is purely a graph-theoretic property, since it depends only on whether each entry of <math>M</math> is zero or positive, and therefore can be found on a directed graph with <math>\mathrm{sign}(M)</math> as its adjacency matrix. 

There are several combinatorial results about the exponent when there are finitely many states. Let <math>n</math> be the number of states, then<ref>{{Cite book |last=Seneta |first=E. (Eugene) |url=http://archive.org/details/nonnegativematri00esen_0 |title=Non-negative matrices; an introduction to theory and applications |date=1973 |publisher=New York, Wiley |others=Internet Archive |isbn=978-0-470-77605-6 |chapter=2.4. Combinatorial properties}}</ref>

* The exponent is <math> \leq (n-1)^2 + 1 </math>. The only case where it is an equality is when the graph of <math>M</math> goes like <math>1 \to 2 \to \dots \to n \to 1 \text{ and } 2</math>.
* If <math>M</math> has <math>k \geq 1</math> diagonal entries, then its exponent is <math>\leq 2n-k-1</math>.
* If <math>\mathrm{sign}(M)</math> is symmetric, then <math>M^2</math> has positive diagonal entries, which by previous proposition means its exponent is <math>\leq 2n-2</math>.
* (Dulmage-Mendelsohn theorem) The exponent is <math>\leq n+s(n-2)</math> where <math>s</math> is the [[Girth (graph theory)|girth of the graph]]. It can be improved to <math>\leq (d+1)+s(d+1-2)</math>, where <math>d</math> is the [[Diameter (graph theory)|diameter of the graph]].<ref>{{Cite journal |last=Shen |first=Jian |date=1996-10-15 |title=An improvement of the Dulmage-Mendelsohn theorem |journal=Discrete Mathematics |volume=158 |issue=1 |pages=295–297 |doi=10.1016/0012-365X(95)00060-A |doi-access=free }}</ref>