# (Non)-homogeneity of Markov chain

Suppose we play a board game, where we roll the dice and step forward corresponding number of steps. Suppose there are $$m$$ squares on the board and first one to arrive on square $$m$$ wins.

A knee jerk reaction would be to say that there are $$m$$ states: $$1,\ldots, m$$ and $$\mathbb P (X_n = j \mid X_{n-1} = i) =: p_{ij}$$ that is the probability of getting to square $$j$$ assuming we started from $$i$$.

But this feels wrong, because if there are, say, $$5$$ squares and we toss heads or tails to decide whether we move forward one or two squares, then this probability $$p_{ij}$$ is not independent of $$n$$. In fact, the game can last at most $$4$$ turns, because we're always guaranteed to move ahead at least one square. Same thing with the dice roll.

The theory I've encountered restricts itself to the homogeneous case. Can we 'fictitiously' convert a non-homogeneous chain to one that does not depend on time or how would we analyse a non-homogeneous chain?

Please explain where I mess up.

The homogeneity condition states $$\mathbb P(X_{n+k} = j \mid X_{n+k-1} = i) = \mathbb P(X_{n} = j \mid X_{n-1} = i) \qquad (k\geq 0)$$ In the board game example with dice we would have $$\mathbb P(X_{2} = 5 \mid X_1 = 2) >0,$$ because we rolled $$1$$ on first turn and now we want to roll a $$3$$. This is fine, but now $$\mathbb P(X_{10} = 5 \mid X_9 = 2) =0,$$ because it's impossible to be on square $$2$$ on the $$9$$th turn in this particular game.

• The formalism forces you to augment the chain by making the state $m$ be absorbing, and to decide what to do when you overshoot. Then $p_{ij}$ is indeed independent of $n$ (it depends on $j-i$ and $m$). – Ian Sep 11 at 13:02
• @Ian I don't understand how it is independent of $n$. What is $p_{12}^{(1)}$ or $p_{12}^{(10)}$? The first one is $>0$, but on the 10th trial we're long gone from square $1$ so the probability must be $0$, doesn't it? Is there something I'm misunderstanding? Making $p_{mm} = 1$ doesn't seem to solve anything to me, we would have to assume this, anyway, since we can't have $p_{mi}>0$, where $i<m$. – Alvin Lepik Sep 11 at 13:10
• There are some mathematical events that the formalism will let you compute probabilities with but you will never actually see because they correspond to invalid states like $X_{10}=1$. But that doesn't hurt your ability to compute things. It is just an artifact of the procedure used to formalize the problem. – Ian Sep 11 at 13:26
• How is it not independent of $n$? Regardless of how you got to space $i$ or how many turns it took you to get there, you determine the next move in exactly the same way. You appear to be misinterpreting the Markov property as requiring that the actions taken as a result of the die roll’s outcome be the same for all states. – amd Sep 11 at 17:15
• @amd I'm prepared to tear my hair out one string at a time.. I just don't get it. I added some elaboration in the first post. Am I incorrectly choosing my state space or what gives? – Alvin Lepik Sep 11 at 18:33

I think where you’re going wrong is when you say that $$\Pr(X_{10}=5 \mid X_9=2)=0$$. Most definitions of the conditional probability $$\Pr(A \mid B)$$ require that $$\Pr(B)\gt0$$.† It’s possible to define it when $$\Pr(B)=0$$ (see here for example), but doing so is problematic.
A more complete statement of the time-homogeneity property is therefore that for all $$n$$, $$\Pr(X_{n+1}=x \mid X_n=y) = \Pr(X_n=x \mid X_{n-1}=y)$$ when both conditional probabilities are well-defined. The Markov property has the same caveat: if $$\Pr(X_1=x_1,\dots,X_n=x_n)=0$$, then we don’t care what $$\Pr(X_{n+1}=x_{n+1} \mid X_n=x_n)$$ is or if it’s even itself defined.
The upshot of this is that you can assign arbitrary transition probabilities to an impossible state/time combination (as long as they sum to $$1$$, of course). Since for this game they’re independent of time when the state is accessible, you might as well assign the same probabilities to the impossible combinations so as to end up with a time-homogeneous Markov chain. As Ian commented, this doesn’t hurt your ability to compute things. Remember, too, that some of those combination are only impossible if you assert the standard starting condition of $$X_1=1$$. When constructing the Markov chain, you have to allow for any value of $$X_1$$.
† This is akin to how, given $$p \implies q$$, we can’t say anything about the truth value of $$q$$ when $$p$$ is false.