1
$\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$
  • $\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 '17 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 '17 at 14:20
  • 1
    $\begingroup$ Feller volume I, section XIV.3. $\endgroup$ – Did Aug 21 '17 at 16:57
  • $\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 '17 at 9:16
  • $\begingroup$ Adding an answer would be ok. $\endgroup$ – Did Aug 23 '17 at 10:26
1
$\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$

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.