Two random chords crossing, Geometric Probability

Problem 12.1

Pick four points $A, B, C, D$ independently and uniformly on a circle, and draw the two chords $AB$ and $CD$ . What is the probability that the chords cross?

Solution. Forget how the four points are labelled and consider only the unordered set of four points on the circle. There are three ways to pair four points into two chords: $\{AB, CD\}, \quad \{AC, BD\}, \quad \{AD, BC\}.$

Fix four points on the circle in cyclic order $P_1, P_2, P_3, P_4$ . Exactly one of the three pairings produces crossing chords — the pairing $\{P_1 P_3, P_2 P_4\}$ , where each chord joins opposite points in cyclic order. The other two pairings yield non-crossing chords.

By symmetry, given four uniform random points, each of the three pairings is equally likely to be the original labelling $\{AB, CD\}$ . (Permuting the labels $A, B, C, D$ leaves the joint distribution of the four points invariant.) Hence $\boxed{\mathbb{P}(\text{crossing}) = \tfrac13.} \qedhere$

Four random points on a circle admit three pairings into two chords. Only one of the three pairings produces crossing chords (left); the other two produce non-crossing chords (centre and right). By symmetry each pairing is equally likely.

import numpy as np
# 4 uniform points on circle; chord AB = P0P1, chord CD = P2P3.
# Segments cross iff endpoints of one separate endpoints of the other.
theta = np.random.rand(4, 10**6) * 2*np.pi
x, y = np.cos(theta), np.sin(theta)
def side(p, q, r):
    return (q[0]-p[0])*(r[1]-p[1]) - (q[1]-p[1])*(r[0]-p[0])
A, B, C, D = [(x[i], y[i]) for i in range(4)]
cross = (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)
print(f"sim: {cross.mean():.5f}   exact: {1/3:.5f}")
# sim: 0.33286   exact: 0.33333