绿皮书题目整理：概率论

基本概率定义和几何操作#

• outcome($\omega$)：试验结果
• 样本空间($\Omega$)：所有试验结果的集合
• 试验结果的概率$P(\omega)$：$P(\omega)\ge 0,\forall \omega\in \Omega, \sum\limits_{\omega\in \Omega}P(\omega)=1$
• 事件：试验结果和样本空间子集的集合
• 事件的概率(P(A))：$P(A) = \sum\limits _{\omega\in A}P(\omega)$

1 扔硬币游戏#

• 两个人扔硬币，A 有 n+1 个硬币，B 有 n 个硬币，问 A 正面向上的硬币比 B 多的概率是多少
• A 正面向上比 B 多和 A 背面向上是互斥事件，而且等概率，所以概率是 1/2

2 卡牌游戏#

• 52 张牌，随机打乱，你拿一张牌，对手拿一张牌，如果你的大你就赢，否则你就输了，赢得概率是多少？
• 只需要计算相等的概率P，然后（1-P）/2就行，相等的概率等于你随便取一张，然后在剩下的牌里只有三张保证为相等

3 喝醉的乘客#

• 100 个乘客找位置，第一个人喝醉了随机挑，后面的人按照规则挑，如果自己的位置还在就坐自己的座位；如果被人占了，就随机挑一个座位；问第 100 个人坐在自己座位上的概率是多少；
• 第一个人选第 1 个和选第 100 个的概率是一样的，两个都不选的话，则相当于让他选到的位置那个人成为喝醉的状态，他就相当于变成了第一个人，仍然在第 1 个和第 100 个之间做选择

4 一圈上的 N 个点#

• 给定 N 个点，随机放在一个圆周上，问在同一个半圆里的概率是多少？
• 对于每一个点，剩余 N-1 个点都落在它顺时针的那个半圆里的概率是 $(\frac{1}{2})^{N-1}$，而且每个点的这个事件彼此之间互斥（因为总有一段会大于 1/2），这样的话总的概率就是 $P = \sum\limits_{i}^{N} (\frac{1}{2})^{N}=N(\frac{1}{2})^{N}$

组合分析#

1 扑克手#

• 分别计算 Hands with a four-of-a-kind（五张卡牌里四张一样）、Hands with a full house（三张牌一样，另外两张牌一样）、Hands with 2 pairs的概率
• Hands with a four-of-a-kind: $\frac{13*12*4}{C_{52}^{5}}$
• Hands with a full house: $\frac{C_{13}^{2}*2*C_{4}^{3}*C_{4}^{2} }{C_{52}^{5}}$
• Hands with a two pairs: $\frac{C_{13}^{3}*3*C_{4}^{2}*C_{4}^{2}*4}{C_{52}^{5}}$

2 单腿跳兔子#

• 兔子上 n 级台阶，可以一次跳一级，也可以跳两级，问一共多少种路径
• 斐波那契数列

3 海盗分金2#

• 11 个海盗把赃款存在保险箱里，要求只有不少于 6 个人的时候，才能开箱，现在找来铁匠上锁，铁匠可以上很多锁，每把锁可以有很多钥匙，但是每把钥匙只能开一个锁，现在最少需要多少把锁？
• 任意五个人，至少要有一个锁这五个人打不开，所以至少要 $C_{11}^{5}$ 把锁

4 围棋锦标赛#

• $2^n$ 个人比赛，能力从高到低排，采取淘汰赛制，问第一强的和第二强的人在决赛相见的概率是多少
• 只要前面 n-1 次比赛都见不上就好了，所以结果是$\prod_{k}^{n-1}a_{k},a_{k}=\frac{2_{n}-2}{2_{n}-1}=\frac{2(2_{n-1}-1)}{2_{n}-1}$，裂项相消之后得到结果 $\frac{2^{n-1}}{2^{n}-1}$
• 也可以用二叉树的思路，只要第二名最开始不在和第一名同一个子树就好了

5 申请信#

• 5 封信都放错信封的概率是多少
• 容斥原理即可

6 生日问题#

• 一个班里至少要有多少个人，才能让至少两个人生日相同的概率大于$\frac{1}{2}$?
• $\frac{A_{365}^{n}}{365^{n}}$

