计算机问题求解 - 离散概率基础

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

有限样本空间Thereare onlyfinite outcomesEach outcomes individually consists an elementaryevent. Foronecointoss,therearetwo outcomes-headandtail."Head"isanelementaryevent.Theprobability of an elementary event corresponds aspecific outcome. If all outcomes are equally likely, then the probability ofanevent Ecanbecomputedas:Etotal number of outcomes in EP(E)Atotal numberof 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出现的可能性是一样的This is a special case of样本空间大小是63=216。so-called inclusion-用F表示事件“3次结果一样”，则|F=6exclusion principle用G表示事件“没有一次结果是4”，则,2,3,5,6)中任选3个数的组合数）要求的事件为F和G的并集：[FUG|=|F|+|G|-|FnG|=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(A A...A,)= N- S, +S, -S, +...+(-1)*S. +...+(-1)"S,where, S, =ZIA,nA,...nA,1 k=1,2,..n<ii≤i2≤...≤i≤nFor anexample:theformulafor 4 subsetsN-(IS,1+S1+JS/+S41)+(/S0S/+S0S+/S0S4/+0+/S0S//S4(S0s+S0S0s+S0S/S0s0s+SinS0S3nS4

包含-排斥定律: 否定形式       =    = = − + − + + − + + − 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，生成一个序列：i1,i2,i3...,in。出现下述情况的概率是多少：对任意的k(1<k<n),ik#k?这样的序列称为derangement

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