跳到主要内容
← 返回题库
免费概率中等

Chords Intersection I

考察公司Five RingsHudson River TradingJump Trading

题目

Draw 1010 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?

解析

先自己试一试,卡住了再打开提示。

提示 1

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

提示 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?

查看解析

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

E[crossings]=∑i<jP(chords i and j cross).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,DA, 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+BDAC + 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 13\tfrac13.

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

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

Answer: 1515.

In general, nn random chords cross 13(n2)\tfrac13\binom{n}{2} times on average.