趣题摘记-概率和期望

这一系列文章记录了我遇到过的一些 趣题。

文章内容	简介
奇思妙想	数学和计算机领域，通过小小思考后能豁然开朗的趣题。
概率和期望	数学和计算机领域，与概率和期望相关的趣题。
算法题精选-1	OI/ICPC 向的算法题，去其琐碎、留其精髓，望博君一笑。
算法题精选-2	OI/ICPC 向的算法题，相比上一期题意更简洁，出处往往不可考

简单游走问题

题意：初始时你在数轴的位置 $0$ 处，每单位时间能向左/右走一格。问第一次走到 $1$ 的期望步数。

解法一：设 $f_i$ 表示正好向右走了 $i$ 步的期望。得 $f_i=\frac{1}{2}(f_{i-1}+f_{i+1})+1$ 且 $f_0=0$，联立化简后得 $f_i = 2f_{i-1}-f_{i-2}-2(i \geq 2)$。继续化简得 $f_i=(3i-4)f_1-(i-1)i$。我们要求的是 $f_1$。假设 $f_1=x$，则 $f_n=(3n-4)x-(n-1)n$，当 $n \rightarrow +\infty$ 时 $f_n \rightarrow -\infty$，显然矛盾。所以 $f_1=+\infty$。

解法二：设 $f_1$ 表示正好向右走了一步的期望。注意期望是有可加性的，所以$f_1=\frac{1}{2}(0+2f_1)+1$，化简得 $f_1=f_1+1$。显然 $f_1=+\infty$。

构造固定概率的函数

题意：一个函数 $f()$ 会以 $p$ 的概率返回 $1$，以 $1-p$ 的概率返回 $0$。构造一个函数 $g()$，以正好 $0.5$ 的概率返回 $0$ 和 $1$。注意：$p$ 是一个固定但是未知的概率。此题在 知乎 上有详细讨论。

解法：连续调用两次 $f()$，显然返回 $01$ 和 $10$ 的概率相同，我们可以根据这个来决定 $g()$ 的返回，如果返回值相同，就继续这么操作。显然，当 $p \rightarrow 0/1$ 时，这个的期望步数趋于无穷大。

改进后解法：我们可以设计算法使期望步数进一步下降。对于询问序列的一个前缀长度 $n$，一旦 $C_n^m$ 是偶数（$m$ 是返回的 $1$ 的个数），其实我们就能立即结束并得到返回值（总能分成两半）。如何决定返回什么呢？每次看当前 01 序列和它的回文哪个字典序小，一样就递归一半，复杂度 $O(N)$ 。

找号码牌的概率题

题意：有 $100$ 个人编号为 $1 \sim 100$，对应他们编号的 $100$ 个号码牌被打乱放在了$100$ 个抽屉里。每个人可以打开至多半数的抽屉，并从中找出对应自己编号的号码牌。只有所有人都找到了自己的号码牌，任务才算成功（所有人会依次独立地操作，彼此不能交流，操作完后所有抽屉都会复原）。假设抽屉的各种放置状态出现的概率均等，设计一种固定的策略，所有人都成功的概率尽可能的大。

策略：首先打开自己号码的抽屉，如果没中，继续打开抽屉里号码牌对应的抽屉……重复 $50$ 次。

成功概率计算：显然，所有人都能找到自己，当且仅当所有圆环的长度不超过 $50$。

下面就是要计算，对于一个随机排列，置换环长度全都不超过 $50$ 的概率是多少。容斥。从 $100$ 个数中选出 $m(> 50)$ 个数构成大环（剩下的随便排）的方案数是：$C_{100}^m \cdot (m-1)! \cdot (100-m)!$。

所以最终答案为 $P=1-\sum \limits_{m=51}^{100} \frac{1}{m}$。且当 $n \rightarrow \infty$ 时，$P \rightarrow 1-\ln{2}$。

抛硬币使得连续两次正面朝上

题意：抛一枚质地均匀的硬币。问期望多少次抛出连续两个向上。

解法：这一类期望问题都不宜直接在序列上计算，可以直接根据概率的意义计算。设 $f_i$ 表示连续抛出 $i$ 个向上的期望抛硬币次数。显然 $f_1=2,f_i=f_{i-1}+1+\frac{1}{2}f_i$，化简得 $f_i=2f_{i-1}+2$，原问题里 $f_2=6$。

正面是反面两倍的概率

题意：抛一枚质地均匀的硬币，一旦正面朝上次数不低于反面朝上次数的两倍就停止，求能无限进行的概率。

转化问题：考虑一个初始在 $x=-1$ 的质点，每次有 $\frac{1}{2}$ 的概率向右移动一步，还有 $\frac{1}{2}$ 的概率向左移动两步。在 $x=0$ 处有一个吸收壁，求小球不被吸收的概率。

