A Markov chain is a belief network with random variables in a sequence, where each variable only directly depends on its predecessor in the sequence. Markov chains are used to represent sequences of values, such as the sequence of states in a dynamic system or the sequence of words in a sentence. Each point in the sequence is called stage.

Figure 8.11 shows a generic Markov chain as a belief network. The network has 5 stages, but does not have to stop at stage $4$; it can extend indefinitely. The belief network conveys the independence assumption

which is called the Markov assumption.

Often the sequences are in time and, $S_t$ represents the state at time $t$. Intuitively, $S_t$ conveys all of the information about the history that could affect the future states. The independence assumption of the Markov chain can be seen as “the future is conditionally independent of the past given the present.”

A Markov chain is a stationary model or time-homogenous model if the variables all have the same domain, and the transition probabilities are the same for each stage, i.e.,

To specify a stationary Markov chain, two conditional probabilities are provided:

• •

  $P(S_0)$ specifies the initial conditions

• •

  $P(S_{i+1}\mid S_i)$ specifies the dynamics, which is the same for each $i\ge 0$.

Stationary Markov chains are of interest for the following reasons:

• •

  They provide a simple model that is easy to specify.

• •

  The assumption of stationarity is often the natural model, because the dynamics of the world typically does not change in time. If the dynamics does change in time, it is usually because of some other feature that could also be modeled.

• •

  The network extends indefinitely. Specifying a small number of parameters gives an infinite network. You can ask queries or make observations about any arbitrary points in the future or the past.

To determine the probability distribution of state $S_i$, variable elimination can be used to sum out the preceding variables. The variables after $S_i$ are irrelevant to the probability of $S_i$ and need not be considered. To compute $P(S_i\mid S_k)$, where $i>k$, only the variables between $S_i$ and $S_k$ need to be considered, and if , only the variables less than $k$ need to be considered.

A stationary distribution of a Markov chain is a distribution of the states such that if it holds at one time, it holds at the next time. Thus $P$ is a stationary distribution if for each state $s$, $P(S_{i+1}=s)=P(S_i=s)$. Thus,

A Markov chain is ergodic if, for any two states $s_1$ and $s_2$ in the domain of $S_i$, there is a non-zero probability of eventually reaching $s_2$ from $s_1$. A Markov chain is periodic with period $p$ if the difference between the times when it visits the same state is always divisible by $p$. For example, consider the Markov chain with states the integers 0 to 9, and at each time it either adds 1 or adds 9 (modulo 10), each with probability 0.5. This Markov chain is periodic with period 2; if it starts in an even state at time 0, it will be in an even state at even times, and in an odd state at odd times. If the only period of a Markov chain is a period of 1, then the Markov chain is aperiodic.

If a Markov chain is ergodic and aperiodic, then there is a unique stationary distribution, and this is the equilibrium distribution that will be approached from any starting state. Thus for any distribution over $S_0$, the distribution over $S_i$ will get closer and closer to the equilibrium distribution, as $i$ gets larger.