Forward algorithm

Let's now formally define our problem for the forward algorithm. In the case of the forward algorithm, we are trying to compute the joint distribution of the position of the robot at any time instance using the output of the sensors till that time instance, as shown in the following diagram:

Forward algorithm: P(Z_k, X_1:k)

Figure 3.3: HMM showing two time slices, k-1 and k

To compute this probability distribution, we will try to split the joint distribution term into smaller known terms. As we will see, we can write a recursion formula over time for the distribution. We start by introducing a new variable, Z_k-1, in the distribution, P(Z_k, X_1:k), as follows:

The marginalization rule of probability is:

The product rule of probability is:

Here, we are basically using the marginalization rule of probability to introduce Z_k-1 and then summing its states....