write . Because is conditionally independent of everything but , and is conditionally independent of everything but , this simplifies to . Thus, since and are given by the model's emission distributions and transition probabilities, one can quickly calculate from and avoid incurring exponential computation time. The initial condition is set as some prior probability over as such that Once the joint probability has been computed using the forward algorithm, we can easily obtain the related joint probability as and the required conditional probability as Once the conditional probability has been calculated, we can also find the point estimate of . For instance, the MAP estimate of is given by while the MMSE estimate of is given by The forward algorithm is easily modified to account for observations from variants of the hidden Markov model as well, such as the Markov jump linear system. Pseudocode Initialize , transition probabilities, , emission probabilities, , observed sequence, prior probability, For to . Calculate Return Example This example on observing possible states of weather from the observed condition of seaweed. We have observations of seaweed for three consecutive days as dry, damp, and soggy in order. The possible states of weather can be sunny, cloudy, or rainy. In total, there can be such weather sequences. Exploring all such possible state sequences is computationally very expensive. To reduce this complexity, Forward algorithm comes in handy, where the trick lies in using the conditional independence of the sequence steps to calculate partial probabilities, as shown in the above derivation. Hence, we can calculate the probabilities as the product of the appropriate observation/emission probability, ( probability of state seen at time t from previous observation) with the sum of probabilities of reaching that state at time t, calculated using transition probabilities. This reduces complexity of the problem from searching whole search space to just using previously computed 's and transition probabilities. Applications of the algorithm The forward algorithm is mostly used in applications that need us to determine the probability of being in a specific state when we know about the sequence of observations. We first calculate the probabilities over the states computed for the previous observation and use them for the current observations, and then extend it out for the next step using the transition probability table. The approach basically caches all the intermediate state probabilities so they are computed only once. This helps us