Forward Algorithm

An exhaustive evaluation would involve computing for all possible execution sequences

the quantity

which sums the probability of observing what we do - note that the load here is exponential in T. Conversely, using the forward algorithm we can exploit knowledge of the previous time step to compute information about a new one - accordingly, the load will only be linear in T.