Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 12 6 c Solution Created 2026-10-03 Updated 2026-10-14
First prove the concentration statement with its correct scale. Let , the th uniform order statistic. The number of sample points at most is . Therefore means , and means , up to probability-zero ties. Take and . Applying Chernoff bounds at gives, for an absolute and sufficiently large ,When the upper endpoint exceeds one its upper-tail event is empty. A union bound makes the total failure probability for all at most . On this event,where integral comparison gives .
The first vertex block has right endpoint and always contains , so its initial chord contributes vertex degree two. All its other endpoints are those with that fall below . Conditional on the right endpoints, these events are independent with probabilities . ThusThe fewer than early summands contribute at most to this conditional mean. For the rest, the uniform estimate and uniform tightness of giveTo control the actual fluctuations without assuming unconditional independence, restrict to the concentration event and . Then . Conditional Chebyshev inequality bounds the probability of a deviation exceeding by . The discarded endpoint event has limiting probability ; let . ThereforeSince has a continuous distribution, the corrected first-vertex degree in the LCD model tail isThis disproves the printed exponent for . The hint's factor is independently contradicted at : its proposed upper bound tends to , whereasThus the printed concentration event has probability tending to zero, not one. Replacing its by leads to the proven exponent . The exponent would instead arise for , but then the graph has vertices and the part (b) endpoint limit at becomes . It cannot repair all the printed claims with one convention. The literal part (c) is false for the named model; the full corrected limit and the source of the discrepancy are established above.