绿皮书题目整理：随机过程与随机微积分

马尔可夫链#

• 常返态 (recurrent)：从该点出发可以到达每一个点，且从每一个点出发可以回到该点
• 瞬态（transient）：不是常返态的点
• 吸收马尔可夫链（absorbing markov chain）：如果链中存在一个点只能回到自身

[!note] 连续出现的平均次数 独立重复实验，每次实验某个结果出现的概率是 $p$，那么连续出现 $k$ 次该结果所需的次数的期望是 $\mathbb{E}_{k}=\frac{1}{(1-p)}[{(\frac{1}{p})^{k}-1}]$

1 赌徒输光问题#

• 与基本的赌徒输光问题一样
• 可以用状态转移矩阵来求解，即求解 $\pi= A \pi, s.t. \pi_{0}=0, \pi_{N}=1$，N 为钱的总数

2 骰子问题#

• 两个人扔两个骰子，A 认为和为 12 先出现，B 认为两次连续的和为 7 先出现，问 A 赢的概率是多少

3 硬币三连#

• 扔公平硬币，扔出连续的三次正面（HHH）的次数期望是多少，THH 呢？

• 考虑四种情况，S，H，HH，HHH 考虑他们的转移概率，然后根据转移概率写出他们到达 HHH 的转移次数

• 第二个问题也是一样，考虑四种情况，S，T，TH，THH

• 扔硬币直到出现 HHH 或者 THH，问 HHH 比 THH 先出现的概率是多少

• 当然也可以仿照上面的操作，考虑到达 HHH 的概率，有以下几种情况：THH, TH, T, S(开始), H, HH, HHH，其中 THH 到达的概率是 0，HHH 到达的概率是 1，然后考虑他们的状态转移，就可以解出来

• 但是实际上通过观察可以发现，HHH 必须要保证它的前面没有 T 出现，否则就会先到达 THH，所以概率其实就是三个 H 一起出现，是 $\frac{1}{2^3} = \frac{1}{8}$

• A 和 B 分别挑一种三连的硬币策略，A 挑完之后告诉 B，B 不能重复 A。然后比谁的情况先出现。问，理性人应该选 A 还是 B？

• 后手出招更优，只需要让自己的后两个硬币等于对方的前两个硬币即可，这样的话对方要赢，必须保证自己的第一个硬币不出现

4 彩球#

• 一个箱子里有 n 个不同颜色的球，每次取出两颗球，涂成一样的颜色放回去，问全涂成一样的颜色需要的次数期望是多少？
• 首先需要意识到颜色的对称性保证了 $\mathbb{E}[N_{n}]=\mathbb{E}[N_{n}|F_{i}]$ 其中 $F_{i}$ 表示最后剩下的颜色是 $i$，不妨就考虑 $\mathbb{E}[N_{n}|F_{1}]$. 然后我们就去计算 markov 链：$\mathbb{E}[N_{k}|F_{1}]=1+P_{k,k-1} \mathbb{E}[N_{k-1}|F_{1}]+P_{k,k} \mathbb{E}[N_{k}|F_{1}]+P_{k,k+1} \mathbb{E}[N_{k+1}|F_{1}]$，其中 $P_{k,l}$ 表示从 $k$ 个颜色 $i$ 到 $l$ 个颜色 $i$ 的概率。

鞅和随机游走#

• 随机游走：$\{ X_{i} \}_{i=1}^{\infty}$ 是 iid，则 $S_{n} = \sum_{i=1}^{n}X_{i}$ 称之为随机游走，当 $X_{i}$ 以 $p,1-p$ 概率取 $\pm1$ 时，称为简单随机游走，如果 $p=\frac{1}{2}$，称为对称随机游走
• 鞅：$\{ X_{i} \}_{i=1}^{\infty}$ 是一个鞅，如果 $\mathbb{E}[|X_{i}|]<\infty$，且 $\mathbb{E}[X_{i+1}|X_{1},\cdots,X_{i}]=X_{i}$，如果 $\mathbb{E}[X_{i+1}|X_{1},\cdots, X_{i}] \ge X_{i}$，则称之为下鞅，如果 $\mathbb{E}[X_{i+1}|X_{1},\cdots, X_{i}] \le X_{i}$，则称之为上鞅
  • 随机游走 $S_{n}$ 是一个鞅，且 $S_{n}^{2}-n$ 也是一个鞅
