Skip to content

Expected complete groups of four in a random graph

Question

Twelve bulbs are arranged on a circle and every pair is joined by a wire. Each wire is independently live with probability 12\tfrac12. Call a set of bulbs fully connected if every pair inside it is joined by a live wire. What is the expected number of fully connected sets of exactly 44 bulbs?

Short answer

49564\tfrac{495}{64}. There are (124)=495\binom{12}{4}=495 sets of four bulbs, and a given set is fully connected when all of its (42)=6\binom42=6 wires are live, which has probability 2−62^{-6}. Linearity of expectation gives 495/64495/64.

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