Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 7 / c

View the necklace as a cycle graph. Between the white bead and $B$ there are two edge-disjoint paths, containing $k$ and $n-k$ links. The beads remain connected if and only if at least one of these paths is uncut.

There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ equally likely cut sets. Keeping the $k$-link path uncut requires all three cuts to be among its $n-k$ complementary links, giving $\left(\genfrac{}{}{0ex}{}{n-k}{3}\right)$ choices. Keeping the other path uncut gives $\left(\genfrac{}{}{0ex}{}{k}{3}\right)$ choices. These two events are disjoint because three links are cut and they cannot all lie in both complementary paths. ThereforeUse $\left(\genfrac{}{}{0ex}{}{a}{3}\right)=0$ for $0\le a<3$. The answer is unchanged by exchanging $k$ and $n-k$, so either orientation around the necklace gives the same value. This is the connectivity calculation for random cuts of a cycle.

Let $I_B$ be the indicator that black bead $B$ belongs to the white bead's connected component. The number of such black beads is ${\sum }_B{I}_B$. By linearity of expectation, no independence between these indicators is needed.

For $n=7$, the six oriented distances $1,\dots ,6$ give respective probabilitiesTheir sum is $2$, the expected number of black beads in the white component. As a check, summing the formula from (i) and using ${\sum }_{k=1}^{n-1}\left(\genfrac{}{}{0ex}{}{k}{3}\right)=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ gives the general value $2\left(\genfrac{}{}{0ex}{}{n}{4}\right)/\left(\genfrac{}{}{0ex}{}{n}{3}\right)=(n-3)/2$, again equal to $2$ when $n=7$.