随机游走先到达哪一端

答案是

$$\frac{b}{a+b}.$$

设停时刻 $T$ 为首次到达 $a$ 或 $-b$。对称随机游走的期望位置保持 0，因此

$$0=E[X_T]=a\cdot P(X_T=a)+(-b)\cdot P(X_T=-b).$$

解得 $P(X_T=a)=\frac{b}{a+b}$。

---

Original Explanation

$b/(a+b)$

Solution

Probability

Let us assume that we stop walking the moment we reach any of $a$ or $-b$. As we keep walking randomly, we'll eventually hit one of the two points, and the game will surely end.

Suppose $P_a$ is the probability that we end at $a$, and $(1 - P_a)$ is the probability that we end with $-b$.

Let $X$ be the position on the $x$-axis at the end of this game.

$E[X] = a \cdot P_a + (-b) \cdot (1 - P_a)$

Also note that the walk is symmetric (equal probability in either direction), so, logically, $E[X] = 0$

$0 = a \cdot P_a - b \cdot (1 - P_a)$

Solve to get $P_a = \dfrac{b}{a + b}$

---

Follow up Question

What is the expected number of steps to reach either $a$ or $-b$?

Follow up Solution

Warning: This solution uses the knowledge of Martingales and advanced stochastic theory.

In probability theory, a Martingale is a model of a fair game where knowledge of past events does not help to predict the mean of the future winnings, and where the expected value of the next play, given all the plays so far, is the same as the present value, even though the next play could have several possible outcomes.

Formally, the sequence $X_n$ is a Martinagle if:

${E} [X_{n+1}\mid X_{1},\ldots ,X_{n}]=X_{n}$

Since we're conducting a random walk, where each step can either be $+1$ (right) or $-1$ (left). This type of problem can be analyzed using a Martingale approach.

Let $X_1, X_2, X_3, \ldots$ be the position on the $x$-axis after $1,2,3\ldots$ steps.

Here $X_n$ is a Martingale because:

$E[X_{n+1} | X_n] = 0.5(X_{n} + 1) + 0.5(X_n - 1) = X_n$

In other words, given we are standing at position $X_n$, the expected value of the next step is the current value.

End Game: Let $N$ = the number of steps to reach any of $a$ or $-b$ starting from position $0$. We end the game when we reach either $a$ or $-b$.

$X_N$ is either $a$ or $-b$, with probability $P_a$ and $(1 - P_a)$ respectively.

Note that $E[X_N] = 0$ because we start from $0$, and all future expected values are equal to the position. This property can be used to find $P_a$

$0 = E[X_N] = a \cdot P_a - b \cdot (1 - P_a)\implies P_a = \dfrac{b}{a+b}$

We want to calculate $E[N]$, i.e. the number of steps taken to end the game.

Leap-of-faith: Consider the special variable $Y_n = (X^2_n - n)$, what's the expected value in the next step?

$E[Y_{n+1} | Y_n] = E[X^2_{n+1} - (n+1) | Y_n]$

$= 0.5 \cdot [(X_{n}+1)^2 - (n+1)] + 0.5 \cdot [(X_{n}-1)^2 -(n+1)]$

$= X^2_n-n = Y_n$

This satisfies the martingale property!

Hence, at the end of the game, the expected value is: $E[Y_N] =$ The current value of $(X^2_n - n) = 0^2 -0 = 0$ (because no moves have been made yet)

Now, we just expand $E[Y_N]$, and we can reach the result with a snap.

$0 = E[Y_N] = E[X_N^2-N]= E[X_N^2] - E[N]$

$\implies 0 = P_a \cdot a^2 + (1 - P_a) \cdot b^2 - E[N]$

$\implies E[N]=\dfrac{b \cdot a^2}{a+b} + \dfrac{a\cdot b^2}{a+b}$

$\implies E[N] = a\cdot b$

Hence it takes on average $(a\cdot b)$ steps to end the game

---

Notes

1. If we take $X_n = Z_1 + \cdots + Z_n$ where $Z_i$ takes either 1 or -1 with probability 0.5 each, then ${\displaystyle E[X_{n}^{2}]=\sum _{i=1}^{n}E[Z_{i}^{2}]+2\sum _{1\leq i<j\leq n}E[Z_{i}Z_{j}]=n.}$

2. $Y_n = (X^2_n - n)$ is a commonly used martingale. This can be used to show that the gambler's total gain or loss varies roughly between plus or minus the square root of the number of steps

3. We do not denote $E[X_n]$ as $E[X_n | X_0]$ because $X_0$ is not an unknown, it is always zero. But any new knowledge like $X_1 = 1$ can impact the expected value, i.e. $E[X_n | X_1=1] = X_1 = 1$

4. $X_n$ is our position after $n$ steps, while $X_N$ is our position at the end of the game.