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

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

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

问题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. 有什么意义？

问题2： 这里的you’d never…和neither would you ever… 有什么意义？

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

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

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

问题4： 有限样本空间中的离散概率与 计数有什么关系？

有限样本空间 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: p(E)=E total number of outcomes in 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 = =

离散概率建模 掷两个色子一次和掷一个色子两次是一样的吗？

离散概率建模 掷两个色子一次和掷一个色子两次是一样的吗？

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是一个函数。 问题5： 为什台任何事件的概率值不会大于1？ 如果A和B相交，P(AUB)是什么？

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

交集非空的事件 ■掷均匀的色子，掷3次。出现事件“或者3次均相等，或者没有一次是4” 的概率是多少？ ■合理假设：每个outcome出现的可能性是一样的。 ■样本空间大小是63=216。 ·用F表示事件“3次结果一样”，则F=6(F={111,222,,666}》 ■用G表示事件“没有一次结果是4”，则1G=53=125(G是从集合{1,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

包含排斥定律：否定形式 没有被包含在若干个子集的并集中的元素个数： N(AA,A)=N-S,+S2-S3+.+(-1)*Sk++(-1)Sn where,Sk=∑1A,nA,n.∩A|k=1,2,,n l≤i1≤i2≤≤ik≤n For an example:the formula for 4 subsets N-(IAH+A2H+A3H+A4) +(A1∩A2HlA1∩A2tlA1∩AtlA2∩A3t|A2∩AtlA3A4D -(A1∩A2∩A3+lA1OA2∩A4tlA1∩A3∩A4tlA2∩A3∩A4D +A1∩A2∩A3∩A4

包含-排斥定律: 否定形式       =    = = − + − + + − + + − 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 - (|A1 |+ |A2 |+ |A3 |+ |A4 |) + (|A1A2 |+|A1A2 |+|A1A4 |+|A2A3 |+|A2A4 |+|A3A4 |) - (|A1A2A3 |+|A1A2A4 |+|A1A3A4 |+|A2A3A4 |) + |A1A2A3A4 | 没有被包含在若干个子集的并集中的元素个数: