Random walk on a star of five spokes

Question

A central hub is connected to five outer nodes (a star shape). The outer nodes connect only to the hub, not to each other. A walker moves each step to a uniformly random neighbor of its current node.

In the long run, what fraction of time does the walker spend at the central hub?

Accepted Answer

For a uniform random walk, the long-run share of a node is proportional to its degree (its number of connections). Count connections: - The hub connects to all 5 outer nodes, so its degree is 5. - Each outer node connects only to the hub, so its degree is 1, and there are five of them. Total of the degrees: 5 + 5 	imes 1 = 10. The share of the hub is its degree over this total: \pi{	ext{hub}} = \frac{5}{10} = \frac{1}{2}. So the walker spends half its time at the hub. This makes sense: every step from an outer node returns to the hub, so the hub is visited on every other step. Each outer no…

Random walk on a star of five spokes

Your answer

Discussion

Learn the concepts

Related questions