4
$\begingroup$

I have a random walk process, discrete in time and state, where at each step the probability of $+1$ is $p$ and $−1$ is $q$. $p+q=1$ and $p$ may be different from $q$ (i.e. the random walk is "biased", "asymmetric", has "drift").

Starting from $x$, where $a<x<b$, I'd like to find the expected hitting time to hit either $a$ or $b$.

There's usually a nonzero probability of the random walk never hitting either boundary, which may imply difficulties getting an expectation. So a median of the hitting time distribution could be a useful alternative, if that can be expressed well.

My question seems related to other hitting time questions such as this on the time of first return and this on the distribution of the hitting time. However I'm rather unsure how to go to those helpful points to the expectation, and to the answer regarding hitting either boundary.

$\endgroup$
5
  • $\begingroup$ The expected hitting time $t_x$ starting from $x$ is finite for every $x$ and the collection $(t_x)$ for $a\leqslant x\leqslant b$ is the unique solution of the system $t_a=t_b=0$ and $$t_x=1+pt_{x+1}+qt_{x-1}$$ for every $a<x<b$. When $p=\frac12$, $$t_x=(b-x)(x-a)$$ For every $p\ne\frac12$, the explicit formula for $t_x$ involves powers of $$\frac{p}q$$ All this is explained in every first course on the subject and might even be explained on the WP page. $\endgroup$
    – Did
    Aug 20, 2017 at 20:08
  • $\begingroup$ @Did thanks - I've looked in a couple of textbooks (and WP of course) and found this treated but only for the unbiased case. So if you or anyone else can recommend an introductory text that includes the biased case directly worked through, I'd be grateful. $\endgroup$
    – Dan Stowell
    Aug 21, 2017 at 14:20
  • 2
    $\begingroup$ Feller volume I, section XIV.3. $\endgroup$
    – Did
    Aug 21, 2017 at 16:57
  • 1
    $\begingroup$ @Did this is perfect thanks. Feller "An introduction to probability theory and its applications" volume I, section XIV.3, has precisely the answer to this and is clearly written. (What should I do with this stackexchange question? Add an answer, or leave it as-is?) $\endgroup$
    – Dan Stowell
    Aug 23, 2017 at 9:16
  • $\begingroup$ Adding an answer would be ok. $\endgroup$
    – Did
    Aug 23, 2017 at 10:26

2 Answers 2

Reset to default
4
$\begingroup$

Thanks to @Did for pointing out the answer is given in the textbook by Feller "An introduction to probability theory and its applications" volume I, section XIV.3. It deals with this exactly and is clearly written, phrased in terms of the "classic ruin problem" (using the random walk as a model of a gambler). You can download the book from the Internet Archive here.

In Feller's terms, the walk starts at $z$ and the "box" is between $0$ and $a$. The expected time to reach either $0$ or $a$ is denoted $D_z$. $D_z$ can be shown to be finite as given later in the textbook.

The balanced case $p=q$ has to be handled separately, in which case $D_z = z(a-z)$. For $p\neq q$,

$$ D_z = \frac{z}{q-p} - \frac{a}{q-p} \frac{1-(q/p)^z}{1-(q/p)^a} \quad . $$

$\endgroup$
2
  • $\begingroup$ That link is no longer active. Would it be possible to outline the proof for getting this result? $\endgroup$
    – user1145925
    Sep 3, 2022 at 19:46
  • $\begingroup$ Also, do we know what is the probability of hitting either side: 0 vs. a? $\endgroup$
    – user1145925
    Sep 3, 2022 at 19:50
0
$\begingroup$

The above answer has a dead link, so I just include another reference here: Levin–Peres–Wilmer "Markov Chains and Mixing Times" (Second Edition), Section 2.5. This does't show exactly what the OP requests, but has highly related material and the OP's exact question can be derived from said material.

This link works at the moment, but if it goes dead, it should be easy to find online: the book is very popular, with over 4k citations as of writing this, and freely available online.

$\endgroup$

You must log in to answer this question.

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