立方体随机游走回原点：期望步数
醉酒变异忍者蚁
题目详情
An ant starts a walk from a cube vertex, it walks on the edges and at every vertex it chooses to walk one of the available edges (including the edge it came from) with an equal probability. How many edges will the ant cross in average to come back to the starting point?
解析
把立方体 8 个顶点按与起点的距离分成 4 层：
- ：起点（距离 0）
- ：与起点相邻的 3 个顶点（距离 1）
- ：距离 2 的 3 个顶点
- ：对顶点（距离 3）
每走一步必然在相邻层之间移动。设从层 出发回到起点的期望步数为 ，可列方程组并解得
因此