Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was referring to this wiki article related to forward and backward algorithm

Actually, I didn't get this part $$ \frac{P(o_1,o_2..o_T,X_t=x_i|\pi)}{P(o_1,o_2..o_T|\pi)} = \frac{f_{0:t}(i)*b_{t:T}(i)}{\prod_{s=1}^{T}c_s} $$

where f denotes the forward algorithm and b denotes the backward algorithm. I didn't get how the probability became the factor of the two. I couldn't derive it. I tried to use chain rule of probability but somehow couldn't derive it. Any suggestions?

share|cite|improve this question
Here is a suggestion: make your post self-contained. Here is another one: show what you have done (for example, surely you replaced every factor in the RHS by its definition to see what was the result?). – Did Jul 10 '12 at 6:11
up vote 1 down vote accepted

Let $o_i^j=\{o_i,o_{i+1},\ldots,o_j\}$. By the chain rule for probability,

\begin{align*} \frac{P(o_1^T,X_t|\pi)}{P(o_1^T|\pi)}&=\frac{P(o_1^t,X_t|\pi)}{P(o_1^t|\pi)}\frac{P(o_{t+1}^T|\pi,o_1^t,X_t)}{P(o_{t+1}^T|\pi,o_1^t)}\\ &=\frac{P(o_1^t,X_t|\pi)}{P(o_1^t|\pi)}\frac{P(o_{t+1}^T|\pi,o_1^t,X_t)}{\sum_xP(X_t=x)P(o_{t+1}^T|\pi,o_1^t,X_t=x)}\\ &=\frac{P(o_1^t,X_t|\pi)}{P(o_1^t|\pi)}\frac{P(o_{t+1}^T|X_t)}{\sum_xP(X_t=x)P(o_{t+1}^T|\pi,X_t=x)}\\ &=\frac{P(o_1^t,X_t|\pi)}{P(o_1^t|\pi)}\frac{P(o_{t+1}^T|X_t)}{P(o_{t+1}^T|\pi)}\\ &=\frac{f_{0:t}(i)}{\prod_{s=1}^tc_s}\frac{b_{t:T}(i)}{\prod_{s=t+1}^Tc_s}, \end{align*} by definition. The third equality follows from the conditional independence of $o_{t+1}^T$ and $\{\pi,o_1^t\}$ given $X_t$.

share|cite|improve this answer
I didn't get it where the third equality came from, the conditional independence. As far as I know, the observations are independent if the corresponding state of the observations is given. If the state is not given, how can you assume that they are independent? – user34790 Jul 10 '12 at 16:02
@user34790 We have conditioning on the state $X_t$ above, which "links" the observations $o_1^t$ and $o_{t+1}^T$ (see figure). This property - that $X_t$ "blocks" any path from $o_1^t$ to $o_{t+1}^T$ - is formally known as d-separation and implies conditional independence (for general Bayesian networks) given the blocking random variable. For a more detailed exposition, see here. – sai Jul 10 '12 at 18:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.