Skip to content

Random walk covering a simplex and returning home

Question

An ant starts at one vertex of an nn-dimensional simplex (which has n+1n+1 vertices, every pair joined by an edge). At each step it moves to one of the other nn vertices chosen uniformly at random. It stops the first time it is back at its starting vertex having already visited every vertex. What is the expected number of steps?

Short answer

n(Hn+1)n(H_n+1), where Hn=1+12+⋯+1nH_n=1+\tfrac12+\dots+\tfrac1n. With ii of the nn other vertices visited, each step reaches a new one with probability n−in\tfrac{n-i}{n}, so covering them all takes nHnnH_n steps on average (coupon collector). From then on each step returns home with probability 1n\tfrac1n, adding nn more.

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