Can anyone give me a simple example of an irreductible (all elements communicate) and transient markov chain? I can't think of any such chain, yet it exists (but has to have an infinite number of elements) thanks

  • $\begingroup$ Think about random walks. $\endgroup$ – Hans Engler Nov 21 '12 at 23:36
  • $\begingroup$ But why is it transient? I would need to compute the probability of going back to origin but I don't know how $\endgroup$ – lezebulon Nov 21 '12 at 23:45

A standard example is asymmetric random walk on the integers: consider a Markov chain with state space $\mathbb{Z}$ and transition probability $p(x,x+1)=3/4$, $p(x,x-1)=1/4$. There are a number of ways to see this is transient; one is to note that it can be realized as $X_n = X_0 + \xi_1 + \dots + \xi_n$ where the $\xi_i$ are iid biased coin flips; then the strong law of large numbers says that $X_n/n \to E[\xi_i] = 1/2$ almost surely, so that in particular $X_n \to +\infty$ almost surely. This means it cannot revisit any state infinitely often.

Another example is simple random walk on $\mathbb{Z}^d$ for $d \ge 3$. Proving this is transient is a little more complicated but it should be found in most graduate probability texts.

  • $\begingroup$ Are there any examples that are funcamentally different than a biased walk on $\Bbb Z$ or a random walk on $\Bbb R^d\ , d\ge 3$? $\endgroup$ – John Cataldo Apr 13 at 8:22
  • $\begingroup$ @JohnCataldo: Sure... how about random walk on a binary tree? $\endgroup$ – Nate Eldredge Apr 14 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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