6
$\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$ Commented 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
    Commented 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$ Commented Oct 22, 2017 at 18:20
  • $\begingroup$ @JamesMartin usul gives the expectation, I ask for the distribution... $\endgroup$
    – Igor Rivin
    Commented Oct 22, 2017 at 18:32
  • 1
    $\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$ Commented Oct 22, 2017 at 20:25

3 Answers 3

2
$\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$
4
$\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$
3
$\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$
3
  • $\begingroup$ @usul Given your setting. Can you generalize the result on how many of the intersections lie within a circle of radius $r>1$. We still initialize the lines by drawing two points on the circle with radius 1. But now we want to know how many of the intersections lie within a circle of radius $r>1$. (My original question is very related to this: math.stackexchange.com/questions/4729880/…) $\endgroup$
    – NicAG
    Commented Jul 3, 2023 at 18:29
  • $\begingroup$ @NicAG - is this aimed at my answer here or at usul (who will not have seen your comment)? $\endgroup$
    – Henry
    Commented Jul 3, 2023 at 19:13
  • $\begingroup$ Sorry, I mixed up the names. It was aimed at you. I can also open a new question on mathoverflow on this topic if the answer is more involved. $\endgroup$
    – NicAG
    Commented Jul 3, 2023 at 20:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .