计数原理与概率公理 | 杨星宇

计数是初等概率的有限基础。要给一个事件分配概率，首先要知道实验有多少种结果，以及其中有多少种结果属于这个事件。

计数原理

定理乘法原理

一个过程分成两个阶段。第一阶段有 $m$ 种结果，固定第一阶段结果后，第二阶段有 $n$ 种结果，那么整个过程有 $mn$ 种结果。

如果过程有 $r$ 个阶段，第 $i$ 个阶段在前面结果确定后有 $n_i$ 种选择，那么总数为

\prod_{i=1}^{r}n_i

例如，抛掷硬币 $k$ 次会产生 $2^k$ 个结果序列。

定理加法原理

如果一个过程可以通过两类互斥方式完成，第一类有 $m$ 种，第二类有 $n$ 种，那么总数为 $m+n$ 。

若两类方式并不互斥，就要用容斥原理修正重复计数：

|A\cup B|=|A|+|B|-|A\cap B|

定理鸽巢原理

把 $N$ 个对象放入 $k$ 个盒子，至少有一个盒子包含不少于 $\lceil N/k\rceil$ 个对象。特别地，把 $k+1$ 个对象放入 $k$ 个盒子时，必有一个盒子至少包含两个对象。

定义样本空间与事件

有限样本空间 $\Omega$ 是实验所有结果的集合。事件是样本空间的子集 $A\subseteq\Omega$ 。

定义概率测度

有限概率模型中的概率是函数 $P:2^\Omega\to[0,1]$ ，满足

P(\Omega)=1, \qquad P(A\cup B)=P(A)+P(B)

其中 $A\cap B=\varnothing$ 。

由此可得

P(\varnothing)=0, \qquad P(A^c)=1-P(A), \qquad P(A\cup B)=P(A)+P(B)-P(A\cap B)

如果所有结果等可能，则

P(A)=\frac{|A|}{|\Omega|}

但这个公式依赖于等可能假设，并不是概率的定义。

例抛掷两次硬币

两次抛掷公平硬币时，

\Omega=\{HH,HT,TH,TT\}

恰好出现一次正面的事件是 $A=\{HT,TH\}$ ，所以 $P(A)=2/4=1/2$ 。

随机变量是函数 $X:\Omega\to\mathbb{R}$ 。离散随机变量的概率质量函数为

p_X(x)=P(X=x)

并满足 $p_X(x)\geq0$ 以及 $\sum_xp_X(x)=1$ 。任意随机变量的累积分布函数定义为

F_X(t)=P(X\leq t)

计数原理主要用于有限样本空间，但概率公理同样适用于结果不等可能或样本空间无限的情形。