概率分析和随机算法

《概率分析和随机算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、概率分析和随机算法主讲：肖臻PPT由汪小林准备北京大学计算机系算法设计与分析主要内容概率与概率分布随机变量及其期望指示器随机变量C.2概率样本空间S是一个集合，其元素称为基本事件。一个事件是样本空间S的子集。事件S称为必然事件。事件Ø称为零事件。如果A∩B=Ø，则称事件A和B互斥。基本事件s∈S可当作事件{s}，因此基本事件是互斥的对于抛两个不同硬币的试验，样本空间S={HH,HT,TH,TT}。得到一个正面一个反面的事件为{HT,TH}概率公理在样本空间S上，概率分布Pr{}是从S中事件到实数的映射，并且满足下列概率公理：对所有事件A，Pr{A}≥0Pr{S}=1对两个互斥事件A和B，

2、Pr{A∪B}=Pr{A}+Pr{B}。（可推广到多个互斥事件）称Pr{A}为事件A的概率。概率公理的一些简单推论Pr{Ø}=0如果A⊆B，则Pr{A}≤Pr{B}以~A表示S-A，则Pr{~A}=1-Pr{A}对任意两个事件A和BPr{A∪B}=Pr{A}+Pr{B}-Pr{A∩B}≤Pr{A}+Pr{B}概率分布离散概率分布：定义在样本空间S上Pr{A}=∑s∈SPr{s}均匀概率分布S是有限集合，对任意s∈S，Pr{s}=1/

3、S

4、连续均匀概率分布：定义在区间[a,b]上Pr{[c,d]}=(d-c)/(a-b)，其中a≤c≤d≤bPr{[x,x]}=0Pr{(c,d)}=Pr{

5、[c,d]}条件概率和独立性已知两次抛硬币后至少有一个是正面的，则两次抛硬币都是正面的概率是多少？条件概率公式Pr{A

6、B}=Pr{A∩B}/Pr{B}两个事件A和B独立当且仅当Pr{A∩B}=Pr{A}Pr{B}如果Pr{B}≠0，则等价于Pr{A

7、B}=Pr{A}贝叶斯定理对两个非零概率的事件A和B满足Pr{A

8、B}=Pr{A}Pr{B

9、A}/Pr{B}=Pr{A}Pr{B

10、A}/(Pr{A}Pr{B

11、A}+Pr{~A}Pr{B

12、~A})一个均质的硬币和一个总是正面朝上的非均质硬币，随机取一个抛两次，结果都是正面，请问这个硬币是非均质硬币的概率？（离散）随机变量（离散）随机变量X是一

13、个从有限或可数无限样本空间S到实数的函数随机变量X的概率密度函数f(x)对于实数x，将事件X=x定义为{s∈S:X(s)=x}f(x)=Pr{X=x}=∑s∈S:X(s)=xPr{s}联合概率密度函数f(x,y)f(x,y)=Pr{X=x且Y=y}事件X=x和Y=y是独立的当且仅当X和Y独立，即有Pr{X=x且Y=y}=Pr{X=x}Pr{Y=y}随机变量的期望随机变量X的期望值（期望、均值、中数）E[X]=∑xxPr{X=x}只要上式中的和是有限或绝对收敛的期望是线性的E[aX+Y]=aE[X]+E[Y]随机变量X和Y独立，则E[XY]=E[X]E[Y]指示器随机变量给定一个样本空间S

14、和事件A，则事件A对应的指示器随机变量I{A}定义为：引理：给定样本空间S和事件A，另XA=I{A}，则E[XA]=Pr{A}证明：E[XA]=E[I{A}]=1*Pr{A}+0*Pr{~A}=Pr{A}基于指示器随机变量计算设指示器随机变量Xi对应于第i次抛硬币正面朝上的事件，令随机变量X表示n次抛硬币中出现正面的总次数，则X=∑i=1..nXi求E[X]小结概率与概率分布随机变量及其期望用指示器随机变量