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).
alt text
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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – j.c.
    Sep 2 '10 at 13:52
  • $\begingroup$ @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! $\endgroup$ Sep 2 '10 at 13:57
  • $\begingroup$ 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 $\endgroup$
    – j.c.
    Sep 2 '10 at 14:05

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.

  • $\begingroup$ Ah, thanks! I would never have hit upon "random geodesic laminations"! $\endgroup$ Sep 2 '10 at 13:55
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 2 '10 at 14:21
  • $\begingroup$ @louigi: Cool! That evaluates to approx. 13 for $n{=}100$. $\endgroup$ Sep 2 '10 at 14:34
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 2 '10 at 15:16

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...

  • 1
    $\begingroup$ 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)$! $\endgroup$ Sep 2 '10 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.