## Random noncrossing chords of a circle

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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! I have not yet absorbed all the information in the cited papers, but so far I have not found this 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.

-

2
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. – jc Sep 2 2010 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! – Joseph O'Rourke Sep 2 2010 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 – jc Sep 2 2010 at 14:05

## 2 Answers

The article "Random recursive triangulations of the disk via fragmentation theory" discusses many properties of the model you describe. The search word is random geodesic lamination.

-
Ah, thanks! I would never have hit upon "random geodesic laminations"! – Joseph O'Rourke Sep 2 2010 at 13:55

2
The height of that tree is conjectured (by Nicolas Curien in a talk I saw) to be of the order n^{(sqrt(17)-3)/2} -- if you pick two uniformly random nodes, this will be the rough distance between them. But an argument is missing to show that there is no small exceptional set of nodes at greater distance from one another. – Louigi Addario-Berry Sep 2 2010 at 14:21
@louigi: Cool! That evaluates to approx. 13 for $n{=}100$. – Joseph O'Rourke Sep 2 2010 at 14:34

2
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. – Louigi Addario-Berry Sep 2 2010 at 15:16

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

Louigi is absolutely right. We control "typical" height not absolute one. Note that a similar discrete model has been investigated by physicists see http://www.phys.ens.fr/~wiese/pdf/hiraRNA.pdf I think the maximal degree after n steps is logarithmic, but I don't have any exact expression for the expected value...

-

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)$! – Joseph O'Rourke Sep 2 2010 at 15:09
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 10, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.92633056640625, "perplexity_flag": "middle"}