Skip to content

Cover time of a random walk on a complete graph

Question

A complete undirected graph has N=100N=100 vertices. On the first turn you jump to a vertex chosen uniformly at random; on each later turn you jump to a uniformly random vertex, where staying put is allowed. What is the expected number of turns until every vertex has been visited at least once? Round to the nearest integer.

Short answer

519519. Each turn lands on a uniform vertex, so this is the coupon collector problem: with kk vertices seen, a new one appears with probability (N−k)/N(N-k)/N, taking N/(N−k)N/(N-k) turns on average. Summing gives NHN=100⋅H100≈518.7N H_N=100\cdot H_{100}\approx518.7.

Adapted from OpenQuant; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Expectation, Variance and Covariance is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free