Xrfgtjtk

I have seen the solution, but I would like to understand how it actually works.

A new variable is defined, $Z_n = (X_n, X_{n-1})$, this is kind of like the join probability of 2 consecutive steps; the smallest value of n in this case is 1. The proof proceeds as follows:

1. $P(Z_n = z_n|Z_{n-1}, Z_{n-2}...Z_1 = z_1)$




2. The above is equal to : $P(X_n = x_n, X_{n-1} = x_{n-1}|X_{n-1} = x_{n-1}, X_{n-2} = x_{n-2}...X_1 = x_1)$




3. Which is equal to: $P(X_n = x_n|X_{n-1} = x_{n-1})$




4. Which finally, is equal to : $P(Z_n=z_n|Z_{n-1} = z_{n-1})$

I'm struggling to understand how the RHS of the 2nd step came about, and also why the 3rd step automatically implies the last step is true.

Your help would be appreciated greatly, thanks in advance !

You can use the rule $P(AB|C) = P(A|BC)P(B|C)$ on step 2, where $A$ is the event $X_n=x_n$, $B$ is the event $X_{n-1}=x_{n-1}$, and $C$ is the event $X_{n-1}=x_{n-1}, ; ... ; X_1=x_1$. By the Markov property, you can see that $P(A|BC)$ will simply reduce to $P(A|B)$. Given the definition of $B$ and $C$, it is trivial to see why $P(B|C) = 1$. This will lead you from step 2 to step 3.

Let's expand step 4:

$P(Z_n=z_n|Z_{n-1}=z_{n-1})$

$=P(X_n=x_n, X_{n-1}=x_{n-1}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2})$

$=P(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-1}=x_{n-1},X_{n-2}=x_{n-2})$ (using $P(AB|C) = P(A|BC)P(B|C)$)

$=P(X_n=x_n|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2})$ (removing redundant term)

$=P(X_n=x_n|X_{n-1}=x_{n-1})$ (Markov property)