随机走立方体到对角点的期望步数

Given a cube

专题: Probability / 概率
难度: L4
来源: QuantQuestion

题目详情

Given a cube, you can jump from one vertex to a neighboring vertex with equal probability. Assume you start from a certain vertex (does not matter which one). What is the expected number of jumps to reach the opposite vertex?

解析

按与目标的距离分层：距离 0、1、2、3。设期望为 $E_0=0,E_1,E_2,E_3$ 。

从距离 3 必到距离 2： $E_3=1+E_2$ 。

从距离 2：以 $2/3$ 到距离 1，以 $1/3$ 回到距离 3： $E_2=1+\frac{2}{3}E_1+\frac{1}{3}E_3.$

从距离 1：以 $1/3$ 到距离 0，以 $2/3$ 到距离 2： $E_1=1+\frac{2}{3}E_2.$

解得 $E_1=7,E_2=9,E_3=10$ ，因此

\boxed{10}.