Hidden Markov Models and Viterbi Algorithm: Fair and Biased Die

269 Views Asked by At

So following is the problem that I am trying to solve using Viterbi algorithm and HMM:

enter image description here

Before attempting to write a program, I want to do this problem by hand for the first 3 observations($651$). Based on the question, I understand that:

$P(i | Fair) = \frac1{6} , 1\leq i \leq 6 $

$P( 6 | Biased ) = \frac5{10} = \frac1{2} $

$P( i | Biased ) = \frac1{10} , 1\leq i \leq 5 $

and the transition matrix is

$Fair$ $Biased$

$\begin{bmatrix} 0.95 & 0.05 \\ 0.1 & 0.9 \\ \end{bmatrix}$

but where should I go from here ?

EDIT: Assume that initially either fair or biased is equally likely($\frac1{2}$) from a "fictitious" state $O$.

I managed to compute the first 4 highest probabilities: $1 , 0.25 , \frac9{400}, \frac{81}{40000}$ corresponding to $O , B, B, B$

Is this right ?

1

There are 1 best solutions below

0
On BEST ANSWER

Your figures look like you're doing it right. I get the following, skipping the first fictitious state, which is probably not necessary.

Iteration $1$:

\begin{align} \nu_1(F) &= P(X_1\mid F)P(F) = P(6\mid F)P(F) = \dfrac{1}{6}\dfrac{1}{2} = \dfrac{1}{12} \\ & \\ \nu_1(B) &= P(X_1\mid B)P(B) = P(6\mid B)P(B) = \dfrac{1}{2}\dfrac{1}{2} = \dfrac{1}{4} \\ \end{align}

Iteration $2$:

\begin{align} \nu_2(F) &= P(5\mid F)\max\{\nu_1(F)P(F\mid F),\; \nu_1(B)P(F\mid B)\} = \dfrac{1}{6}\max\{\dfrac{1}{12}\cdot 0.95,\;\dfrac{1}{4}\cdot 0.1\} \\ &= \dfrac{1}{6}\dfrac{1}{12}\cdot 0.95 = \dfrac{19}{1440} \qquad\qquad [FF] & \\ \nu_2(B) &= P(5\mid B)\max\{\nu_1(F)P(B\mid F),\; \nu_1(B)P(B\mid B)\} = \dfrac{1}{10}\max\{\dfrac{1}{12}\cdot 0.05,\;\dfrac{1}{4}\cdot 0.9\} \\ &= \dfrac{1}{10}\dfrac{1}{4}\cdot 0.9 = \dfrac{9}{400} \qquad\qquad [BB] \end{align}

Iteration $3$:

\begin{align} \nu_3(F) &= P(1\mid F)\max\{\nu_2(F)P(F\mid F),\; \nu_2(B)P(F\mid B)\} = \dfrac{1}{6}\max\{\dfrac{19}{1440}\cdot 0.95,\;\dfrac{9}{400}\cdot 0.1\} \\ &= \dfrac{1}{6}\dfrac{19}{1440}\cdot 0.95 = 0.002089... \qquad\qquad [FFF] & \\ \nu_3(B) &= P(1\mid B)\max\{\nu_2(F)P(B\mid F),\; \nu_2(B)P(B\mid B)\} = \dfrac{1}{10}\max\{\dfrac{19}{1440}\cdot 0.05,\;\dfrac{9}{400}\cdot 0.9\} \\ &= \dfrac{1}{10}\dfrac{9}{400}\cdot 0.9 = \dfrac{81}{40000} = 0.002025 \qquad\qquad [BBB] \end{align}

So I get $[FFF]$ very slightly in front after $3$ iterations.