算法问题

1. 逻辑题

蓄水池抽样

从包含 $n$ 个项目的集合 $S$ 中选取 $k$ 个样本，其中 $n$ 为未知量

解答

1. 从 $S$ 中抽取首 $k$ 项放入「水塘」中
2. 对于每一个 $S[j] (j\ge k)$ 项：
   1. 随机产生一个范围从 0 到 $j$ 的整数 $r$
   2. 若 $r<k$ 则把水塘中的 $r$ 项换成 $S[j]$ 项

水桶取水问题

两个容积确定的水桶, 取定量的水

解答

记容积为 $a$ 和 $b$, 取定量的水为 $c$, 则有以下几种情况:

1. $c > \max(a, b)$, 无解
2. $c = a$ 或 $c = b$, 直接取出即可

不失一般性, 设 $\operatorname{gcd}(a, b) = 1$, 由欧拉定理, $a ^ {\varphi(b)}\equiv 1 \mod b$. 记 $p=a^{\varphi(b)-1}$, $q=(a^{\varphi(b)}-1)/b$, 有 $pa-qb=1$.

从而 $pca - qcb = c$. 也就是说, 先用 $a$ 桶取水 $cp$ 次, 满的 $b$ 桶倒空 $cq$ 次, 就能得到 $c$ 的水量.

2. 概率论

2.1 排列组合

球盒问题

$n$ 个球放到 $m$ 个盒子中, 允许空盒子, 有几种放法?

解答
相当于 $n+m$ 个球放到 $m$ 个盒子中, 不允许空盒子
使用隔板法, 就是 $\operatorname{C}_{n+m-1}^{m-1}$

数字和

有多少个小于1,000,000的正整数, 其各位数字和等于19

解答

隔板法 Stars and Bars

0到999999允许前导0, 是6位数字, 将19个球放在6个盒子中, 允许空盒, 有 $\operatorname{C}_{16+9-1}^5=42504$ 种组合.

但是盒子中不能有超过 10 个球. 设第一个盒子超过10个球, 那么相当于 19-10 个球放在 6 个盒子中, 允许空盒, 有 $\operatorname{C}_{14}^5=2002$ 种组合.
这6个盒子是等价的, 因此答案为 $42504-6\times 2002=30492$.

2.2 条件概率/期望与贝叶斯

全概率公式 $P(B)=\sum_i P(B\mid A_i)P(A_i)$
全期望公式 $\mathbb{E}[B]=\sum_i \mathbb{E}[B\mid A_i]P(A_i)$

骰子掷出相邻点数

连续2次掷骰结果相差至多为1的期望

解答

按照对称性分3类, $E_1, E_2, E_3$分别表示当前点数为${1, 6}, {2, 5}, {3, 4}$时完成任务的期望.

当当前结果为1, 下一次掷出1或2的概率为1/3→结束, 下一次掷出3, 4的概率为 1/3→$E_3$, 下一次掷出5的概率为 1/6→$E_2$, 下一次掷出6的概率为1/6→$E1$, 则有

\[\begin{aligned}E_1=&1+\frac{1}{6}E_1+\frac{1}{3}E_3+\frac{1}{6}E_2\\ E_2=&1+\frac{1}{6}E_1+\frac{1}{6}E_2+\frac{1}{6}E_3\\ E_3=&1+\frac{1}{3}E_1+\frac{1}{6}E_2\end{aligned}\]

解得 $E_1=288/115, E_2=246/115, E_3=252/115$.
故总期望 $E=1+\dfrac{E_1+E_2+E_3}{3}=\dfrac{377}{115}$.

2.3 随机变量与概率分布

概率计算方法: 递推关系(转移矩阵求解, 或者齐次指数展开求解), 最后得到通项公式

根据骰子向前走

一个人扔六面的骰子，数值1到6，扔到几就向前走几格，可以无限扔，问他恰好走到第2023格的概率

解答

骰子等概率的从前面 6 个格子走到这个格子

\[P_{n}=(P_{n-6}+P_{n-5}+P_{n-4}+P_{n-3}+P_{n-2}+P_{n-1})/6\]

假设起点概率是 1, 经过起点前的点概率不存在.

\[P_{0}=1，P_{-1}=P_{-2}=P_{-3}=P_{-4}=P_{-5}=0\]

列出转移矩阵为:

