HMM, probability of a short state sequence starting at an arbitrary time? So, I'm going through some course literature on my own and don't have peers to discuss with.
The question is "How will you find the probability of a short state sequence starting at an arbitrary time given the full sequence of observation?"
I know that with the forward algorithm, we can compute the probability of seeing an observation sequence as well as the probability of states in at the last t. With the forward-backward, we can do that for any timepoint k given we have the full sequence of observations...
Viterbi can tell us the likelihood of a state sequence given a sequence of observations...
But, how would I get the probability for a subsequence of states..? Some sort of viterbi tweaking I guess?
 A: Let the state sequence be $x_1^T=(x_1,x_2,\ldots,x_T)$ and the observation sequence be $y_1^T=(y_1,y_2,\ldots,y_T)$. If we define the forward probabilities
\begin{align}
\alpha_t(x_t)=\mathbb{P}(Y_1^t=y_1^t, X_t=x_t)
\end{align}
and the backward probabilities
\begin{align}
\beta_t(x_t)=\mathbb{P}(Y_1^t=y_1^t | X_t=x_t)
\end{align}
then we have posterior
\begin{align}
\mathbb{P}(X_t=x_T|Y_1^t=y_1^T) = \frac{\alpha_t(x_t)\beta_t(x_t)}{\alpha_{T+1}(END)}.
\end{align}
Now, if we generalise these classical definitions by delayed forward probabilities
\begin{align}
\alpha_t^{(d)}(x_t)&=\mathbb{P}(Y_1^{t+d-1}=y_1^{t+d-1}, X_t^{t+d-1}=x_t^{t+d-1})\\
&= \alpha_t(x_t)\Biggl\{ \prod_{i=1}^{d-1} \mathbb{P}(x_{t+i}|x_{t+i-1})\mathbb{P}(y_{t+i}|x_{t+i}) \Biggr\}\\
&=\alpha_t(x_t)\gamma_{t+1,t+d-1}(x_{t+1}^{t+d-1})
\end{align}
and delayed backward probabilities
\begin{align}
\beta_t^{(d)}(x_t^{t+d-1})&=\mathbb{P}(Y_{t+d}^T=y_{t+d}^T | X_t^{t+d-1}=x_t^{t+d-1})\\
&= \beta_{t+d}(x_{t+d})
\end{align}
then we have delayed posterior
\begin{align}
\mathbb{P}(X_t^{t+d-1}=x_t^{t+d-1}|Y_1^T=y_1^T) &= \frac{\alpha^{(d)}_t(x_t^{t+d-1})\beta^{(d)}_t(x_t^{t+d-1})}{\alpha_{T+1}(END)}\\
&\propto \alpha_t(x_t)\gamma_{t+1,t+d-1}(x_{t+1}^{t+d-1})\beta_{t+d}(x_{t+d})
\end{align}
for any time $t\in\{1,2,\ldots,T-d+1\}$ and delay $d\in\{1,2,\ldots,T\}$. Set $d=2$ to answer your question on computing the probability of state sub-sequence $x_{t}^{t+1}$ given the observation sequence $y_1^T$.
You mentioned the Viterbi algorithm, so let me point out that $\gamma_{t+1,t+d-1}(x_{t+1}^{t+d-1})$ is the classical Viterbi path metric for the state sub-sequence. However, since we do not know the start state of the sub-sequence, $x_t$, nor the end state of the sub-sequence, $x_{t+d}$, we must use the forward and backward probabilities to weight each possible start and end state. The delayed Viterbi path metric is the numerator of the delayed posterior, namely
$$\alpha_t(x_t)\gamma_{t+1,t+d-1}(x_{t+1}^{t+d-1})\beta_{t+d}(x_{t+d}),$$
which is maximised over $x_t^{t+d}$ using the Viterbi algorithm to yield the maximum a posteriori sub-sequence estimate (MAP estimate).
