Question 1a: What are the states of this hidden Markov model? What are the emitted symbols? What is the transition matrix?
States: $\pi = $
Symbols: $b = $
Transition matrix: $a = $
On some early mornings, the lizard people disperse mind control nanochips into the water supply. Whenever they disperse the nanochips, they do so again the following morning with probability 0.1. Whenever they don't disperse the nanochips, they disperse them the following morning with probability 0.3. When the water is contaminated, it appears slightly murky with probability 0.7 and it appears clean with probability 0.3. When the water does not contain nanochips, it appears slightly murky with probability 0.2 and it appears clean with probability 0.8.
Question 1b: What are the states? What is the transition matrix? What are the emitted symbols? Draw a picture of the hidden Markov model.
States: $\pi = $
Transition matrix: $a = $
Symbols: $b = $
Picture:
2) HMM Joint Probabilities
Question 2a: What are the joint probabilities of seeing the following state and symbol sequences from the HMM in Question 1a? Assume we start at state $\pi_1$ = 'happy'.
Question 2b: What is the joint probability of seeing the following state and symbol sequence from the HMM in Question 1b? Assume we start at state $\pi_1$ = 'dispersal' with probability 0.2 and $\pi_1$ = 'no dispersal' with probability 0.8.
tutorial8Q3.ipynb is a notebook which contains some unfinished functions based on Question 1b. The states and symbols are expressed as integers: state 0 has no dispersal, state 1 has dispersal, symbol 0 is clean water, symbol 1 is murky water.
Question 3a: Complete the function run_HMM(n,s) which will run the HMM $n$ times starting from state $s$. This function should return an array of $n$ symbols emitted according to the probabilities above.
Question 3b: Call your function run_HMM(n,s) starting at state 0, and run it for $n = 10^5$ turns. What proportion of the time is the water murky?
Question 3c: Complete the function run_HMM_k_times(k,n,s) which will call run_HMM(n,s) $k$ times and return a $k \times n$ matrix where every row in the matrix is a simulation..
Question 3d: Call your function run_HMM_k_times(k,n,s) starting at state 0 (no dispersal), for 4 steps. Do this $k=10^5$ times. What is the average number of days that you have murky water in this 4 day period?
Question 3e: Do the same again but this time start at state 1 (dispersal). What is the average number of days that you have murky water in this 4 day period?
4) Viterbi Algorithm
$A = $
ND
D
ND
-0.4
-1.2
D
-0.1
-2.3
$E =$
C
M
ND
-0.2
-1.6
D
-1.2
-0.4
We will perform the Viterbi algorithm to find the most probable state sequence from the HMM in Question 1b. This will be done in log space. The natural log of the transition and emission matrices are above.
We want to find $\pi * = \text{arg}\max\limits_\pi P(x, \pi)$. The initial state is dispersal (D) with probability 0.5 and no dispersal (ND) with probability 0.5 (log 0.5 = -0.7).
This is constructed using $V_l (i+1) = E_l(x_i+1) + \max\limits_k (V_k(i) + A_{kl})$.
Question 4: Complete the table below to find the most probable state path which generated the symbol sequence $x$ = (murky, murky, murky, clean, clean, clean, clean).
