算法导论Appendix C

算法导论 数学归纳法

C.2 Probability

丢两枚硬币，可能的事件和每个事件的概率

Axioms(公理) of probability

所有事件为S，子事件为A
1.Pr{A}>=0
2.Pr{s}=1
3.Pr{AUB}=Pr{A}+Pr{B}假如ab互斥
4.Pr{AUB}=Pr{A}+Pr{B}-Pr{AB}适用于所有AB
5.Pr{A|B}=Pr{AB}/Pr{B}在B事件下A事件发生的概率

Bayes's theorem

$Pr\{A|B\}=Pr\{A\bigcap B\}/Pr\{B\}，Pr\{B|A\}=Pr\{B\bigcap A\}/Pr\{A\},Pr\{A\bigcap B\}=Pr\{B\bigcap A\}$
所以$Pr\{A\bigcap B\}=Pr\{A|B\}*Pr\{B\}=Pr\{B|A\}*Pr\{A\}$
$Pr\{B\}=Pr\{B\bigcap A\}+Pr\{B\bigcap \overline A\}=Pr\{B|A\}*Pr\{A\}+Pr\{B| \overline A\}*Pr\{A\}$
可得$Pr\{A|B\}=\frac {Pr\{A\}*Pr\{B|A\}}{Pr\{B|A\}*Pr\{A\}+Pr\{B| \overline A\}*Pr\{A\}}$

两枚硬币中有一枚是普通的，有一枚是怎么扔都向上的。现在随机选一枚硬币扔两次，问两次都向上且选了普通硬币的概率是多少。
事件A为选到特殊硬币，事件B为两次都向上，$Pr\{A\}=1/2,Pr\{B|A\}=1,Pr\{B| \overline A\}=1/4(1/2*1/2);$
$Pr\{A|B\}=4/5;$

11.16更新

Exercises

C 2-5
证明：$P(A_1\bigcap A_2\bigcap A_3......\bigcap A_n)=P(A_1)P(A_2|A_1)P(A_3|A_1\bigcap A_2)......P(A_n|A_1\bigcap A_2\bigcap A_3......\bigcap A_{n-1})$
证明：用数学归纳法证明
当n=2时$P(A_1\bigcap A_2)=P(A_1)P(A_2|A_1)$
根据Bayes's theorem过程中的公式显然是成立的。
当n=m时
$P(A_1\bigcap A_2\bigcap A_3......\bigcap A_m)=P(A_1)P(A_2|A_1)P(A_3|A_1\bigcap A_2)......P(A_m|A_1\bigcap A_2\bigcap A_3......\bigcap A_{m-1})$
当n=m+1
左边为$P(A_1\bigcap A_2\bigcap A_3......\bigcap A_m)\bigcap P(A_{m+1})$
右边为$P(A_1)P(A_2|A_1)P(A_3|A_1\bigcap A_2)......P(A_m|A_1\bigcap A_2\bigcap A_3......\bigcap A_{m-1})P(A_{m+1}|A_1\bigcap A_2\bigcap A_3......\bigcap A_{m})$
再用一次$Pr\{A\bigcap B\}=Pr\{A|B\}*Pr\{B\}=Pr\{B|A\}*Pr\{A\}$显然左边等于右边
所以该公式成立