概率 概率问题:一个随机的完美迷宫,它有多少个 “死角”?

neozhaoliang · 2020年09月02日 · 最后由 neozhaoliang 回复于 2020年09月25日 · 110 次阅读

我们称一个迷宫是完美的,如果迷宫中的任何两个房间之间都有且仅有唯一的道路相连。我们称迷宫中的一个房间是“死角”,当且仅当它只有一条道路与其它房间相通 。换句话说,一旦进去了就必须原路返回,没有其它出路。

问题:假设在一个 $n\times n$ 的网格图上,以完全相等的概率在所有的完美迷宫中随机任选一个,那么这个迷宫包含的死角的个数的比例的期望值是多少?这个期望是常数吗?还是随着 $n$ 的增加线性增长?或者 $\log$ 增长?

解释一下:完美迷宫可以看作是 $n\times n$ 网格图的一个生成树,迷宫的死角其实就是生成树的叶节点,其度数为 1。这个问题的本意就是问,对于 $n\times n$ 网格图的一个完全随机的生成树,其叶节点的个数与 $n^2$ 的比值与 $n$ 的变化关系。下图显示的是 48x36 的网格图的一个随机生成树,其中白色的部分是迷宫的房间:

你能猜到这个问题的答案吗?

共收到 1 条回复

公布一下答案:随着 $n\to\infty$,一个节点 $v$ 是随机生成树的叶节点的概率存在极限,这个极限值是

$$\frac{8(\pi-2)}{\pi^3}\approx 0.2945449182075.$$

是不是很奇妙呢?这个问题与随机游动,电网络和 Abelian sandpile 模型都有密切的联系。 下图显示了一个 80x80 的网格图的一个随机生成树,它包含 1884 个叶节点,所以叶节点占全部节点的比例为 $1884/6400=0.294375$,跟极限值很接近了!

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册