《计算机问题求解-2013-03-26-离散概率基础》由会员分享，可在线阅读，更多相关《计算机问题求解-2013-03-26-离散概率基础（28页珍藏版）》请在金锄头文库上搜索。
1、计算机问题求解 论题2-5- 离散概率基础2013年03月26日离散概率模型A process: 掷两个色子Sample space Outcome Event probabilityAxioms for a probability space满足下列性质的P 称为一个probability distribution 或者一个 probability measure。记住：P 是一个函数。Tree Diagrams: 结合计数与概率过程: 从下列硬币中依次 取两枚:nickel: 1 dime: 2 quarter: 2为什么这个 值等于该路 径中前面结 点上的值的 乘积，将在 后面解释。有限
2、样本空间nThere are only finite outcomes.nEach outcomes individually consists an elementary event.qFor one coin toss, there are two outcomes head and tail. “Head” is an elementary event.nThe probability of an elementary event corresponds a specific outcome.nIf all outcomes are equally likely, then the pr
3、obability of an event E can be computed as:不满足equally likely分布的例子交集非空的事件n掷均匀的色子，掷3次。出现事件“或者3次均相等，或者没 有一次是4”的概率是多少？n合理假设：每个outcome出现的可能性是一样的。n样本空间大小是 63=216。n用F表示事件“3次结果一样”，则|F|=6 (F=111,222,666)n用G表示事件“没有一次结果是4”，则|G|=53=125 (G是 从集 合1,2,3,5,6中任选3个数的组合数)n要求的事件为F和G的并集: |FG|=|F|+|G|-|FG|=6+125-5=126n因此，
4、最终结果是：126/216 = 7/12This is a special case of so-called inclusion- exclusion principle包含-排斥定律: 否定形式For an example：the formula for 4 subsetsN - (|S1|+ |S2|+ |S3|+ |S4|)+ (|S1S2|+|S1S2|+|S1S4|+|S2S3|+|S2S4|+|S3S4|) - (|S1S2S3|+|S1S2S4|+|S1S3S4|+|S2S3S4|) + |S1S2S3S4|没有被包含在若干个子集的并集中的元素个数:Hatcheck Probl
5、emn大剧院衣帽间的员工太粗心，将n个客人的帽子上的标 签搞乱了。他将n顶帽子随意地递交给每个客人。q问题：“每个客人都拿错了帽子”的概率是多少？n数学模型：随机地排列自然数 1,2,3,n，生成 一个序列：i1, i2, i3,in。出现下述情况的概率 是多少 ： 对任意的 k(1kn), ikk？n这样的序列称为 derangement.Number of DerangementnDefine ik=k as Property Ak , and Ak is used for the subset of all permutations satisfying property Ak.The
6、Probability of Derangement条件概率书上的例子：掷两个特殊的色子：出现三角形、圆、正方形的面数分别是1 ，2，3。事件E: 至少一个有圆的面朝上；事件F: 朝上的两个面图案相同。 如果知道时间F已经发生，那么事件E的概率是多少？ 按照常识来分析：可以理解为样本空间改变了。 利用上面的定义式来计算。原来的样本空间大小是36，如果只 考虑两面相同，样本空间大小缩小 为14，其中出现圆图案的是4。 关键假设：三种图案间的比例不变 ！相互独立的事件Hashing相关的“事件”如果将n个keys “哈希”到大小为k的表中，则样本空间 包含长度为n，元素为1,2,k中任意元素的序列。碰撞: 概率有多大?条件概率应用与概率分析 考试成绩附注：R: 回答正确；K：知道正确答案不那么“直观”的概率分析网络通信的例子ab贝努利试验 成败之间又是二项系数 ！ 0.678期望值与算法分析随机变量X: 赋值语句执行次数 家庭作业nCS pp.260-: 6, 10-13nCS pp.274-: 2, 9, 10, 14, 15nCS pp.290-: 3-4, 8, 11-13nCS pp.307-: 5, 6, 8, 10, 17, 20, 21
