偏置随机游走：最小初始资金使胜率 ≥ 1/2

Minimal Initial Point in a Stochastic Process

专题: Probability / 概率
难度: L6
来源: QuantQuestion

题目详情

考虑随机过程 $\{X_n\}$ ： $X_0=a$ ，且对 $n\ge 1$ 有

X_n=a+Z_1+\cdots+Z_n,

其中 $Z_i$ 独立同分布，且 $P(Z_i=1)=0.49$ ， $P(Z_i=-1)=0.51$ 。

令 $\tau_c$ 与 $\tau_0$ 分别为过程首次到达 $c$ 或 0 的时间。给定 $c=10000$ ，求最小的正整数 $a$ ，使得

\mathbb{P}(\tau_c<\tau_0)\ge \frac{1}{2}.

Consider a stochastic process $\{X_n\}$ where $X_0 = a$ and $X_n = a + Z_1 + Z_2 + \cdots + Z_n$ for $n \geq 1$ . The $Z_i$ are independent and identically distributed random variables, each taking a value of $1$ with probability $0.49$ and $-1$ with probability $0.51$ . Let $\tau_c$ and $\tau_0$ be the first times the process reaches $c$ or $0$ , respectively. Given $c = 10{,}000$ , determine the minimal positive integer $a$ such that the probability $\mathbb{P}(\tau_c < \tau_0)$ is at least $1/2$ .

解析

这是带偏置的赌徒破产（Gambler's Ruin）。设向上概率 $p=0.49$ 、向下概率 $q=0.51$ ，令 $r=\frac{q}{p}>1$ 。

当 $p\ne q$ 时，从 $a$ 出发先到 $c$ （而非 0）的概率为

\mathbb{P}(\tau_c<\tau_0)=\frac{r^a-1}{r^c-1}.

要求其 $\ge 1/2$ ，等价于

r^a\ge \frac{r^c+1}{2}.

由于 $c=10000$ 很大， $r^c\gg 1$ ，因此近似为 $r^a\gtrsim \frac{1}{2}r^c$ ，即

a\gtrsim c-\frac{\ln 2}{\ln r}.

这里 $r=0.51/0.49\approx 1.040816$ ， $\ln r\approx 0.04$ ，所以 $\frac{\ln 2}{\ln r}\approx 17.33$ 。

因此最小整数 $a=\boxed{9983}$ 。