# Hidden Markov Model

###Hidden Markov Models### A Hidden Markov Model($N$,$\sum$,$\Theta$) consists of the following elements:

1.$N$ is a positive integer specifying the number of states in the model. Without loss of generality, we will take the $N$th state to be a special state, the final or stop state.

2.$\sum$ is a set of output symbols, for example $\sum={a,b}$

3.$\Theta$ is a vector of parameters. It contains three types of parameters:
$\pi j$ for $j=1\ldots N$ is the probability of choosing state $j$ as an initial state. Note that $\sum_{j=1}^N \pi j =1$

$a_{j,k}$ for $j=1\ldots (N-1),k=1\ldots N$

is the probability of transitioning from state j to state k. Note that for all j,

${\sum}_{k=1}^N a_{j,k} =1$

$b_j(o)$ for $j=1\ldots N-1$, and $o \in \sum$,

is the probability of emitting symbol $o$ from state j. Note that for all $j$,

${\sum}_{o\in \sum} b_j(o) =1$.

 Thus it can be seen that $\Theta$ is a vector of $N+(N-1)N+(N-1) \sum$ parameters.

An HMM specifies a probability for each possible $(x,y)$ pair, where x is a sequence of symbols drawn from $\sum$, and y is a sequence of states drawn from the integers $1\ldots N-1$. The sequences $x$ and $y$ are restricted to have the same length. As an example, say we have an HMM with $N=3, \sum{a,b}$, and with some choice of the parameters $\Theta$. Take $x = a,a,b,b$ and $y=1,2,2,1$. Then in this case,
$P(x,y|\Theta) = \pi_1 a_{1,2} a_{2,2} a_{2,1} a_{1,3} b_1(a) b_2(a) b_2(b) b_1(b)$

Thus we have a product of terms specifying the probability of emitting each symbol from its associated state.

In general, if we have the sequence $x$, and the sequence$y$,

 $P(x,y \Theta) = \pi_{y1} a_{y_n,N}\prod_{j=2}^{n}a_{y_{j-1,y_j}}\prod_{j=1}^{n}b_{y_j}(x_j)$

Thus we see that the probability is a simple function of the prameters $\Theta$.