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

问题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