• 停时：一个随机变量 $T$ 是一个停时，如果 $\{ T=n \}$ 只依赖于 $X_{1},\cdots,X_{n}$，停时的意思是说，是否停止只能根据已经发生的事件来决定，而不能根据未来的事件来决定
  • Wald 定理：如果 $T$ 是一个停时，且 $\mathbb{E}[T]<\infty$，则 $\mathbb{E}[S_{T}]=\mathbb{E}[X_{1}] \mathbb{E}[T]$
  • 停时鞅也是一个鞅

1 醉酒人#

• 一条 100 m 的桥，醉酒人站在 $17$ m 的位置，每次以 $0.5$ 的概率向左走 $1$ m，以 $0.5$ 的概率向右走 $1$ m，问醉酒人先到达桥末端的概率是多少？结束时间期望是多少？
• 考虑停时 $N=\inf\{ n|S_{n}=-17 \text{或}83 \}$ ，根据停时鞅的性质，$\mathbb{E}[S_{N}]=\mathbb{E}[S_{0}]=0$，又因为 $S_{N}$ 只能取 $-17$ 或者 $83$，所以 $\mathbb{P}(S_{N}=-17) \cdot (-17) + \mathbb{P}(S_{N}=83) \cdot 83 = 0$，所以 $\mathbb{P}(S_{N}=-17) = \frac{83}{100}$，$\mathbb{P}(S_{N}=83) = \frac{17}{100}$；又因为 $S_{N}^{2}-N$ 是一个鞅，所以 $\mathbb{E}[S_{N}^{2}-N]=\mathbb{E}[S_{0}^{2}]=0$，所以 $\mathbb{E}[N] = \mathbb{E}[S_{N}^{2}] = \frac{83}{100} \cdot (-17)^{2} + \frac{17}{100} \cdot 83^{2} = 1441$
• 我们有结论：对于对称随机游走 $S_{n}$，停时 $N$ 为 $\inf\{ n:S_{n} =-\alpha,\beta\}$ ，则 $\mathbb{P}(S_{N}=-\alpha) = \frac{\beta}{\alpha+\beta}$，$\mathbb{P}(S_{N}=\beta) = \frac{\alpha}{\alpha+\beta}$，$\mathbb{E}[N] = \alpha \cdot \beta$，对于非对称随机游走 $S_{n}$，停时 $N$ 为 $\inf\{ n:S_{n} =-\alpha,\beta\}$，则 $\mathbb{P}(S_{N}=-\alpha) = \frac{1-(\frac{p}{1-p})^{\beta}}{(\frac{p}{1-p})^{\alpha}-(\frac{p}{1-p})^{\beta}}$，$\mathbb{P}(S_{N}=\beta) = \frac{(\frac{p}{1-p})^{\alpha}-1}{(\frac{p}{1-p})^{\alpha}-(\frac{p}{1-p})^{\beta}}$，$\mathbb{E}[N] = \frac{\alpha}{1-2p}-\frac{\alpha+\beta}{1-2p}\cdot \frac{1-(\frac{p}{1-p})^{\alpha}}{1-(\frac{p}{1-p})^{\alpha+\beta}}$

2 掷骰游戏#

