概率期望

【8】概率相关概念
【9】求概率的乘法公式、全概率公式、贝叶斯公式

概型

古典概型，等概率的基本事件。
几何概型，按面积体积等随机。

值得注意的是在几何概型中，存在会发生，但是发生概率为 $0$ 的事件。

独立事件

$A$ 和 $B$ 独立，当且仅当 $P(AB) = P(A) P(B)$ 。

$A, B, C$ 独立，当且仅当两两独立，且 $P(ABC) = P(A)P(B)P(C)$ 。

期望

期望的定义：
$\mathbb{E}[x] = \sum_{i} i\Pr[x = i]$

期望是线性的：
$\mathbb{E}[ax + b] = a \mathbb{E}[x] + b$

$\mathbb{E}[x + y] = \mathbb{E}[x] + \mathbb{E}[y]$

乘法只有在 $x$ 和 $y$ 独立的情况下。

$\mathbb{E}[x y] = \mathbb{E}[x] \mathbb{E}[y]$

方差

方差的定义：
$\mathrm{Var}(x) = \mathbb{E}[(x - \mathbb{E}[x])^2]$

方差的重要性质：
$\mathrm{Var}(x) = \mathbb{E}[x^2] - \mathbb{E}[x]^2$
平方的平均数减平均数的平方

条件概率

$\Pr[B | A] = \Pr[A \wedge B] / \Pr[A]$

羊和车

https://en.wikipedia.org/wiki/Monty_Hall_problem

有 $3$ 个门， $2$ 个后面是羊， $1$ 个后面是车。

你可以选一个门，得到门后面的东西。但是你不知道门后面是什么。

这时你随机选了一个，然后主持人打开了一个门，后面是羊，问你改不改变自己的选择。

问题是改变是否可以提高门后面是车的概率？

应该改变，不改变是车的概率是 $\frac{1}{3}$ ，改变是车的概率 $\frac{2}{3}$ 。

门后面是车概率提高了，如果不便于理解，可以想象有 $n = 10^9$ 个门，其中一个后面是车，然后主持人打开了 $n - 2$ 个。

当然，改变的前提是你想要一个车而不是羊。

酒鬼

一个酒鬼每天 $0.3$ 的概率去 $A$ 酒吧， $0.3$ 的概率去 $B$ 酒吧， $0.3$ 的概率去 $C$ 酒吧， $0.1$ 的概率在家。

警察想找到这个酒鬼，去看了 $A, B$ 酒吧都没发现，问他在 $C$ 酒吧的概率是多少？

答案

概率是 $0.75$ 。

生日问题一

如果认为每天出生概率相同。（虽然由于政策，季节，并不相同。）

并且认为任意两个人生日相互独立。

并且不考虑闰年。

选多少个人，有两个人生日相同的概率就超过了 $0.5$ ？

答案

23个人。

$\frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots$

生日问题二

如果认为每天出生概率相同。（虽然由于政策，季节，并不相同。）

并且认为任意两个人生日相互独立。

并且不考虑闰年。

选多少个人，有一个人与你生日相同的概率就超过了 $0.5$ ？

答案

$\left ( \frac{364}{365} \right ) ^ n = 0.5$

用对数（或者二分）算。 $n = 253$ 时左侧略小于 $0.5$ 满足条件。

生日问题三

如果认为每天出生概率相同。（虽然由于政策，季节，并不相同。）

并且认为任意两个人生日相互独立。

并且不考虑闰年。

你是一个良心老板，要雇人打工，你要雇佣 $n$ 个人。

在一年中，对于一天来说，如果他是任意一个人的生日，那么这天所有人都放假。

作为一个良（黑）心老板，你当然想最大化人数乘以工作日，你希望知道期望的最大值是多大。

答案

注意期望是可以相加的，你只需要关注一天（比如第一天）有多少人能上班。

你并不需要以一年为周期考虑这个问题。

每个人会导致上班的概率乘以 $(1 - \frac{1}{365})$ 。

$n$ 个人上班的话，收益是

$n ( 1 - \frac{1}{365}) ^ n$

你可以通过打表，二分，求导，或者是解不等式来处理这个问题。

可以发现 $n = 364$ 和 $n = 365$ 同时是最大值。

两个孩子

https://en.wikipedia.org/wiki/Boy_or_Girl_paradox

已知两个孩子中其中一个是女孩。求另一个是男孩的概率。

我们默许男孩和女孩的概率均为50%。

我们默许两人的性别相互独立。

