0
$\begingroup$

The walk on the 1D Lattice with no barriers can be illustrated where a walker starts at zero (0) on the number line and a fair coin is flipped. If it lands on heads, the walker moves one (1) unit to the right. If it lands on tails, the marker is moved one (1) unit to the left.

Unlike the random walk on the 1D lattice where the walk can be extended to infinity at either end of the number line, the random walk with barriers ends when the walker runs into either barrier on each side of the number line.

If the walker starts at zero and walks until either the barrier at A or the barrier at B is hit, what is the probability of hitting the barrier at A and the probability of hitting the barrier at B? Find a formula generalizing this probability.

  • 2
    you should read about gambler's ruin2012-03-01

2 Answers 2

3

There are lots of ways to do this depending on what you know. If you know/believe such a random walk is a martingale, then you can use the optional stopping theorem, which in this case says the expected value of your random walk the first time it hits either $A$ or $B$ is equal to your starting location. Letting $P_B$ be the probability that the random walk hits $B$ first, this yields

$P_B B+(1-P_B) A=0.$

Solving for $P_B$, we get $P_B=\frac{-A}{B-A}$.

Another way of doing this that doesn't require much background is to observe that if $f(n)$ (for integers $A\leq n \leq B$) is the probability starting at $n$ that you hit $B$ before you hit $A$, then we have $f(A)=0$, $f(B)=1$, and for $A $f(m)=1/2f(m-1)+1/2f(m+1).$ If $g$ were another functions satisfying these three conditions, then $h=f-g$ would be a function with $h(A)=0$, $h(B)=0$, and $h(m)=1/2h(m-1)+1/2h(m+1).$ If the maximum $M$ of $h$ occurred at $m_0$, then we would have $M=1/2h(m_0-1)+1/2h(m_0+1)$ and since $M$ is the maximum value, we conclude $h(m_0-1)=h(m_0+1)=M$. Continuing this procedure we can see that $h$ is a constant (and therefore everywhere $0$ since $h(A)=0$) and thus there is a unique function satisfying the three conditions $f$ satisfies (this is a simple example of a maximal principle).

It is easy to see that the line that is $0$ at $A$, $1$ at $B$ and has slope $\frac{1}{B-A}$ satisfies these three conditions, so we conclude that $f$ is this line (and in particular $f(0)=\frac{-A}{B-A}$).

1

Hints:

  1. Work out the probability if $A=-1$ and $B=1$: you will find this is $\frac{1}{2}$.
  2. Work out the probability if $A=-1$ and $B=2$: slightly harder.
  3. Work out the probability if $A=-2$ and $B=1$: you may already see this from (2).
  4. Spot the pattern and develop a hypothesis for more general $A$ and $B$.
  5. Prove the hypothesis.