预备知识
数学归纳法
用数学归纳法证明一个命题 分成两个步骤。
- 基础情形（
base case）：证明命题对起始值成立，通常证明 或 成立。 - 归纳步骤（
inductive step）：假定命题对任意自然数 都成立，即 成立；需要证明 也成立。
一旦完成了这两个步骤，那么对于任意自然数 命题 都成立。
离散概率
样本空间
样本空间（sample space）是随机过程中所有可能结果的集合，一般用希腊字母 表示。比如掷骰子问题中 。
样本空间中每一个元素 都有一个非负概率 表示其发生的概率。所有结果的概率之和为 1：
如果所有可能的结果发生的概率相等，那么是均匀分布（uniform distribution），每个元素对应的概率是
事件
事件（event）是样本空间的子集，。事件的概率是
随机变量
随机变量（random variable）是从随机过程的结果到数值的映射。它是样本空间 上的函数 ，输入 ，对应的输出 是一个数值。
期望
期望（expectation）是随机变量 的加权平均值，权重是不同结果的概率，写作 。如果随机过程重复多次， 是 的平均值，比如掷骰子问题中 。
期望的线性性质
期望的线性性质（linearity of expectation）是一个非常重要且有用的性质，核心思想是和的期望等于期望的和。下面给出正式的数学表示。比如掷两个骰子，若要求点数之和的期望值，一种方法是计算 36 种结果中各点数之和的概率；另一种更简单的方式是将两个骰子的点数看作独立的随机变量。每个骰子点数的期望值都是 3.5，相加即可得到 7。
令 是定义在 上的随机变量， 是实数，那么 下面是证明过程。