Skip to content

Average number of closed groups from a name draw

Question

At a party, each of 5050 guests drops their name into a hat, and then each guest in turn draws one name. Each guest is linked to the person whose name they drew, so the guests split into closed loops (someone who draws their own name forms a group of one; if A draws B, B draws C and C draws A, then A, B, C form one group). What is the expected number of groups? Give your answer to one decimal place.

Short answer

About 4.54.5. The draw is a uniformly random permutation of 5050 people and groups are its cycles. The expected number of cycles of a random permutation of size nn is the harmonic number HnH_n, and H50≈4.499H_{50}\approx4.499.

Adapted from QuantQuestions.io; 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