《算法合集之《信息学竞赛中概率问题求解初探》》由会员分享，可在线阅读，更多相关《算法合集之《信息学竞赛中概率问题求解初探》（21页珍藏版）》请在金锄头文库上搜索。
1、 IOI2009 冬令营论文 梅诗珂 1 走进概率的世界 信息学竞赛中概率问题求解初探 安徽省合肥一中 梅诗珂 摘要摘要 信息学中许多算法的设计都与概率有关。 信息学竞赛中求概率或期望的问题也占有相当 的分量，并且具有较大的难度。本文应用组合数的性质、误差分析、补集转化和函数分段等 方法和技巧，求解了四个例题，从而总结了概率问题的一般特点与对应策略。 关键字 概率，随机变量，连续，离散，概率密度，积分概率，随机变量，连续，离散，概率密度，积分 目录 摘要 . 1 关键字 . 1 目录 . 错误！未定义书签。错误！未定义书签。 正文 . 2 1 基础知识 . 2 1.1 样本空间、事件和概率 .
2、 2 1.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.
3、2 例四：Random Shooting . 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+P
4、B 则可称 PA为事件 A 的概率。上述三条称为概率公理。 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 的概率分布的概率分布， 记做
5、PX=xk = pk （k=1,2,） 。常见的离散型随机变量的概率分布有两点分布，二项分布， 几何分布，超几何分布，泊松分布。 1.1.2.2.2 2 连续型随机变量及其概率分布连续型随机变量及其概率分布 如果 X 是在实数域或区间上取连续值的随机变量，设 X 的概率分布函数概率分布函数为 F(x)=PXx，若存在非负可积函数 f(x)，使对任意的 x，有xdttfxF)()(，则称 X 为连续型随连续型随机变量机变量，称 f(x)为 X 的概率密度函数概率密度函数。要注意，概率密度不是概率。常见的连续型随机变IOI2009 冬令营论文 梅诗珂 3 量分布有均匀分布，正态分布，指数分布。 1
6、.2.21.2.2.1.1 连续型随机向量及其概率分布连续型随机向量及其概率分布 如果 X1,X2,XN 都是连续型随机变量，则称(X1,X2,XN)为 N N 维随机向量维随机向量，其概率 分布函数为 F(x1,x2,xN)=PX1x1,X2x2,XNxN。若存在非负可积函数f(x1,x2,xN)使得 DNNNdxdxdxxxxfxxxF.),.,(),.,(212121，其中等式右端表示 N 重积分，就称 f(x1,x2,xN)是 N 为随机向量(X1,X2,XN)的联合概率密度函数联合概率密度函数。如 果有 X1,X2,XN 互相独立，并且分别有概率密度函数 f1(x1),f2(x2),
7、fN(xN)，那么)().()(),.,(221121NNNxfxfxfxxxf就是一个合法的联合概率密度函数。 1.1.3 3 数学期望数学期望 1.1.3.1 3.1 离散型随机变量的数学期望离散型随机变量的数学期望 设离散型随机变量 X 的分布律为 PX=xk = pk（k=1,2,）,若1|kkkpx存在，则称1kkkpx为 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，只要分割 满足| |0 的情况，我们需要 定理一定理一：在 red 个红球，blue 个蓝球中先取 a 个球，再取 b 个球，剩余不同颜色的球数的概率分布与先取 b 个球， 再取 a 个球所对应的剩余不同颜色的球数的概率分布是相同 的。 1 TopCoder SRM 349 div one 1000 IOI2009 冬令营论文 梅诗珂 5 证明：这个定理看上去很
9、显然，因为先取 a 个球再取 b 个球应当是与直接取(a+b)个球 等价的，现在我们用代数方法证明。首先证明 )(nbaCCCCa baba nb ana n 。因为 )(!)!( )!()!(! )!( !)!( !)!( !nbaCCbaba banban banbanaannCCa baba nb ana n 。 假设在先取 a 个球，再取 b 个球后，红球被取了 r 个。显然每次取球是互相独立的。所 以这种情况的概率是 )() 1( ) 1(1 111),(01b ablueredarb aabluear ared a blueredaa bluea redraMinaCCCCCC )
10、(11),(01a baaa rbaa r ba blueredrba bluer redraMinaCCC CCC （应用上面的结论） ba blueredrba bluer red CCC 其中 a1 表示第一次取到的红球数，在第二个等式的右边，因为 a1a 和 a1r 总有一个成 立，所以等式恒成立。这个等式告诉我们从 red 个红球与 blue 个蓝球中先取 a 个球，再取 b 个求，与直接取(a+b)个球造成的剩余不同颜色的球数的概率分布是完全相同的。所以取 球的顺序与最终的结果没有关系。 我们设 F(r,b)表示当前有 r 个红球，b 个蓝球的，被事先取走了 removed 个球（不知道 它们的颜色） ，面对这个局面的玩家所能得到的最大胜率。当玩家取走 m 个球时，根据定理 一，新的局面与玩家先取走新的局面与玩家先取走 mm 个球，再让个球，再让 removedremoved 个球被取走所得到的局面完全一样！个球被取走所得到的局面完全一样！但 是有一种边界情况要考虑:由于不能保证 removedr，可能在一些情况下，取走 m 个球后， 玩家已经输了，而不能进行下面的游戏
