A Markov model is given visual representation with a *state
diagram*, such as the one below.

**State Diagram for a Markov Model**

The rectangles in the diagram represent the possible states
of the process you are trying to model, and the arrows represent transitions
between states. The label on each arrow represents the probability
of that transition. At each step of the process, the model may generate
an output, or *emission*, depending on which
state it is in, and then make a transition to another state. An important
characteristic of Markov models is that the next state depends only
on the current state, and not on the history of transitions that lead
to the current state.

For example, for a sequence of coin tosses the two states are heads and tails. The most recent coin toss determines the current state of the model and each subsequent toss determines the transition to the next state. If the coin is fair, the transition probabilities are all 1/2. The emission might simply be the current state. In more complicated models, random processes at each state will generate emissions. You could, for example, roll a die to determine the emission at any step.

*Markov chains* are mathematical descriptions
of Markov models with a discrete set of states. Markov chains are
characterized by:

A set of states {1, 2, ...,

*M*}An

*M*-by-*M**transition matrix**T*whose*i*,*j*entry is the probability of a transition from state*i*to state*j*. The sum of the entries in each row of*T*must be 1, because this is the sum of the probabilities of making a transition from a given state to each of the other states.A set of possible outputs, or

*emissions*, {*s*_{1},*s*_{2}, ... ,*s*_{N}}. By default, the set of emissions is {1, 2, ... ,*N*}, where*N*is the number of possible emissions, but you can choose a different set of numbers or symbols.An

*M*-by-*N**emission matrix**E*whose*i*,*k*entry gives the probability of emitting symbol*s*_{k}given that the model is in state*i*.

Markov chains begin in an *initial
state* *i*_{0} at
step 0. The chain then transitions to state *i*_{1} with
probability $${T}_{1{i}_{1}}$$, and emits an output $${s}_{{k}_{1}}$$ with probability $${E}_{{i}_{1}{k}_{1}}$$. Consequently, the probability
of observing the sequence of states $${i}_{1}{i}_{2}\mathrm{...}{i}_{r}$$ and
the sequence of emissions $${s}_{{k}_{1}}{s}_{{k}_{2}}\mathrm{...}{s}_{{k}_{r}}$$ in
the first *r* steps, is

$${T}_{1{i}_{1}}{E}_{{i}_{1}{k}_{1}}{T}_{{i}_{1}{i}_{2}}{E}_{{i}_{2}{k}_{2}}\mathrm{...}{T}_{{i}_{r-1}{i}_{r}}{E}_{{i}_{r}k}$$

Was this topic helpful?