\[M = \left[\begin{array}{ll} &1&&&&\\ &&1&&&\\ &&&1&&\\ &&&&1&\\ &&&&&1\\ \frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6} \end{array}\right]^n\cdot\left[\begin{array}{ll}0\\0\\0\\0\\0\\1\\\end{array}\right]\]

每次左乘一个转移矩阵, 得到的概率从 $P(i)\sim P(i+5)$ 变成 $P(i)\sim P(i+6)$. 从状态 $i$ 到状态 $i$ 的概率一定为 1, 因为是已经确定的, 要计算的只有 $i+6$.

要估算的话令此时的特征多项式为

\[\lambda^6-\dfrac{1}{6}(1+\lambda^2+\lambda^3+\lambda^4+\lambda^5) = 0\]

因式分解得:

\[(6\lambda^5+5 \lambda^4+4 \lambda^3+3 \lambda^2+2 \lambda+1)(\lambda-1)=0\]

解得:

\[\begin{aligned}\lambda_1&=1\\\lambda_2&=+0.294195+0.668367 i\\\lambda_3&=+0.294195-0.668367 i\\\lambda_4&=-0.375695+0.570175 i\\ \lambda_5&=-0.375695-0.570175 i\\\lambda_6&=-0.670332\\\end{aligned}\]

也就是说 $M≈\dfrac{1}{7} (1 +{\lambda_1}^n+{\lambda_2}^n+ {\lambda_3}^n+{\lambda_4}^n+{\lambda_5}^n+{\lambda_6}^n)$

除了 $\lambda_1^n = 1$, 其他的模平方全部小于 1, 加上指数会全都变成 0, 显然就会收敛到 $\dfrac{2}{7}$.

使用通项公式的求解方式 $a_{i+7}=\dfrac{1}{6}(a_{i+6}+a_{i+5}+a_{i+4}+a_{i+3}+a_{i+2}+a_{i+1})$, 设 $a_n = r^n$, 得到特征方程

\[r^7-\dfrac{1}{6}(r^6+r^5+r^4+r^3+r^2+r)=0\]

解得 $a_n = c_1 + c_2\lambda_2^n + c_3\lambda_3^n + c_4\lambda_4^n + c_5\lambda_5^n + c_6\lambda_6^n$, 其中 $c_i$ 是初值决定的.

最终结果只和特征值有关, 和初值无关, 到达稳态之后是 100 还是 2023 还是 2024 都不怎么重要.

2.4 期望、方差与协方差

一般方法: 期望的递推关系, 利用对称性求出期望, 其实也是一种动态规划

均匀分布的期望

每次均匀随机取 $[0,1]$, 比上个数大就停, 求最后一个数的期望.

解答

设随机变量序列为

\[X_1, X_2, \cdots\overset{\text{i.i.d.}}{\sim}U(0,1)\]

规则是:

• 先取$X_1$
• 若 $X_n>X_{n-1}$, 则停止, 最后一个数就是 $X_n$; 否则继续

求停止时最后一个数 $Y$ 的期望 $E[Y]$.

设

\[f(x)=\mathbb{E}[Y\mid X_1=x]\]

表示当前数为 $x$ 时, 最终停止的那个数的条件期望. 如果当前数为 $x$, 下一次随机取 $U\sim U(0,1)$.

\[f(x)=\int_x^1 udu+\int_0^xf(u)du=\int_0^xf(u)du+\frac{1-x^2}{2}\]

这里如果选择数的分布不是均匀分布, 而是一个概率密度函数 $p(u)$, 则上式调整为 $f(x)=\int_0^x f(u)p(u)du+\int_x^1 up(u)du$.

两边求导, 得到 $f’(x)=f(x)-x$. (微积分第一基本定理)

解得 $f(x)=x+1+Ce^x$. (线性微分方程组, 先求齐次通解, 再用常数变易法求通解)

当 $x=0$ 时, $f(0)=0.5$, 故 $f(x)=x+1-\frac{1}{2}e^x$.

期望 $\mathbb{E}=\int_0^1f(x)dx=2-\frac{e}{2}$.

均匀分布点的期望

区间[0,1]均匀分布独立地标 $n(n≥3)$ 个点, 定义P的邻居为最靠近P的点, 若一个点的邻居的邻居是它本身, 则称该点为”好点”. 求好点个数的期望.

解答

