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) ] $$

  • $\begingroup$ sorry it was a typo :-) $\endgroup$ – QuantumLogarithm Mar 27 '13 at 10:18
  • 1
    $\begingroup$ I am confused - why did you accept the silly edit and then correcting the typo, rather than rejecting the willy edit then correcting the typo?... $\endgroup$ – user1729 Mar 27 '13 at 10:24
  • 1
    $\begingroup$ ? I accepted the edit but then I noticed that it contained a typo too, as it was written "bareer" instead of "barrier". $\endgroup$ – QuantumLogarithm Mar 27 '13 at 10:48
  • $\begingroup$ That wasn't a typo - the edit billed itself as "funny"! (I spent ages working out why the edit was being made, and then I realised...) $\endgroup$ – user1729 Mar 27 '13 at 10:52

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.


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.