# Random noncrossing chords of a circle

Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord. The disk is then partitioned into regions bounded by chords alternating with circular arcs. For example, here are $n{=}100$ random noncrossing chords, with a region bounded by 5 chords highlighted (in green).

I am interested in the statistics of the structure of the dual trees for these regions. Assign each region a node, and connect two nodes by an edge if they share a chord. In the example above, the highlighted region's node has degree 5. Example questions: What is the expected maximum degree of a node for $n$ chords? Making a max-degree node the root, what is the expected height of the tree? (In the example above, the height is 21.) Etc.

Has anyone encountered this model before? Or a model sufficiently analogous to help establish these statistics? Thanks for any pointers!

Edit. Many thanks for the wealth of information provided by the community! So far I have not found the following specific question answered (although it is likely implied, perhaps in the papers they cite): What is the expected maximum degree of a node as $n \rightarrow \infty$? What brought me to this topic in the first place is that I wondered if it might be near 3.

• are you aware of the work by David Aldous on random triangulations of the circle? there's a nice American Mathematical Monthly article of his from 1991 reviewing that construction. He considers triangulations of regular n-gons as n goes to infinity, and chooses triangulations uniformly from that set. in this case the dual trees are binary trees and there is a series of bijections to positive walks from 0 to 2(n-1) which in the large n limit tend to Brownian excursions after rescaling.
– j.c.
Sep 2 '10 at 13:52
• @jc: No, I was not familiar. Must be this paper: "Triangulating the Circle at Random." Amer. Math. Monthly 101 (1994) 223-233. I will investigate. Thanks! Sep 2 '10 at 13:57
• oops, I misstated the result: the positive walks are those starting at 0 and first returning to 0 after 2(n-1) steps of +1 or -1
– j.c.
Sep 2 '10 at 14:05

• @louigi: Cool! That evaluates to approx. 13 for $n{=}100$. Sep 2 '10 at 14:34
• But there are constants. Together Theorem 1.1 (ii) and Proposition 4.1 imply that, viewing the circle as the unit circle in the complex plane, the expected distance from 1 to $e^{2 \pi i u}$ is about $2.0(n u (1-u))^{\beta}$, where $\beta = (\sqrt{17}-3)/2$. (The 2.0 here is a pretty good approximation to what is in fact a ratio of Gamma functions.) This gives expected distance a little over 12 between $1$ and $-1$, for example. Sep 2 '10 at 15:16
• Thanks, your paper that Gjergji cited is exactly what I was looking for! I will enjoy learning the source of the magic number $\frac{1}{2} (\sqrt{17} -3)$! Sep 2 '10 at 15:09