Problem 16.1 Medium Free 3 variations

Probability of Ever Reaching a Level

A particle performs a random walk on the integers, starting at $0$ . At each step, independently of the past, it moves up one unit with probability $p$ and down one unit with probability $1-p$ . Suppose $p = 1/3$ . Find the probability that the particle ever reaches position $1$ .

Work it out, then compare with the answer.

SolutionShow the worked solution

Write $q=1-p$ and let $h$ be the probability of ever reaching $1$ from $0$ . By translation invariance, $h$ is also the probability of ever climbing one level from any starting point.

The equation for $h$ . Condition on the first step.

With probability $p$ the particle moves to $1$ and has reached the level.
With probability $q$ it moves to $-1$ . To reach $1$ from there, it must first reach $0$ , which has probability $h$ . Once it is at $0$ , the strong Markov property says the future is a fresh walk, so it then reaches $1$ with probability $h$ , independently of the first climb.

Hence

h = p + q h^2, \qquad\text{that is}\qquad qh^2 - h + p = 0 .

Since $p+q=1$ , this factorises as $(h-1)(qh-p)=0$ . The roots are $1$ and $p/q$ .

Choosing the root. Let $h_n$ be the probability of reaching $1$ within $n$ steps, so that $h_0=0$ and $h_n\uparrow h$ . If the particle first steps down, reaching $1$ within $n+1$ steps requires climbing from $-1$ to $0$ within $n$ steps and then from $0$ to $1$ within $n$ steps. Therefore

h_{n+1}\le p+q h_n^2 .

Put $f(x)=p+qx^2$ and let $r\ge 0$ be any root of $f(x)=x$ . The function $f$ is increasing on $[0,\infty)$ . So if $h_n\le r$ , then $h_{n+1}\le f(h_n)\le f(r)=r$ . Since $h_0=0\le r$ , induction gives $h_n\le r$ for all $n$ , and hence $h\le r$ . Thus $h$ is the smallest non-negative root:

h=\min\!\left(1,\tfrac{p}{q}\right).

Here $p=\tfrac13$ , $q=\tfrac23$ . The roots are $1$ and $\tfrac12$ , so

\boxed{\tfrac12}

Key idea. One step down means two independent one-level climbs are needed to recover. The hitting probability is the smallest non-negative root of the resulting quadratic.

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 16.1a

A particle performs a random walk on the integers, starting at $0$ . At each step, independently of the past, it moves up one unit with probability $p$ and down one unit with probability $1-p$ . Suppose $p = 2/3$ . Find the probability that the particle ever reaches position $1$ .

Work it out, then compare with the answer.

Solution

The same argument gives $h=p+qh^2$ , with roots $1$ and $p/q=2$ . The probability $h$ cannot exceed $1$ , and it is the smallest non-negative root, so $h=1$ . The upward drift makes reaching level $1$ almost certain.

\boxed{1}

Variation 16.1b

A particle performs a random walk on the integers, starting at $0$ . At each step, independently of the past, it moves up one unit with probability $1/3$ and down one unit with probability $2/3$ . Find the probability that the particle ever reaches position $7$ .

Work it out, then compare with the answer.

Solution

To reach $7$ , the particle must reach $1$ , then $2$ from $1$ , and so on up to $7$ from $6$ . These are seven consecutive one-level climbs. By the strong Markov property they are independent, and each has probability $h=\tfrac12$ from the main problem. Hence

\boxed{\left(\tfrac12\right)^7=\tfrac1{128}}

Variation 16.1c

A particle performs a random walk on the integers. At each step, independently of the past, it moves up one unit with probability $1/3$ and down one unit with probability $2/3$ . Given that the particle is currently at position $4$ and that it will eventually reach position $7$ , find the probability that its very next step takes it to position $5$ .

Work it out, then compare with the answer.

Solution

From position $i$ , the probability of ever reaching $7$ is $h^{7-i}$ , where $h=\tfrac12$ .

Let $A$ be the event that the particle eventually reaches $7$ . Condition on the next step from $4$ :

\mathbb{P}(\text{up}\mid A)=\frac{p\,h^{2}}{h^{3}}=\frac{p}{h}=\frac{1/3}{1/2}.

As a check, $\mathbb{P}(\text{down}\mid A)=q h^4/h^3=qh=\tfrac13$ , and the two probabilities sum to $1$ . Conditioning on reaching the level swaps the step probabilities.

\boxed{\tfrac23}

Spotted an error? Email us