FreeProbabilityMedium

Chords Intersection I

Asked atFive RingsHudson River TradingJump Trading

Draw $10$ chords in a circle. Each chord joins two points chosen independently and uniformly at random on the circumference. What is the expected number of points where two chords cross?

Solution

Try it yourself first. Open a hint if you get stuck.

Hint 1

Write the number of crossings as a sum over pairs of chords, and use linearity of expectation.

Hint 2

For one pair of chords, only the order of the four endpoints around the circle matters. In how many ways can four points be split into two chords, and how many of those cross?

Show solution

Step 1: Count by pairs of chords. For each pair of chords $i < j$ , let $X_{ij} = 1$ if they cross and $0$ if they don't. (Three chords meeting at one point has probability $0$ .) The number of crossing points is $\sum_{i<j} X_{ij}$ , and by linearity of expectation,

E[\text{crossings}] = \sum_{i<j} P(\text{chords } i \text{ and } j \text{ cross}).

Step 2: One pair of chords. Fix the four endpoints of the two chords and name them $A, B, C, D$ in clockwise order. There are exactly three ways to pair four points into two chords:

Three circles with points A, B, C, D in clockwise order. AB + CD: no crossing. AC + BD: the chords cross. AD + BC: no crossing.

Only $AC + BD$ crosses, because it is the only pairing where each chord separates the other chord's two endpoints. The two chords' endpoints are four independent uniform points, so each of the three pairings is equally likely. So every pair of chords crosses with probability $\tfrac13$ .

Step 3: Add up. There are $\binom{10}{2} = 45$ pairs of chords, so

E[\text{crossings}] = 45 \cdot \tfrac13 = 15.

Answer: $15$ .

In general, $n$ random chords cross $\tfrac13\binom{n}{2}$ times on average.

Question

Solution