Exercise $1.$ The Viterbi Algorithm: A Problem in Dynamic Procramming:

Note there is helper code for this problem on Brightspace. This topic is not tested on the final eram, but you

do need to complete it for the homework.

Consider the state space model above. The $x_t$ values are the unobserved, noise$-$free states and the $Y_t$ values

are the obeerved, noisy states. The state indicates the direction, where $0$ is left and $1$ is right. This is maybe

more obvious by transforming $x_t$ into $D_t=2(x_t-\frac{1}{2}).$ Notice that $D_{t}in\{-1,1\}$ corresponds to "left" and

"right" on the $x-$axis. The path $\{P_t{\}}_t=0^T$ can be computed from the states, $P_t={\displaystyle \underset{t^{\text{'}}=0}{\overset{t}{}}}2(x{t}^{\text{'}}-\frac{1}{2})={\displaystyle \underset{t^{\text{'}}=0}{\overset{t}{}}}{D}_{t^{\text{'}}}.$

In Homework $4,$ we predicted the nolse$-$free path $x_t$ from noisy observations $Y_{0\text{:}t}.$ In Homework $5,$ we

predicted the noise$-$free path $x_t$ from all the noisy observations $Y_{0\text{:}T}.$ We noticed that neither strategy was

very good. We noted the most likely sequence of states is different from the most likely individual state. The

Viberbi algorithm is a method to predict the most likely sequence of states.

$($a$)$ When is the following true?

$argma{x}_{x_{0,T}}P(x_0=x_0,$dots,$x_T=x_T|Y_{0,T})=argma{x}_{x_{0,T}}pro{d}_t=0^{T}P(x_t=x_t|Y_{0.T})$

$($b$)$ Briefly argue $($with words or math$)$ that $ma{x}_{a,b}\{f(a)g(a,b)\}=ma{x}_a\{f(a)ma{x}_{b}g(a,b)\}$ when $f(a)0$

and $g(a,b)0.$