3
$\begingroup$

Let $\{X_{n}\}$ be a Markov Chain on the state space $S=\{1,...,100\}$ with $X_{0}=30$, and transition probabilities given by $p_{1,1}=p_{100,100}=1$, $p_{99,100}=p_{99,98}=1/2$ and for $2\leq i\leq98$, $p_{i,i-1}=2/3$ and $p_{i,i+2}=1/3$. Let $T=\inf\{n\geq0:X_{n}=1\mbox{ or 100}\}$. How can we show that $\mathbb{P}(T<\infty)=1$, that is the chain will eventually get absorbed at 1 or 100 with probability 1.

3 Answers 3

4

It follows from the general theory of finite state space Markov chains that the chain must eventually leave the set of transient states. In your model, the boundary states 1 and 100 are recurrent. However, from any state in $\{2,3,\dots, 98,99\}$ it is possible to hit state 1, but it is not possible to return. It follows that these states are transient, and hence $\mathbb{P}(T<\infty)=1$.

3

In any Markov chain, any non-absorbing state from which an absorbing state is accessible is transient, and so with probability $1$ that state will only occur finitely many times. In a finite Markov chain, after all non-absorbing states have occurred for the last time the state must be an absorbing one.

1

See this link. What you want to do is re-order the names of the states so that the two absorbing states are the last two in your list.

After re-ordering, you can write down the canonical form of the transition matrix in block form, where the upper left will be all transitions between non-absorbing states, the upper right will be all transitions from non-absorbing to absorbing, the lower left will be zeros (since absorbing cannot go into non-absorbing), and the lower right will be the identity (absorbing states stay where they are).

The upper left block of this matrix tells you everything you want to know. If we call this block $Q$, then $N = (I-Q)^{-1}$ is a matrix that can directly tell you the expected number of steps to absorption when starting in any transient state (see the link above).

For your case, a helpful approach might be truncate the problem down to $S=\{1,2,...,10\}$ or something small like that. You might even be able to prove what the expected time to absorption is using induction on the number of elements in $S$.

Worst case scenario, you have to write a program that actually builds this 100x100 block matrix, computes $N$, and sums the expected times to absorption to illustrate that it's less than $\infty$. This can be done easily in NumPy, Matlab, Mathematica, Octave, and possibly also Maple.