将 $n$ 个点按大小排序 $X_1<X_2<\cdots<X_n$, 定义相邻点之间的间隔 $D_i=X_{i+1}-X_i$, 满足 $D_i>0, \sum_{i=1}^{n-1} D_i<1$.

若第 $i$ 个点为好点, 它满足

\[\begin{cases} D_1<D_2&,i=1\\ D_{n-1}<D_{n-2}&,i=n-1\\ D_i<D_{i-1}, D_i<D_{i+1}&,\textrm{otherwise} \end{cases}\]

每个这样的相邻点对对应两个“好点”，所以若满足条件的点对数为 $M$，则好点数为 $2M$。

单纯形的概念:

一个 $(k-1)$ 维的标准单形(standard simplex)定义为

\[\Delta^{k-1}=\left\{(x_1,\cdots,x_k)\mid\vert x_i\geq0,\sum_{i=1}^k x_i=1\right\}\]

例子:

• 所有离散概率分布 ${p_1,\cdots p_k}$ 都位于 $k-1$ 维单形上($\sum p_i=1$).
• Dirichlet 分布：它是定义在单形上的连续分布，是多项分布的共轭先验, 广泛用于贝叶斯统计。
• 机器学习与优化：
  Softmax 函数的输出将任意实数向量映射到概率单纯形上，这是多分类神经网络的基石。在强化学习中，策略（选择各个动作的概率）也位于单纯形上。
• 经济学与博弈论：
  混合策略纳什均衡中，参与人随机选择纯策略的概率分布也定义在单纯形上，单纯形的紧致性和凸性保证了不动点定理（如 Brouwer 定理）的应用。

单形的几何对称性催生了强大的概率对称性（可交换性）。在统计中，只要一个分布是“对称的”（即密度函数在坐标置换下不变），有一些简单结论：

• 极值概率平分. 在单形上有 $k$ 个变量, 他们的联合分布关于坐标置换对称, 那么任意一个变量大于另一个变量的概率 $P(X_i<X_j)=1/2$.
• 条件均匀性. 如果原始点是独立的均匀分布(题中的情况)，那么在给定排序位置的条件下，剩余部分的分布依然在子单形上均匀。这就允许我们做“切割”和“拼接”的计算。
• 与泊松过程的桥梁（著名的性质）
  如果在一个长度为 1 的线段上随机扔 $n-1$ 个点（即我们题中的 $n$ 个点分隔出的 $n$ 段空隙），这 $n$ 段空隙的联合分布（Dirichlet(1,…,1)）正好等价于：生成 $n$ 个独立的参数为 1 的指数分布随机变量，然后除以它们的总和。
• 重心与边缘分布
  在单形上的对称分布，任意一个变量的边缘分布都是 Beta 分布。比如，在 $(n−1)$ 维单形上的均匀分布，任意一个单独的 $X_i$ 的边缘密度为 $(n-1)(1-x)^{n-2}$，这直接给出了单个间隔的分布规律。

回到原题, 令 $Y_i=D_i, Y_n=1-\sum D_i$, 则 $(Y_1, \cdots,Y_n)$服从参数为 $(1,1,\cdots,1)$ 的Dirichlet分布, 因为所有参数都是 1（完全相等），这个分布在任意坐标置换下保持不变，所以称为对称的 Dirichlet 分布。这种对称性意味着：任意两个坐标交换位置，联合概率密度函数完全不变。

由对称性, 端点要求 $D_1<D_2$, 由对称性, $P(D_1<D_2)=P(D_{n-1}<D_{n-2})=1/2$; 内部 $P(D_i<D_{i-1}, D_i<D_{i+1})=1/3$.

\[E[M]=2\times\frac{1}{2}+(n-3)\cdot\frac{1}{3}=\frac{2n}{3}\]

好点数的期望为 $2n/3$.

期望会变化的公平价值

100面的骰子, 点数1~100. 每次重掷支付1元, 可无限重掷. 结束时获得点数的钱. 公平价值是多少.

解答

公平价值相当于这个游戏的期望. 设在投骰子之前(且未支付本次费用)的期望价值为 $V$

• 若掷出点数 $x$, 直接停止, 获得 $x$
• 若选择重掷, 支付1元成本后, 游戏回到最初状态, 净收益是 $V-1$

