# Discrete Markov chain

Let $(A_n)$ be a discrete Markov chain with transition matrix $M$ and $B_n = A_{(mn)}$ where $m\in \mathbb N$, I want to show that $(B_n)$ is a Markov chain with transition matrix $M^m$.

Please help me refine my argument. I have a picture of what is going on, but I don't know how to argue in symbols/more rigorously.

$B_n = A_{(mn)}$ means that you need to jump $m$ steps for each 1 jump in $A_n$ hence $(B_n)$ has the $m$-th transition matrix $M^m$. (How do I show that I can use $M$ as the "base transition matrix"?) Then to show that $(B_n) = Markov(\lambda, M^m)$, would I have to show that $\mathbb P(B_{n+1}=i_{n+1}|B_0=i_0,...,B_n=i_n)=(M^m)_{i_ni_{n+1}}$, or does that follow from the fact that $(A_n)$ is Markov?

Thanks.

-
Do you know Kolmogorov-Chapman equation? Will be of help. The structure you described is called a skeleton. See e.g. Meyn and Tweedie, 'Markov Chains and Stochastic Stability', p.67-68 –  Ilya Oct 11 '11 at 11:31
@Gortaur: Thanks! –  Henry D. Oct 12 '11 at 8:23

Markov property for $(B_n)$ follows form the Markov property for $(A_n).$ To prove this write

$P(B_{n+1}=i_{n+1}|B_n=i_n,\ldots,B_0=i_0)=$

$=\sum\limits_{j_1,\ldots,j_{m-1}}P(A_{m(n+1)}=i_{n+1},A_{mn+m-1}=j_{m-1},\ldots,A_{mn+1}=j_1|A_{mn}=i_n,$

$A_{m(n-1)}=i_{n-1}\ldots,A_0=i_0)=$

$=\sum\limits_{j_1,\ldots,j_{m-1}}P(A_{m(n+1)}=i_{n+1}|A_{mn+m-1}=j_{m-1},\ldots,A_{mn+1}=j_1,A_{mn}=i_n,$

$A_{m(n-1)}=i_{n-1}\ldots,A_0=i_0)*P(A_{mn+m-1}=j_{m-1}|A_{mn+m-2}=j_{m-2}\ldots,A_{mn+1}=j_1,$

$A_{mn}=i_n,A_{m(n-1)}=i_{n-1}\ldots,A_0=i_0)*\ldots*P(A_{mn+1}=j_1| A_{mn}=i_n,$

$A_{m(n-1)}=i_{n-1}\ldots,A_0=i_0),$

where $j_1,\ldots,j_{m-1}$ take all possible values from the state space. Then use Markov property of $(A_n)$: $P(B_{n+1}=i_{n+1}|B_n=i_n,\ldots,B_0=i_0)=\sum\limits_{j_1,\ldots,j_{m-1}}M_{i_nj_1}M_{j_1j_2}\ldots M_{j_{m-1}i_{n+1}}=M^m_{i_ni_{n+1}}.$

-