Personal Blogs

I saw this on a YouTube channel "Knights & Knaves" but this or similar questions seem to have been asked elsewhere too.

In a circle, if we draw 10 random chords, what is the expected number of times two of the chords will intersect? 

(What we mean by a random chord needs defining but for the purposes of this question we take it to be that each chord joins two points on the circumference with a uniform probability distribution, so the probability of the point chosen lying in a given arc is the length of that arc as a proportion of the circumference.)

One solution begins with the case of two chords and reasons along these lines. Suppose we choose four random points and consider the point A. If we join it randomly to one of the other points there are three cases, as shown below, and they are all equally likely, with probability 1/3.

Cases 1 and 3 have no intersections, Case 2 has 1. So the expected number of intersections is 

(1/3)x0 + (1/3)x1 + (1/3)x0 = 0 + 1/3 + 0 = 1/3

This seems to be the generally accepted argument, but I felt it was rather glib, so I got Copilot to write a simulation in Python. You can find the program at the end of this post. I added a bit of code at the end to run it multiple times and after 10,000,000 trials the overall proportion of times it found an intersection was 33.34%, so that seems to support the expectation being 1/3.

The argument continues as follows. We know the expectation for one pair of chords is 1/3 and if there are 10 chords there will be "10 choose 2" which is 10x(10-1)/2 = 45. There is a beautiful fact, called Linearity of Expectation, which tells us if the know the individual expectations of a set of random variables we can find their combined expectation just by adding all the individual expectations together, and this is valid even if the random variables are not independant of one another.

So in the present case we just add 45 lots of 1/3, one for each pair of chords, and find the expected number of intersections is 15. In the general case of n chords we have "n choose 2" pairs, and the expected number of intersections is nx(n-1)/2 lots of 1/3, or nx(n-1)/6.

I think this is the standard line of argument and there is no need to consider how many pairs there are. Here is a simpler approach that occurred to me.

Suppose we have two chords c1 and c2 and we add a third, c3. The expectation that c1 intersects c2 is 1/3 and the expectations that c3 intellects c1 and c2 are 1/3 and 1/3 respectively. By the Linearity of Expectation we can just add all these, so we get 1/3 + 1/3 + 1/3 = 1.

Now if we add a fourth chord c4, the expectation of it intersecting c1, c2 and c3 respectively will all be 1/3 so now the total expectation is 1 + 3x(1/3) = 2. When add a fifth chord the expectation will be 2 + 4x(1/3) = 10/3, and so on. After we have added the n-th chord the total expectation will be

(1 + 2 + 3 +... + (n-1)) x (1/3) = ((n-1)xn/2) x (1/3) = nx(n-1)/6

and voilà, we have the same answer as before!

Here is the Python program generated by Copilot

import math
import random

def generate_random_point_on_circle():
    angle = random.uniform(0, 2 * math.pi)
    return (math.cos(angle), math.sin(angle))

def ccw(A, B, C):
    """Check if three points are listed in a counter-clockwise order."""
    return (C[1] - A[1]) * (B[0] - A[0]) > (B[1] - A[1]) * (C[0] - A[0])

def segments_intersect(A, B, C, D):
    """Return True if line segments AB and CD intersect."""
    return ccw(A, C, D) != ccw(B, C, D) and ccw(A, B, C) != ccw(A, B, D)

def random_chords_intersect():
    # Generate two chords
    A = generate_random_point_on_circle()
    B = generate_random_point_on_circle()
    C = generate_random_point_on_circle()
    D = generate_random_point_on_circle()
    
    # Check if they intersect
    return segments_intersect(A, B, C, D)

count = 0
trials = 10000000
for trial in range(trials):
    if random_chords_intersect():
        count = count + 1
print((count/trials)*100)