Assignment 2

Hidden Markov Coins

Out: October 5, 2021.
Alice has two coins that she can flip at any time. The two coins have distinct probabilities of showing Heads/Tails. Bob observes the outcomes of Alice's coin tosses but unfortunately he does not which coin Alice is tossing at any time (since both coins look alike). We assume Alice knows which coin is which at all times.

But Bob knows Alice's tendencies in choosing the coins. For example, suppose the coins are called coins X and Y, respectively. If Alice tosses coin X in the current step, then in the next step she will toss X again with probability 0.75 and will toss coin Y otherwise (with probability 0.25). On the other hand, if she tosses coin Y, she will choose to toss coin X in the next step with probability 0.9 and toss coin Y again with probability only 0.1. This can be represented as a probability transition matrix: 

0.75  0.9
0.25  0.1
where the first row and column is indexed by X and the second row/column is indexed by Y.

Bob also knows the "biases" of the two coins (although he can not tell them apart). For example, coin X shows Heads (H) or Tails (T) with probabilities 0.4 and 0.6, respectively. But coin Y shows Heads (H) with probability 0.8 and shows Tails (T) with probability 0.2. This can be represented as two sequences (or vectors): 

0.4  0.8
Note: we need only record the probabilities of showing Heads for each coin.

Now, suppose Bob observed a sequence of tosses, say: 

HTHTHHHHTHTTHTHTHHTHHHHTHHTHTHHTTTH
His goal is to determine how Alice had chosen her sequence of coins. Or rather find the sequence of choices made by Alice that is most likely. For example, 
XYXYXYXXXYXYXYYYYXYXYXYXYXYXYYYYXXX
is a particular sequence of choices that could have been made by Alice (but this might not be the most likely sequence).
Write a program that takes three input text files. The first file contains the probability transition matrix of Alice's tendencies. The second file contains the biases (probability of showing Heads) of the coins. The third file contains the sequence of outcomes from Alice's coin tosses.

The program should output a single text file containing the most likely sequence of coins that Alice had used in producing the outcome sequence of tosses.

For simplicity, use 1 to represent H and 0 to represent T. Also, use integers to represent the coins: say 0 for X and 1 for Y.

Note: Some examples of the input files can be found here.

Extensions (optional)

  1. Extend your program so it can handle more general output alphabets.
  2. Compute the probability of an observation sequence.
  3. Compute the most likely state at any step in the observation sequence.

What to Hand-in

Submit via email a single compressed file that contains your source file(s).

You may work in groups of three.