• 一直掷骰子，知道投出 $1,2,3$ ，问期望总点数是多少？
• 直接运用 Wald 定理，停时 $N$ 是 $\inf\{ n|X_{n} \in \{1,2,3\}\}$，所以 $\mathbb{E}[N] = \frac{1}{\mathbb{P}(X_{n} \in \{1,2,3\})} = 2$，又因为 $\mathbb{E}X_{n}=\dfrac{7}{2}$ ，所以 $\mathbb{E}[\sum_{i=1}^{N}X_{i}] = \mathbb{E}[N] \cdot \mathbb{E}[X_{n}] = 7$

3 排队#

• $2n$ 个人在排队买票，$n$ 个人只有 $5$ 块，$n$ 个人有 $10$ 块，售票员没有零钱，如果每个人都买 $5$ 元的一张票，问无需调整顺序即可完成售票的概率是多少？
• 运用反射定理即可。首先，一共有 $\binom{2n}{n} = \dfrac{2n!}{n!n!}$ 条路径，我们需要考虑的是 $\forall0<i<2n, S_{i}\ge 0$ 的路径的数量。根据反射定理，$\exists 0<i<2n,S_{i}=-1$ 的路径数量等于终点落在 $(2n,-2)$ 的路径数量，即 $\binom{2n}{n-1} = \dfrac{2n!}{(n-1)!\cdot (n+1)!}$，所以 $\forall0<i<2n, S_{i}\ge 0$ 的路径数量等于 $\binom{2n}{n}-\binom{2n}{n-1} = \dfrac{2n!}{n!n!}-\dfrac{2n!}{(n-1)!\cdot (n+1)!} = \dfrac{1}{n+1}\cdot \dfrac{2n!}{n!n!}$，所以无需调整顺序即可完成售票的概率是 $\dfrac{\binom{2n}{n}-\binom{2n}{n-1}}{\binom{2n}{n}} = \dfrac{1}{n+1}$

4 硬币序列#

• 公平硬币，问要求出连续出现 $k$ 次正面（HHH）的次数期望是多少？
• 考虑连续出现 $k$ 次正面的期望次数为 $\mathbb{E}f(n)$ ，只需根据转移概率写出 $\mathbb{E}f(n)$ 的递推式即可，$\mathbb{E}f(n) = \dfrac{1}{2}[\mathbb{E}f(n-1)+1] + \dfrac{1}{2}\mathbb{E}f(n-1)$, 且 $\mathbb{E}f(1)=2$, 所以 $\mathbb{E}f(n) = 2^{n+1}-2$，所以连续出现 $k$ 次正面的期望次数为 $\mathbb{E}f(k) = 2^{k+1}-2$。
• 通用鞅方法：这个解释起来比较麻烦，首先明确，每投一次会有一个赌徒加入战场。对于这个赌徒而言，他花 $1$ 押注接下来的 $k$ 次投掷都是正面，对于每一次结果揭晓，如果猜的不对则清零，否则奖金翻倍，直到猜对 $k$ 次为止。对于这个赌徒而言，他的期望收益是 $0$，所以这是一个公平博弈。最后大家获得的总奖金应该等于总的参与人数，也就等于总的投掷次数。对于一个长度为 $k$ 的序列，只有最后 $k$ 个人有拿到奖金的权利。我们可以得到 $\mathbb{E}N= 2^k+2^{k-1}+\cdots+2^1 = 2^{k+1}-2$。这个结论可以继续推广到任意序列和概率。

动态规划#