我会选择两者更大的那个 $V=E[\max(x, V-1)]$, 临界值 $s\approx V-1$, 即大于等于 $s$ 的保留, 小于 $s$ 的重掷. 利用期望公式, 有

\[V=\frac{1}{100}\left[(s-1)(V-1)+\sum_{x=s}^{100}x\right]\]

当 $s=86$ 时, $V=87.33$, 那么 $x=86$ 要重掷, 与题设不符
当 $s=87$ 时, $V=87.36$, 那么 $x\leq 86$ 要重掷, $x>87$ 要保留
当 $s=88$ 时, $V=87.31$, 那么 $x=87$ 要保留, 与题设不符

故公平价值为 87.36.

有临界条件的期望

每次均匀随机取[0,1], 理性的你可以随时停止并以和作为分数, 但若和大于1则0分, 求平均分数

解答

定义 $V(s)$ 为当前和为 $s$ 时的期望分数, 有两种选择: 停止(分数就为 $s$); 继续取值(分数为继续取值的期望). 理性的人选择分数更高的选项. 则有

\[V(s) = \max\left\{s, \int_0^{1-s}V(s+x)dx\right\}=\max\left\{s, \int_s^1V(x)dx\right\}\]

因为第二项是单调递减的函数, 因此必存在临界值 $s_0$, 使得

\[V(s)=\begin{cases}s, s\geq s_0\\ \int_s^1V(x)dx, s<s_0\end{cases}\]

而 $s_0$ 处满足

\[s_0=\int_{s_0}^1V(x)dx=\int_{s_0}^1x dx=\frac{1-s_0^2}{2}\]

解得 $s_0 = \sqrt 2-1$.

当 $s<s_0$ 时, 两边求导, 得到 $V^\prime(s)=-V(s)$, 解得 $V(s)=Ce^{-s}$, 代入边界条件 $V(s_0)=s_0$, 得到 $C=s_0e^{s_0}$. 故

\[V(s)=\begin{cases}s, s\geq \sqrt 2-1\\ (\sqrt 2-1)e^{\sqrt 2-1-s}, s<\sqrt 2-1\end{cases}\]

那么原题 $\mathbb{E}[0]=V(0)=(\sqrt 2-1)e^{\sqrt 2-1}\approx 0.857$.

2.5 顺序统计量

极值期望

n 个独立同分布变量, $X_i\sim U(0,1)$ 的最大值, 最小值期望

解答

\[Z=\max(X_1,\cdots,X_n),\quad W=\min(X_1,\cdots,X_n)\]

累积分布函数 $P(Z\leq z)=\prod P(X_i\leq z)=z^n$, $P(W\geq w)=\prod P(X_i\geq w)=(1-w)^n$.
概率密度函数 $f_Z(z)=P^\prime(Z\leq z)=nz^{n-1}$, $f_W(w)=-P^\prime(W\geq w)=n(1-w)^{n-1}$.
期望 $\mathbb{E}[Z]=\int zf_Z(z)dz=\int_0^1 nz^n dz=\frac{n}{n+1}$
期望 $\mathbb{E}[W]=\int wf_W(w)dw=\int_0^1 nw(1-w)^{n-1} dw=\frac{1}{n+1}$

极值期望2

1~N 个数字, 选择其中 k 个, 最大值, 最小值的期望.

解答

相当于N-k个位置中随即放置 k 个标记, 将N-k个位置分成了k+1段. 由于N-k个未选中的数字在这k+1个间隔中具有完全的对称性, 所以每个间隔的期望长度都是 $\frac{N-k}{k+1}$.

因此最小值的期望 $E[\min]=\frac{N-k}{k+1}+1=\frac{N+1}{k+1}$
最大值的期望 $E[\max]=N-\frac{N-k}{k+1}=\frac{kN+k}{k+1}=\frac{k(N+1)}{k+1}$.

极值期望3

54张扑克牌, 依次抽取, 抽到至少一张A和一张K的次数期望

解答

由极值期望2, 抽到第一张牌(比如是A)的期望是 $\frac{54+1}{8+1}=\frac{55}{9}$, 接下来, 抽到第一张K的期望是 $\frac{54-55/9+1}{4+1}=\frac{88}{9}$

故期望之和为 $\frac{55}{9}+\frac{88}{9}=\frac{143}{9}$.

更繁琐的方法:

