Problem $2(30$ points$)$:

Consider a two$-$bit register. The register has four possible states: $00,01,10$ and $11.$ Initially, at time $t=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, the register is randomly manipulated as follows: with probability $\frac{1}{2},$ the register is left unchanged; with probability $\frac{1}{4},$ the two bits of the register are exchanged $(01$ becomes $10,10$ becomes $01,00$ becomes $00,$ and $11$ becomes $11)$; and with probability $\frac{1}{4},$ the left bit is flipped $($example: $10$ becomes $00).$ After the register has been manipulated in this fashion, the right bit is observed.

Suppose that on the first two time steps and $t=2),$ we observe the sequence $1,1.$ In other terms, the observed bit at time step $t=1$ is $1,$ and the observed bit at time step $t=2$ is also $1.$

Show how the register can be formulated with a temporal model $($a Hidden Markov Model$)$: What is the probability of transitioning from every state to every state? What is the probability of observing each output $(0$ or $1)$ in each state?

Use the forward algorithm $($filtering$)$ to determine the probability of being in each state at time $t$ after observing only the first $t$ bits, for $t=1,2.$

Use the forward$-$backward algorithm $($smoothing$)$ to determine the probability of being in each state at time $t=1$ given both observed bits.

Use the forward algorithm $($prediction$)$ to determine the probability of observing $1$ in the next time step $t=3.$