Finite hidden Markov models for sequence decoding

A finite discrete hidden Markov model (HMM) is a tuple $(S,Y,\pi ,A,B)$, where $S$ is a finite nonempty hidden-state set, $Y$ is a finite nonempty observation alphabet, $\pi :S\to [0,1]$ is an initial probability distribution, $A:S\times S\to [0,1]$ is a transition matrix, and $B:S\times Y\to [0,1]$ is an emission matrix. The parameters satisfy ${\sum }_{s\in S}\pi (s)=1,{\sum }_{s^{\mathrm{\prime }}\in S}A(s,s^{\mathrm{\prime }})=1(s\in S),{\sum }_{y\in Y}B(s,y)=1(s\in S)\mathrm{.}$

For each length $T\ge 1$, hidden path $z=(z_1,\dots ,z_T)\in S^T$, and observation sequence $y=(y_1,\dots ,y_T)\in Y^T$, define the joint mass $p(z,y)=\pi (z_1)B(z_1,y_1){\prod }_{t=2}^{T}A(z_{t-1},z_t)B(z_t,y_t)\mathrm{.}$ The evidence of $y$ is $p(y)={\sum }_{z\in S^T}p(z,y)$. When $p(y)>0$, the conditional path mass is $p(z\mid y)=p(z,y)\mathrm{/}p(y)$, and a sequence MAP (maximum-a-posteriori) path is any $z$ maximizing this conditional mass. If $p(y)=0$, the conditional path mass is undefined, so there is no posterior sequence MAP path for that observation sequence. A zero transition or emission factor gives that hidden path zero joint mass.