What does the Markov assumption say about the history of state sequences?

Question

Does the Markov assumption say that the conditional probability of the next state only depends on the current state or does it say that the conditional probability depends on a fixed finite number of previous states?

As far as I understand from the related Wikipedia article, the probability of the next state $s'$ to appear only depends on the current state $s$.

However, in the book "Artificial Intelligence: A Modern Approach" by Russell and Norvig, on page 568, they say: "Markov assumption — that the current state depends on only a finite fixed number of previous states".

To me, the second statement seems contradictory to the first, because it may mean that a state can depend on the history of states as long as the number is fixed a finite. For example, the current state depended on the last state and the state before the last state, which is 2 sequential previous states (a finite number of states).

Is Markov assumption and Markov property the same?

Answer 1

A stochastic process has the Markov property if the probability distribution of future states conditioned on both the present and past states depends only on the present state or, more formally, the following equality holds.

$$ p(s_{t+1} \mid s_{t}, s_{t-1:1}) = p(s_{t+1} \mid s_{t}), \forall t $$

The hidden Markov model (HMM) is an example of a model where the Markov property is often assumed to hold. In other words, the Markov assumption is made in the case of the HMM.

There are also the variable-order (or higher-order) Markov models, where the future state can depend on the previously $n$ states or, more formally, the following equality holds.

$$ p(s_{t+1} \mid s_{t}, s_{t-1:1}) = p(s_{t+1} \mid s_{t:t-n}), \forall t $$

In this context, a hidden Markov model is called a first-order Markov model ($n=0$). Therefore, there can also be second-order ($n=1$), third-order ($n=2$), etc., Markov models. In fact, there are also higher-order hidden Markov models.

To conclude, the expressions Markov property and Markov assumption are not exactly interchangeable. The Markov property is an attribute that a stochastic process can be assumed to possess. In that case, the Markov assumption is made. The expression Markov property usually refers to a first-order Markov property, but it can more generally refer to a higher-order Markov property.