• 动态系统基础概念：假设问题有 $N+1$ 个阶段，分别记为 $0,1,\cdots,N-1,N$。在阶段 $k, 0\le k\le N-1$，状态转移可以表示为 $x_{k+1}=f(x_{k},u_{k},w_{k})$ ，其中 $x_{k}$ 是阶段 $k$ 的状态，$u_{k}$ 是阶段 $k$ 的决策，$w_{k}$ 是阶段 $k$ 的随机扰动。对于每一个阶段 $k, 0\le k\le N-1$，有一个损失函数 $g_{k}(x_{k},u_{k},w_{k})$，对于阶段 $N$，有一个终止损失函数 $g_{N}(x_{N})$。动态规划的目标是找到一个决策序列 $\pi^{\star}=\{ u_{0}^{\star}, u_{1}^{\star}, \cdots, u_{N-1}^{\star} \}$ 来最小化总的期望损失 $J_{\pi^{\star}}(x_{0})=\min_{\pi}\mathbb{E}[\sum_{k=0}^{N-1}g_{k}(x_{k},u_{k},w_{k})+g_{N}(x_{N})]$
• DP 算法：对于有限决策问题，DP 算法的核心思想是决策一定要对于尾部子问题最优，即最小化 $J_{k}(x_{k})=\min_{u_{k}}\mathbb{E}[g_{k}(x_{k},u_{k},w_{k})+J_{k+1}(f(x_{k},u_{k},w_{k}))]$，其中 $J_{N}(x_{N})=g_{N}(x_{N})$。最后得到的 $J_{0}(x_{0})$ 就是最优的期望损失，$\pi^{\star}$ 就是最优的决策序列。

1 掷骰问题#

• 掷一个骰子至多三次，每次投完可以选择拿走对应点数的奖金或者继续投掷，问期望奖金是多少？
• 最后一次投掷的期望收益是 $3.5$; 因此倒数第二次只有在 $4,5,6$ 才有可能停下，所以倒数第二次决策是期望收益是 $\dfrac{1}{6}(4+5+6)+\dfrac{1}{2} \cdot\dfrac{7}{2}=\dfrac{17}{4}$; 因此第一次只有在 $5,6$ 才有可能停下，所以第一次决策的期望收益是 $\dfrac{1}{6}(5+6)+\dfrac{2}{3} \cdot \dfrac{17}{4} = \dfrac{14}{3}$。

2 世界大赛系列赛#

• 世界大赛系列赛，A 队和 B 队进行比赛，先赢得 4 场比赛的队伍获胜，每场比赛五五开。假如你有 100 块，你只能对每场下注，想要达到的效果是，如果 A 队总冠军，则再赚 100，否则全部输光。如果每场比赛都是公平博弈，问应该采取什么策略。
• 用 $(i,j)$ 表示 A 队已经赢了 $i$ 场，B 队已经赢了 $j$ 场的状态，那么对于状态 $(i,j)$，如果 $i=4$，则期望收益是 $100$；如果 $j=4$，则期望收益是 $-100$。期望收益用 $f(i,j)$ 表示，即 $f(4,j)=100, j=0,1,2,3$ 且 $f(i, 4)=-100, i=0,1,2,3$。考虑完终止条件后，我们考虑中间情况，对于每一局 $(i,j)$，假设下注 $y$ ，无非两种情况：局势变为 $(i,j+1)$ 或 $(i+1,j)$ ，期望收益分别变成 $f(i,j)-y$ 或 $f(i,j)+y$。由此我们得到

$$\begin{align} f(i+1,j) &= f(i,j)+y \\ f(i,j+1) &= f(i,j)-y \end{align}$$

• 因此可以解出来

$$\begin{align} f(i,j) &= \dfrac{f(i+1,j)+f(i,j+1)}{2} \\ y &= \dfrac{f(i+1,j)-f(i,j+1)}{2} \end{align}$$

3 动态掷骰问题#

• 一个骰子在没投到 6 之前可以一直投掷，每次投掷的点数都会累加到总分上，每次你可以决定是否继续投掷，问期望总分是多少？
• 每次决策只看期望收益和损失，当已经拥有 $n$ 元时，期望收益是 $\dfrac{1}{6}(n+1) + \dfrac{1}{6}(n+2) + \dfrac{1}{6}(n+3) + \dfrac{1}{6}(n+4) + \dfrac{1}{6}(n+5) =\dfrac{5}{6}n+\dfrac{5}{2}$ ，期望损失是 $n$，所以只要 $n<15$ 就继续投掷，$n\ge 15$ 就停下，所以不再投掷的情况包括 $15,16,17,18,19$，它们的期望收益就是它们本身，对于前面的数

