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