题解：假设小球被吸收的概率是 $p$，则 $p=\frac{1}{2}+\frac{1}{2}p^3$，解得 $p=\frac{\sqrt 5-1}{2}$。

最大化正好获得一个礼物的概率

来源：2019 Multi-University Training Contest 10 C by chenjb

题意：有 $n$ 个包裹，第 $i$ 个包裹有 $p_i$ 的概率存放着礼物。现在要选择一个包裹的子集，使得全打开后正好获得一个礼物的概率尽量的大。

分析：如果已经知道选择的集合，答案显然是 $\sum \limits_k p_k \prod \limits_{i \ne k} (1-p_i)$。

记已经打开的包裹中没有礼物的概率是 $s_0$，恰好有一个礼物的概率为 $s_1$。那么，再打开一个概率为 $p$ 的包裹会使 $(s_0, s_1) \rightarrow (s_0 (1 - p), s_1 + (s_0 - s_1) p)$。显然，当 $s_0 \leq s_1$ 时加入任何包裹都不会使答案变优。类似地，如果删除一个礼物之后 $s_0 \leq s_1$，那么删除这个包裹不会使答案变得更差。因此，任意一个最优解对应的非空包裹集合 $G$ 都满足 $s_0 \leq s_1$，且该集合每个真子集均有 $s_0 > s_1$，也即 $\forall T \subsetneqq G, \frac{s_1}{s_0} = \sum \limits_{p \in T}{\frac{p}{1 - p}} < 1$。

不难发现 $\frac{p}{1 - p}$ 和 $p$ 的单调性相同，因此，如果一个满足上述条件的非空包裹集合 $G$ 不是由包含礼物概率最大的那些包裹构成，那么可以把集合内概率最小的包裹 $a$ 换成集合外概率最大的包裹 $b$，从而得到一个答案不会更劣的包裹集合 $(G - \lbrace a \rbrace) \cup \lbrace b \rbrace$。设新集合中概率最小的包裹为 $c$，新集合的真子集 $((G - \lbrace a \rbrace) \cup \lbrace b \rbrace) - \lbrace c \rbrace$ 可能不满足 $s_0 > s_1$，此时可以不断地删去集合中概率最小的包裹，直到该集合满足条件。这个过程不会使答案变劣，不断地替换和删除包裹可以得到最优解。

结论：按照概率从大到小的顺序打开包裹直到 $s_0 \le s_1$ 或者全部打开为止，可得到一个最优解。

不放回随机采样的实现

题意：有 $n$ 个物品，分别有权重 $w_i$，现在要不放回地选取其中的 $k$ 个物品，设计一种采样方法使得：每轮每个物品被选中概率是它的权重与剩余所有物品权重和的比值。

模拟解法：每一轮我们在 $[0,\sum \limits_{i \in rest}w_i)$ 随机一个数，然后去定位这个数字所在的前缀和位置。可以用树状数组来加速模拟这一过程。复杂度 $O(n+k\log N)$。

正解：本题有一个 等价转化。经过转化后，我们可以对每一个物品设一个随机变量 $u_i \sim (0,1)$，注意不同物品的 $u_i$ 条件独立。对于每个物品，它的概率估价值 $p_i=u_i^{1/w_i}$。回到原题，如果要不放回地选取其中的 $k$ 个物品，我们直接把 $u_i$ 按从大到小排，取前 $k$ 大即可。

简略证明：只考虑两个物品，假设他们的权重分别是 $a$ 和 $b$ 。

$$\begin{align} \mathcal{P}(x=a)&=\int_{0}^1 \int_0^1 [x^{1/a} \ge y^{1/b}]~dx~dy \\ &=\int_{0}^1 dx \int_{0}^{1} [y \le x^{b/a}]dy \\ &=\int_{0}^1 x^{b/a}dx \\ &=\frac{a}{a+b} \end{align}$$

石头剪刀布只能出两个

题意：两个人绝顶聪明的人猜拳，甲只能出石头和剪刀，乙都可以出。双方玩无限次。每次胜利记 1 分，平局记 0 分，失败记 -1 分。双方都希望自己的得分尽量高。问无限局下情况如何。

结论1：乙出石头永远不会输。其实这个结论对解这道题没啥帮助= =。

结论2：乙永远不可能出剪刀。因为乙可以把出剪刀的局全部替换成石头，一定不会变劣。

