How is the law of total probability used here?

Question

Consider a Markov chain $\{X_n, n = 0, 1, \dots\}$.

The probability of going from one state $i$ to state $j$ in two steps is $p_{ij}^2 = P(X_2 = j | X_0 = i)$.

Then by the law of total probability we have:

$p_{ij}^2 = P(X_2 = j | X_0 = i) = \sum _{k \in S}P(X_2 = j | X_1 = k, X_0 = i) P (X_1 = k | X_0 = i)$.

How is $P(X_2 = j | X_0 = i) = \sum _{k \in S}P(X_2 = j | X_1 = k, X_0 = i) P (X_1 = k | X_0 = i)$ by the law of total probability?

The law of total probability says that if $\{B_i\}$ is a partition of the sample space $S$, then for any event $A$ we have $P(A) = \sum P(A \cap B_i) = \sum P(A | B_i)P(B_i)$.

I'm having trouble seeing how this is used here. Does anyone have an explanation?

Answer 1

Your first quote is not correct, so applying the total probability law as you started yields: $$\begin{align}P(X_2 = j | X_0 = i) &= \sum _{k \in S}P(X_2 = j | X_1 = k, X_0 = i) P (X_1 = k | X_0 = i)\\&=\sum_{k\in S} P(X_2=j|X_1=k)P(X_1=k|X_0=i)\\&=\sum_{k\in S} p_{ik}p_{kj}\end{align}$$

This corresponds to matrix multiplication, so you might be confusing $p_{ij}^2$ with $(P^2)_{ij}$, that is the $ij$-th entry of the squared transition matrix.

P.S. Assuming first order Markov chains as usual.

Answer 2

Since all of Kolmogorov's axioms hold when the probabilities are conditioned on an additional event $C$, everything that follows from the axioms also holds conditional on $C$. For example, the complement rule $P(A^c)=1-P(A)$ also holds conditional on $C$, that is, $P(A^c|C)=1-P(A|C)$. The same is true for the law of total probability so it follows that $P(A|C) = \sum P(A \cap B_i|C) = \sum P(A | B_i \cap C)P(B_i|C)$. $C$ corresponds to the event $X_0=i$ in your example.