Expected number of pieces cut by random chords, Geometric Probability

Problem 22.1

$n$ chords are drawn independently on a disc, each determined by two independent uniform random endpoints on the boundary circle. Into how many pieces do the $n$ chords partition the disc, on average?

Solution. Start with the disc as a single region (one piece). As each chord is added, the number of new pieces it creates equals one plus the number of times it crosses previously-drawn chords — every new crossing splits an existing region into two.

Let $X_{ij}$ be the indicator that chord $i$ crosses chord $j$ . The total number of crossings among all $n$ chords is $X = \sum_{i < j} X_{ij}$ , with (from Chapters 12 and 18) $\mathbb{E}[X] = \binom{n}{2} \cdot \tfrac13 = \frac{n(n-1)}{6}.$

The number of pieces is $1 + n + X$ (one initial piece, plus one for each chord, plus one for each crossing). Therefore $\boxed{\mathbb{E}[\text{pieces}] = 1 + n + \frac{n(n-1)}{6}.} \qedhere$

Four chords of the unit disc (endpoints on boundary) shown in four colours. The disc is partitioned into 1 + 4 + X pieces, where X is the number of pairwise intersections. Here there are 5 intersections, giving 10 pieces. — Four chords of the unit disc (endpoints on boundary) shown in four colours. The disc is partitioned into $1 + 4 + X$ pieces, where $X$ is the number of pairwise intersections. Here there are 5 intersections, giving 10 pieces.

For $n = 1$ we expect $2$ pieces. For $n = 2$ : $1 + 2 + \tfrac13 = \tfrac{10}{3} \approx 3.33$ . For $n = 5$ : $1 + 5 + \tfrac{10}{3} = \tfrac{28}{3} \approx 9.33$ . For $n = 10$ : $1 + 10 + 15 = 26$ .

The formula $1 + n + X$ is an instance of Euler’s formula for planar graphs: $V - E + F = 1 + C$ , where $C$ is the number of connected components of the graph and $F$ includes the exterior face. When $n$ chords with $X$ crossings are drawn in a disc, the planar graph has $V = 2n + X$ vertices (chord endpoints plus crossings), $E = n + 2X + 2n$ edges (chord pieces plus boundary arcs), and $C=1$ because the circle boundary connects all chord endpoints. Thus $F=2-V+E=2+n+X$ , and subtracting the exterior face leaves $1+n+X$ pieces inside the disc.

import numpy as np
# For n = 5 random chords, expected pieces = 1 + 5 + 10/3 = 28/3.
# Count crossings using the side-of-line test (same as the chapter on crossing pairs), then add 1 + n.
n, N = 5, 10**4
pieces = []
for _ in range(N):
    theta = np.random.rand(2*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])
    cr = 0
    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])
            if np.sign(side(A,B,C))*np.sign(side(A,B,D)) < 0 and \
               np.sign(side(C,D,A))*np.sign(side(C,D,B)) < 0:
                cr += 1
    pieces.append(1 + n + cr)
print(f"sim: {np.mean(pieces):.4f}   exact: {1+n+n*(n-1)/6:.4f}")
# sim: 9.3485   exact: 9.3333