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

share|improve this question

1 Answer 1

up vote 0 down vote accepted

Hints:

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

share|improve this answer
    
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...] –  cubic lettuce Oct 25 '12 at 8:54
    
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! –  cubic lettuce Oct 25 '12 at 9:30

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.