尾概率公式 $\mathbb{E}[X] = \sum_{i=0}^{\infty} P(X>i)$
$P(X>i)$ 表示前 $i$ 张牌中没有A或者没有K(在i+1处抽到至少一张A和一张K).
由容斥原理, 有 $P(X>i)=2P(A_n)-P(A_n \cap K_n)=\frac{2\operatorname{C}_{50}^i-\operatorname{C}_{46}^i}{\operatorname{C}_{54}^i}$.
故期望

\[\mathbb{E}[X]=\sum_{i=0}^{54}P(X>i)=\sum_{i=0}^{54}\frac{2\operatorname{C}_{50}^i-\operatorname{C}_{46}^i}{\operatorname{C}_{54}^i}=\frac{143}{9}\]

随机蚂蚁 TODO

绿皮书¹, P102

硬币最长连续正面的期望

连续抛100次硬币, 求最长连续正面的期望长度

解答

抛硬币的通用假设是 $f(i,j)$ 表示前 $j-1$ 次均为正面, 第 $j$ 次为反面, 然后对这样的状态求和. 抛硬币出k次正面 也是这样.

尾概率(尾和)公式 $\mathbb{E}[X] = \sum_{i=1}^{\infty} P(X\geq i)$. “最长正面数超过 $i$”不好套用前面的迭代, 因为”前 $j-1$ 次均为正面”影响了用后面的部分决定最长正面数, 因此考虑”最长正面数小于 $i$”.

令 $a_n^{(k)}$ 表示在 $n$ 次抛硬币中, 最长连续正面数小于 $k$ 的序列数量. 为什么不用概率而是数量, 因为概率是数量除以 $2^n$, 只要求出数量, 概率就可以直接算出来. 则

\[\mathbb{E}=\sum_{k=1}^{100}\left(1-\frac{a_{100}^{(k)}}{2^{100}}\right)\]

现在考察递推关系.

抛 $n$ 次, 拆分, 第 $i$ 项表示 “$i-1$ 次正, 反, $n-i$ 次任意”的组合, 那么有

\[a_n^{(k)}=a_{n-1}^{(k)}+a_{n-2}^{(k)}+\cdots+a_{n-k}^{(k)}=\sum_{i=1}^{k}a_{n-i}^{(k)}\]

边界条件 $a_n^{(k)}=2^n$ 当 $n<k$, 因为小于 $k$ 的序列都是合法的.

有递推公式其实已经可以得到答案了, 用动态规划直接得到结果.
接下来用生成函数的方法. 生成函数的特点是, 把数列 ${a_0, a_1, \cdots}$ 放到 ${x^0, x^1, \cdots}$ 的系数位置上, 这样当展开后, 通过观察系数可以得到数列的通项公式. 令

\[A_k(x)=\sum_{n=0}^{\infty}a_n^{(k)}x^n=a_0^{(k)}+a_1^{(k)}x+a_2^{(k)}x^2+\cdots\]

隐去下标, 左右两边分别乘以 $x, x^2, \cdots, x^k$, 然后相加再减去 $A(x)$, 等式左边为

\[\begin{aligned}&x A(x) + x^2 A(x) + \cdots + x^k A(x) - A(x) \\=&(x+x^2+\cdots+x^k-1)A(x)\\=&\frac{2x-1-x^{k+1}}{1-x}A(x)\end{aligned}\]

等式右边的 $x^n$ 项的系数为 $a_{n-1}+a_{n-2}+\cdots+a_{n-k}-a_n$, 当 $n\geq k$ 时, 等于 $0$. 因此右边只剩下 $x^0,x^1,\cdots,x^{k-1}$ 这些项.

$x^0$ 的系数 $-a_0=-1$
$x^1$ 的系数 $-a_1+a_0=-1$
$x^2$ 的系数 $-a_2+a_0+a_1=-1$ $x^{k-1}$ 的系数 $-a_{k-1}+a_0+a_1+\cdots+a_{k-2}=-2^{k-1}+2^0+2^1+\cdots+2^{k-2}=-1$

因此等式右边为 $-1-x-x^2-\cdots-x^{k-1}=-\dfrac{1-x^k}{1-x}$. 故

\[A_k(x)=\frac{1-x^k}{1-2x+x^{k+1}}\]

$a_n^{(k)}$ 即为 $A_k(x)$ 的展开式中 $x^n$ 的系数, 也就是 $[x^n]A_k(x)$. 有

