返回题库

立方体边上随机行走：回到起点期望时间

We have an ant

专题
Algorithmic Programming / 算法编程
难度
L4

题目详情

Suppose we have an ant traveling on edges of a cube, going from one vertex to another. The ant never stops and it takes him one minute to go along one edge. At every vertex, the ant randomly picks one of the three available edges and starts going along that edge. We pick a vertex of the cube and put the ant there. What is the expected number of minutes that it will take the ant to return to that same vertex?

解析

按与起点的图距离分层，设 f(i)f(i) 为距起点 ii 的期望回返时间，i=0,1,2,3i=0,1,2,3。

有 f(0)=1+f(1).f(0)=1+f(1).

距 1：以 1/31/3 回到 0，以 2/32/3 到距 2： f(1)=13⋅1+23(1+f(2)).f(1)=\frac{1}{3}\cdot1+\frac{2}{3}(1+f(2)).

距 2：以 2/32/3 到距 1，以 1/31/3 到距 3： f(2)=23(1+f(1))+13(1+f(3)).f(2)=\frac{2}{3}(1+f(1))+\frac{1}{3}(1+f(3)).

距 3：必到距 2： f(3)=1+f(2).f(3)=1+f(2).

解得 f(0)=8f(0)=\boxed{8}.