趣题摘记-概率和期望

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

文章内容	简介
奇思妙想	数学和计算机领域，通过小小思考后能豁然开朗的趣题。
概率和期望	数学和计算机领域，与概率和期望相关的趣题。
算法题精选-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.$