Moves for a robot to dock at the charger

Question

A robot lives in three zones A, B, C arranged in a line. From zone A it always moves to B. From zone B it moves to A or to C, each with probability 1/2. Zone C is the charging dock: once there, the robot stays and stops. It starts in zone A. On average, how many moves until the robot docks at C?

Accepted Answer

Let a and b be the expected moves to reach C from A and from B; C has value 0. Each move is one step: a = 1 + b \quad (	ext{from } A 	ext{ it always goes to } B), \qquad b = 1 + 	frac12 a + 	frac12 \cdot 0. Substitute a = 1 + b into the second equation: b = 1 + 	frac12 (1 + b) = 	frac32 + 	frac12 b \;\Longrightarrow\; 	frac12 b = 	frac32 \;\Longrightarrow\; b = 3, \qquad a = 1 + 3 = 4. Takeaway. A deterministic move contributes x = 1 + x' with no averaging; solving the two-state system gives 4 moves from A.

Moves for a robot to dock at the charger

Your answer

Discussion

Learn the concepts

Related questions