返回题库

对称随机游走

The expected time

专题
Probability / 概率
难度
L4

题目详情

概率题：对称随机游走：先到哪边与期望时间。

英文原题

What is the expected time for a symmetric random walk that starts at 0 to reach either aa or bb , where a<0<ba< 0< b are two integers? What is the probability that it will reach bb before aa ?

解析

设对称随机游走从 0 出发，吸收边界为整数 a<0<ba<0<b，令

T=inf⁡{n≥0:Wn∈{a,b}}.T=\inf\{n\ge 0: W_n\in\{a,b\}\}.

先到 bb 的概率：WnW_n 是鞅，对停时 TT 用可选停止，有

0=E[WT]=a P(WT=a)+b P(WT=b).0=\mathbb{E}[W_T]=a\,\mathbb{P}(W_T=a)+b\,\mathbb{P}(W_T=b).

解得

P(WT=b)=−ab−a,qquadP(WT=a)=bb−a.\boxed{\mathbb{P}(W_T=b)=\frac{-a}{b-a}},\\qquad \boxed{\mathbb{P}(W_T=a)=\frac{b}{b-a}}.

期望吸收时间：Mn=Wn2−nM_n=W_n^2-n 也是鞅，故

0=E[MT]=E[WT2]−E[T]⇒E[T]=E[WT2].0=\mathbb{E}[M_T]=\mathbb{E}[W_T^2]-\mathbb{E}[T]\Rightarrow \mathbb{E}[T]=\mathbb{E}[W_T^2].

代入 WT∈{a,b}W_T\in\{a,b\} 及上述概率，得

E[T]=−ab.\boxed{\mathbb{E}[T]=-ab}.

英文解析

T=inf⁡{n≥0:Wn∈{a,b}}.T=\inf\{n\ge 0: W_n\in\{a,b\}\}. 0=E[WT]=a P(WT=a)+b P(WT=b).0=\mathbb{E}[W_T]=a\,\mathbb{P}(W_T=a)+b\,\mathbb{P}(W_T=b). P(WT=b)=−ab−a,qquadP(WT=a)=bb−a.\boxed{\mathbb{P}(W_T=b)=\frac{-a}{b-a}},\\qquad \boxed{\mathbb{P}(W_T=a)=\frac{b}{b-a}}. 0=E[MT]=E[WT2]−E[T]⇒E[T]=E[WT2].0=\mathbb{E}[M_T]=\mathbb{E}[W_T^2]-\mathbb{E}[T]\Rightarrow \mathbb{E}[T]=\mathbb{E}[W_T^2]. E[T]=−ab.\boxed{\mathbb{E}[T]=-ab}.