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

于一个定值（比如1e-5），而且i和N同奇偶，就可以停止动态规划，因为此时继续规划下去所产生的不同已经不可能影响到要输出的结果。经过实验发现，最大的数据也只在几百次迭代中就稳定了，这样就将效率大大提高，满足了题目的要求。

方法4 概率—期望系统

这个是我自创的，或许是由于不是很难吧，这个东西我在资料中没有见到过。其实这就是方程的思想在概率和期望问题中的一个应用。 概率—期望系统的定义

概率—期望系统是一个带权的有向图。这个图中的点代表一个事件，而如果点A与点B之间有一条权为p的边，就表示A发生后，B紧接着发生的概率是p。初始的时候，有一个点（叫做初始点）代表的事件发生了，其他事件根据概率依次发生，每次只发生一个。求其他各个事件发生次数的期望。记时间A的发生次数期望为EA，A到B的边权为PAB 一些限制

? 对任意的AB，PAB≤1 ? 对于任意点A，

(A,B)?E?PAB?1，且对于系统中的所有点，至少有一个点使等

号不成立。如果等号都成立的话这些事件将无穷无尽的发生下去，而概率—期望系统则变得没有意义（此时期望或者是无穷大，或者是0）。

? 不能有指向初始点的边，这是因为求解时我们把初始顶点的概率设为1。但

是如果真的有这样的边，可以添加一个假点作为初始点，这个假点到真正的初始点有一条概率为1的边。 概率—期望系统的求解

我们首先来看一种最简单的概率—期望系统：有向无环图的概率—期望系统。这种系统是很简单的，因为它没有后效性，所以可以通过动态规划的方法在O(E)的时间内解决。许多使用动态规划解决的概率—期望问题都是基于这类系统的。比如ZJU1022 Parallel Expectation就是这样的。

但是在有些问题中（比如下面的例4），我们需要解决更一般的概率—期望系统。这时图中含有圈，因而造成了后效性。我们当然可以用迭代法，而如果设第i次迭代时A的期望用Ei,A来表示，迭代的方程就是

Ei?1,A?(B,A)?E?PBAEi,B

通过若干次的迭代，就可以达到我们需要的精度。但是这个方法的效率是不稳定的，考虑这样一个例子：A是起始点，PAB=1，PBC=1，PCB=0.99，这个例子的解是EA=1, EB=100, EC=100，但是如果用迭代的话需要很多次才能达到这个结果。而如果PCB=0.9999，那么迭代法的速度就更加缓慢。

如何避免这种情况的出现呢？我们当然不能限制数据，而应该寻找更稳定的方法。考虑刚才迭代的过程，我们发现，在迭代的终点，近似的有

EA?(B,A)?E?PBAEB，这是一个方程，而这个方程的解其实就是我们所要求的解。

我们只要把这个方程解出来，就可以得到精确的结果，而刚才说的迭代过程，实

际上就是这个方程的求解过程（线性方程组的一种解法——Jacobi法就是这样做的）。而求线性方程组的解，我们更常用的稳定算法是高斯消元法，完全可以在这里使用。这样就得到了一种稳定而精确的解法：

首先根据概率—期望系统建立方程组，然后用高斯消元法去解，得到的结果就是我们要求的期望。这种算法的时间复杂度是O(n3)。

当然这个复杂度是不很理想的，但是对于解方程组，我们没有更简单而高效的方法，所以这个算法还是比较可取的。而迭代法也不能忽视，在概率不会出现极大或极小，而且边又不多的时候，迭代法的效率往往会高于高斯消元。

此外，即使概率—期望系统中有环，也并不一定就不能使用动态规划来解决，当环之间满足一个偏序的时候，我们仍然可以使用等比数列求和的方法来进行处理，从而达到更好的复杂度。 例四 简单游戏4

所谓简单游戏，相信大家小时候都玩过，就是那种掷出股子子，然后按掷的步数走的游戏。现在有一个n(1≤n≤100)个格子的游戏，一些格子上有指令。指令分成若干种,如下： ? 0——空指令

? -1——陷阱，到了这里后要掷出六才能继续向前,注意不是向前六步，而是要

再掷一次决定步数。 ? -2——停一次

? 其它数字——转移指令，走到数字所代表的格子

走到陷阱中是很难出来的，因此大家都不希望走到陷阱里。玩一次游戏走到陷阱里的平均次数到底是多少呢?这个问题将由你来解决。

输入：第一行n，表示游戏的格数。第二行有n个数，表示每个格子的指令（第一个和最后一个都没有指令）。注意如果某次走到的位置达到或超过最后一个格子，都表示游戏结束。

输出：走到陷阱里的平均次数。保留3位小数，请尽量使用extended类型。 样例: 输入 4 0 -1 2 0 输出 0.400 解释：第一次走到陷阱里，概率为1/3，第二次走到陷阱里，概率为(1/3)*(1/6),第三次(1/3)*(1/6)2，……

由等比数列的求和公式中令n=无穷，可得概率之和为(1/3)/(1-(1/6))=2/5=0.4 分析

如果按照题目中的那个“解释”的思路走，就不免中了圈套。题目中的转向指令可以造成非常复杂的圈套圈的情况，用求极限的思想很难解决。

有了概率—期望系统，这个问题就并不困难了。我们只要构造一个图就可以。把到达每个格子作为一个事件，每个事件如果没有转向指令就向后面的六个格子

4

题目来源 原创

各连出一条概率为1/6的边，如果有转向指令就向转向的那个格连一条概率为1的边。的由于题目中没有限制第一个格子不会有转移指令指向，所以我们不能简单的把第一个格子作为起始点，而应该做一个假起点，叫做0点，然后让0到1有一条概率为1的边就可以。例如样例中的游戏对应的图和方程就是： 方程组： E1 = 1 1E = 2 3 4 21 6 E1 + E3 0 11E3 = 6 E1 + 6 E2 其中三角形箭头表示概率是1，普解得E2 = 0.4，这就是我们需要的结果。 通箭头表示概率是1/6。 对于任何一个游戏，我们都可以按这种方法建立一个概率—期望系统，剩下的问题就是应用高斯消元法来解决就可以了。 当然我们不能忘记迭代法。但是容易看出，迭代法在这道题中可能遇到特殊设计的数据（一个典型的数据就是5个转向指令连成一排，这种结构只要重复几次就会造成答案非常大，可以达到105以上），对于这种数据，迭代是无法出解的。因此，本题选择高斯消元是比较好的方法。

总结

本文对有关概率和期望的问题进行了一些研究，介绍了直接计算，动态规划，迭代以及概率—期望系统四种常用方法。在实际解题时，只有具备扎实的数学基础，灵活运用这些方法，才能顺利的解决各种各样的概率问题。