Let $M$ denote the Markov chain on states $\{0, 1, 2, ...\}$ with absorbing state $0$. For $i \geq 1$, let the transition probabilities be $p$ for $(i, i-1)$ and $1-p$ for $(i, i+1)$. Further, assume $p > 1/2$, thus, there is a drift towards $0$. I am interested in the mean absorbing/hitting time in state $0$, when started at state $n > 0$, denoted as $\mathbb{E}\{h(n)\}$. Due to the drift towards $0$, this should easily be determinable by using the linearity of the expectation on each single step?

More precise, the expected change ('increment') $\Delta$ on each single step of a walk that did not yet reach $0$, is $\mathbb{E(\Delta)} = (-1) \cdot p + 1 \cdot (1-p) = 1 - 2p < 0$. Thus, 'on average' we make progress $|1 - 2p|$ towards $0$ on each step, so we should hit $0$ after $h := \frac{n}{|1-2p|}$ many time steps, since $n + \mathbb{E}\{h \cdot \Delta\} = n + h \mathbb{E}\{\Delta\} = n - n = 0$. Thus, it should hold that $\mathbb{E}\{h(n)\} = h$.

I suppose that there is something wrong with this easy argument, since I fail to find a formal proof for it; I cannot adopt the hitting time definition to this. So my two questions are:

(1) Is this approach right or wrong, and how can $\mathbb{E}\{h(n)\}$ be determined correctly?

(2) If this argument is wrong, shouldn't it at least provide an upper bound on the hitting time?

Could somebody please help on this?


1 Answer 1



(1) Show that $\mathbb E(h(n))=n\mathbb E(h(1))$.

(2) Show that $\mathbb E(h(1))=1+(1-p)\mathbb E(h(2))$.

(3) Conclude that, indeed, $\mathbb E(h(n))=n/(2p-1)$ for every $n\geqslant1$.

  • $\begingroup$ Thank you very much for your hints! [Whoops, whenever I press <Return>, I already publish this comment? And there is no preview? Strange. Hold on, I am writing more...] $\endgroup$ Commented Oct 25, 2012 at 8:54
  • $\begingroup$ Further, this approach can even easily be extended to the case of a chain with alternating probabilities $p_1$, $p_2$, started at even $n$. (But for pattern periods $k$ greater than 2, the pendant of (2) runs into trouble then). The fundamental different way of thinking is, that this approach groups the random walks by their first visit of some nearer node (independently of the individual walk lengths so far), while my approach tried to deal with the expected progress of each random walk after each batch of exactly $k$ steps (here, $k=1$). Thanks a lot for your help! $\endgroup$ Commented Oct 25, 2012 at 9:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .