Random walk on a triangle with a tail

Question

Four points are connected like this: P, Q, R form a triangle (each joined to the other two), and one extra point S is joined only to R. A bug moves each step to a uniformly random neighbor of its current point. In the long run, what fraction of time does the bug spend at point R, the junction?

Accepted Answer

For a uniform random walk, the long-run share of a point is proportional to its degree (its number of connections). Count connections: - P: joined to Q, R, so degree 2. - Q: joined to P, R, so degree 2. - R: joined to P, Q, S, so degree 3. - S: joined only to R, so degree 1. Total of the degrees: 2 + 2 + 3 + 1 = 8. The share of R is its degree over this total: \piR = \frac{3}{8}. So the bug spends three eighths of its time at the junction R, the busiest point. The dangling point S gets only 	frac18. Takeaway. The most connected node claims the largest long-run share. Just divide each node's …

Random walk on a triangle with a tail

Your answer

Discussion

Learn the concepts

Related questions