Intersections among n random chords, Geometric Probability

Problem 18.1

Let $n \geq 2$ chords be drawn independently on a circle, each chord defined by two independent uniform random endpoints on the circle. What is the expected number of pairs of chords that cross each other?

Solution. Let $X$ be the number of pairs of crossing chords. Write $X = \sum_{i < j} X_{ij}$ , where $X_{ij}$ is the indicator of “chord $i$ crosses chord $j$ ”.

By Chapter 12, each individual pair of chords (defined by $4$ independent uniform endpoints) crosses with probability $\tfrac13$ . Hence $\mathbb{E}[X_{ij}] = \tfrac13$ for every pair $(i, j)$ .

By linearity of expectation (even though the $X_{ij}$ are not independent, linearity still applies), $\mathbb{E}[X] = \sum_{i < j} \mathbb{E}[X_{ij}] = \binom{n}{2} \cdot \tfrac13.$ Therefore $\boxed{\mathbb{E}[X] = \frac{n(n-1)}{6}.} \qedhere$

Five random chords of the unit circle, each in a distinct colour, with endpoints on the boundary. For n = 5 chords the expected number of pairwise intersections is \binom{5}{2}/3 = 10/3 \approx 3.33 . — Five random chords of the unit circle, each in a distinct colour, with endpoints on the boundary. For $n = 5$ chords the expected number of pairwise intersections is $\binom{5}{2}/3 = 10/3 \approx 3.33$ .

For $n = 10$ we expect $15$ crossings, for $n = 100$ some $1650$ . This quadratic growth in $n$ — a direct consequence of summing $\binom{n}{2}$ pair indicators and applying linearity of expectation — is the foundation of many probabilistic-combinatorial arguments (“each pair of objects contributes its $\tfrac13$ to the mean”). The indicators are not independent — two pairs sharing a chord are correlated — but linearity needs no independence. By Markov’s inequality one can quickly bound the number of crossings above; tighter bounds come from second-moment or martingale methods. The special case $n = 2$ reproduces Chapter 12’s answer $\tfrac13$ .

import numpy as np
# Count crossings among n=5 chords using the geometric side-test from the two-chord crossing problem.
n, N = 5, 10**5
theta = np.random.rand(2*n, N) * 2*np.pi
x, y = np.cos(theta), np.sin(theta)
def side(A, B, C):
    return (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])
total = np.zeros(N)
for i in range(n):
    for j in range(i+1, n):
        A, B = (x[i], y[i]), (x[n+i], y[n+i])
        C, D = (x[j], y[j]), (x[n+j], y[n+j])
        cr = (np.sign(side(A,B,C))*np.sign(side(A,B,D)) < 0) & \
             (np.sign(side(C,D,A))*np.sign(side(C,D,B)) < 0)
        total += cr
print(f"sim: {total.mean():.4f}   exact: {n*(n-1)/6:.4f}")
# sim: 3.3283   exact: 3.3333