7 第 100 个数字#

• $(1+\sqrt{2})^{3000}$ 的小数点后第 100 个数字是多少？
• 考虑 $(1+\sqrt{2})^{n}+(1-\sqrt{2})^{n}$ 是整数，所以只需要计算 $(1-\sqrt{2})^n$ 的部分，可定小于 $0.1^{100}$ 所以最后可能是 0

8 整数的立方#

• $x \in [1, 10^{12}]$，x 为整数，问 $x^{3}$ 以 11 结尾的概率是多少？
• $x = 10a+b$ 计算可得 $x^{3}= (10a+b) ^{3} = a^3+30a^2b+300ab^{2}+100b^{3}$ ，只需要 $a^{3}=1$，因此 $a =1$，所以 $30a^{2}b=30b$ 以 10 结尾，所以 $b$ 以 7 结尾。所以概率是 1%

条件概率与贝叶斯公式#

1 男孩女孩#

• 有一个家庭有两个孩子，已知其中一个是女孩，问另一个是女孩的概率是多少？
• 直接算
• 有一个家庭有两个孩子，现在看到一个女孩，问另一个是女孩的概率是多少？
• 1/2

2 女儿国#

• 如果世界里的父母都一直生，直到生出一个女孩为止，那么这个世界上有多少比例的女孩？
• 1/2

3 不公平的硬币#

• 1000 个硬币里，有一个两面都是头的硬币，其他都是正常的硬币，随机拿一个硬币，抛 10 次，结果都是头，问这个硬币是两面都是头的概率是多少？
• 使用贝叶斯公式$P(A|B) = \frac{P(B|A)P(A)}{P(B)}=\frac{2}{999*(\frac{1}{2})^{10}+2}$

4 不公平硬币下的公平概率#

• 一枚不均匀的硬币，如何产生公平概率？
• 只需要考虑正反和反正等价

5 飞镖游戏#

• Jason 丢了两次飞镖，第二次比第一次差，问第三次比第一次差的概率是多少？
• 只需要考虑三次飞镖的结果排序各种情况等概率，因此很容易算出来是 $\frac{n}{n+1}$

6 生日队伍#

• 影院排着队，如果有人的生日和已经拿到票的人的生日相同，那么这个人就会直接拿到票，问哪里位置最好
• 只需要考虑前面的人的生日各不相同且自己和前面的人生日相同的概率乘积，找到其最大值

7 骰子排序#

• 有 6 个骰子，随机投掷，问有大多概率服从升序
• 概率为三个骰子点数不同且三个数升序的概率

8 三门问题#

• 有三扇门，A、B、C，背后分别是汽车、山羊、山羊，先选一扇门，然后主持人打开另一扇有山羊的门，问换门的获胜概率是多少？
• 不换的话就和最开始的概率一样，换的话只需要最开始选错，所以概率是 2/3

9 变形虫数#

• 有一个变形虫，每一分钟可能会死亡、维持原样、分裂为 2 个或 3 个，概率相同，分裂后的变形虫会做出类似的行为，问变形虫灭绝的概率是多少？
• 使用全概公式$P(die~out)=1/4+1/4*P(die~out)+1/4*P(both~die~out)+1/4*P(three ~die~out)$解得$P(die~out)=\sqrt{2}-1$

10 罐里的糖果#

• 罐里有红色、绿色、蓝色糖果，红色 10 个，绿色 20 个，蓝色 30 个，随机一次拿出一个，问拿完红糖果之后剩下至少一个绿色糖果和蓝色糖果的概率是多少？
• 考虑这样一个统计量，最后一个被拿出的糖果所在的位置，分别记为 $T_{r},T_{g},T_{b}$，于是拿完红糖果之后剩下至少一个绿色糖果和蓝色糖果的等价于 $T_{r}<T_{g}\cap T_{r}<T_{b}=T_{r}<T_{g}<T_{b}\cup T_{r}<T_{b}<T_{g}$，这两个是互斥事件。$P(T_{r}<T_{g}<T_{b})=P(T_{b}=60)P(T_{r}<T_{g}|T_{b}=60)$，前者只需考虑 60 个球等概率地排在最后一个，后者只需要不考虑蓝球然后进行类似的分析即可。

