一个完全随机的迷宫，它有多少个死角？

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

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

解释一下：完美迷宫可以看作是 n x n 网格图的一个生成树，迷宫的死角其实就是生成树的叶节点，其度数为 1 。这个问题的本意就是问，对于网格图的一个完全随机的生成树，其叶节点所占比例 (注意这个比例是随机变量，不同的树比例也不同)随着 n 的变化关系。下图显示的是 80x80 的网格图的一个随机生成树，其中叶节点用蓝色的圆点标出。它有 1884 个叶节点，所占比例为 1884/6400=0.294375 。

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

PS: 上一次的 "走出太阳系" 的问题 https://v2ex.com/t/716022 的解答公布了，见 http://pywonderland.com/random-walk-potential-kernel/

本文答案会在下周公布。