Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

### 6.5.1 Markov Chains

A **Markov chain** is a special sort of belief network used to
represent sequences of values, such as the sequence of states in a
dynamic system or the sequence of words in a sentence.

Figure 6.13 shows a generic Markov chain as a
belief network. The network does not have to
stop at stage *s _{4}*, but it can be extended indefinitely. The
belief network conveys the independence assumption

P(S_{t+1}|S_{0},...,S_{t})=P(S_{t+1}|S_{t}),

which is called the
**Markov assumption**.

Often, *S _{t}* represents the

**state**at time

*t*. Intuitively,

*S*conveys all of the information about the history that can affect the future states. At

_{t}*S*, you can see that "the future is conditionally independent of the past given the present."

_{t}A Markov chain is **stationary**
if the transition probabilities are the same for each time point [i.e.,
for all *t>0*, *t'>0*,
*P(S _{t+1}|S_{t})=P(S_{t'+1}|S_{t'})*].
To specify a stationary Markov chain, two conditional
probabilities must be specified:

*P(S*specifies initial conditions._{0})*P(S*specifies the dynamics, which is the same for each_{t+1}|S_{t})*t ≥ 0*.

Stationary Markov chains are of interest because

- 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 some other feature exists that could also be modeled.
- The network can extend indefinitely. Specifying a small number of parameters can give 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}*, VE can be used to sum out the preceding variables. Note that the
variables after

*S*are irrelevant to the probability of

_{i}*S*and need not be considered. This computation is normally specified as matrix multiplication, but note that matrix multiplication is a simple form of VE. Similarly, to compute

_{i}*P(S*, where

_{i}|S_{k})*k>i*, only the variables before

*S*need to be considered.

_{k}