醉蚂蚁走立方体

Drunk Ant

专题: Probability / 概率
难度: L6
来源: Brainstellar

题目详情

一只蚂蚁站在立方体某个顶点，只能沿棱边行走。它每次从当前顶点等概率选择一条棱走到相邻顶点。

问：到达对角顶点（相距最远的顶点）的期望走过棱边数是多少？

提示：把顶点按“离目标的距离层级”合并成若干等价状态。

An ant is standing on one corner of a cube & can only walk on the edges. The ant is drunk and from any corner, it moves randomly by choosing any edge! What is the expected number of edges the ant travels, to reach the opposite corner?

Hint

Try to find the equivalent vertices for the distance yet to travel. This should give $4$ equivalent merged vertices, with $1$ st being the start & the $4$ th being the destination.

解析

答案是 10。

把顶点分成 4 个等价状态：

$S_0$ ：起点
$S_1$ ：与起点相邻的 3 个点
$S_2$ ：与终点相邻的 3 个点
$S_3$ ：终点

设从状态 $S_i$ 到达终点的期望步数为 $E_i$ ，写出递推方程并求解，可得 $E_0=10$ 。

Original Explanation

$10$

Solution

We can define $4$ equivalent states, based on the corner the Ant is at:

Starting corner.
Corner adjacent to the starting corner.
Corner that shares an edge with the opposite corner.
The opposite corner.

Plot

We can represent the expected number of steps $E_i$ from each state as follows:

$E_0 = 1 + \dfrac{1}{3}(E_1 + E_1 + E_1)$
$E_1 = 1 + \dfrac{1}{3} (E_0 + E_2 + E_2)$
$E_2 = 1 + \dfrac{1}{3}(E_1 + E_1 + E_3)$
$E_3 = 0$ (already reached the destination)

Solving this we find $E_0 = 10$

Calculations:

$\implies E_0 = 1 + E_1 ~~\&~~ E_2 = 1 + 2/3 \cdot E_1$

Substitute $E_0$ and $E_2$ in the middle equation.

$\implies 3E_1 = 3 + (1 + E_1) + 2 (1 + 2/3 E_1)$

$\implies 3E_1 = 4 + E_1 + 2 + 4/3 E_1$

$\implies 2/3 E_1 = 6 \implies E_1=9 \implies E_0 = 10$