11 扔硬币游戏#

• 两个人轮流扔硬币，如果出现 HT 游戏结束，而且投出 T 的人获胜。A 先投，A 获胜的概率是多少？
• $\begin{cases}P(A) = P(H)P(A|H)+P(T)(1-P(A))\\ P(A|H) =P(H)(1-P(A|H))\end{cases}$

12 俄罗斯轮盘赌#

• 俄罗斯轮盘赌，一颗子弹，打完之后不转动，先玩还是后玩？
• 先玩和后玩是等价的，概率都是 1/2，因为游戏一旦开始，位置就确定了
• 更改一下条件，如果每次扣动扳机之后都调整转盘，还是一样的吗？
• 不一样，这时候就不一样了，因为 $p = \frac{1}{6}+ \frac{5}{6}(1-p)$
• 如果这时候放了两颗子弹，有个人打了一发没中，接下来轮到你选择，你转不转轮盘？
• 这个时候如果不转，那就是 $2/5$，否则就是 $2/6$
• 如果放了两颗连续的子弹呢？
• 如果不转，那就是 $1/4$，否则就是 $2/6$

13 尖#

• 四个人每个人摸 13 张，问每个人都有尖的概率是多少？
• 可以直接用组合来算 $\frac{\frac{52!}{13!13!13!13!}}{\frac{4!\times48!}{12!12!12!12!}}$
• 也可以直接考虑每张尖属于不同堆的条件概率 $1\times \frac{39}{51} \times \frac{26}{50}\times \frac{13}{49}$

14 赌徒输光问题#

• 赌徒有 i 元，每次读报，赢一元的概率是 $p$，输一元的概率是 $1-p$，赢 $N$ 元或者输光为止，问他赢钱的概率是多少？
• 采用递归的分析方法，关键是要假设这么一个概率，即在 i 元的情况下，赢得概率为 $P(i)$，则有 $P_{i} = pP_{i+1}+qP_{i-1}$ 结合边界条件 $P_{0}=0,P_{N}=1$，可以得到结果

$$P_{i}=\begin{cases} \frac{1-(\frac{q}{p})^{i}}{1-(\frac{q}{p})^{N}} & \text{if } p \neq q\\ \frac{i}{N} & \text{if } p = q \end{cases}$$

15 篮球得分#

• 一名球员正在投 100 次篮，已经投了 2 次，第一次投中了，第二次没投中，接下来每一次投中的概率是得分占已投篮次数的比例，问他最后得 50 分的概率是多少？
• 非常神奇的一道题目，需要从简单情况递推得到结果，以 $P_{n,k}$ 表示 $n$ 次投中了 $k$ 次的概率，则有递推关系 $P_{n+1,k}=P(miss|(n,k))P_{n,k}+P(score|(n, k-1))P_{n,k-1}$。然后从 3 开始，$P_{3,1}=\frac{1}{2},P_{3,2}=\frac{1}{2}$，接着可以猜测 $P_{n,k}=\frac{1}{n-1}$。并且验证可以得证

16 路上的车#

很简单我就不写了

离散和连续分布#

1 相遇问题#

• 两个人在 5 点到 6 点之间随机到的车站，只停留 5 分钟，问两个人相遇的概率是多少？
• 这是一个典型的几何概型，考虑一个二维平面，横坐标是 A 的到达时间，纵坐标是 B 的到达时间，两个点的距离小于等于 5 分钟的概率就是一个 $|Y-X|=5$ 区域的面积占整个区域的面积的比例，结果是 $23/144$

2 三角形的概率#

• 一个棍子随机折断两次，问形成三角形的概率是多少？
• 考虑断的位置是 $(x,y)$，不妨设 $x<y$ ，则满足 $y>1-y, x+(1-y)>y-x,(y-x)+(1-y)>x$

3 泊松过程的性质#

• 就是在说泊松过程无记忆性

4 正态时刻#

• 正态分布的高阶矩怎么算
• 使用母函数 $M(t) = \mathbb{E} e^{tX}$，于是可以得到 $M^{(n)}(0)=\mathbb{E}X^{n}$

期望，方差，协方差#

1 连面条#

