# Is the Markov property assumed in the forward algorithm?

I'm majoring in pure linguistics (not computational), and I don't have any basic knowledge regarding computational science or mathematics. But I happen to take "Automatic Speech Recognition" course in my graduate school and struggling with it.

I have a question regarding getting the formula for a component of the forward algorithm.

$$\alpha_t(j) = \sum_{i=1}^{N} P(q_{t-1} = i, q_t=j, o_1^{t-1}, o^t|\lambda)$$

When $$q$$ is a hidden state, $$o$$ is a given observation, and $$\lambda$$ contains transition probability, emission probability and the start/end state.

Is the Markov assumption (the current state is only dependent upon the one right before it) assumed here? I thought so, because it contains $$q_{t-1}=i$$ and not $$q_{t-2}=k$$ or $$q_{t-3}=l$$.

In general, to formally state that the Markov property holds, you need to have $$P( x_t \mid x_{t-1:1}) = P(x_t \mid x_{t-1})$$.

So, you cannot conclude only from $$P(q_{t-1} = i, q_t=j, o_1^{t-1}, o^t|\lambda)$$ that the Markov property holds, because $$P(q_{t-1} = i, q_t=j, o_1^{t-1}, o^t|\lambda)$$ is the joint probability of $$q_{t-1} = i, q_t=j, o_1^{t-1}$$ and $$o^t$$ given $$\lambda$$.

Nonetheless, the theory of hidden Markov model often assumes that a few properties (including the Markov property) hold

1. the Markov property: $$P(q_{t+1} \mid q_{t}) = P(q_{t+1} \mid q_{t:1}),$$ where $$q_t$$ is the hidden state at time step $$t$$ and $$q_{t:1} = q_t, q_{t-1}, \dots, q_1$$.

2. the stationarity property: $$P(q_{t_1 + 1} \mid q_{t_1}) = P(q_{t_2 + 1} \mid q_{t_2}),$$ for any time step $$t_1$$ and $$t_2$$. In other words, the state transition probabilities are independent of the actual time at which the transitions takes place.

3. the output independence property: $$P(o^{T:1} \mid q_{T:1}) = \prod_{t=1}^T P(o^t \mid q_t , \lambda)$$ where $$o^{T:1} = o^T, o^{T-1}, \dots, o^1$$. In other words, this is the assumption that the output at time step $$t$$, $$o^t$$, is independent of the outputs at previous time steps.

• Oh, I think i should've put one more line for someone who's not familiar with the Forward Algorithm. Alphat(j)=P(o1,o2,...,oT-1,oT,qt=j|Lambda). Sorry that I don't know how to type mathematical symbols. – Jeeyoung Jeon Jun 17 at 0:18
• @JeeyoungJeon The forward algorithm (FA) is used in context of HMMs, so all the assumptions that are made in the context of HMMs also hold in the context of FA. – nbro Jun 17 at 0:21
• I edited my former comment, but I think I've found the answer from you already. Thanks! – Jeeyoung Jeon Jun 17 at 0:24