南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）离散概率基础

计算机问题求解一论题2-7 离散概率基础 2018年04月18日

计算机问题求解 – 论题2-7 - 离散概率基础 2018年04月18日

问题1： 你能否给我们讲讲书上那个关 于邮购商店的“故事”，那里 什么地方体现了“碰运气”？

If we have a table with 100 buckets and 50 keys to put in those buckets, it is possible that all 50 of those keys could be assigned (hashed)to the same bucket in the table.However,someone who is experienced with using hash functions will tell you that you'd never see this in a million years. But that same person might also tell you that neither would you ever see. in a million years,all the keys hash into different locations.In fact,it is far less likely that all 50 keys would hash into one place than that all 50 keys would hash into different places,but both events are quite unlikely.Being able to understand just how likely or unlikely such events are is a major reason for taking up the study of probability. 间题2： 这里的you'd never..和neither would you ever.有什么意义？

离散概率模型 间题3： 你能香以下面的过程为例解释 离散概率模型中的主要概念？ Outcome Sample space Event probability A process::掷两个色子两次

离散概率模型 A process: 掷两个色子 Outcome Sample space Event probability 两次

Axioms for a probability space 满足下列性质的P称为一个probability distribution或者一个 probability measure. L.P(A)≥0 for any A C S. 2.P(S)=1 3.P(A U B)=P(A)+P(B)for any two disjoint events A and B. 记住：P是一个函数。 问题4： 为什台任何事件的概率值不会大于1？ 如果A和B相交，P(AUB)是什么？

Axioms for a probability space 满足下列性质的P称为一个probability distribution 或者一个 probability measure。 记住：P 是一个函数

问题5： 有限样本空间中的离散 概率与计数有什么关系？ P(E)=∑Px). x:x∈E

有限样本空间 There are only finite outcomes. Each outcomes individually consists an elementary event. For one coin toss,there are two outcomes-head and tail. “Head”is an elementary event. The probability of an elementary event corresponds a specific outcome. If all outcomes are equally likely,then the probability of an event E can be computed as: total number of outcomes in E D(E) E A total number of outcomes

有限样本空间 ◼ There are only finite outcomes. ◼ Each outcomes individually consists an elementary event. ❑ For one coin toss, there are two outcomes – head and tail. “Head” is an elementary event. ◼ The probability of an elementary event corresponds a specific outcome. ◼ If all outcomes are equally likely, then the probability of an event E can be computed as: total number of outcomes total number of outcomes in | | | | ( ) E A E p E = =

交集非空的事件 ■掷均匀的色子，掷3次。出现事件“或者3次均相等，或者没有一次是4” 的概率是多少？ ■合理假设：每个outcome出现的可能性是一样的 ■样本空间大小是63=216。 This is a special case of ■用F表示事件“3次结果一样”，则F=6 so-called inclusion- exclusion principle ■用G表示事件“没有一次结果是4”，则罗 T八，2,3,5,6} 中任选3个数的组合数) ■要求的事件为F和G的并集： IFUG=|F1+|G-lFnG=6+125-5=126 ■因此，最终结果是：126/216=7/12

交集非空的事件 ◼ 掷均匀的色子，掷3次。出现事件“或者3次均相等，或者没有一次是4” 的概率是多少？ ◼ 合理假设：每个outcome出现的可能性是一样的。 ◼ 样本空间大小是 6 3=216。 ◼ 用F表示事件“3次结果一样”，则|F|=6 (F={111,222,…,666}) ◼ 用G表示事件“没有一次结果是4”，则|G|=53=125 (G是 从集合{1,2,3,5,6} 中任选3个数的组合数) ◼ 要求的事件为F和G的并集: |FG|=|F|+|G|-|FG|=6+125-5=126 ◼ 因此，最终结果是：126/216 = 7/12 This is a special case of so-called inclusion￾exclusion principle

包含排斥定律：否定形式 没有被包含在若干个子集的并集中的元素个数： N(AAA)=N-S+S2-S3+.+(-1)Sk+.+(-1)"Sn where,S=∑lA,nA,∩nA.lk=l,2,n l≤i1≤i2≤.ik≤n For an example:the formula for 4 subsets N-(IS+S2+IS3+S4D) +(IS1⌒S2+lS1∩S2+S1∩S4+lS2S3+lS2⌒S4+lS3S40 -(IS1nS2S3+lS1nS2∽S4+lS1∩S3∽S4+lS2⌒S3⌒S4) +lS1∩S2nS3nS4l

包含-排斥定律: 否定形式       =    = = − + − + + − + + − i i i n k i i i n n k k n k k S A A A k n N A A A N S S S S S 1 ... 1 2 1 2 3 1 2 1 2 where | ... | 1,2,..., ( ... ) ... ( 1) ... ( 1) ， For an example：the formula for 4 subsets N - (|S1 |+ |S2 |+ |S3 |+ |S4 |) + (|S1S2 |+|S1S2 |+|S1S4 |+|S2S3 |+|S2S4 |+|S3S4 |) - (|S1S2S3 |+|S1S2S4 |+|S1S3S4 |+|S2S3S4 |) + |S1S2S3S4 | 没有被包含在若干个子集的并集中的元素个数:

Hatcheck Problem ■大剧院衣帽间的员工太粗心，将个客人的帽子上的标签搞乱了。他将 n顶帽子随意地递交给每个客人。 口问题：“每个客人都拿错了帽子”的概率是多少？ ■数学模型：随机地排列自然数1,2,3..，n,生成一个序列：1， i2,3,…,n。出现下述情况的概率是多少：对任意的k(1≤k≤)， K≠K? n这样的序列称为derangement

Hatcheck Problem ◼ 大剧院衣帽间的员工太粗心，将n个客人的帽子上的标签搞乱了。他将 n顶帽子随意地递交给每个客人。 ❑ 问题：“每个客人都拿错了帽子”的概率是多少？ ◼ 数学模型：随机地排列自然数 1,2,3,…,n，生成一个序列：i1 , i2 , i3 ,…,in。出现下述情况的概率是多少 ： 对任意的 k(1kn), ikk？ ◼ 这样的序列称为 derangement