Expected hitting time of one of two barriers

Question

In the webpage "hitting time of one of two barriers", the probability that a non symmetric random walk hits one of two barriers is computed. The walker starts from $x=0$ and the barriers are located in $x=+n$ and $x=-n$. The walker can move one step on the right with probability $p$ and one step on the left with probability $q$.

The probability to hit one of the two barriers at time $n + 2k$ is:

$$ P_{hit}(n+2k) = \sum_{ - \lfloor k/n \rfloor }^{\lceil k/n \rceil} {(-1)}^r \binom{n + 2k - 1}{nr + k}( p ^n + q^n ) {(pq)}^k $$

How does the expected hitting time grow with the distance from the barrier and the initial point, $n$? Linearly? This means finding an expression for $E_{hit}(n)$, with

$$ E_{hit} = \sum_{t=0}^{\infty} t \cdot [ P_{hit}(t) ] $$

Answer 1

Calculating an expected value by first calculating the full probability distribution and then summing over it is usually far more complicated than calculating it directly using the linearity of expectation.

In the present case, the expected time $E_x$ to hit one of the barriers when starting at $x$ satisfies

$$ E_x=1+pE_{x+1}+(1-p)E_{x-1}\;. $$

A specific solution can be found using the linear ansatz $E_x=bx$, which yields

$$ bx=1+pb(x+1)+(1-p)b(x-1) $$

and thus $b=1/(1-2p)$. The characteristic equation for the homogeneous equation is

$$ p\lambda^2-\lambda+(1-p)=0\;, $$

with solutions $\lambda=1$ and $\lambda=(1-p)/p=:\mu$, and thus $E_x=a+bx+c\mu^x$. The calculation is simplified if we shift the boundaries to $x=0$ and $x=2n$. Then $E_0=0$ and $E_{2n}=0$ yields $a+c=0$ and

$$ \frac{2n}{1-2p}+c\left(\mu^{2n}-1\right)=0 $$

and thus

$$ E_x=\frac1{1-2p}\left(x-2n\frac{\mu^x-1}{\mu^{2n}-1}\right)\;. $$

In particular the expected hitting time from $x=n$ (corresponding to $x=0$ in the original formulation) is

$$ \begin{align} E_n &= \frac n{1-2p}\left(1-2\frac{\mu^n-1}{\mu^{2n}-1}\right) \\ &= \frac n{1-2p}\left(1-2\frac1{\mu^n+1}\right) \\ &= \frac n{1-2p}\frac{\mu^n-1}{\mu^n+1} \\ &= \frac n{p-q}\frac{p^n-q^n}{p^n+q^n} \;. \end{align} $$

Note that the special cases $E_n=n$ for $p=0$ and $p=1$ and $E_n=n^2$ for $p=1/2$ come out right.