While studying about Forward Backward Algorithm, I came across the question below. I was unable to solve the question after trying for a lot of time.
Consider a two-bit register. The register has four possible states: 00, 01, 10 and 11. Initially, at time 0, the contents of the register is chosen at random to be one of these four states, each with equal probability. At each time step, beginning at time 1, the register is randomly manipulated as follows: with probability 0.5, the register is left unchanged; with probability 0.25, the two bits of the register are exchanged (e.g., 01 becomes 10); and with probability 0.25, the right bit is flipped (e.g., 01 becomes 00). After the register has been manipulated in this fashion, the left bit is observed. Suppose that on the first three time steps, we observe 0, 0, 1.
Q) Using the forward-backward algorithm to determine the probability of being in each state at time k given all three observed bits, for k=0,1,2,3.