答案是 $\frac{2}{3}$ ，因为题目中给的条件是，第一个是女孩或者第二个是女孩，这个条件成立。

附加题：如果其中一个是星期日出生的女孩。求另一个是男孩的概率。

答案是 $\frac{14}{27}$ 。

结论：随着对一个人了解的深入，另一个人的状态会越来越趋向平均。

如果认为每天出生概率相同。（虽然由于政策，季节，并不相同。）

并且认为任意两个人生日相互独立。

并且认为所有孩子性别随机且独立。

并且不考虑闰年。

某人家有两个孩子，已知其中一个是女生，问另外一个是男生的概率？

某人家有两个孩子，已知其中一个星期日出生的女生，问另外一个是男生的概率？

某人家有两个孩子，已知其中一个圣诞节出生的女生，问另外一个是男生的概率？

\subsubsection{答案}

$\frac{2}{3}$

$\frac{14}{27}$

$\frac{730}{1459}$

因为基本事件并不相同。

猜数字

甲选择两个不同的实数 $x_0, x_1$ 满足 $0 \leq x_0, x_1 \leq 1$ 。

乙选择其中一个 $i$ ，并且得知 $x_i$ 具体是多少。

乙需要猜测另一个 $x_{1-i}$ 和 $x_i$ 的大小关系。

找一个乙胜率大于50%的策略。

换句话说，这个世界上有很多个甲。有的甲固定选 $0.3$ 和 $0.6$ ；有的甲以 $0.5$ 的概率选 $0.1$ 和 $0.2$ ，以 $0.5$ 的概率选 $0.8$ 和 $0.9$ ；
有的甲从 $0$ 到 $1$ 之间均匀随机选取两个数字。

你作为乙，要求你的策略，无论面对哪个甲，胜率都必须大于50%。

策略：均匀随机一个 $y$ ，如果选到的 $x_i$ 大于 $y$ ，就猜 $x_i$ 较大。，如果选到的 $x_i$ 小于 $y$ ，就猜 $x_i$ 较小。

这样如果随机的 $y$ 在 $x_0, x_1$ 之间必胜，否则胜率50%。

最擅长的英雄

B君高中，刚开始去机房学OI，只是为了打Dota，B君只打AI。

B君每次会随机选择一个英雄，你可以认为是从 $0$ 到 $1$ 中随机选择一个实数。

选择的数值越大，表示B君操作的越熟练，B君可以和AI队友换英雄。

所以问从 $0$ 到 $1$ 中随机 $k$ 个数字，最大值的期望是多少？

答案

$\int_{0}^{1} k x^k\mathrm{d} x = \frac{k}{k+1}$

事实上这个结论可以推广，将他们从小到大排序之后，第 $i$ 个数字期望是 $\frac{i}{k+1}$ 。

地震后的幻想乡

考清华

http://news.xinhuanet.com/politics/2017-11/27/c_1122014276.htm
港珠澳大桥建造有多难？连续33次考上清华的感觉！
相邻两次并不独立。

等车

B君来自石家庄，石家庄的公交车并没有时刻表。（并且还很堵车，所以可以认为是随机的）

如果公交车平均 $t$ 的时间来一辆。

期望等待时间是多久？

答案

如果公交车是均匀出现，期望等待时间是 $\frac{t}{2}$ 。

如果公交车是随机出现（泊松分布）期望等待时间是 $t$ 。

形象的来理解你可以认为从现在开始的 $nt$ 时间内会来 $n$ 辆车。

其中最早的车期望是 $\frac{nt}{n+1}$ 的时间来。

如果 $n$ 趋于无穷大，这个数列的极限是 $t$ 。

等两台车

B君在车站等公交车，一共有两条线经过， $4$ 路和 $13$ 路。

其中有 $0.8$ 的概率 $13$ 路先来，有 $0.2$ 的概率 $4$ 路先来。

问这能不能说明 $13$ 路车更密集？

答案

如果这是在石家庄的话……是可以说明的（随机发车，泊松分布）

如果是在一些定时发车的城市，是不能说明的。（也许只是相位不同）

立起来的硬币

