李贤平概率论：第一章习题

组合恒等式

Story Proof

下面讨论 Story Proof 证明组合恒等式的一个方法，首先我们来看 Vande Monde Identity 的经典 Story Proof 证明：

\[ \sum\limits_{k=0}^{a-r} \binom{a}{a-k-r}\binom{b}{k} = \binom{a+b}{a-r} \]

我们构造一个问题为：“从 $a+b$ 个人当中取 $a-r$ 个人”，那么此时将 $a+b$ 个人分解为 $a$ 和 $b$ 个人两组，从 $b$ 人组当中取出 $k$ 人，$a$ 人组中取出 $a-k-r$ 人，那么遍历 $k=0$ 到 $a-r$ 个人的所有情况，自然就覆盖了问题的所有情况，我们也就证明了这样的恒等式.

术语

在李贤平的教材当中，Story Proof 称为“利用概率论的想法证明”.

李贤平概率论上这样的例子不是很多，但是还是需要多关注.

李贤平概率论第一章习题 T32

利用概率论的想法证明下列恒等式：
$$ 1+ \frac{A-a}{A-1}+ \frac{(A-a)(A-a-1)}{(A-1)(A-2)} +\cdots + \frac{(A-a)\cdots 2\times 1}{(A-1)\cdots (a+1)a}= \frac{A}{a}$$
且其中 $A>a$ ，均为正整数.

首先左侧 $\dfrac{A}{a}$ 都不一定是整数，因此需要先变换再考虑构造 Story .

我们两侧乘 $(A-1)!a$ ，可以得到：

\[ \sum\limits_{k=1}^{A-a}a\binom{A-a}{k-1}(k-1)! (A-k)! =A! \]

下面我们考虑证明这个恒等式的 Story .

右侧自然为全排列，左侧是先从 $a$ 中选 $1$ ，再从 $A-a$ 中选 $k-1$ 人进行排列，最后对剩余的进行排列，那么此时我们不难构造如下问题：

考虑给 $A$ 个人进行前后排队，求排队的总方案个数.

这个问题答案显然为全排列 $A!$ ，而我们根据刚才的分析，可以构造出新的方案：先分组为 $X$ 和 $Y$ 组，其中 $X$ 组的人数为 $a$ 人，我们考虑：

先选出 $X$ 组的一个人站在第 $k$ 位，那么有 $a$ 种选择；
他的前面不能有 $X$ 组的人，从而只能在 $Y$ 组当中选，因而有 $\displaystyle\binom{A-a}{k-1}(k-1)!$ ；
最后，剩下的人进行全排列：$(A-k)!$ .

上述的方案覆盖到了所有的全排列方案：因为对于一个特定的全排列方案，从第一位开始往后数，我们总能找到第一个 $X$ 组的人他前面仅有 $Y$ 组的人或者无人. 因此两者形成的方案是相等的，恒等式也就此成立. $\square$

古典概型问题

容斥原理与全错位排列

容斥原理的公式如下：

\[ \begin{aligned} P\left(\bigcup_{k=1}^n A_k\right) &= \sum\limits_{k=1}^n P(A_k) -\sum\limits_{1\leqslant i < j \leqslant n}P(A_iA_j) \\ &+\sum\limits_{1 \leqslant i <j < k \leqslant n }P(A_iA_j A_k) -\cdots+(-1)^{n-1}P(A_1 A_2\cdots A_n) \end{aligned} \]

利用归纳法证明即可，需要注意要用到集合运算的分配律.

全错位排列又称 de Montmort 问题，利用容斥原理可以恰好解决这个问题.

李贤平概率论第一章习题 T34

某班有 $N$ 个士兵，每人各有一支枪，这些枪外表完全一样，在一次夜间紧急集合当中，如果每个人随机取走一支枪，问至少有一个人拿到自己的枪的概率.

设 $A_i$ 为第 $i$ 个士兵拿到自己的枪的事件，那么这个问题要求的就是

\[ P \left( \bigcup_{k=1}^n A_k \right) \]

利用容斥原理即可. $\square$

取数问题

下面讨论 T20~T23 四道题，这四个题非常相似，可以直接记忆并应用.

严格次序概率

自动排序情形

李贤平概率论第一章习题 T22

任意从数列 $1,2,\cdots,N$ 中不放回地取出 $n$ 个数并按大小排列成 $x_1<x_2<\cdots<x_n$ ，尝试求 $x_m=M$ 的概率，这里 $1\leqslant M \leqslant N$.

首先，总共的可能情况为：

\[ \binom{N}{n} \]

在这些情况当中，符合题意的情况满足：具有 $m-1$ 个小于 $M$ 的数，有 $n-m$ 个大于 $M$ 的数和一个 $M$ . 因此总共的情况可以记为：

\[ \binom{M-1}{m-1}\binom{1}{1}\binom{N-M}{n-m} \]

因此根据几何概型的公式有

\[ P = \dfrac{\binom{M-1}{m-1}\binom{1}{1}\binom{N-M}{n-m}}{\binom{N}{n}} \]

李贤平概率论第一章习题 T23

