整理自algo-class的ppt: note1 note2
参考资料:
Mathematics for Computer Science by Lehman & Leighton
Wikibook on Discrete Probability

---

样本空间 Ω = "所有可能的情况"
每一种结果 i ∈ Ω, 都有对应的概率 p(i) ≥ 0
样本空间概率和为1:
∑p(i) = 1 for i ∈ Ω
事件是样本空间的子集 S ⊆ Ω
事件的概率的定义:
∑p(i) for i ∈ S

---

随机变量 X 是一个函数:
X: Ω → ℝ
期望的定义:
随机变量 X 的期望 E[X] = 随机变量 X 的平均值
=∑ X(i)·p(i) for i ∈ Ω
期望的性质:
若 X1,...,Xn 是定义在 Ω 上的随机变量, 则
E[∑Xi] = ∑[E[Xi]]
(即使 Xi 不独立也成立! 但乘法不一样, 见下)

---

若 X,Y ⊆ Ω 是事件:

那么条件概率"Y发生下X发生的概率"的定义为:
Pr[X|Y] = Pr[X∩Y] / Pr[Y]
事件独立性的定义:
事件 X,Y ⊆ Ω 是独立的 ⇔ Pr[X∩Y] = Pr[X]·Pr[Y]
根据条件概率的定义:
上面那个成立 ⇔ Pr[X|Y] = Pr[X] ⇔ Pr[Y|X] = Pr[Y]
警告: 不要相信直觉...

---

随机变量的独立性的定义:
定义在 Ω 上的随机变量 A, B 是独立的 ⇔
事件 Pr[A=a], Pr[B=b] 是独立的, 对于所有的 a b
(⇔ Pr[A=a and B=b] = Pr[A=a]·Pr[B=b] )
如果随机变量 A, B 独立才有:
E[A·B] = E[A]·E[B]
警告: 不要相信直觉...相关的变量也可能独立...