\[\begin{aligned}a_{100}^{(k)}=&[x^{100}]\frac{1-x^k}{1-2x+x^{k+1}}\\ \mathbb{E}=&100-\frac{1}{2^{100}}\sum_{k=1}^{100}[x^{100}]\frac{1-x^k}{1-2x+x^{k+1}}\end{aligned}\]

3. 随机过程

3.1 马尔可夫链

掷骰子出连续2个6

一个公平的骰子, 平均掷多少次才能掷出连续的两个6?

解答

使用马尔科夫链, 设置3个状态:

• 状态0: 还没有掷出6
• 状态1: 刚掷出一个6
• 状态2: 刚掷出两个6

设从状态 $i$ 到状态 $j$ 的转移概率为 $P(i,j)$, 转移矩阵

\[M = \left[\begin{array}{ccc} \frac{5}{6} & \frac{1}{6} & 0 \\ \frac{5}{6} & 0 & \frac{1}{6} \\ 0 & 0 & 1 \\ \end{array}\right]\]

第一行的意思是, 当我处于状态0时, 我需要掷一次骰子, 然后有 $\frac{5}{6}$ 的概率回到状态0, 有 $\frac{1}{6}$ 的概率转移到状态1.

设期望从状态 $i$ 到达状态 $2$ 的步数为 $E(i)$, 则有:

\[\begin{aligned} E(0) &= 1 + \frac{5}{6}E(0) + \frac{1}{6}E(1) \\ E(1) &= 1 + \frac{5}{6}E(0) + \frac{1}{6}E(2) \\ E(2) &= 0 \\ \end{aligned}\]

联立方程组, 解得:

\[E(0) = 42, \quad E(1) = 7, \quad E(2) = 0\]

因此, 平均掷42次才能掷出连续的两个6.

解法2. 参考吸收马尔科夫链的基本矩阵概念, 已知瞬态转移矩阵

\[\mathbf{Q}=\begin{bmatrix}\frac{5}{6} & \frac{1}{6} \\ \frac{5}{6} & 0\end{bmatrix}\]

基本矩阵 fundamental matrix $\mathbf{N}=(\mathbf{I}-\mathbf{Q})^{-1}$, 联立求解方程

\[\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}\frac{1}{6}&-\frac{1}{6}\\-\frac{5}{6}&1\end{bmatrix}=\begin{bmatrix}1&0\\0&1\end{bmatrix}\]

得到

\[\mathbf{N}=\begin{bmatrix}36 & 6 \\ 30 & 6\end{bmatrix}\]

从状态0开始, 到状态2结束, 中间状态0的期望步数为36, 状态1的期望步数为6, 那么一共42步. 注意这里的36, 包含了初始时刻的那一步.

转移矩阵:

\[P = \begin{bmatrix}Q & R \\ 0 & I\end{bmatrix}\]

其中, $Q$ 是瞬态状态之间的转移矩阵, $R$ 是从瞬态状态到吸收状态的转移矩阵, $I$ 是吸收状态的单位矩阵.

而 $N=(I-Q)^{-1}$ 是基本矩阵, 其元素 $N_{ij}$ 表示从瞬态状态 $i$ 到瞬态状态 $j$ 的期望访问次数.

处在状态0/1的概率分别为$P=(P_0, P_1)$, 那么根据转移矩阵, 下一步的概率为$P’ = P \cdot Q$, 继续迭代, 直到收敛.

定义随机变量

\[N_{ij}=\textrm{从状态 }i\textrm{ 出发, 吸收前访问状态 }j\textrm{ 的次数}\]

可写成

\[N_{ij} = \sum_{n=0}^{\infty} \mathbb{I}(X_n = j, X_n \textrm{尚未吸收})\]

其中 $\mathbb{I}(X_n = j)$ 是指示函数, 当 $X_n = j$ 时为1, 否则为0.

那么有

\[\begin{aligned} \mathbb{E}[N_{ij}]=&\sum_{n=0}^{\infty}P(X_n = j, X_n \textrm{尚未吸收})\\ =&p_i\cdot (I+Q+Q^2+\cdots)\\ =&(\mathbf{I}-\mathbf{Q})^{-1}_{ij} \end{aligned}\]

也就是从状态 $i$ 开始, 到达吸收状态前访问状态 $j$ 的期望次数.

