Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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. –  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! –  Joseph O'Rourke 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
add comment

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.

share|improve this answer
    
Ah, thanks! I would never have hit upon "random geodesic laminations"! –  Joseph O'Rourke Sep 2 '10 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 '10 at 14:21
    
@louigi: Cool! That evaluates to approx. 13 for $n{=}100$. –  Joseph O'Rourke Sep 2 '10 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 '10 at 15:16
add comment

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

share|improve this answer
    
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 '10 at 15:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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