Discrete-time Markov chain

• Time-homogeneous Markov chains (or stationary Markov chains) are processes where

${\displaystyle \Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)}$

for all n. The probability of the transition is independent of n.[1]

• A Markov chain with memory (or a Markov chain of order m)

where m is finite, is a process satisfying

${\displaystyle {\begin{aligned}{}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}}$

In other words, the future state depends on the past m states. It is possible to construct a chain ${\displaystyle (Y_{n})}$ from ${\displaystyle (X_{n})}$ which has the 'classical' Markov property by taking as state space the ordered m-tuples of X values, ie. ${\displaystyle Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)}$.

A state ${\displaystyle i}$ has period ${\displaystyle k}$ if any return to state ${\displaystyle i}$ must occur in multiples of ${\displaystyle k}$ time steps. Formally, the period of state ${\displaystyle i}$ is defined as

${\displaystyle k=\gcd\{n>0:\Pr(X_{n}=i\mid X_{0}=i)>0\}}$

(where ${\displaystyle \gcd }$ is the greatest common divisor) provided that this set is not empty. Otherwise the period is not defined.[1] Note that even though a state has period ${\displaystyle k}$, it may not be possible to reach the state in ${\displaystyle k}$ steps. For example, suppose it is possible to return to the state in ${\displaystyle \{6,~8,~10,~12,\dots \}}$ time steps; ${\displaystyle k}$ would be ${\displaystyle 2}$, even though ${\displaystyle 2}$ does not appear in this list.

If ${\displaystyle k=1}$, then the state is said to be aperiodic. Otherwise (${\displaystyle k>1}$), the state is said to be periodic with period ${\displaystyle k}$. Periodicity is a class property—that is, if a state has period ${\displaystyle k}$ then every state in its communicating class has period ${\displaystyle k}$.[1]

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"):

${\displaystyle T_{i}=\inf\{n\geq 1:X_{n}=i\}.}$

The number

${\displaystyle f_{ii}^{(n)}=\Pr(T_{i}=n\mid X_{0}=i)}$

is the probability that we return to state i for the first time after n steps. Therefore, state i is transient if

${\displaystyle \Pr(T_{i}<\infty \mid X_{0}=i)=\sum _{n=1}^{\infty }f_{ii}^{(n)}<1.}$

State i is recurrent (or persistent) if it is not transient. Recurrence and transience are class properties, that is, they either hold or do not hold equally for all members of a communicating class.[1]

A state i is recurrent if and only if the expected number of visits to i is infinite:[1]

${\displaystyle \sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .}$

Even if the hitting time is finite with probability 1, it need not have a finite expectation. The mean recurrence time at state i is the expected return time M_i:

${\displaystyle M_{i}=E[T_{i}]=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.}$

State i is positive recurrent (or non-null persistent) if M_i is finite; otherwise, state i is null recurrent (or null persistent). Positive and null recurrence are classes properties.[1]

A state i is called absorbing if it is impossible to leave this state. Therefore, the state i is absorbing if and only if

${\displaystyle p_{ii}=1{\text{ and }}p_{ij}=0{\text{ for }}i\not =j.}$

If every state can reach an absorbing state, then the Markov chain is an absorbing Markov chain.[3]

A Markov chain is said to be reversible if there is a probability distribution π over its states such that

${\displaystyle \pi _{i}\Pr(X_{n+1}=j\mid X_{n}=i)=\pi _{j}\Pr(X_{n+1}=i\mid X_{n}=j)}$

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

${\displaystyle p_{ij}=\Pr(X_{n+1}=j\mid X_{n}=i)\,,}$

the detailed balance equation can be written more compactly as

${\displaystyle \pi _{i}p_{ij}=\pi _{j}p_{ji}\,.}$[1]

The single time-step from n to n + 1 can be thought of as each person i having π_i dollars initially and paying each person j a fraction p_ij of it. The detailed balance condition states that upon each payment, the other person pays exactly the same amount of money back.[4] Clearly the total amount of money π each person has remains the same after the time-step, since every dollar spent is balanced by a corresponding dollar received. This can be shown more formally by the equality

${\displaystyle \sum _{i}\pi _{i}p_{ij}=\sum _{i}\pi _{j}p_{ji}=\pi _{j}\sum _{i}p_{ji}=\pi _{j}\,,}$

which essentially states that the total amount of money person j receives (including from himself) during the time-step equals the amount of money he pays others, which equals all the money he initially had because it was assumed that all money is spent (that is, p_ji sums to 1 over i). The assumption is a technical one, because the money not really used is simply thought of as being paid from person j to himself (that is, p_jj is not necessarily zero).

As n was arbitrary, this reasoning holds for any n, and therefore for reversible Markov chains π is always a steady-state distribution of Pr(X_n+1 = j | X_n = i) for every n.

If the Markov chain begins in the steady-state distribution, that is, if ${\displaystyle Pr(X_{0}=i)=\pi _{i}}$, then ${\displaystyle Pr(X_{n}=i)=\pi _{i}}$ for all ${\displaystyle n}$ and the detailed balance equation can be written as

${\displaystyle \Pr(X_{n}=i,X_{n+1}=j)=\Pr(X_{n+1}=i,X_{n}=j)\,.}$

The left- and right-hand sides of this last equation are identical except for a reversing of the time indices n and n + 1.

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 π necessarily implies that the Markov chain has been constructed so that π 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 π distribution, this necessarily implies that π is a steady-state distribution of the Markov chain.

A Markov chain need not necessarily be time-homogeneous to have an equilibrium distribution. If there is a probability distribution over states ${\displaystyle {\boldsymbol {\pi }}}$ such that

${\displaystyle \pi _{j}=\sum _{i\in S}\pi _{i}\,\Pr(X_{n+1}=j\mid X_{n}=i)}$

for every state j and every time n then ${\displaystyle {\boldsymbol {\pi }}}$ is an equilibrium distribution of the Markov chain. Such can occur in Markov chain Monte Carlo (MCMC) methods in situations where a number of different transition matrices are used, because each is efficient for a particular kind of mixing, but each matrix respects a shared equilibrium distribution.

For a subset of states A ⊆ S, the vector k^A of hitting times (where element ${\displaystyle k_{i}^{A}}$ represents the expected value, starting in state i that the chain enters one of the states in the set A) is the minimal non-negative solution to[6]

${\displaystyle {\begin{aligned}k_{i}^{A}=0&{\text{ for }}i\in A\\-\sum _{j\in S}q_{ij}k_{j}^{A}=1&{\text{ for }}i\notin A.\end{aligned}}}$