• 100 根面条，任意取两端连起来，直到没有两端，问最后环的个数的期望是多少？
• 还是一个递推的题目：考虑使用 $f_i$ 表示 i 根面条形成的环数，显然 $\mathbb{E}f_{1}=1$，接着考虑 $\mathbb{E}f_{2}=\mathbb{E} [\frac{1}{3}(1+f_{1})+ \frac{2}{3}f_{1}]=1+ \frac{1}{3}$，紧接着可以递推得到 $\mathbb{E}f_{n}= \mathbb{E}[1+ \frac{1}{3}+\cdots+ \frac{1}{2n-1}]$

2 最优对冲比例#

• 两只股票 A 和 B，B 的份额是多少才能最小化对冲头寸的风险
• 非常简单： $h=\rho \frac{\sigma_{A}}{\sigma_{B}}$

3 骰子游戏#

• 每次投骰子，投到的点数就是收益，如果点数大于三继续，否则停止，问期望是多少
• 一个简单的解法是 wald 等式：可以把投骰子的过程分解成两个部分，前面 $n-1$ 局，和最后一局，最后一局的期望是 $2$，前面 $n-1$ 局的期望是 $\mathbb{E} \sum\limits_{i}^{n-1}X_{i}$，于是非常轻易的可以得到最后的结果是 $1\times5+2=7$

4 纸牌游戏#

• 52 张牌背面朝上，问要找到第一张尖翻的次数的期望
• 其实就是求 $\mathbb{E} \tau+1= \mathbb{E}\sum\limits_{i=1}^{48}X_{i}+1$，其中 $\tau$ 表示在第一张 A 之前的纸牌个数，$X_{i}$ 表示第 i 张非 A 牌（与顺序无关）是否在第一张 A 前，可以想象成插空法，于是 $\mathbb{E}X_{i}=1/5$ ，于是可以得出答案

5 随机变量的和#

• 设 $X_{1},X_{2},\cdots,X_{n}$ 是独立同分布的随机变量，服从 $[0,1]$ 上的均匀分布，问 $S_{n} = \sum\limits_{i=1}^{n}X_{i} \le 1$ 的概率是多少
• 想象一个高维的锥体，可以得到结果就是 $\frac{1}{n!}$

6 集水浒卡#

• 有 N 种水浒卡，每个盒子等概率的有一张。A：问集齐一套的概率是多少；B：n 张卡里面，种类数的期望是多少
• A：考虑 $X = \sum\limits_{i=1}^{N}X_{i}$ ，其中 $X_{i}$ 是找到第 i 张卡的次数，$X_{i}$ 服从几何分布，期望是 $N/(N-i+1)$，于是结果是 $N\sum\limits_{i=1}^{N} \frac{1}{i}$
• B：考虑 $Y = \sum\limits_{i=1}^{N}Y_{i}$，其中 $Y_{i}$ 是第 $i$ 种卡是否被抽到的指示函数，$Y_{i}$ 服从伯努利分布，期望是 $1-(1-\frac{1}{N})^{n}$，于是结果是 $N(1-(1-\frac{1}{N})^{n})$

7 联合违约概率#

• 一个债券 50% 的概率违约，另一个债券 30% 的概率违约，问至少一个债券违约的概率和相关系数的范围
• 至少一个债券违约的概率是 $P (I_A \cup I_B) = P(I_A) + P(I_B) - P(I_A \cap I_B) = \mathbb{E} (I_A)+\mathbb{E} (I_B)-(\mathbb{E}I_{A}\mathbb{E}I_{B}-\mathbb{Cov}(I_{A}, I_{B}))$
• 相关系数的范围可以通过债券违约的概率最小是 0.5，最大是 0.8 来得到

次序统计量#

[!note] 第 $i$ 小的数字的期望 从 $1$ 到 $n$ 的 $n$ 个数中随机抽取 $k$ 个数，问第 $i$ 小的数的期望是

$$\mathbb{E}X_{(i)} = \frac{i(n+1)}{k+1}$$

1 随机蚂蚁#

• 500 只蚂蚁在一英寸的线上走，出发点随机，速度是 1 英尺/min，碰头了就互相掉头，问所有蚂蚁掉下来的时间期望
• 由于碰撞之后互相掉头相当于没掉，只要考虑时间最长的那只留了多久，所以结果就是 $\frac{500}{501}$