HW9: Hidden Markov Models Solution

    • Stationary Distributions of Markov Chains

Alice decides that she wants to keep re-taking AI every semester for the rest of eternity (she really likes AI). We’re interested in modeling whether she passes the class or not as a Markov chain. Suppose that in semester t she passes the class; then in semester t + 1 she passes the class with probability 0:8 (maybe she gets bored and forgets to pay attention). On the other hand, if she doesn’t pass in semester t then she’ll pass with probability 0:4.

    1. Suppose that in semester t = 0 Alice passes the class with probability 0:5. Compute the probability that she passes in semester t = 1 and semester t = 2.

P (pt=1; pt=0) = 0:4

P (pt=1; ft=0) = 0:2

P (pt=1) = 0:6

P (pt=2; pt=1; pt=0) = 0:32

P (pt=2; pt=1; ft=0) = 0:16

P (pt=2; ft=1; pt=0) = 0:04

P (pt=2; ft=1; ft=0) = 0:12

P (pt=2) = 0:64

    2. Compute the stationary distribution of this chain. (Hint: the easiest way to do this is to start with some \guess" { say 50/50 { and then keep simulating the chain for a while until it seems to settle down. Once you think you’ve got a guess at what the stationary distribution might be, try transi-tioning from there to see if you get back to the stationary distribution.) (Not as helpful hint: if you like linear algebra, you can directly compute the stationary distribution from the transition matrix

using an eigenvalue decomposition: take a look at Wikipedia for how!)
P =
0:4
0:6







0:8
0:2






det(P   I) = 0 !  = 0:4; 1



Eigenvectors =
0:5
and

1


1


1























Therefore the stationary distribution is
0:5

0:5

    • Alice and the Crazy Coke Machine

Alice is up late studying for her algorithms nal exam and needs to stay hydrated (and ca einated!). Un-fortunately, Clarence was the one who bought the soda machine in the lab. He went for the cheapest model. All you can do with this soda machine is put money in and hope it gives you the type of drink you want. It carries three types of soda: Coke (C), Diet Coke (D) and Sprite (S).


1
Alice has been monitoring the soda machine for a while and has gured out that it behaves as an HMM. It has two internal states (call them A and B). When asked for a soda from state A, it gives a coke with probability 1/2, and a diet coke and a sprite each with probability 1/4. On the other hand, when asked for a soda in state B, it gives a diet coke with probability 1/2, a sprite with probability 1/3 and a coke with probability 1/6. Furthermore, it transitions from state A to A with probability 4/5 and from state B to B with probability 3/5.

The machine formally works as follows. It is in some state s. Someone puts in money and it dispenses a soda according to the probability rules set out above, being in state s. It then (randomly) transitions to a new state s0 according to the transition probabilities above.

1. Draw a state space lattice for this soda machine (as on the slides from HMM) for three time steps.

















    2. Suppose that Alice doesn’t know what state the machine is in currently (speci cally, she believes it’s equally likely to be in either state), but puts money in and gets a Sprite out. What is the probability distribution over states that it was in when Alice put her money in? What is the probability distri-bution over states that it is in now?

Initially:

P(A j S) = P(A) P(S j A) = (.5)(.25) = .125 ! 3/7 P(B j S) = P(B) P(S j B) = (.5)(.333) = .167 ! 4/7 After:

P(A) = P(A) P(A j A) + P(B) P(A j B) = (.5)(.8) + (.5)(.4) = 0.6 P(B) = P(B) P(B j B) + P(A) P(B j A) = (.5)(.6) + (.5)(.2) = 0.4

    3. Suppose Alice comes back the next day (so again she doesn’t know what state the machine is in) and really wants a diet coke. Unfortunately, the machine isn’t being particularly nice to her and it pro-duces the following series of emissions upon taking money from Alice: C S S D. What is the most likely sequence of states the machine went through in this process?

Soda 1:

m1(A) = P (CjA)P (A) = (:5)(:5) = :25

m1(B) = P (CjB)P (B) = (:167)(:5) = :083

Soda 2:
(P (AjA)m1

= (:25)maxx1
((:8)(:25)

m2(A) = P (SjA)maxx1

(A)


= (:25)(:8)(:25) = :05

P (A B)m1
(B)

(:4)(:083)

j


2

m2
(B) = P (SjB)maxx1

(P (BjA)m1
(A)
= (:333)maxx1
((:2)(:25)
= (:333)(:6)(:083) = :017



P (B B)m1
(B)



(:6)(:083)




j








Soda 3:
(P (AjA)m2



= (:25)maxx2

((:8)(:05)

m3
(A) = P (SjA)maxx2

(A)



= (:25)(:8)(:05) = :01



P (A B)m2
(B)



(:4)(:017)


(B) = P (SjB)maxx2

j






((:2)(:05)

m3


(P (BjA)m2
(A)
= (:333)maxx2

= (:333)(:6)(:017) = :0034



P (B B)m2
(B)



(:6)(:017)




j








Soda 4:

(P (AjA)m3


= (:25)maxx3
((:8)(:01)

m4
(A) = P (DjA)maxx3


(A)


= (:25)(:8)(:01) = :002



P (A B)m3
(B)



(:4)(:0034)


(B) = P (DjB)maxx3
j




((:2)(:01)

m3

(P (BjA)m3
(A)
= (:5)maxx3

= (:5)(:6)(:0034) = :00102



P (B B)m3
(B)



(:6)(:0034)

j

Therefore, the most likely sequence of states is: A, A, A, A








































3