在 T22 基础上，若采用有放回取数，并按大小排列成 $x_1\leqslant x_2\leqslant\cdots\leqslant x_n$ ，尝试求 $x_m=M$ 的概率.

这个题目在李贤平概率论上标 * 号，主要是因为有几个思维上的 Gap 比较麻烦.

首先总情形为 $N^n$ 不需多说，此时仍视为需要我们自己排序的情形，因此考虑分子时需要考虑排序.

对于分子部分，由于各种情况都有可能，可以设 $k_1$ 次抽到小于 $M$ 的数，$k_2$ 次抽到大于 $M$ 的数，$n-k_1-k_2$ 次抽到等于 $M$ 的数，那么我们先将 $n$ 次的抽取分堆：

\[ \dfrac{n!}{k_1!k_2! (n-k_1-k_2)!} \]

分堆之后，我们现在就要将每次的抽取分配一个数，因此相当于分别在各自能抽取的数中进行选取：

\[ \dfrac{n!}{k_1! k_2! (n-k_1-k_2)!}{(M-1)^{k_1}(N-M)^{k_2}} \]

根据 $k_1\leqslant m-1$ 和 $k_2 \leqslant n-m$ 的范围，进行遍历，最后除以 $N^n$ 即得到概率，概率为：

\[ \sum\limits_{k_1=0}^{m-1}\sum\limits_{k_2=0}^{n-m}\dfrac{n!}{k_1! k_2! (n-k_1-k_2)!} \dfrac{(M-1)^{k_1}(N-M)^{k_2}}{N^n} \]

$\square$

记一个错误的思路

考虑无顺序的情形：对于总情形，也就是无序有放回从 $N$ 个里面取出 $n$ 个，那么根据有重复组合数有总数目：
$$ \binom{N+n-1}{n} $$

这个时候，再对这里面进行分情况讨论，对于小于 $M$ 的情况，有重复组合为： $\binom{M-1+k_1-1}{k_1}$ ，大于 $M$ 同理有：$\binom{N-M+k_2-1}{k_2}$ ，那么此时就有概率：
$$ \frac{\displaystyle\binom{M-1+k_1-1}{k_1} \binom{N-M+k_2-1}{k_2}}{\displaystyle\binom{N+n-1}{n}} $$

这个概率是不对的，经过思考可以发现：在任何使用有重复组合数的方法中，都存在“等可能”的陷阱.

例如，在有重复组合的情况当中，总数为 $3$ 的情况下， $1,2,2$ 和 $1,2,3$ 均被视为一个方案，但是它们并不是等可能的！取出 $1,2,3$ 的有序情况有 $6$ 种，但是 $1,2,2$ 只有 $3$ 种，这并不是等可能的，因此也就出现了问题.

这个示例启发了我们一点：古典概型中一定要尽量避免有重复组合数，甚至是无序的情况，因为无序背后往往需要考虑一种方案对应的有序方案是否是等可能的.

无限比赛

李贤平概率论第一章习题 T41

甲乙丙按照下面的规则进行比赛：第一局由甲乙参加，而丙轮空，由第一轮的胜利者和丙进行第二轮的比赛，失败者轮空，如此进行比赛，一直到某人连胜两场为止，这个人成为优胜者.

若甲乙丙单场获胜概率均为 $\dfrac{1}{2}$ ，则甲乙丙最终获胜的概率是多少？

对于无限继续的比赛，由于没有总场数的限制，我们需要进行找规律.

设事件 $A$ 为“甲为优胜者”，$B$ 为“乙是优胜者”，$C$ 为“并是优胜者”，对于单场比赛，$a$ 为“甲赢得该局”，$b,c$ 以此类推.

由于对称性，可以知道 $P(A)=P(B)$ ，$P(C)=1-2P(A)$ . 接下来考虑找规律.

所有可能的情形为：

\[ \begin{aligned} & aa,acc,acbb,acbaa,acbacc\cdots \\ & bb, bcc,bcaa,bcabb,bcabcc,\cdots \end{aligned} \]

在注意力集中的情况下，我们发现如下的规律：

比赛结束时，丙为优胜者等价于丙赢下了所有第 $3$ 的倍数的场次.

这个结论简单说明一下：

在比赛结束时，如果丙赢下了所有第 $3$ 的倍数场次，那么如果第一场是乙获胜，则总场数为 $3$ 的倍数，自然丙为优胜者，否则为 $3n+1$ 场，也必然是丙获胜.
若丙为优胜者，则场次只能是 $3n$ 和 $3n+1$ ，逆推可以得到结论.

因此，对于丙，如果其为获胜者，则有

\[ \begin{aligned} P(C) &= [P(acc)+P(bcc)] +[P(acbacc)+P(bcabcc)]+\cdots \\ &=2\times \frac{1}{2^{3}} +2 \times \frac{1}{2^{6}} +\cdots \end{aligned} \]

从而

\[ P(C) = \sum\limits_{k=1}^\infty \frac{1}{2^{3k-1}} = \frac{2}{7} \]

因此 $P(A) = P(B) = \dfrac{5}{14}$ . $\square$