南京大学计算机科学与技术系

《南京大学计算机科学与技术系》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南京大学计算机科学与技术系离散概率(I)离散数学课程组南京大学计算机科学与技术系离散数学:离散概率内容提要引论概率论2离散数学:离散概率引论起源于17世纪的赌博游戏奠基人之一：法国数学家拉普拉斯Pierre-SimonLaplace(1749-1827)军事、经济、政治、社会运筹帷幄计算机科学：算法设计与分析设计概率算法分析算法的平均复杂度3离散数学:离散概率有限概率试验从一组可能的结果中得出一个结果的过程试验的样本空间可能结果的集合一个事件样本空间的一个子集4离散数学:离散概率有限概率事件的概率如果S是结果具有相等

2、可能性的有限样本空间，E是其中的一个事件，即是S的一个子集，则事件E的概率是p(E)=

3、E

4、/

5、S

6、易见0≤p(E)≤15离散数学:离散概率举例掷两个骰子，点数之和等于7的概率？

7、S

8、=6*6=36

9、E

10、=?(x,y),x+y=7,x≥1,y≥1(x’,y’),x’+y’=5,x’≥0,y’≥0C(5+2-1,5)=C(6,1)=6p(E)=

11、E

12、/

13、S

14、=6/36=1/66离散数学:离散概率举例标准扑克牌52张，一手牌（5张牌组成）出现满堂红(AAAKK)，即3张同一类且其余2张在另一类，概率是多少？P(13,2)

15、C(4,3)C(4,2)/C(52,5)≈0.0014标准扑克牌52张，一手牌（5张牌组成）正好含有4种相同面值(AAAAK)的概率是多少？C(13,1)C(4,4)C(48,1)/C(52,5)≈0.000247离散数学:离散概率事件组合的概率定理1:设E是样本空间S中的一个事件。事件(事件E的补事件)的概率是证明:

16、

17、=

18、S

19、−

20、E

21、,8离散数学:离散概率事件组合的概率（举例）随机生成10位0-1串，其中至少一位为0的概率?解:设E是10位中至少一位是0的事件。事件E的补事件是所有位都是1的事件。9离散数学:离散

22、概率事件组合的概率（续）定理2:设E和E是样本空间S中的事件。那么12证明:10离散数学:离散概率事件组合的概率（举例）从不超过100的正整数中随机选一个，它能被2或5整除的概率？解:设E是选出一个被2整除的事件，E是选出一个被512整除的事件。则E∩E是选出一个被10整除的事件。12p(E∪E)=p(E)+p(E)–p(E∩E)121212=50/100+20/100−10/100=3/5.11离散数学:离散概率概率推理常见问题：两个事件中哪个更有可能发生？蒙蒂⋅霍尔游戏(电视节目,MontyHallPuzzle)

23、1/3（总是不变）2/3（总是改变）12离散数学:离散概率概率论概率指派事件的组合条件概率独立性伯努利（Bernoulli）试验与二项分布随机变量蒙特卡洛（MonteCarlo）算法13离散数学:离散概率概率指派假定：各种结果的可能性都是相等的.取消这个假定。设S是某个具有可数个结果的试验的样本空间。我们赋给每个结果s一个概率p(s)，满足下列条件：i.0≤p(s)≤1(∀s∈S)ii.这个函数p:S[0,1]称为概率分布.14离散数学:离散概率概率指派（举例）掷一枚均匀的硬币，结果H(heads)和

24、T(tails)应该赋予什么概率?对于一枚不均匀的硬币，如果如果头像向上常常是头像向下的两倍，相应的概率又如何？解:我们有p(H)=2p(T).因为p(H)+p(T)=1,所以2p(T)+p(T)=3p(T)=1.从而,p(T)=1/3，p(H)=2/3.15离散数学:离散概率均匀分布定义:假设S是一个含n个元素的集合.均匀分布(uniformdistribution)赋给S中每个元素1/n的概率.举例:对于均匀的硬币，p(H)=p(T)=1/2.16离散数学:离散概率一个事件的概率定义:一个事件E的概率是E中各结果

25、的概率之和.举例：掷一个不均匀的骰子，3这一面出现的次数是其他面的两倍，其它五个面的出现是均等的，出现奇数点的概率？解:令E={1,3,5}表示出现奇数点的事件.我们有p(3)=2/7，p(1)=p(2)=p(4)=p(5)=p(6)=1/7.因此,p(E)=p(1)+p(3)+p(5)=4/7.17离散数学:离散概率事件的组合补事件:事件的并:定理:如果E,E,…是样本空间S中两两互不相交12的事件序列，那么18离散数学:离散概率条件概率定义:设E和F是事件，且p(F)>0.E在给定F条件下的概率,记作p(E

26、F)

27、,定义为:19离散数学:离散概率条件概率（举例）随机产生的4位二进制串，16个串是均匀产生的，那么在第一位是0的条件下，串中含有2个连续0的概率？解:设E是串中含有2个连续0的事件,F是第一位为0的事件.E⋂F={0000,0001,0010,0011,0100}.p(E⋂F)=5/16.p(F)=8/16=½.所以,20离散数学:离散概率条件