\href{https://roosephu.github.io/2013/08/23/IIIS/}{姚班招生题目2013} 物理第三题

将一个硬币抛起来如果立起来的可能性是 $\frac{1}{3}$ 求硬币与厚度的关系？

答案

\href{http://www.matrix67.com/blog/archives/4372}{Matrix 67的解答}

这个题有人跟我说，这么算是不对的。

因为抛起来是一个三维的随机，而不是二维的。

二维，直径是厚度的 $\sqrt{3}$ 倍。

三维，直径是厚度的 $\sqrt{8} = 2\sqrt{2}$ 倍。

两次硬币

（条件概率）

扔一枚硬币，第一次是正面的概率是多少？

第一次是正面，问第二次是正面的概率是多少？

对以下两种情况分别讨论

一枚正常的硬币。
从两枚硬币中随机选出一枚，其中一枚两面都是正面，一枚两面都是反面。

答案

第一个问题答案都是 $0.5$ 。

第二个问题的答案，分别是 $0.5$ 和 $1$ 。

因为两次硬币正面并不独立。

硬币

一个硬币，前 $100$ 次均为正面。

求第 $101$ 次为正面的概率。

\href{https://www.zhihu.com/question/29683794}{看知乎学知识系列}

第一种答案 $\frac{1}{2}$ ，我们认为硬币是正面的概率为 $p = \frac{1}{2}$ 。

第二种答案
$\frac{\int_{0}^{1} x^{101} \mathrm{d}x}{\int_{0}^{1} x^{100} \mathrm{d}x} = \frac{101}{102}$
我们认为硬币是正面的概率 $p$ 是在 $0$ 到 $1$ 之间均匀分布的，然后用积分计算条件概率。

天选之人

每个人有一个随机的身高

因为没有尺子，不知道每个人具体多高，但可以两个人进行比较得到谁更高

和 $100$ 个人进行比较，发现都是自己更高

问自己比第 $101$ 个人更高的概率？

答案

$\Pr[\textrm{比第101个人分高}|\textrm{比前100个人分高}] = \Pr[\textrm{比前101个人分高}] / \Pr[\textrm{比前100个人分高}]$

$\Pr[\textrm{比前101个人分高}] = \int_{0}^{1} x^{101}\mathrm{d}x = \frac{1}{102}$

$\Pr[\textrm{比前100个人分高}] = \int_{0}^{1} x^{100}\mathrm{d}x = \frac{1}{101}$

所以最终答案是 $\frac{101}{102}$ 。

这个结论可以推广，如果你问了 $p+q$ 个人，你比其中 $p$ 个人高，比其中 $q$ 个人低。

那么你比下一个人高的概率是 $\frac{p + 1}{p + q + 2}$ 。

摸牌

扑克牌 $52$ 张，其中 $26$ 红， $26$ 黑。

随机洗牌。

你一张一张摸，如果是红色，你获得 $1$ 元，如果是黑色，你失去 $1$ 元。

你可以随时叫停。

问期望收益。

答案

首先答案是不小于 $0$ 。

因为无论何种逆境，你都可以选择摸完，最后收益为 $0$ 。

然后可以模拟 $2, 4, 6$ 张的情况。

发现并没有规律。

最后决定写一个DP，就是没有规律。

对于 $52$ 张，答案大约是 $2.624475548994$ 。

时代不同了，男女都一样

如果认为所有孩子性别随机且独立。

如果每个家庭都持续生育，直到出现一个男孩。

那么社会上的男女比例会是多少？

答案

当然是 $1:1$ 。

注意，这个和每个家庭的男女比例平均是多少不一样。

赌徒

一个人有 100 元，每次赌 1 元
如果赢了，就获得1元
如果输了，就输了1元
赢和输的概率是1/2

假设输到0，或者赢到300，就不玩了，问以赢到300结束的概率是多少？
100/300

f[i] 是当前有i的钱赢的概率
f[i] = (f[i-1] + f[i+1]) / 2 + 1
f[i] * 2 = f[i - 1] + f[i + 1]
f[i + 1] - f[i] = f[i] - f[i - 1]
f[i]是等差数列
f[300] = 1
f[0] = 0
f[i] = i/300

奇妙的高精度

\href{https://roosephu.github.io/}{罗雨屏多年前给我讲的一道题}

输入 $x$ ，计算 $(1 + x + x^2 + x^4) \bmod 10007$ 的结果。

只允许用加法，减法，取模，（和用变量存下运算结果）。

问最少需要几次运算？

答案

主要是如何乘法。

注意到 $M^2 \bmod (M - x) = x^2$ ，只要满足 $M - x > x^2$ 即可。

注意到我们可以先计算 $x \bmod 10007$ ，这样 $x$ 和 $x^2$ 就有范围了。

可以得到一个九次的做法。

注意到 $f(M) \bmod (M - x) = f(x)$ ，如果 $f(x)$ 是多项式，并且 $M - x > f(x)$ 。

可以得到一个四次的做法。