抛硬币出k次正面

抛硬币, 出现正面的概率为 $p$, 抛到连续出现 $k$ 次正面为止, 抛的次数的期望是多少?

解答

简化问题
直到连续出现两次正面为止，平均要抛多少次才能结束游戏？

假设期望为 $\operatorname{E}(2)$. 递归. 首先先抛一枚硬币，如果是背面，那么需要重头开始；如果是正面，那么再抛一枚硬币，新抛的这枚如果也是正面，则游戏结束，如果是背面，那么又需要重头开始。

\[\operatorname{E}(2) = 1 + (1-p)\operatorname{E}(2)+p[1+p\times 0+(1-p)\operatorname{E}(2)] = \frac{1+p}{p^2}\]

原问题

先抛掷 $\operatorname{E}(k-1)$ 次，得到连续的 $k-1$ 个正面，然后再抛一次，若是正面，则游戏结束；否则需要重头开始，也就是说又需要 $\operatorname{E}(k)$ 次。

\[\operatorname{E}(k) = \operatorname{E}(k-1) + 1 + p\times 0+(1-p)\operatorname{E}(k)= \frac{1+E(k-1)}{p}=\frac{1}{1-p}\left(\frac{1}{p^n}-1\right)\]

概率生成函数

定义 一个离散随机变量的概率母函数(probability generating function)是指该随机变量的概率质量函数的幂级数表达式。

\[G(z)=\operatorname{E}(z^{X})=\sum _{x=0}^{\infty }p(x)z^{x}\]

1. 概率 ${\displaystyle p(k)=\operatorname {Pr} (X=k)=\frac {G^{(k)}(0)}{k!}}$
2. 期望 $\displaystyle \operatorname {E} [X]=G^\prime(1^{-})$
3. 方差 $\operatorname {Var} (X)=\mathbb{E}[X^2]-\mathbb{E}^2[X]=(E[X(X-1)]+E[X])-E^2[X]=G^{\prime\prime}(1^{-})+G^\prime(1^{-})-\left[G^\prime(1^{-})\right]^{2}$
4. $k$-阶矩 k^th raw moment ${\displaystyle \operatorname {E} [X^{k}]=\left.\left(z{\frac{\partial }{\partial z}}\right)^{k}G(z)\right\vert_{z=1^{-}}}$
5. 矩生成函数 Moment-generating function $M_{X}(t)=\displaystyle G_{X}(e^{t})$

原问题的概率生成函数

参考
记恰好 $n$ 次投掷硬币获得 $k$ 次连续正面的概率为 $P_{n,k}$ . 有 $P_{n,n}=p^n$, $P_{k,n}=0(k<n)$.
根据第一次投掷出反面的次数 $i$ 分类讨论, 有

\[P_{n,k} = \sum_{i=1}^k p^{i-1}(1-p)P_{n-i,k}\]

右边第 $i$ 项表示刚开始投了 $i-1$ 次正面, 第 $i$ 次投掷出反面, 然后剩下的 $n-i$ 次投掷的末尾恰好出现 $k$ 次连续正面的概率.

利用随机变量生成函数 $G_k(z) = \sum_{n=0}^\infty P_{n,k}z^{n}$. 有

\[\begin{equation} \begin{split} G_k(z)=\sum_{n=0}^\infty P_{n,k}z^n & =P_{k,k}z^k+\sum_{n=k+1}^\infty P_{n,k}z^n=P_{k,k}z^k+\sum_{n=k+1}^\infty \sum_{i=1}^k p^{i-1}(1-p)P_{n-i,k}z^n \\ & = P_{k,k}z^k+\sum_{i=1}^k p^{i-1}(1-p)z^i\sum_{n=k+i}^\infty P_{n-i,k}z^{n-i} \\ & = P_{k,k}z^k+G_k(z)\sum_{i=1}^k p^{i-1}(1-p)z^i \\ & = p^kz^k + \frac{(1-p)(p^kz^{k+1}-z)}{pz-1}G_k(z) \\ & = \frac{p^kz^k(1-pz)}{1+p^kz^{k+1}(1-p)-z} \end{split} \end{equation}\]

期望

