有关概率和期望问题的研究

有关概率和期望问题的研究

河北唐山一中 鬲融

摘要

在各类信息学竞赛中（尤其是ACM竞赛中），经常出现一些与概率和期望有关的题目。这类题目需要较高的数学水平和一定的算法技巧，必须经过仔细分析，选择合适的数学模型和算法才能顺利的解决问题。本文就对这类题目的一些常见方法进行了研究。

数学基础

这里写的数学基础是有关概率和期望的一点简单的计算法则，虽然我们都很熟悉，但是有时也可能会忘记使用，所以在这里列出来，也作为以后内容的基础。 概率的运算

? 两个互斥事件，发生任一个的概率等于两个事件的概率和 ? 对于不相关的事件或者分步进行的事件，可以使用乘法原则。 ? 对于一般情况p(A+B)=p(A)+p(B)-p(AB) 期望的运算

? E(φ)= ΣφiPi，这是期望的定义，其中φi是一个取值，而Pi是取这个值的

概率 ? 期望有“线性”，也就是说对于不相关的两个随机变量φ和ξ，E(φ±ξ)=E(φ)

±E(ξ)；E(φξ)=E(φ)E(ξ)；E(φ/ξ)=E(φ)/E(ξ)

? 在某些情况下，期望可以表示成一个无穷的等比数列，然后利用极限的思想

来求。

当然，这些只是最基础的知识，要解决好概率和期望的问题，还需要掌握一些组合数学的知识。

常用方法

方法1 直接计算

这种方法说起来很简单，就是推导出一个数学公式，然后通过程序来计算这个式子的值。这样的题目在与概率和期望有关的题目中比例不小，但是由于它们大都需要一定的组合数学基础，而一旦推导出公式，对算法的要求并不太高，而时间复杂度往往也比较低，所以这类问题不是本文的重点。有关内容可以在任何一本组合数学书中学到。

例一 百事世界杯之旅1

“??在2003年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可以参加百事世界杯之旅的抽奖活动，获取球星背包、随身听，更可以赴日韩观看世界杯。还不赶快行动！??” 你关上电视，心想：假设有n个不同球星的名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？ 输入输出要求

输入一个数字n，2≤n≤33，表示不同球星名字的个数。 输出凑齐所有的名字平均需要购买的饮料瓶数。如果是一个整数则直接输出。否则就用下面样例中的格式分别输出整数部分和小数部分。分数必须是不可约的。 样例输入和输出 输入 输出 2 3 5 5 11— 12 17 340463 58------ 720720 分析 这是一道比较简单的概率和期望问题。只要确定好计算方法，就可以很容易的得到公式。如果单独考虑每一名球星，那么就中了命题人的圈套。因为考虑单独的一个球星的时候所买的“没用”的饮料在考虑其他球星的时候可能会变成有用的。正确的思路是，假设现在已经有k个球星的名字，那么要使球星的名字n

达到k+1个平均需要买多少瓶饮料？这是很容易计算的，是 。所以我们从没

n-k有球星的名字开始，直到把所有的球星名字都凑齐，平均需要的饮料数(E)就可以计算出来：

1??111E?n???????

n??123由于题目的数据规模并不大，所以可以直接使用PASCAL的Comp或Int64(C/C++的

long long)进行计算。而题目要求得到即约分数，只要在计算的时候使用分数并注意约分就可以了。

方法2 动态规划

动态规划是一种应用范围很广的方法，由于概率和期望具有前面提到过的一些性质（特别是期望的定义以及期望的“线性”性质），使我们可以在概率和期望之间建立一定的递推关系，这样就可以通过动态规划来解决一些概率问题。

与其他方面的动态规划一样，合理的选择状态以及高效的状态转移方程是应用这种方法的关键，而状态的选择在这类问题中尤为重要。选择合适的状态不仅

1

题目来源 SHTSC 2002 Day 1 Prob 2

可以提高效率，而且可以保证动态规划所必须的无后效性。而动态规划的各种优化方法也可以应用。

概率和期望的最值问题也往往使用动态规划的方法来解决。 例二 多米诺骨牌2

你试图把一些多米诺骨牌排成直线，然后推倒它们。但是如果你在放骨牌的时候不小心把刚放的骨牌碰倒了，它就会把相临的一串骨牌全都碰倒，而你的工作也被部分的破坏了。

比如你已经把骨牌摆成了DD__DxDDD_D的形状，而想要在x这个位置再放一块骨牌。它可能会把左边的一块骨牌或右边的三块骨牌碰倒，而你将不得不重新摆放这些骨牌。

这种失误是无法避免的，但是你可以应用一种特殊的放骨牌方法来使骨牌更多的向一个方向倒下。

给出你要摆放的骨牌数目，以及放骨牌时它向左和向右倒的概率，计算你为完成任务摆放的骨牌数目的平均数。假设你使用了最佳的摆放策略。

输入将包含至多100个测试点，每个测试点占一行，包含需要摆放的骨牌数目n (1≤n≤1000)，以及两个非负实数Pl, Pr，表示骨牌向左和向右倒的概率。保证1＜Pl+Pr≤0.5。

