《算法合集之《信息学竞赛中概率问题求解初探》资料》由会员分享，可在线阅读，更多相关《算法合集之《信息学竞赛中概率问题求解初探》资料（21页珍藏版）》请在金锄头文库上搜索。
1、 IOI2009 冬令营论文 梅诗珂 1 走进概率的世界 信息学竞赛中概率问题求解初探 安徽省合肥一中 梅诗珂 摘要摘要 信息学中许多算法的设计都与概率有关。 信息学竞赛中求概率或期望的问题也占有相当 的分量，并且具有较大的难度。本文应用组合数的性质、误差分析、补集转化和函数分段等 方法和技巧，求解了四个例题，从而总结了概率问题的一般特点与对应策略。 关键字 概率，随机变量，连续，离散，概率密度，积分概率，随机变量，连续，离散，概率密度，积分 目录 摘要 1 关键字 1 目录 . 错误！未定义书签。错误！未定义书签。 正文 2 1 基础知识 2 1.1 样本空间、事件和概率 . 2 1.2 随
2、机变量 . 2 1.2.1 离散型随机变量及其概率分布 . 3 1.2.2 连续型随机变量及其概率分布 . 3 1.3 数学期望 . 3 1.3.1 离散型随机变量的数学期望 . 3 1.3.2 连续型随机变量的数学期望 . 3 1.4 积分 . 3 2 关于离散型随机变量的问题 4 2.1 例一 LastMarble . 4 2.2 例二 Randomness 6 3 关于连续型随机变量的问题 8 3.1 例三 RNG . 8 3.1.1 方法一 . 8 3.1.2 方法二 10 3.1.2 比较两种方法 11 IOI2009 冬令营论文 梅诗珂 2 3.2 例四：Random Shooti
3、ng . 12 4 总结 . 16 感谢 . 16 参考文献 16 附录 . 16 附录 1 区域体积的表示 16 附录 2 例三方法一中区域体积公式的证明 . 17 附录 3 论文原题 17 正文正文 1 1 基础知识基础知识 1 1.1.1 样本空间样本空间、事件和概率事件和概率 样本空间样本空间 S S 是一个集合，它的元素称为基本事件基本事件。样本空间的一个子集被称为事件事件， 根据定义，所有基本事件互斥。 概率：如果有一种事件到实数的映射 P P，满足： 1） 对任何事件 A，PA0 2） PS=1 3） 对两个互斥事件，PAB=PA+PB 则可称 PA为事件 A 的概率。上述三条称
4、为概率公理。 1.1.2 2 随机变量随机变量 如果对样本空间 S 中的任意事件 e，都有唯一的实数唯一的实数 X(e)与之对应，则称 X=X(e)为样 本空间 S 上的随机变量随机变量，其中离散型随机变量离散型随机变量与连续型随机变量连续型随机变量较常见。 1.1.2.12.1 离散型随机变量及其离散型随机变量及其概率分布概率分布 取值范围为有限或无限可数个实数的随机变量称为离散型随机变量离散型随机变量。设离散型随机变 量 X 取值 xi时的概率为 pk (k=1,2,),则称 X 的所有取值以及对应概率为 X X 的概率分布的概率分布， 记做 PX=xk = pk （k=1,2,） 。常见
5、的离散型随机变量的概率分布有两点分布，二项分布， 几何分布，超几何分布，泊松分布。 1.1.2.2.2 2 连续型随机变量及其概率分布连续型随机变量及其概率分布 如果 X 是在实数域或区间上取连续值的随机变量，设 X 的概率分布函数概率分布函数为 F(x)=PX x，若存在非负可积函数 f(x)，使对任意的 x，有 x dttfxF)()(，则称 X 为连续型随连续型随 机变量机变量，称 f(x)为 X 的概率密度函数概率密度函数。要注意，概率密度不是概率。常见的连续型随机变 IOI2009 冬令营论文 梅诗珂 3 量分布有均匀分布，正态分布，指数分布。 1.2.21.2.2.1.1 连续型随
6、机向量及其概率分布连续型随机向量及其概率分布 如果 X1,X2,XN 都是连续型随机变量，则称(X1,X2,XN)为 N N 维随机向量维随机向量，其概率 分布函数为 F(x1,x2,xN)=PX1x1,X2x2,XNxN。若存在非负可积函数 f(x1,x2,xN)使得 D NNN dxdxdxxxxfxxxF.),.,(),.,( 212121 ，其中等式右端表 示 N 重积分，就称 f(x1,x2,xN)是 N 为随机向量(X1,X2,XN)的联合概率密度函数联合概率密度函数。如 果有 X1,X2,XN 互相独立，并且分别有概率密度函数 f1(x1),f2(x2),fN(xN)，那么 )(
7、).()(),.,( 221121NNN xfxfxfxxxf就是一个合法的联合概率密度函数。 1.1.3 3 数学期望数学期望 1.1.3.1 3.1 离散型随机变量的数学期望离散型随机变量的数学期望 设离散型随机变量 X 的分布律为 PX=xk = pk（k=1,2,）,若 1 | k kkp x存在，则 称 1k kkp x为 X 的数学期望数学期望，简称期望期望，记为 E(X)E(X)。 1.3.21.3.2 连续型随机变量的数学期望连续型随机变量的数学期望 设连续型随机变量 X 的概率密度函数为 f(x),若广义积分 dxxxf| )(|收敛，则称 dxxxf)(为连续型随机变量 X
8、 的数学期望，记为 E E(X)(X)。 1.1.4 4 积分积分 积 分 ： 设 函 数 f 在 闭 区 间 a,b 上 有 定 义 ， 记 区 间 a,b 的 一 个 分 割 为 (x0=a,x1,x2,xn=b)(x00，只要分割 满足| |0 的情况，我们需要 定理一定理一：在 red 个红球，blue 个蓝球中先取 a 个球，再取 b 个球，剩余不同颜色的 球数的概率分布与先取 b 个球， 再取 a 个球所对应的剩余不同颜色的球数的概率分布是相同 的。 1 TopCoder SRM 349 div one 1000 IOI2009 冬令营论文 梅诗珂 5 证明：这个定理看上去很显然，
9、因为先取 a 个球再取 b 个球应当是与直接取(a+b)个球 等价的，现在我们用代数方法证明。首先证明 )(nbaCCCC a ba ba n b an a n 。因为 )( ! )!( )!()!( ! )!( !)!( ! )!( ! nbaCC ba ba banba n banbana ann CC a ba ba n b an a n 。 假设在先取 a 个球，再取 b 个球后，红球被取了 r 个。显然每次取球是互相独立的。所 以这种情况的概率是 )( ) 1( ) 1( 1 1 11),( 01 b abluered arb aablue ar ared a bluered aa
10、blue a red raMin a C CC C CC )( 11),( 01 a ba aa rba a r ba bluered rba blue r red raMin a C CC C CC （应用上面的结论） ba bluered rba blue r red C CC 其中 a1 表示第一次取到的红球数，在第二个等式的右边，因为 a1a 和 a1r 总有一个成 立，所以等式恒成立。这个等式告诉我们从 red 个红球与 blue 个蓝球中先取 a 个球，再取 b 个求，与直接取(a+b)个球造成的剩余不同颜色的球数的概率分布是完全相同的。所以取 球的顺序与最终的结果没有关系。 我们
11、设 F(r,b)表示当前有 r 个红球，b 个蓝球的，被事先取走了 removed 个球（不知道 它们的颜色） ，面对这个局面的玩家所能得到的最大胜率。当玩家取走 m 个球时，根据定理 一，新的局面与玩家先取走新的局面与玩家先取走 mm 个球，再让个球，再让 removedremoved 个球被取走所得到的局面完全一样！个球被取走所得到的局面完全一样！但 是有一种边界情况要考虑:由于不能保证 removedr，可能在一些情况下，取走 m 个球后， 玩家已经输了，而不能进行下面的游戏。要解决这种特殊情况，只需对 F 的定义和动态规划 方程略加修改：让 F(r,b)表示当前有 r 个红球，b 个蓝
12、球，被取走了 removed 个球但仍然至但仍然至 少还有少还有 1 1 个红球个红球的情况下，当前玩家的最大胜率。 我们用 Pro(r,b,k)表示有 r 个红球，b 个蓝球，取走 k 个球而红球数仍大于 0 的概率， 那么 Pro(r,b,k)= bakra k br ak b a r C CC 0, 。我们用递推式求解，显然 Pro(0,b,0) = 0; Pro(r,b,0) = 1; (r0) ) 1, 1,(Pr) 1, 1(Pr),(Pr kbro br b kbro br r kbro 再考虑(1)，因为 r 个红球，b 个蓝球取走 removed 个球仍有至少 1 个红球的情
13、况，包含 了有(r-p)个红球，(b-q)个蓝球，取走 removed 个球后仍有至少 1 个红球的情况，因此在前 IOI2009 冬令营论文 梅诗珂 6 者满足的基础上后者满足的概率是 ),(Pr ),(Pr removedbro removedqbpro 。由此我们得出最终方程。 0),(brF (r+b = removed) mqp m br q b p r brMinm qbprF C CC removedbro removedqbpro MaxbrF),(1 ( ),(Pr ),(Pr (),( )3 ,(1 (r+bremoved) （2） Fred,blue就是我们所求的答案。
14、观察（2）式，我们发现它与（1）式唯一不同之处只是多乘了 ),(Pr ),(Pr removedbro removedqbpro ，两个式子的 形式惊人的相似，既在意料之外又在情理之中。而如果证明不出定理（1） ，那么解题方法很可能会复杂很多， 这也就说明了数学证明对解决概率问题的重要性。下面一个例子，我们将体会到观察的重要性。 2.2 例二：Randomness 2 题目描述： 有一个随机数生成器能随机返回 1 到 R 的正整数， 现在有 N 个事件， 要求第 i 个事件的 发生概率是 i i b a ,用该随机数生成器设计一种事件触发装置， 使随机数生成器的期望使用次数 Exp 尽量少,求
15、出 Exp(精确到 1e-7)。 约束条件： 2R1000 , 1N1000 , 1aibi=2，我们有 22 ) 1( )( mm mk k mk k R N RR N R NR R kH 这个式子告诉我们：只要只要 mm 足够大，我们可以让足够大，我们可以让 ExpExp 的误差小到任意程度的误差小到任意程度，而且这个 误差减小的速度是很快的。根据题中要求的精度，只要算到第 50 层就足够了。 回顾本题的分析过程， 我们发现开头对例子的观察是关键， 有了对该样例的观察我们才 得到了第 i 层随机生成器的概念， 接下来的一切就水到渠成了。 这告诉我们解决概率问题多 从简单情况，特殊情况观察是个不错的选择。这是因为概率问题涉及的状态多，比较抽象， 只有多从形象的例子观察规律，才能较好的把握问题的模型，才谈得上解决问题。 IOI2009 冬令营论文 梅诗珂 8 3 3 关于连续型随机变量的问题关于连续型随机变量的问题 关于连续型随机变量的问题， 信息学竞赛中出现得还不多， 可能是由于题目的解决往往 要用到积分。但这类题目中
