medium   Probability

Undirected Graph Search I

A release-checked medium problem for training Linearity of Expectation, Geometric Probability.

Question

You are given a complete undirected graph with $N \geq 2$ nodes. You first select a uniformly random node to go to, and then each step after, you select to move to any of the nodes ($\textbf{including}$the one you are presently on) in the graph uniformly at random. Find the expected number of turns that are performed until you visit all of the nodes with $N = 100$ and round to the nearest integer.

Practice focus

This Probability problem is tagged Linearity of Expectation, Geometric Probability. State the random variables and conditioning information explicitly, then check the result against boundary cases before opening hints or a solution.

Explore related collections

Reviewed questions in this area

easyBaby BoyReviewed

Probability · SIG, DE Shaw

easyBad BagelReviewed

Probability · SIG, Jane Street