最后一个测试点包含一个数0。对于每个测试点输出题目要求的数目，保留两位小数。

分析

首先应该明确怎样找到最佳的摆放策略。我们可以考虑在位置i放最后一块骨牌。显然，i前面的i-1块骨牌和i后面的n-i块骨牌是互不影响的。所以我们假设摆放i-1块骨牌需要的次数平均是（或说期望是）E1，摆放n-i块骨牌需要的次数平均是E2。那么我们摆放了这两段之后，就要把最后一块放上。这时如果把左边的碰倒了，就只好重新摆放。右边的也是同样的道理。所以需要摆放的平均值(E)是：

1-Pr1-Pl1E = 1-Pl-Pr E1 + 1-Pl-Pr E2 + 1-Pl-Pr 这个式子的推导并不困难，方法之一就是应用方程的思想（参见后面介绍的概率—期望系统）。

既然得到了这个式子，我们就可以通过动态规划来得到最优的摆放方案。设Ei是摆放i块骨牌所需要的最少期望次数，那么状态转移方程是：

1-Pr1-Pl1

Ei = min{1-Pl-Pr Ek + 1-Pl-Pr Ei-1-k + 1-Pl-Pr } (0≤k≤i-1)

这样就得到了一个O(n2)的算法。根据题目中的数据规模，最大的运算量是100*10002 = 108，虽然可以忍受，但是还是比较慢的，如果数据稍大一点就容易超时。

这就需要我们对动态规划进行优化。

这是一个1D/1D的动态规划，我们自然希望得到O(n)的算法，而这种优化一般都是通过动态规划的方程性质得到的。

观察动态规划的方程，我们可以发现，当k从0变化到i-1时第一项是不断增大的，第二项是不断减小的，第三项则是一个常数。因此整个函数一定是单峰的，这样就可以通过二分的方法进行优化，复杂度已经降到了O(nlogn)。而事实

2

题目来源 UVA 10529

上，E这个数列不但是单增的，而且是凹的（如果PlPr=0就不凹也不凸，但是这不影响这里的讨论），通过这个性质我们还可以证明决策使用的k一定是不减的（证明很简单，略去）。这样通过记录上一次决策使用的k，就得到了一个（均摊的）O(n)的算法。

方法3 迭代

动态规划要求问题无后效性，而如果问题有不可避免的后效性，动态规划就无能为力了。这时我们可以采用迭代的方法来进行计算。

当然，迭代也不是万能的，它要求问题有收敛性而且收敛的速度要足够快，而且要求的结果精度不要太高。对于同一规模的不同的输入，迭代法的效率可能会有很大的改变，所以这种方法有可能因为遇到比较坏的数据而失效。

此外，迭代法也未必是要解决有后效性的问题，只要问题有收敛性，迭代都可以起到一定的作用，下面这道例题就没有后效性，但是由于动态规划的时间复杂度过高，所以采用了一种动态规划和迭代混合的方法来解决。 例三 巧克力3

2100年，ACM牌巧克力将风靡全球。 “绿的，橘红的，棕色的，红的?”，彩色的糖衣可能是ACM巧克力最吸引人的地方。你一共见过多少种颜色？现在，据说ACM公司从一个24种颜色的调色板中选择颜色来装饰他们的美味巧克力。

有一天，Sandy用一大包有五种颜色的巧克力玩了一个游戏。每次他从包里拿出一粒巧克力并把它放在桌上。如果有桌上有两粒相同颜色的巧克力，他就把他们吃掉。他惊奇的发现大多数时候桌上都有2到3粒巧克力。

如果ACM巧克力有C(1≤C≤100)种颜色，在拿出了N(1≤N≤1000000)粒巧克力之后在桌上恰有M(1≤M≤1000000)粒的概率是多少？ 分析

如果N不是那么大的话，我们是很容易用动态规划来解决此题，状态转移方程就是

Pi+1,k=Pi,k-1*(C-k-1)/C+Pi,k+1*(k+1)/C

其中Pi,k表示拿出了i粒巧克力后桌上剩余M粒的概率（当然还要考虑一些边界情况）。但是现在N可以达到1000000，如果直接动态规划肯定是要超时的。

这个题的标准算法是使用生成函数。也就是说把“桌上有m块巧克力”转化成“有m种巧克力取了奇数块，其余的都取偶数块的取法”。所以就可以列出

(ex-e-x)m(ex+e-x)c-m

生成函数是 ，所以总的取法数就是xn的系数乘以n!和C(c,m)，c 2

而概率就是总的取法数除以cn，然后通过进一步的代数分析来化简解决。这种方

2

法当然是很优秀的，复杂度是O(c)。但是由于这道题的精度要求很低，迭代的方法也是可以达到目的的，而且复杂度也接近O(c2)。

这道题里不会出现极大或极小的概率，一般来说这种情况下的收敛是比较快的。我们可以不断的计算P的值，当它的变化不足以影响结果时就停止计算。当然这道题里的收敛是分奇偶的（显然桌上剩余的巧克力数和拿出的巧克力数是同奇偶的），所以不能比较Pi和Pi-1，而要比较Pi和Pi-2，只要看到Pi和Pi-2差距小

3

题目来源ZJU Online Judge 1363