MATH 4431/ 6604 Probability Models Fall 2021
Prof. J Grigull
Assignment 4/ Nov 24
Solve all problems 1-5 (each problem is worth 10 points). Show your complete work: Solutions
without adequate accompanying work will receive no marks. Assignments must be submitted
on Crowdmark on the link provided in eClass.
Due date: Dec 3, 11:59PM
1) Given is a two-state Poisson-HMM with TPM
= �0.1 0.904 0.6�
and 1 = 1, 2 = 3, for state-dependent probability distributions:
( = | = )~()

Calculate the probability that the first three observations from this model are 0,2,1. (Assume initial
distribution 1 = 2 = 1 2� .) Apply the formula

(1 = 0,2 = 2,3 = 1) = (0)(2)(1),

where () = �−1 1! 00 −2 2
!� and bold symbols represent matrices/ vectors.

2) a) Given is the Poisson-HMMs with TPM
= �0.8 0.1 0.10.1 0.8 0.10.1 0.1 0.8�

and parameters for state-dependent Poisson-distributions: i) 1 = 10, 2 = 20,3 = 30
and ii) 1 = 15, 2 = 20, 3 = 25. Using the same sequence of random numbers (for
identical state sequences in i) and ii)) generate observation sequences of length 1000 for i)
and ii).
b) Use the Viterbi algorithm (Matlab) to infer the most likely sequence of states in each case:
Compare these two sequences to the true underlying sequence, i.e. the generated one.
c) What conclusion can you draw about the accuracy of the Viterbi algorithm?

In each of three rounds, one of two coins A or B that are outwardly indistinguishable is handed to us
blindfolded. In each round we toss the obtained coin 5 times and register the number of heads
obtained. Coins A and B are biased and land heads with probability = 0.8 and = 0.4, respectively.
The choice of coin handed to us blindfolded in any given round is governed by an (unobserved) Markov
chain over two states: In state 1, we receive coin A, in state 2 we receive coin B. The state transitions are
governed by the TPM
= � 0.8 0.20.25 0.75�
In state = 1 the number of observed heads over 5 tosses follows the (, 5) distribution, whereas
in state 2 this number follows the (, 5)distribution.
Suppose observed sequences over three rounds of coin tosses are given as i) = (5,2,4) and ii) =(0,4,1).

3) Calculate () for observation sequences in i) and ii).

4) Determine the Viterbi path ∗ = (1∗,2∗,3∗) for the observation in i).

5) Access and read the article “What is the expectation-maximisation algorithm” by Do & Batzoglou in
Nature Biotechnology (2008) vol. 26, 897-899 (discussed during lecture). Replace the record given in Fig.
1a by the following 5 series of 10 coin tosses each:
H H H T H T H H T H
T T H T H H T T H T
T H H H T T H H T T
T H H H T H H H H H
T H T T H T T T H H
Let and denote the (unknown) probability that coin A (B) turns Head, respectively. Starting with
initial estimates �
(0) = 0.6,�(0) = 0.5, apply the Expectation-Maximisation algorithm to the record