Question

Markov chain/Stochastic matrix:
I know for the regular one-step transition probabilities, \[\sum_{j=0}^{\infty}P_{i,j}=1\]. (Where \(P_{i,j}\) is the one=step transition probability \(P(X_1=j|X_0=i)\))

Can we say something similar for the n-step transitional probability, that \[\sum_{j=0}^{\infty}P^{(n)}_{i,j}=1\]?

Answer 1

Intuitively I don't see why not, but the n-step probabilities would be considerably more complicated because they would have to take into account all of the possible ways you could end up with j.

Answer 2

Yeah there is some intuition that tells me it should be true I tried some diff. examples (albeit with easy cases) for which it was true as well. I'm not quite sure how to prove it though :S

Answer 3

You could probably do it by induction, let's see...

Answer 4

^ I think I am getting somewhere with induction

Answer 5

Oh, duh. Of course. Here:

Answer 6

Assume it holds for (n-1).

The probability of going from i to j in n steps:
\[ P_{ij}^{(n)} = \sum_{l=0}^\infty P_{il}^{(n-1)} \cdot P_{lj} \]
So
\[\sum_{j=0}^\infty P_{ij}^{(n)} = \sum_{j=0}^\infty \sum_{l = 0}^\infty P_{il}^{(n-1)}\cdot P_{lj}\]
but j is independent of l, so
\[ = \sum_{l = 0}^\infty P_{il}^{(n-1)} \sum_{j=0}^\infty P_{lj} = \sum_{l = 0}^\infty P_{il}^{(n-1)} =1\]
due to our assumption and since
\[ \sum_{j=0}^\infty P_{lj} = 1\]

Answer 7

Oh very nice :)!! Thank you. I was on a similar path, but realized the independence of j and l much later, using a very long expansion. This is nice an concise :)

Answer 8

and concise*

Answer 9

Sure, no problem. Nice question, thanks.