Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.