I am presented with the following theorem in the context of Markov chains and stochastic systems:

The $n$-step transition matrix is the $n$th power of $\mathcal{P}$:

$$\mathcal{P}^{(n)} = P^n.$$

And the following proof is provided:

Proof: First, we show that $\mathcal{P}^{(n)} = \mathcal{P}\mathcal{P}^{(n - 1)}$. This is equivalent to showing

$$p_{ij}^{(n)} = \sum_{k \in S} p_{ik}p_{kj}^{n - 1}, \ \ \ (i, j) \in S. \tag{3}$$

The events $\{ X_1 = k \}$ with $k \in S$ partition the sample space. So if $n \ge 2$, then

$$\begin{align} p_{ij}^{(n)} &= \sum_k P(X_n = j, X_1 = k \vert X_0 = i) \\ &= \sum_k P(X_n = j \vert X_1 = k, X_0 = i) P(X_1 = k \vert X_0 = i) \\ &= \sum_k P(X_n = j \vert X_1 = k) p_{ik} \\ &= \sum_k p_{kj}^{(n - 1)} p_{ik}, \end{align}$$

Now (3) follows from the iterative argument below:

$$\mathcal{P}^{(n)} = \mathcal{P} \mathcal{P}^{(n - 1)} = \mathcal{P}(\mathcal{P} \mathcal{P}^{(n - 2)}) = \mathcal{P}^2\mathcal{P}^{(n - 2)} = \dots = \mathcal{P}^n \mathcal{P}^0 = \mathcal{P}^n$$

In going from $\sum_k P(X_n = j \vert X_1 = k, X_0 = i) P(X_1 = k \vert X_0 = i)$ to $\sum_k P(X_n = j \vert X_1 = k) p_{ik}$, why did the term $P(X_n = j \vert X_1 = k, X_0 = i)$ lose $X_0 = i$ to become $P(X_n = j \vert X_1 = k)$? I'm not sure what the reasoning is for the loss of the conditional dependence on $X_0 = i$.

I would greatly appreciate it if people would please take the time to clarify this.


1 Answer 1


I believe it has to do with the Markovian assumption. It is assumed that

$$P(X_n \mid X_{n-1}, \dots , X_0) = P(X_n \mid X_{n-1})$$

This is also true for larger lags

$$P(X_n \mid X_{n-k}, X_{n-k-1}, \dots, X_0) = P(X_n \mid X_{n-k})$$

  • $\begingroup$ I suspected it to have something to do with the Markovian assumption. Thanks for the answer. $\endgroup$ Commented Mar 15, 2020 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.