连通图上随机走动的概率

最近刚刚完成了我们游戏里的一个功能，抽象出来就和一般我们大家玩的大富翁游戏差不多，在一张地图上抛骰子，然后走动，触发地图上的事件，如果没玩过大富翁可以看看我的截图：

 

 

我做的功能和这个差不多，这里我想说的不是游戏如何玩，而是策划在配置地图上的每一个格子的奖励或者惩罚时感到困惑。困惑的是策划不知道每个格子被踩中的概率是多少。于是来找我。

 

首先我明确知道我们游戏中玩家初始时是被随机放到地图上的某一个点的，其实不随机也没有关系，我想知道的只是每个格子被踩中的概率。这里不讨论技能和别的什么因素的影响，比如使用道具来控制行走或者因为事件触发行走之类的情况，简化一下只讨论在这一张地图上使用骰子行走的情况。

 

还有一点也需要说明，就是这个地图其实是有一些特殊的，学习过基本的关于图的知识都会明白连通图的概念，这个地图就是一个连通图，同时还是一个特殊的连通图，为什么说特殊呢？因为不会出现度为 1 的节点，这是什么意思呢？通俗点说就是不会出现死胡同，每一个格子都至少和其他任意两个格子连在一起，不像飞行棋，走到最后大家的目标就是走进死胡同里，这个大富翁的玩家目标是坚持到最后，当然这不是我们讨论的。我们不妨假设一个玩家可以在这个地图上走无限步，那么地图上每个格子被走到的概率是多少呢？还有一点需要说明，就是玩家行走是随机的，也就是说玩家的下一步是从和玩家当前格子相邻的那些格子中选一个进行行走，虽然在我的程序里有控制行走方向的机制以及格子的落步概率，我们不妨认为相邻格子的概率都是一样的，这样便于简化讨论。

 

好了，我已经把上面那个问题抽象出来了，就是在一个所有节点的度都大于等于2的无向连通图上，有个玩家去投骰子进行行走，让我们来看一下每个格子被走到的概率是多少？这里还有一点需要说明，我想象玩家会投无限次骰子，那么其实每次玩家走多少步对于我计算这个概率的影响只有一些极其特殊的情况下才存在，换句话说，在大多数情况下，玩家一步走多少都没有影响，有影响的是当地图比较特殊的时候，比如只有 2 个格子，玩家每次都走 2 步，那么玩家只会原地不动，我们排除这种情况，想象地图足够大。

 

这就像在电信路由中经常用的“随机徘徊”的方法，满足马尔可夫性质。我首先拿一个田字格来做试验，假如地图是这样的：

 

玩家从节点 1 开始出发，事实上从哪个节点开始出发都一样，每次摇骰子，然后进行走动，每次走动都从当前节点的相邻节点中平均概率选择一个节点作为行走目标，我测试一下行走 10W 步之后，每个节点被走到的次数，我用 lua 写了个模拟程序，如下：

我用一个 table 保存这张图，其实就是记录每个节点相连的节点罢了。比如节点 1，与它相连的节点有 2、4，所以 table 里第一项就保存了 2、4。

打印结果如下：

 

如果把结果用柱状图表示出来就是这样的：

可以清楚的看出，上面的 9 个节点被分成了 3 类，{ 1,3,7,9 }是一类，{ 2，4，6，8 }是一类，{ 5 }单独成为一类，再回头去看看那个地图，就明白了，{ 1,3,7,9 }其实就是角落的节点，{ 2，4，6，8 }是边中间的节点，{ 5 }是正中的节点，那么这 3 类有什么区别呢？仔细分析就发现原来他们的度不一样，{ 1,3,7,9 }的度都是 2，{ 2，4，6，8 }的度是 3，{ 5 }的度是 4。

照这么看来似乎这个概率只和节点的度有关系，于是我测试了下面这个复杂点的图，希望验证这个结论：

这个图上行走的结果如下柱状图：

 

虽然因为图太大，看不清具体的数值，但是可以明显看到，节点也被分成了 3 类，实际上也是上面的 3 种不同的度的节点集合。度为 4 的集合{ 16, 20, 41, 45 }，度为 3 的集合{ 37, 49 }，其他的节点度都为 2。而且从概率上看，度为 4 的节点的概率是度为 2 的节点概率的 2 倍，度为 3 的节点的概率是度为 2 的节点的概率的 1.5 倍。这正好是他们度之间的比值。

我变换了不同的地图的情况，发现都符合这个规律。所以我斗胆的认为这样的图中格子的概率只和它的度有关，而且是和度成正比例关系。

数学知识匮乏，我暂时无法证明这个，也许这是某个已知结论的特例或者是延伸，这里记录一下，以后说不定用的着。

事实上我设计的功能中，要求玩家不能走回头路，然而加上这个限制条件，这里的结论也一样成立，我还变换了不同的起始点并改变了每步能够走动的距离，甚至绘制了一张格子概率随着行走距离和初始坐标点变化的图，要是有朋友也感兴趣或者是能够帮我证明一下，我不甚感激。