算法合集之《信息学竞赛中概率问题求解初探》

IOI2009冬令营论文梅诗珂1走进概率的世界——信息学竞赛中概率问题求解初探安徽省合肥一中梅诗珂摘要信息学中许多算法的设计都与概率有关。信息学竞赛中求概率或期望的问题也占有相当的分量，并且具有较大的难度。本文应用组合数的性质、误差分析、补集转化和函数分段等方法和技巧，求解了四个例题，从而总结了概率问题的一般特点与对应策略。关键字概率，随机变量，连续，离散，概率密度，积分目录摘要........................................................................1关键字......................................................................1目录.......................................................错误！未定义书签。正文........................................................................21基础知识..............................................................21.1样本空间、事件和概率.............................................21.2随机变量.........................................................21.2.1离散型随机变量及其概率分布.................................31.2.2连续型随机变量及其概率分布.................................31.3数学期望.........................................................31.3.1离散型随机变量的数学期望...................................31.3.2连续型随机变量的数学期望...................................31.4积分.............................................................32关于离散型随机变量的问题..............................................42.1例一LastMarble...................................................42.2例二Randomness..................................................63关于连续型随机变量的问题..............................................83.1例三RNG.........................................................83.1.1方法一.....................................................83.1.2方法二....................................................103.1.2比较两种方法..............................................11IOI2009冬令营论文梅诗珂23.2例四：RandomShooting...........................................124总结.................................................................16感谢.......................................................................16参考文献....................................................................16附录.......................................................................16附录1区域体积的表示..................................................16附录2例三方法一中区域体积公式的证明.................................17附录3论文原题........................................................17正文1基础知识1.1样本空间、事件和概率样本空间S是一个集合，它的元素称为基本事件。样本空间的一个子集被称为事件，根据定义，所有基本事件互斥。概率：如果有一种事件到实数的映射P{}，满足：1）对任何事件A，P{A}≥02）P{S}=13）对两个互斥事件，P{A∪B}=P{A}+P{B}则可称P{A}为事件A的概率。上述三条称为概率公理。1.2随机变量如果对样本空间S中的任意事件e，都有唯一的实数X(e)与之对应，则称X=X(e)为样本空间S上的随机变量，其中离散型随机变量与连续型随机变量较常见。1.2.1离散型随机变量及其概率分布取值范围为有限或无限可数个实数的随机变量称为离散型随机变量。设离散型随机变量X取值xi时的概率为pk(k=1,2,…),则称X的所有取值以及对应概率为X的概率分布，记做P{X=xk}=pk（k=1,2,…）。常见的离散型随机变量的概率分布有两点分布，二项分布，几何分布，超几何分布，泊松分布。1.2.2连续型随机变量及其概率分布如果X是在实数域或区间上取连续值的随机变量，设X的概率分布函数为F(x)=P{X≤x}，若存在非负可积函数f(x)，使对任意的x，有xdttfxF)()(，则称X为连续型随机变量，称f(x)为X的概率密度函数。要注意，概率密度不是概率。常见的连续型随机变IOI2009冬令营论文梅诗珂3量分布有均匀分布，正态分布，指数分布。1.2.2.1连续型随机向量及其概率分布如果X1,X2,…,XN都是连续型随机变量，则称(X1,X2,…,XN)为N维随机向量，其概率分布函数为F(x1,x2,…,xN)=P{X1≤x1,X2≤x2,…,XN≤xN}。若存在非负可积函数f(x1,x2,…,xN)使得DNNNdxdxdxxxxfxxxF...),...,,(),...,,(212121，其中等式右端表示N重积分，就称f(x1,x2,…,xN)是N为随机向量(X1,X2,…,XN)的联合概率密度函数。如果有X1,X2,…,XN互相独立，并且分别有概率密度函数f1(x1),f2(x2),…,fN(xN)，那么)()...()(),...,,(221121NNNxfxfxfxxxf就是一个合法的联合概率密度函数。1.3数学期望1.3.1离散型随机变量的数学期望设离散型随机变量X的分布律为P{X=xk}=pk（k=1,2,…）,若1||kkkpx存在，则称1kkkpx为X的数学期望，简称期望，记为E(X)。1.3.2连续型随机变量的数学期望设连续型随机变量X的概率密度函数为f(x),若广义积分dxxxf|)(|收敛，则称dxxxf)(为连续型随机变量X的数学期望，记为E(X)。1.4积分积分：设函数f在闭区间[a,b]上有定义，记区间[a,b]的一个分割π为(x0=a,x1,x2,…,xn=b)(x0x1x2…xn)，记||π||=Max(xi-x(i-1))（1≤i≤n），我们任取ξi∈[x(i-1),xi](1≤i≤n)为区间[x(i-1),xi]的代表，如果存在一个数A，使得对任意小的з0,都存在δ0，只要分割π满足||π||δ,都有|)()(|11Axxfiinii而不管ξi的取值，我们就称函数f在[a,b]上可积，称A为函数f在[a,b]上的定积分，记为badxxf)(。一个实用的结论是：任意连续函数在任意闭区间上都是可积的。Newton-Leibniz公式：设连续函数f在[a,b]上有定义，则)()()(aFbFdxxfba,其中F(x)是f(x)的任一个原函数。IOI2009冬令营论文梅诗珂4下面，我们将分别对离散型随机变量与连续型随机变量两种情况举两个例子进行分析。2关于离散型随机变量的问题关于离散型随机变量的问题，在信息学竞赛中出现过多次了，比如NOI2005的《聪聪与可可》，NOI2006的《神奇口袋》，NOI2008的《赛程安排》。这类问题对算法设计要求往往不高，只要证明出了关键的定理，问题就被解决了。解决这类问题，就一定要对离散型随机变量的常见分布的性质比较熟练。下面，我们来看一道关于最大胜率的例题。2.1例一：LastMarble1题目描述：有red个红球，blue个蓝球在一个袋子中。两个玩家轮流从袋子中取球，每个人每次可以取1，2或3个球，但在他把球拿出袋子之前，他并不知道所取球的颜色。每次球被取出袋子后，它们的颜色被公布给所有人。取走最后一个红球的人输。现在已知有人在游戏开始前取走了removed个球，并且谁也不知道球的颜色。在两个玩家都采取最优策略时，先手的胜率是多少？约束条件：1≤red,blue≤100,0≤removed≤red-1。分析：当removed=0的时候，这个问题是很普通的动态规划问题。我们只需设F(r,b)代表现在剩r个红球，b个蓝球，面对当前局面的玩家所能得到的最大胜率。那么：1),0(bF(b≥0)mqpbqrpmbrqbprbrMinmqbprFCCCMaxbrF,0,0)3,(1))),(1((),((1)其中mbrqbprCCC是取到p个红球，q个蓝球的概率。F(red,blue)就是我们要的答案。为了解决removed0的情况，我们需要定理一：在red个红球，blue个蓝球中先取a个球，再取b个球，剩余不同颜色的球数的概率分布与先取b个球，再取a个球所对应的剩余不同颜色的球数的概率分布是相同的。1TopCoderSRM349divone1000IOI2009冬令营论文梅诗珂5证明：这个定理看上去很显然，因为先取a个球再取b个球应当是与直接取(a+b)个球等价的，现在我们用代数方法证明。首先证明)(nbaCCCCababanbanan。因为)(!!)!()!()!(!)!(!)!(!)!(!nbaCCbababanbanbanbanaannCCababanbanan。假设在先取a个球，再取b个球后，红球被取了r个。显然每次取球是互相独立的。所以这种情况的概率是)()1()1(1111),(01bablueredarbaablueararedablueredaabluearedraMinaCCCCCC)(11),(01abaaarbaarbablueredrbabluerredraMinaCCCCCC（应用上面的结论）bablueredrbabluerredCCC其中a1表示第一次取到的红球数，在第二个等式的右边，因为a1≤a和a1≤r总有一个成立，所以等式恒成立。这个等式告诉我们从red个红球与blue个蓝球中先取a个球，再取b个求，与直接取(a+b)个球造成的剩余不同颜色的球数的概率分布是完全相同的。所以取球的顺序与最终的结果没有关系。■我们设F(r,b)表示当前有r个红球，b个蓝球的，被事先取走了removed个球（不知道它们的颜色），面对这个局面