\[\operatorname{E}(k) = G_k'(1^{-}) =\frac{1}{1-p}\left(\frac{1}{p^k}-1\right)\]

方差

\[\begin{equation} \begin{split} \operatorname{var}(k) &= G_k''(1^{-})+G_k'(1^{-})-\left[G_k'(1^{-})\right]^2 \\ &= -\frac{2k}{p^k(1-p)}+\frac{(1+p^{k+1})(1-p^k)}{p^{2k}(1-p)^2}\end{split} \end{equation}\]

期望和方差可以利用SymPy计算直接得到结果

import sympy as sp
k = sp.Symbol('k', integer=True, positive=True)
z, p = sp.symbols('z p', real=True, positive=True)
G = p**k*z**k*(1-p*z)/(1+p**k*z**(k+1)*(1-p)-z)
E = sp.simplify(sp.diff(G, z).subs(z, 1))
V = sp.simplify(sp.diff(G, z, 2).subs(z, 1) + E - E**2)

3.2 鞅(martingale)和随机行走

排队买票 TODO

绿皮书, P117

赌徒破产的概率

初始有1元, 每局可盈/亏1元, 10局后有3元, 求中途没有破产的概率

解答

使用反射原理来解决这个问题。

横坐标为局数, 纵坐标为当前金额. 初始点为 (0,1), 终点为 (10,3). 赢6次, 输4次, 共有 $\operatorname{C}_{10}^6$ 条路径从 (0,1) 到 (10,3).

---
config:
  xyChart:
    height: 400
    xAxis:
      showAxisLine: false
  themeVariables:
    xyChart:
      plotColorPalette: '#00FF00, #FF0000, #000000'
---
xychart
x-axis 0 --> 10
y-axis -1-->5
line "未破产" [1,2,3,2,3,4,3,4,5,4,3]
line "破产" [-1,0,1,0,1,2,1,2,3,2,3]
line [0,0]

如果中途破产, 则有一条对称的路径从 (0,-1) 到 (10,3), 这条路径一定会经过 $y=0$ 这条线, 赢7次, 输3次, 共有 $\operatorname{C}_{10}^7$ 条路径从 (0,-1) 到 (10,3).

故未破产的概率为 $1-\frac{\operatorname{C}_{10}^7}{\operatorname{C}_{10}^6}=\frac{3}{7}$.

赌徒破产2

赌徒初始有 $t$ 元, 盈/亏1元的概率分别为 $p$ 和 $q=1-p$, 赌到 $N$ 元或者破产, 求不破产概率.

解答

如果用鞅来算, $X_i$ 表示第i局身上有多少钱, $Y_i = (\frac{q}{p})^{X_i}$ 是一个鞅, 设不破产概率为 $P$, 则有 $\mathbb{E}[Y_\tau]=P(q/p)^N+(1-P)(q/p)^0=\mathbb{E}[Y_0]=(q/p)^i$, 解得

\[P=\frac{1-\left(\frac{q}{p}\right)^t}{1-\left(\frac{q}{p}\right)^N}\]

如果用递推关系, 设 $P_i$ 表示从 $i$ 元开始, 最终不破产的概率, 有

\[P_i = \begin{cases} 0, & i = 0 \\ 1, & i = N \\ pP_{i+1} + qP_{i-1}, & 0 < i < N \end{cases}\]

第三式化简, 令 $q/p=r$,

\[\begin{align*}\frac{P_{i+1}-P_i}{P_i-P_{i-1}} = r\\ P_{i+1}-P_i=Cr^i\\ P_i=C\sum_{i=0}^{i-1}r^i+P_0=C\frac{1-r^i}{1-r}\\ P_N=C\frac{1-r^N}{1-r}=1\Rightarrow C=\frac{1-r}{1-r^N}\\ P_i=\frac{1-r^i}{1-r^N}=\frac{1-(q/p)^i}{1-(q/p)^N} \end{align*}\]

4. 算法与数据结构

4.1 复杂度分析

4.2 排序与查找

4.3 哈希

4.4 堆与优先队列

4.5 树与图

4.6 DFS / BFS

4.7 动态规划

4.8 贪心

4.9 二分

4.10 双指针与滑动窗口

4.11 分治

4.12 随机化算法

5. 金融数学

5.1 期权定价

5.2 Black-Scholes

5.3 Greeks

5.4 期权组合

5.5 奇异期权

5.6 固定收益

5.7 无套利与套利

5.8. 量化问题

1. A Practical Guide to Quantitative Finance Interviews ↩︎