Cover time of a random walk on a complete graph
Question
A complete undirected graph has 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
. Each turn lands on a uniform vertex, so this is the coupon collector problem: with vertices seen, a new one appears with probability , taking turns on average. Summing gives .
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 solutionLessons behind this question
- Expectation, Mean, and Variance
- Conditional Expectation and Variance Revisited
- Continuous Random Variables and Probability Density Functions
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