= Solution
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 $\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 description
$$
\boxed{R_1^2<\cdots<R_n^2\text{ are the order statistics of }n\text{ independent }U(0,1)\text{ variables};\quad L_i\mid(R_1,\ldots,R_n)\ \text{independently }U(0,R_i).}
$$
Every 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 \b[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.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2005/iii/paper-12-lcd.png]
{title=A linearized chord diagram with six vertex blocks, six edges and loops counted twice in the block degrees}
Back to article page
