5
$\begingroup$

This is a follow-up to this question: Given $n$ random chords of a circle, what is the distribution of the number of intersections? Random is defined by "endpoints uniform on the circle".

Update Numerical experiments indicate that the distribution converges to a gaussian.

$\endgroup$
6
  • 3
    $\begingroup$ It really depends on how chord lengths are distributed. For any collection of n chords (with no length appearing more than twice, and none a diameter), you can get from 0 to n choose 2 intersections by rotating chords individually. However, if they are all small , 0 is more likely, and if they are all near the length of a diameter, n choose 2 is more likely. Gerhard "You Might Use Circular Reasoning" Paseman, 2017.10.22. $\endgroup$ Oct 22, 2017 at 15:33
  • $\begingroup$ @GerhardPaseman The chords come from $2n$ uniform points on the circle, so the lengths are what they are... $\endgroup$
    – Igor Rivin
    Oct 22, 2017 at 15:52
  • $\begingroup$ @IgorRivin Then you should make that clear in the question! There are lots of ways to choose "random chords". In particular, the model referred to in the post you quoted has chords produced by two uniform points in the disc, rather than two uniform points on the perimeter. (Possibly it was edited since you wrote your question?) In any case, for two uniform points on the circle, usul has a nice simple answer below. $\endgroup$ Oct 22, 2017 at 18:20
  • $\begingroup$ @JamesMartin usul gives the expectation, I ask for the distribution... $\endgroup$
    – Igor Rivin
    Oct 22, 2017 at 18:32
  • $\begingroup$ Ah, I see. At the time I made my comment, the title of the question was "The expected number of chord intersections". So it's somewhat natural that both usul and I thought that you wanted the expected number :) $\endgroup$ Oct 22, 2017 at 20:25

3 Answers 3

1
$\begingroup$

The number of crossings in a chord diagram depends only on the order that the ends of the chords appear on the circle. Also, for any chord diagram every pairing of the $2n$ endpoints is equally likely. Therefore, it suffices to take any $2n$ distinct points on the circle and pair them at random.

This is a widely studied problem. A survey and the asymptotic distribution of the number of crossings appears in this paper (note the ridiculous price Springer wants for this conference proceedings), and can be read for free here.

$\endgroup$
3
$\begingroup$

For the expectation, linearity of expectation should help a lot. There are ${n\choose 2}$ pairs of chords, and if each chord is drawn i.i.d. then each pair has some probability of intersection of $p$, so the answer is $p{n\choose 2}$.

In the case where both endpoints of each chord are drawn uniformly at random, I believe $p=1/3$. Let's call the two chords AB and CD and imagine we first randomly place A; this divides the circle into a line segment, say, clockwise. Now the chords intersect if the ordering on this line segment is C, B, D or D, B, C, but do not intersect for any of the other four orderings. All six orderings are equally likely, so there's a $1/3$ chance that two chords will intersect.

$\endgroup$
2
$\begingroup$

A similar question came up in 2002 in usenet:alt.math.recreational and I gave an empirical answer which translated to this question would be that for $0 \le k \le \frac{n(n-1)}{2}$ the probability of $k$ intersections among the $n$ chords is

$$\frac{1}{(2n-1)!!} \sum_{j=0}^m (-1)^j {(n-j)(n-j+1)/2 - 1 - k \choose n-1} \left( {2n \choose j} - {2n \choose j-1}\right) $$

where $(2n-1)!! = \frac{(2n)!}{2^n \, n!}$ is the double factorial and $m=\Big\lfloor n+\frac12 - \sqrt{2n+2k+\frac14} \Big\rfloor$

Some values (not divided by the double factorial) are in OEIS A067310 and OEIS A067311 with the latter entry giving many related references.

As usul has said, the expectated number of intersections is $\frac{n(n-1)}{6}$. Empirically the variance seems to be $\frac{n(n-1)(n+3)}{45}$. I could well believe that suitably relocated and rescaled this converges in distribution towards a Gaussian distribution as $n$ increases , though for small $n$ it seems to be slightly right-skewed: the diagram shows the distributions for $n=15$, with a red Gaussian comparison illustrating this.

enter image description here

$\endgroup$

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.