算法问题
1. 逻辑题
蓄水池抽样
从包含 $n$ 个项目的集合 $S$ 中选取 $k$ 个样本，其中 $n$ 为未知量
解答
- 从 $S$ 中抽取首 $k$ 项放入「水塘」中
- 对于每一个 $S[j] (j\ge k)$ 项：
- 随机产生一个范围从 0 到 $j$ 的整数 $r$
- 若 $r<k$ 则把水塘中的 $r$ 项换成 $S[j]$ 项
水桶取水问题
两个容积确定的水桶, 取定量的水
解答
记容积为 $a$ 和 $b$, 取定量的水为 $c$, 则有以下几种情况:
- $c > \max(a, b)$, 无解
- $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 首步分析
全概率公式 $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)$
- 先走一步，然后根据第一步发生了什么分类。典型结构: $E=1+\sum P_i E_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}$.
先抛到硬币正面
甲乙轮流抛硬币谁先抛到正面谁赢.甲先手甲获胜概率是多少？
解答
若概率为 $P$, 抛第一次
- 0.5概率正面→赢
- 0.5概率反面→乙抛
- 0.5概率正面→输
- 0.5概率反面→回到初始情况
$P=0.5\times 1+0.5\times(0.5\times 0+0.5\times P)$, 解得 $P=2/3$.
2.2 状态转移
概率计算方法: 递推关系(转移矩阵求解, 或者齐次指数展开求解), 最后得到通项公式
- 马尔科夫链的状态转移. 定义多个状态, 从这个状态出发，下一步会转移到哪些状态？
根据骰子向前走
一个人扔六面的骰子，数值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 都不怎么重要.
不公平的赌徒破产
一个人从10元开始每天以55%概率赚1元、45%概率亏1元. 到0元破产或到20元停止。求到20元的概率.
解答
使用递推公式, 设当前为 $i$ 元时, 赚20元的概率是 $a_i$.
\[\begin{aligned}a_0&=0\\ a_{20}&=1\\ a_i&=0.55a_{i+1}+0.45a_{i-1}, \quad 1 \leq i \leq 19\end{aligned}\]齐次方程的特征方程为 $\lambda=0.55\lambda^2+0.45$, 解得 $\lambda_1=1, \lambda_2=0.45/0.55$. 故通解为 $a_i=c_1+c_2(0.45/0.55)^i$.
利用边界条件 $a_0=0$ 和 $a_{20}=1$, 可以解得 $c_1=0$ 和 $c_2=\frac{1}{(0.9)^{20}}$. 因此,
\[a_i = \frac{1-(9/11)^i}{1-(9/11)^{20}}\]赌徒破产-博弈轮次的条件期望
甲有2元, 公平博弈, 5元获胜. 在最终破产的情况下, 求博弈轮次的期望
解答
条件期望没办法用鞅, 只能用递推(状态转移).
$P_i(t)$ 表示初始有 $i$ 元的情况下, $t$ 轮后游戏结束. $B$ 表示是通过破产(而不是获胜)让游戏结束.
\[\begin{aligned}E_i[t\mid B] &=\sum_{t=0}^{\infty}tP_i(t\mid B)\\ &=\sum_{t=0}^{\infty}t\cdot\frac{P_i(t,B)}{P_i(B)}\\ &=\frac{1}{P_i(B)}\sum_{t=0}^{\infty}tP_i(t,B) \end{aligned}\]根据公平博弈的鞅, $5\times(1-P_i(B))=i$, 得到 $P_i(B)=\dfrac{5-i}{5}$.
下面对 $tP_i(t,B)$ 递推. $P_i(t,B)$ 表示初始有 $i$ 元的前提下, 经过 $t$ 轮破产的概率.
博弈一次后, 赚1元和亏1元的概率都为0.5.
令 $f_i=\sum_{t=0}^{\infty}tP_i(t,B)$, 则有递推关系 $f_i = \frac{1}{2}f_{i+1} + \frac{1}{2}f_{i-1} + \frac{5-i}{5}$ 和边界条件 $f_0=f_5=0$.
这种递推方程用线性方程求解的方法, 假设 $f_i=ai^3+bi^2+ci+d$ 代入可以得到 $f_i=\dfrac{i^3}{15}-i^2+\dfrac{10i}{3}$.
因此 $f_2=\dfrac{16}{5}$, 原题为 $\dfrac{f_2}{P_2(B)}=\dfrac{16}{3}$.
硬币最长连续正面的期望
连续抛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}$ 的系数位置上, 这样当展开后, 通过观察系数可以得到数列的通项公式. 令
隐去下标, 左右两边分别乘以 $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}\]掷骰子出连续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}\]- 概率 ${\displaystyle p(k)=\operatorname {Pr} (X=k)=\frac {G^{(k)}(0)}{k!}}$
- 期望 $\displaystyle \operatorname {E} [X]=G^\prime(1^{-})$
- 方差 $\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}$
- $k$-阶矩 kth raw moment ${\displaystyle \operatorname {E} [X^{k}]=\left.\left(z{\frac{\partial }{\partial z}}\right)^{k}G(z)\right\vert_{z=1^{-}}}$
- 矩生成函数 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$ 分类讨论, 有
右边第 $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计算直接得到结果
1
2
3
4
5
6
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)
不重叠5连黑的期望
考虑一行20个相邻的无色方格。将每个单独方格以相等概率涂成黑色或白色，并且各方格相互独立。一个连通的5-连通组是一组5个连续黑色方格。
注意，重叠的连通组不计数。例如，WBBBBBWWB 和 WBBBBBBWB 有1个连通的5-连通组，但WBBBBBBBBBBW 有2个连通的5-连通组。
求这行方格中连通5-连通组的期望数量。
解答
一段连续黑格长度为 $n$, 它应贡献 $\lfloor n/5 \rfloor$ 个连通5-连通组.
令 $C_k$ 为长度为 $k$ 的全黑窗口的期望数量, 这样的窗口可以开 $21-k$ 个, 每个窗口全黑的概率是 $2^{-k}$, $C_k = \frac{21-k}{2^k}$.
为了凑出 $\lfloor n/5 \rfloor$, 总期望 $E=C_5-C_6+C_{10}-C_{11}+C_{15}-C_{16}+C_{20}=284785/1048576$.
2.3 期望、方差与协方差
一般方法: 期望的递推关系, 利用对称性求出期望, 其实也是一种动态规划
均匀分布的期望
每次均匀随机取 $[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 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}$，这直接给出了单个间隔的分布规律。 体积
\[V_{N-1}(t)=\frac{t^{N-1}}{(N-1)!}\]
对于一般情况 $X_1,\cdots,X_N\geq0, \sum_{i=1}^N X_i=t$, 它是一个 $N-1$ 维单纯形, 它的标准坐标体积是
回到原题, 令 $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$.
单纯形2
在区间（0,1）中抽取101个均匀随机数求所选数值中任意两个之间的距离都不小于1/1000的概率。
解答
抽取的101个随机数 $X_1,\cdots,X_{101}\overset{\text{i.i.d.}}{\sim}U(0,1)$, 要求任意两个之间距离都至少为1/1000.
若没有1/1000的限制, 原题转化成单纯形这种几何区域的”体积”.
排序后的随机数 $0<X_1<\cdots<X_{101}<1$, 定义间隔 $Y_i=X_{i+1}-X_i, i=0,\cdots,101$, 其中 $X_0=0, X_{102}=1$.
则有 $Y_i>0, \sum_{i=0}^{101}Y_i=1$, 也就是 $(Y_0,\cdots,Y_{101})$ 构成了一个101维单纯形 $\Delta_{101}$, 服从参数为 $(1,1,\cdots,1)$ 的Dirichlet分布.
对应的 ${X_i}$ 是 101 维超立方体 $[0,1]^{101}$ 的一个子集, 体积为 $V_{101}(1)=\frac{1^{101}}{101!}=\frac{1}{101!}$.
这个结果是在排序后得到的, 即只考虑了一个排列, 因此最终区域体积为 $101!\times V_{101}(1)=1$.
加上1/1000的限制, 则有 $Y_i\geq 1/1000, i=1,\cdots,100$, 则 $(Y_0, Y_1-1/1000,\cdots,Y_{100}-1/1000, Y_{101})$ 服从参数为 $(1,1,\cdots,1)$ 的Dirichlet分布, 且 $\sum_{i=0}^{101}(Y_i-1/1000)=9/10$.
因此有效的区域体积为 $101!\times V_{101}(9/10)=0.9^{101}$.
因此概率为 $0.9^{101}$.
期望会变化的公平价值
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$.
极值期望
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}$
离散极值期望
掷两枚公平骰子, 取较大点数作为收益, 期望收益是多少?
解答
如果最大值 $M=k$, 说明两枚骰子的点数都不超过 $k$, 且至少有一枚骰子点数为 $k$.
\[\begin{aligned}P(M\leq k)=\frac{k^2}{36}\\ P(M=k)=P(M\leq k)-P(M\leq k-1)\\ =\frac{k^2-(k-1)^2}{36}=\frac{2k-1}{36}\\ \mathbb{E}[M]=\sum_{k=1}^6 kP(M=k)=\sum_{k=1}^6 k\frac{2k-1}{36}=\frac{91}{36} \end{aligned}\]极值期望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}$.
故期望
随机蚂蚁
绿皮书1, P102
500只蚂蚁被随机放在一根1英尺长的绳子上（每只蚂蚁在0到1之间独立均匀分布）。每只蚂蚁以1英尺/分钟的恒定速度随机移动到绳子的一端（向左或向右的概率相等），直到它从绳子的一端掉下来。同时假设蚂蚁的大小是无限小的。当两只蚂蚁正面相撞时，它们都会立即改变方向，并以每分钟1英尺的速度继续移动。所有蚂蚁从绳子上掉下来的预期时间是多少？
解答
蚂蚁碰撞后等价于越过彼此继续前进, 每只蚂蚁掉落的预期时间为 $X\sim U(0,1)$. 所有蚂蚁掉落的预期时间为 $\max{X_1,\cdots,X_{500}}$.
由极值期望, 有 $\mathbb{E}[\max(X_1,\cdots,X_{500})]=\frac{500}{501}$.
见面的概率
N个人在9:00到10:00之间独立且均匀随机地到达。每个人恰好等待15分钟。求所有N个人同时在场的概率。
解答
固定一个最早来的人, 那么为了所有人同时在场, 就需要其他人都在 $[x, x+0.25]$ 的时间范围内到场.
对于任意分布来说, 分两种情况
- 来的最早的人的时间 $x<0.75$
设A来的最早, 由于对称性这样的选择有N种. 其他人只有在 $[x, x+0.25]$ 的时间范围内到场, 概率为 $0.75\times 0.25^{N-1}$. 还得乘以N种选择, 因为前面得到的概率只适合于A来的最早这种情况. - 来的最早的人的时间 $x\geq0.75$
即要求所有人在 $[0.75, 1]$ 的时间范围内到场, 概率为 $0.25^N$
这两种情况是互斥的, 因此可以直接相加. 那么总概率
\[P = N\frac{3}{4}\cdot\left(\frac{1}{4}\right)^{N-1}+\left(\frac{1}{4}\right)^{N}=\frac{3N+1}{4^N}\]为什么不可以用全概率的方法, 考虑最小值3/4概率在[0,0.75]范围内, 1/4概率在[0.75,1]范围内?
因为限定了最小值之后, 其他人的分布就不是均匀分布了.
若将最小值在[0,0.75]范围内作为前提条件, 其他人出现在[x, x+0.25]的概率为 $(\frac{0.25}{1-x})^{N-1}$, 同时, 最小值的密度 $f(x)=\lvert P^\prime(x\geq x_1)\rvert=-((1-x)^N)^\prime=N(1-x)^{N-1}$.
因此这个部分的概率为 $\int_0^{3/4}N(1-x)^{N-1}\left(\frac{0.25}{1-x}\right)^{N-1}dx=\int_0^{3/4}N(0.25)^{N-1}dx=3N/4^N$.
所有点在同一边
在圆周上独立均匀随机取n个点，存在某个长度为半个圆周的连续圆弧覆盖全部点的概率是多少
将某个点当作”最左边的点”, 其他所有点都在它顺时针的半个圆弧中的概率是 $\frac{1}{2^{n-1}}$. 由于有n个点, 因此总概率为 $\frac{n}{2^{n-1}}$.
连通块期望
有100个格子排成一排，每个格子独立地以1/2的概率染成黑色、以1/2的概率染成白色。把颜色相同且连续的一段称为一个“连通块”(连续同色段)。求连通块数量的期望值。
解答
定义指标变量, 对每个位置 $i$ 定义指标变量 $I_i$.
$I_1=1$, 因为第一个各自一定会开启一个连通块.
对于 $i\leq 2$, 若第 $i$ 个格子的颜色与第 $i-1$ 个不同, 则 $I_i=1$, 否则 $I_i=0$.
因此期望为 $I_1+\cdots I_{100}$.
计算每一项的期望
$E[I_1]=1$.
对于 $i>1$, $I_i=1$ 当且仅当第 $i$ 个格子的颜色与第 $i-1$ 个不同, 这种情况的概率是 $\frac{1}{2}$.
因此 $E[I_i]=\frac{1}{2}$.
所以期望为
\[\mathbb{E}[I_1+\cdots I_{100}]=E[I_1]+\cdots+E[I_{100}]=1+\frac{1}{2}\times 99=\frac{101}{2}.\]2.4 鞅(martingale)和随机行走
排队买票
绿皮书, P117
n 个人有$5, n个人有$10 排队买$5的票, 售票处初始状态没有钱. 顺利完成这2n个交易的概率是多少.
解答
等价于 有n个+1, n个-1的随机游走, 以 $(0,0)$ 为起点, 终点为 $(2n,0)$, 且中途不低于0的概率. 同赌徒破产的概率类似, 只是前者要触及的线是 $y=-1$, 后者要触及的线是 $y=0$.
考虑何时交易失败: 某个时刻-1的数量比+1多, 即折线触及 $y=-1$. 只有触及 $y=-1$ 的折线(的前半部分)可以做关于 $y=-1$ 的对称, 相当于起始点是 $(-2,0)$, 终点是 $(2n,0)$, 共有 $\operatorname{C}_{2n}^{n+1}$ 条路径.
---
config:
xyChart:
height: 400
xAxis:
showAxisLine: false
themeVariables:
xyChart:
plotColorPalette: '#FF0000, #00FF00, #000000'
---
xychart
x-axis 0 --> 10
y-axis -5-->3
line "失败" [0,1,2,1,0,-1,0,1,2,1,0]
line "对称" [-2,-3,-4,-3,-2,-1,0,1,2,1,0]
line [0,0]
故概率为 $1-\frac{\operatorname{C}{2n}^{n+1}}{\operatorname{C}{2n}^n}=\frac{1}{n+1}$.
赌徒破产的概率
初始有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*}\]圆周遍历
圆周上有n个点，从一点出发，每次等可能地移动到相邻点，平均几次走完所有点？
解答
访问过的点肯定可以连起来, 设已经访问了 $k$ 个点, 访问第 $k+1$ 个点的期望是 $E_k$.
相当于随机游走, 初始位置是 $k$, $k+1, 0$是吸收壁. 所处位置的随机变量为 ${X_i}$, $X_i$ 和 $X_i^2-i$ 都是鞅.
\[\begin{aligned} E[X_0]=k=E[X_\tau]=p(k+1)\\ p=\frac{k}{k+1}\\ E[X_\tau^2-\tau]=p(k+1)^2-E[\tau]=E[X_0^2-0]=k^2\\ E[\tau]=p(k+1)^2-k^2=k \end{aligned}\]因此总时间为 $E_1+\cdots+E_{n-1}=\frac{n(n-1)}{2}$.
2.5 排列组合
球盒问题
$n$ 个球放到 $m$ 个盒子中, 允许空盒子, 有几种放法?
解答
相当于 $n+m$ 个球放到 $m$ 个盒子中, 不允许空盒子
使用隔板法, 就是 $\operatorname{C}_{n+m-1}^{m-1}$
不同球的球盒问题
把10个不同球放入4个不同盒子, 每个盒子至少一个球，有几种放法？
解答
无法使用隔板法, 用容斥原理. 每个球可以放到4个盒子中, 总共有 $4^{10}$ 种放法.
排除有空盒子的情况
- 有1个空盒子, 那么有 $\operatorname{C}_4^1\cdot 3^{10}$ 种放法
- 有2个空盒子, 那么有 $\operatorname{C}_4^2\cdot 2^{10}$ 种放法
- 有3个空盒子, 那么有 $\operatorname{C}_4^3\cdot 1^{10}$ 种放法
因此答案为 $4^{10}-\operatorname{C}_4^1\cdot 3^{10}+\operatorname{C}_4^2\cdot 2^{10}-\operatorname{C}_4^3\cdot 1^{10}$
间隔法求期望
一副52张扑克牌平均翻几次才能看到第一张A
解答
可以使用递推公式, 也可以用间隔法
52张牌中有4个A, 相当于4个A把剩下的48张牌分成了5个部分
非A - A1 - 非A - A2 - 非A - A3 - 非A - A4 - 非A
由于对称性, 这5个空隙(非A)的期望长度相同, 为 48/5
那么第一张A的位置期望就是 $48/5+1=10.6$.
非常巧妙, 是离散版的顺序统计量.
数字和
有多少个小于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$.
区域划分
圆上N个点两两相连, 最多可分成多少个区域
解答
想要区域数最大, 要求圆内没有三条弦交于同一点.
对于N个点已经划分好的图形, 若再加上一个点, 会多出N条弦.
研究其中的一条弦, 设这条弦会与其他弦产生k个交点, 那么这条弦会被分成k+1段, 每一段都可以划分出一个新的区域. 因此每条弦会产生k+1个新的区域. k由每个内部点贡献, 1由每条弦贡献.
每个内部交点恰好对应圆周上任选4个点后两个对角线的交点, 那么整个图形的内部点一共有 $\textrm{C}_N^4$ 个交点
弦的数量为 $\textrm{C}_N^2$
因此最多可分成 $\textrm{C}_N^2+\textrm{C}_N^4+1$ 个区域. 1为初始的区域数.
蚂蚁相遇
10 只蚂蚁等间距站在一个圆周上。 每只蚂蚁独立选择： 顺时针； 或逆时针。 之后所有蚂蚁以相同速度运动，恰好 1 分钟绕圆一周。当两只蚂蚁相遇时，它们立刻同时反向继续走。所有蚂蚁都是可以区分的。 一分钟后，所有蚂蚁都恰好回到自己原来的位置的概率是多少？
解答
蚂蚁弹性碰撞, “相当于”越过彼此保持原有方向继续往前走. 1分钟后10只蚂蚁(不分彼此的情况下)回到了原来的位置.
实际上2号蚂蚁永远加载1和3号蚂蚁之间, 即相当于整体向右方移动了 $x$ 格. (每个蚂蚁占了一格)
设初始状态有 $x$ 个顺时针运动, $10-x$ 个逆时针运动, 整个系统净绕行的圈数为 $x-(10-x)=2x-10$, 要求回到原来位置, 等价于要求圈数是 10 的倍数 $2x-10 \mod 10\equiv 0$, 即 $x=0,5,10$.
因此概率为 $\frac{1+\operatorname{C}_{10}^5+1}{2^{10}}=\frac{257}{1024}$.
循环的期望
设 $C_n$ 表示 ${1,2,\cdots,2n}$ 的一个随机排列中循环的个数, 求 $\mathbb{E}[C_n]$.
解答
随机排列的标准结论: 长度为 $k$ 的循环的期望个数为 $1/k$.
因此, $E=\sum_{k=n+1}^{2n}\frac{1}{k}$.
4. 算法与数据结构
4.1 枚举
- 回文字符串
对每个字符遍历, 以该字符为中心向两边扩展, 直到不满足回文条件.
Manacher 算法, 复杂度 O(n), 维护一个回文半径数组, 对于每个字符, 如果在回文半径内, 那么可以直接得到回文半径, 否则就向两边扩展.
4.2 排序与查找
4.3 哈希
4.4 堆与优先队列
4.5 树与图
4.6 DFS / BFS
4.7 动态规划
4.8 贪心
4.9 二分
寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
解答
使用二分法
用更小的长度的数组做二分法
中位数的特点就是, 存在一个分割线, 所有左边的数都小于分割线的右边的数. 当然还要求左右的长度差不超过1.
二分法确定的位置和要求的中位数的位置是无关的, 只是用来确定分割的位置. 把要选取的值放在分割线的左边或是右边都可以.
因为中位数要分长度奇偶, 奇数只看 n//2 的位置, 偶数要看 n//2 和 n//2-1 的位置. 所以下面的例子把奇数的中位数放在分割线的右边, 偶数的中位数放在分割线的两边.
除了确定了分割线两边的长度, 还需要考虑到边界条件.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
if len(nums1) > len(nums2):
"""
长度更小的更容易
而且可以保证二分法在nums1上游动时, nums2的分割线不会越界
"""
nums1, nums2 = nums2, nums1
size1 = len(nums1)
size2 = len(nums2)
l1 = 0
r1 = size1
half_len = (size1 + size2) // 2
"""
若总长是偶数, 左边N/2, 右边N/2, 取第N/2和第N/2+1个数的平均值
若总长是奇数, 左边N/2, 右边N/2, 取第N/2+1个数, 把这个数放在分割线的右侧
"""
while l1 <= r1: # 当l1=r1时直接给出结果
mid = (l1 + r1) // 2
right1 = nums1[mid] if mid < size1 else float("inf") # nums1右边第一个数
left1 = nums1[mid - 1] if mid > 0 else float("-inf") # nums1左边第一个数
right2 = nums2[half_len - mid] if half_len - mid < size2 else float("inf") # nums2右边第一个数
left2 = nums2[half_len - mid - 1] if half_len - mid > 0 else float("-inf") # nums2左边第一个数
if left1 > right2: # nums1的分割线太靠右
r1 = mid
elif left2 > right1: # nums1的分割线太靠左
l1 = mid + 1
else:
if (size1 + size2) % 2 == 0:
return (max(left1, left2) + min(right1, right2)) / 2
else:
return min(right1, right2)
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. 量化问题
A Practical Guide to Quantitative Finance Interviews ↩︎