$$\mathbb{E}(f(n)|n<15)= \dfrac{1}{6} \sum_{i=1}^{5}\mathbb{E}(f(n+i))$$

• 由此递归，可以解出来 $\mathbb{E}f(0)=6.15$。

4 动态卡牌问题#

• 一副牌 52 张，26 张红的 26 张黑的，发牌员每次抽一张，如果是红的，你就赢 1 块，如果是黑的，你就输 1 块。你随时可以让发牌员停下来，问最优策略是什么？
• 用 $(b,r)$ 来表示当前剩下的黑牌数量和红牌数量，那么当 $b=0$ 时，期望收益是 $0$，当 $r=0$ 时，期望收益是 $b$。对于其他情况，我们知道

$$\mathbb{E}[f(b,r)]= \max\{ b-r,\dfrac{b}{b+r}\mathbb{E}f(b-1,r)+\dfrac{r}{b+r}\mathbb{E}f(b,r-1) \}$$

布朗运动和随机微积分#

布朗运动：$W_{t}$ 是一个布朗运动，如果满足以下条件

• $W_{0}=0$，且 $W_{t}$ 是连续的
• $W_{t}$ 有独立增量，即对于 $0\le t_{1}<t_{2}<\cdots<t_{n}$，$W_{t_{2}}-W_{t_{1}}, W_{t_{3}}-W_{t_{2}}, \cdots, W_{t_{n}}-W_{t_{n-1}}$ 互相独立
• $W_{t}$ 的增量服从正态分布，即对于 $s<t$，$W_{t}-W_{s} \sim N(0,t-s)$ 布朗运动的性质
• 路径连续
• $\mathbb{E}W(t)=0, \mathbb{E}W^{2}(t)=t$
• 马尔可夫性质
• 鞅性质：$W_{t}$ 是一个鞅，即 $\mathbb{E}[W_{t}|\mathcal{F}_{s}]=W_{s}, s<t$，且 $Cov(W(s),W(t))=s, \forall_{0}<s<t$
• 还有两个和布朗运动有关的重要的鞅：$Y(t)= W^{2}(t)-t$ 和 $Z(t) = \exp \left\{ \lambda W(t) -\frac{ 1}{2}\lambda^{2}t \right\}$ （指数鞅） 首达时（FPT）：对于布朗运动 $W_{t}$，定义首达时 $\tau_{a} = \inf\{ t>0: W_{t}=a \}$
• FPT 的期望是很好求的，可以通过 $B_{t}^{2}-t$ 这个鞅来求解，$\mathbb{E}[\tau_{a}] = a^{2}$
• FPT 的分布需要用到反射定理，$\mathbb{P}(\tau_{x}\le t) = \mathbb{P}(\sup_{0\le s\le t}W_{s}\ge x) = 2\mathbb{P}(W_{t}\ge x)$ 于是我们就可以得到 $\tau_{x}$ 的分布函数为 $F_{\tau_{x}}(t) = 2\mathbb{P}(W_{t}\ge x) = 2\int_{x}^{\infty} \dfrac{1}{\sqrt{2\pi t}}e^{-\frac{y^{2}}{2t}}dy$，所以 $\tau_{x}$ 的概率密度函数为 $f_{\tau_{x}}(t) = \dfrac{x}{\sqrt{2\pi t^{3}}}e^{-\frac{x^{2}}{2t}}$，所以 $\tau_{x}$ 服从 Levy 分布。
• 有两侧边界的 FPT （分别为 $-\alpha,\beta$）撞到两侧的概率可以用停时鞅的性质求解：对于布朗运动 $W_{t}$，停时 $N$ 是 $\inf\{ t: W_{t}=-\alpha \text{或} \beta \}$，则由 $-P_{-\alpha}\alpha+P_{\beta}\beta=0$，可以知道 $\mathbb{P}(W_{N}=-\alpha) = \dfrac{\beta}{\alpha+\beta},\mathbb{P}(W_{N}=\beta) = \dfrac{\alpha}{\alpha+\beta}$；当然，我们也可以再次证明 $\mathbb{E}N = \alpha \cdot \beta$

