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

Multiplying the beta distribution density by $x$ gives a constant multiple of the normalized density with parameters $(p+1,q)$:Integrating and using the fact that the latter probability density function integrates to one givesThis is a normalization-ratio argument, requiring no explicit integration of the polynomial density.

For $q>1$, decreasing the second parameter by one gives another valid beta distribution density andNormalization therefore givesThe restriction $q>1$ is essential for this finite expected value; when $q=1$, the singularity near $1$ instead makes the expectation infinite.

By independence, the joint probability density is the product of the two uniform distribution densities:Changing its values on the boundary does not affect any probability or expected value.

Split the unit square into $v\le u$ and $v>u$. The maximum is $u$ on the first triangle and $v$ on the second, soThe shared boundary has zero probability, so it is not counted twice in this joint density calculation.

For $W=\max \{U,V\}$ and $0\le w\le 1$, independence gives the cumulative distribution functionThe cumulative distribution function is zero below $0$ and one above $1$. Differentiating on the interior givesup to irrelevant endpoint values. There are no endpoint atoms. This maximum is an order statistic.

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$.