question.md

This exercise develops a space-efficient variant of the forward–backward algorithm described in Figure forward-backward-algorithm (page forward-backward-algorithm). We wish to compute $\textbf{P} (\textbf{X}k|\textbf{e}{1:t})$ for $k=1,\ldots ,t$. This will be done with a divide-and-conquer approach.

1. Suppose, for simplicity, that $t$ is odd, and let the halfway point be $h=(t+1)/2$. Show that $\textbf{P} (\textbf{X}k|\textbf{e}{1:t}) $ can be computed for $k=1,\ldots ,h$ given just the initial forward message $\textbf{f}{1:0}$, the backward message $\textbf{b}{h+1:t}$, and the evidence $\textbf{e}_{1:h}$.
   

2. Show a similar result for the second half of the sequence.
   

3. Given the results of (a) and (b), a recursive divide-and-conquer algorithm can be constructed by first running forward along the sequence and then backward from the end, storing just the required messages at the middle and the ends. Then the algorithm is called on each half. Write out the algorithm in detail.
   

4. Compute the time and space complexity of the algorithm as a function of $t$, the length of the sequence. How does this change if we divide the input into more than two pieces?