Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 12 / 6

There are genuine normalization inconsistencies in this PDF. In the standard linearized chord diagram model $G_n^{(1)}$, time $n$ gives $n$ edges and total vertex degree $2n$, with self-loops counted twice. The paper calls $2n$ the number of edges. Its right-endpoint hint also uses $\sqrt{i/(2n)}$ rather than $\sqrt{i/n}$. These cannot both describe the standard model; part (c)'s exponent is consequently inconsistent as well. We give the definition, prove the alternative construction and its limits, and explicitly identify the corrected conclusion rather than infer an invalid constant from the printed hint.

Start from the empty graph at time zero, or from one vertex with one self-loop at time one. To obtain $G_t$ from $G_{t-1}$, add vertex $t$ and an edge directed from $t$ to $I_t$, whereA self-choice creates a self-loop. The old vertex degrees sum to $2(t-1)$, so these probabilities sum to one. This is exact preferential attachment, including the outward half of the new edge as weight one for the new vertex; it is not a rule normalized by $2t$ or a process adding two edges at each step. The degree of a vertex here is its total incoming plus outgoing vertex degree. The construction in part (a) has exactly one chord per vertex and makes the edge-count discrepancy explicit.

Draw $n$ independent pairs of independent uniform random variables on $[0,1]$. In each pair call the minimum $L$ and maximum $R$, then relabel whole pairs so $R_1<\cdots <R_n$. Merge all endpoints in $(R_{i-1},R_i]$ into vertex $i$, with $R_0=0$, and join the blocks containing the two endpoints of each pair, orienting from the right endpoint to the left. Self-loops are retained. This gives the uniform linearized chord diagram representation.

Before ordering, a pair has joint density $2$ on $0<L<R<1$. Consequently its maximum has distribution $\mathrm{Pr}(R\le r)=r^2$ and density $2r$; conditional on $R=r$, its minimum is uniform on $[0,r]$. Independence and relabelling give the equivalent precise descriptionEvery one of the $(2n)!$ relative orderings of the independently drawn labelled endpoints has the same probability. After forgetting pair labels and within-pair labels, each matching of $2n$ ordered points is produced by $2^{n}n!$ orderings. Thus its matching is uniform among the $(2n-1)!!$ pairings.

To prove equivalence with the recursive graph law, remove the last endpoint and its mate from a uniform pairing. The remaining ordered points have a uniform $(n-1)$-pairing, and the mate's old rank is uniform among the $2n-1$ possible ranks, independently of that smaller pairing. Conversely insert the mate into a uniformly chosen one of its $2n-1$ gaps, and pair it with the new final endpoint. For each old vertex block, the number of gaps assigned to it is exactly the number of endpoints already in that block, hence its old total vertex degree. These are the gaps immediately before each endpoint of that block. The last gap, after the last old endpoint, makes both new endpoints belong to the new final block and produces a self-loop. Therefore the attachment probabilities are $d_i/(2n-1)$ for old vertices and $1/(2n-1)$ for the new one. Induction proves the continuous construction and the recursive LCD model have the same distribution. Inserting a left endpoint into an old block raises exactly that vertex's vertex degree without splitting any old block.

The first right endpoint is the smallest of $n$ independent pair maxima. A maximum exceeds $r$ with probability $1-r^2$, so for $0\le x\le \sqrt{n}$,Taking the limit gives the requested, correctly normalized resultThus $\sqrt{n}{R}_1$ converges to a continuous nonnegative limit $W$ with survival function $\mathrm{Pr}(W\ge x)=e^{-x^2}$. In particular the scaled first right endpoint is tight. This calculation uses maxima of pairs, not the first order statistic of all $2n$ individual endpoints, which would have a different scale. The converted TeX loses the formula in this part; the displayed limit has been recovered directly from the PDF.

First prove the concentration statement with its correct scale. Let $U_i=R_i^2$, the $i$th uniform order statistic. The number of sample points at most $z$ is $B_z\sim \mathrm{Bin}(n,z)$. Therefore $U_i>z$ means $B_z<i$, and $U_i<z$ means $B_z\ge i$, up to probability-zero ties. Take ${\epsilon }_n=1/\log n$ and $M=\lceil n^{1/10}\rceil$. Applying Chernoff bounds at $z=(1\pm {\epsilon }_n{)}^{2}i/n$ gives, for an absolute $c_0>0$ and sufficiently large $n$,When the upper endpoint exceeds one its upper-tail event is empty. A union bound makes the total failure probability for all $M\le i\le n$ at most $2n\exp (-c_{0}M/(\log n{)}^2)=o(1)$. On this event,where integral comparison gives ${\sum }_{i=M}^n{i}^{-1/2}=2\sqrt{n}+O(\sqrt{M})$.

The first vertex block has right endpoint $R_1$ and always contains $L_1$, so its initial chord contributes vertex degree two. All its other endpoints are those $L_i$ with $i\ge 2$ that fall below $R_1$. Conditional on the right endpoints, these events are independent with probabilities $R_1/R_i$. ThusThe fewer than $M$ early summands contribute at most $M=o(\sqrt{n})$ to this conditional mean. For the rest, the uniform estimate and uniform tightness of $\sqrt{n}{R}_1$ giveTo control the actual fluctuations without assuming unconditional independence, restrict to the concentration event and $\sqrt{n}{R}_1\le A$. Then $\mu (R)\le M+2+CA\sqrt{n}$. Conditional Chebyshev inequality bounds the probability of a deviation exceeding $\eta \sqrt{n}$ by $(M+2+CA\sqrt{n})/({\eta }^{2}n)=o(1)$. The discarded endpoint event has limiting probability $e^{-A^2}$; let $A\to \infty$. ThereforeSince $W$ has a continuous distribution, the corrected first-vertex degree in the LCD model tail isThis disproves the printed exponent $-y^2/8$ for $G_n^{(1)}$. The hint's factor is independently contradicted at $i=n$: its proposed upper bound tends to $1/\sqrt{2}$, whereasThus the printed concentration event has probability tending to zero, not one. Replacing its $2n$ by $n$ leads to the proven exponent $-y^2/4$. The exponent $-y^2/8$ would instead arise for $d_1(2n)/\sqrt{n}$, but then the graph has $2n$ vertices and the part (b) endpoint limit at $x/\sqrt{n}$ becomes $e^{-2x^2}$. 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.