Passing a token around a triangle

Question

Three friends A, B, C stand at the corners of a triangle, each connected to the other two. A token starts with A. Each round the current holder passes it to one of the other two, chosen at random.

On average, how many passes until the token first reaches B?

Accepted Answer

Let a be the expected passes to reach B starting from A, and c the expected passes starting from C. From A the token goes to B (done) or to C, each with chance 1/2: a = 1 + 	frac12 \cdot 0 + 	frac12 c. From C it goes to B (done) or to A, each with chance 1/2: c = 1 + 	frac12 \cdot 0 + 	frac12 a. By symmetry a = c, so a = 1 + 	frac12 a, giving 	frac12 a = 1 and a = 2. Takeaway. On a triangle (three mutually connected corners) the expected time between two corners is 2 steps, matching the general "n - 1" for a fully connected graph on n nodes.

Passing a token around a triangle

Your answer

Discussion

Learn the concepts

Related questions