总结：这样双方其实都只能出两个。不妨设双方各执最优策略下甲出石头和剪刀的概率分布是 $a,b$，乙出石头和步的概率分布是 $x,y$，我们有乙得分期望 $E=bx+ay-by=-1+2a+2x-3ax$。$E$ 对 $x$ 求偏导解得 $a=\frac{2}{3}$。同理解得 $x=\frac{2}{3}$。即在无限局情况下，甲获胜的概率是 $\frac{1}{9}$，乙获胜的概率是 $\frac{4}{9}$。

等概率乘 1.1 或 0.9

来源：知乎上的 讨论。

圣彼得堡悖论

来源：知乎的 讨论，是 A Probability Path by Sidney I. Resnick 中名为 St. Petersburg paradox 的例子。

题意：如果有一个游戏，有 $2^{-n}$ 的概率获得 $2^n(n \ge 1)$ 元，那么玩 $n$ 场期望能赢多少钱？

直接转化：随机变量 $X$ 服从离散分布 $P(X=2^k)=2^{-k},k=1,2,\dots$，则 $E(x)=+\infty$ 确实成立。

悖论：如果我们玩 $n$ 次游戏（每次游戏都是独立同分布的），当 $n \rightarrow +\infty$ 时，由大数定律可得样本均值可以逼近总体均值，也就是说平均每把游戏可以赢 $+\infty$ 元。但感觉实际操作不会赢那么多！

解释：大数定律的条件之一是 $E|X_i|<+\infty$，所以上述描述不满足大数定律，即无法推出相关结论。

最终结论：经过 General Weak Law of Large Numbers 的 一系列推导 后可得：

$$\frac{S_n}{n \log_2n} \xrightarrow{p} 1$$

即当我们玩的次数 $n$ 足够大的时候，可以用 $n \log_2n$ 去近似玩 $n$ 次游戏总共赢得的钱。

三个随机变量的相关系数

来源：知乎讨论-王赟的回答

题意：三个随机变量 $A,B,C$。设 $x,y,z$ 分别是 $AB,AC,BC$ 的相关系数，求当 $x,y$ 确定时 $z$ 的取值范围。

题解：列出协方差矩阵

$$M=\left[ \begin{array}{ccc}1 & x & y \\x & 1 & z\\y & z & 1 \end{array} \right]​$$

由于方差非负，所以 $M$ 必须是半正定矩阵。又因为 $M$ 是实对称阵，等价于它的三个特征值均非负。

特征方程 $|\lambda I - M|$ 是一个关于 $\lambda$ 的一元三次方程：

$$(\lambda - 1)^3 - (x^2+y^2+z^2) (\lambda - 1) - 2xyz = 0 \\ \lambda^3 - 3\lambda^2 + (3-x^2-y^2-z^2)\lambda + (x^2+y^2+z^2-2xyz-1) = 0$$

如果方程 $\lambda^3+b\lambda^2+c\lambda+d=0$ 有三个实根 $\lambda_1,\lambda_2,\lambda_3$，则三个实根均非负的充要条件是：

$$\left\{ \begin{array}{lc}b = -(\lambda_1+\lambda_2+\lambda_3) \le 0 & (1) \\c = \lambda_1\lambda_2 + \lambda_1\lambda_3 + \lambda_2\lambda_3 \ge 0 & (2) \\d = -\lambda_1\lambda_2\lambda_3 \le 0 & (3)\end{array} \right.$$

由于 $-1\le x,y,z \le 1$，前两个式子必定满足，等价于下列不等式恒成立：

$$x^2+y^2+z^2-2xyz-1 \le 0$$

如果 $x,y$ 已知，把方程看做是 $z$ 的一元二次方程，即

$$z^2 - 2xyz + (x^2+y^2-1) \le 0$$

注意到判别式 $\Delta = 4(1-x^2)(1-y^2) \ge 0$，那么该不等式的解为 $z_1 \le z \le z_2$，即

$$xy-\sqrt{1-x^2}\sqrt{1-y^2} \le z \le xy+\sqrt{1-x^2}\sqrt{1-y^2}$$

数形结合：尝试用三角函数换元去分析这个结果。

因为 $-1\le x,y,z \le 1$，分别设它们为 $x = \cos\alpha, y = \cos\beta, z = \cos\gamma$，其中 $\alpha, \beta, \gamma \in [0,\pi]$。

那么上述的结果等价于 $\cos\alpha \cos\beta - \sin\alpha \sin\beta \le \cos\gamma \le \cos\alpha \cos\beta + \sin\alpha \sin\beta$。

三角恒等变换可得 $\cos(\alpha+\beta) \le \cos\gamma \le \cos(\alpha-\beta)$，即 $|\alpha - \beta| \le \gamma \le \min(\alpha + \beta, 2\pi - \alpha - \beta)$

说明这里的随机变量可以看成无穷维空间的向量，协方差是它们的内积，而相关系数是向量的夹角的余弦。