Feynman-Kac 方程：对于伊藤过程 $X_{t}$ ，满足 $\mathrm{d}X(t) = \beta(t,X)\mathrm{d}t + \gamma(t,X)\mathrm{d}W(t)$，定义 $V(t,x) = \mathbb{E}[f(X_{T})|X_{t}=x]$，则 $V(t,x)$ 满足以下偏微分方程

$$\frac{\partial V}{\partial t} + \beta(t,x)\frac{\partial V}{\partial x} + \frac{1}{2}\gamma^{2}(t,x)\frac{\partial^{2}V}{\partial x^{2}} = 0 ,$$

其中 $V(T,x) = f(x)$。

• 对于带 drift 项 $m$ 的布朗运动，这个过程不再是鞅，我们考虑 $P(t,x)$ 表示 $W_{t}+mt$ 在 $t$ 时刻，在达到 $-5$ 前达到 $x$ 的概率。根据马尔可夫性质我们知道 $P(t,x)$ 与 $t$ 独立。根据 $Feynman-Kac$ 方程，我们可以给出 $mP_{x}(x)+\frac{ 1}{2}P_{xx}(x)=0, -5<x<3$ 。又有 $P(-5)=0,P(3)=1$。于是解出这个常微分方程的结果是 $P(x)= c_{1}+c_{2}e^{-2mx}$ ，其中 $c_{1} = \dfrac{1}{1-e^{-16m}}, c_{2} = -\dfrac{1}{e^{10m}-e^{-6m}}$，所以 $P(0) = \dfrac{1-e^{-10m}}{1-e^{-16m}}$。
  • 另一种方法是考虑指数鞅 $Z(t) = \exp \left\{ \lambda (X-mt) -\frac{ 1}{2}\lambda^{2}t \right\}$，只需取 $\lambda=-2m$ 则可以得到 $\mathbb{E}[\exp(-2mX)] = 1$, 我们就可以很快算出 $P(0) = \dfrac{1-e^{-10m}}{1-e^{-16m}}$。

伊藤引理：对于伊藤过程 $X_{t}$，满足 $\mathrm{d}X(t) = \beta(t,X)\mathrm{d}t + \gamma(t,X)\mathrm{d}W(t)$，以及一个二阶可微函数 $f(x,t)$，则 $f(X_{t},t)$ 也是一个伊藤过程，满足

$$\mathrm{d}f(X_{t}) = \left[ \frac{ \partial f }{ \partial t } +\beta(t,X)\frac{\partial f}{\partial x} + \frac{1}{2}\gamma^{2}(t,X)\frac{\partial^{2}f}{\partial x^{2}} \right]\mathrm{d}t + \gamma(t,X)\frac{\partial f}{\partial x}\mathrm{d}W(t)$$

其中，漂移项为 $\frac{ \partial f }{ \partial t } +\beta(t,X)\frac{\partial f}{\partial x} + \frac{1}{2}\gamma^{2}(t,X)\frac{\partial^{2}f}{\partial x^{2}}$，扩散项为 $\gamma(t,X)\frac{\partial f}{\partial x}$。

• 根据伊藤引理，我们可以判断更复杂的伊藤过程的性质，比如 $Z_{t}=\sqrt{ t }B_{t}$，我们可以知道 $Z_{t}\sim N(0,t^{2})$ 即 $Z_{t}$ 的期望是 $0$，方差是 $t^{2}$；但是由伊藤引理，我们可以得到更详细的信息，$Z_{t}$ 的漂移项是 $\dfrac{1}{2\sqrt{t}}B_{t}$，扩散项是 $\sqrt{t}$，所以 $Z_{t}$ 不是一个鞅。