Jumping among six fully connected hubs

Question

Six hubs are each directly connected to all of the others. A traveler starts at one hub; each jump goes to one of the other five hubs, chosen uniformly. The traveler stops on reaching a particular target hub.

What is the expected number of jumps to reach the target, starting from another hub?

Accepted Answer

From any non-target hub, all five destinations are equally likely, so by symmetry every non-target hub has the same expected count e. One jump lands on the target (value 0) with probability 	frac15, or on one of the four other non-target hubs (each value e) with total probability 	frac45: e = 1 + 	frac15 (0) + 	frac45 e \;\Longrightarrow\; 	frac15 e = 1 \;\Longrightarrow\; e = 5. Takeaway. On a fully connected graph of n vertices, every step hits the target with probability \frac{1}{n-1}, so the expected hitting time is n - 1; here 5 jumps.

Jumping among six fully connected hubs

Your answer

Discussion

Learn the concepts

Related questions