Part (a): Probability of intersection for $n = 2$

Problem Setup

We are given 4 points ($p_1, p_2, p_3, p_4$) on a circle, labeled counter-clockwise. We randomly pair them into two line segments. There are three distinct pairing possibilities:

1. $\{(p_1, p_2), (p_3, p_4)\}$
2. $\{(p_1, p_3), (p_2, p_4)\}$
3. $\{(p_1, p_4), (p_2, p_3)\}$

We need to calculate the probability that the two line segments intersect.

Key Insight

For two line segments to intersect, one endpoint of each segment must lie "inside" the other segment's endpoints in the cyclic order. In the context of the circle:

• Two line segments intersect if and only if their endpoints are interleaved in the circular order. For example:
  • If the segments are $(p_1, p_3)$ and $(p_2, p_4)$, the order $p_1, p_2, p_3, p_4$ ensures intersection.
  • If the order is $p_1, p_3, p_2, p_4$, there is no intersection.

Enumerating Cases

For 4 points, there are $\binom{4}{2} / 2 = 3$ ways to pair the points. Let us examine these pairings:

1. $(p_1, p_2), (p_3, p_4)$: No interleaving, so no intersection.
2. $(p_1, p_3), (p_2, p_4)$: Interleaved, so they intersect.
3. $(p_1, p_4), (p_2, p_3)$: Interleaved, so they intersect.

Thus, in $2$ out of $3$ cases, the segments intersect.

Probability

The probability of intersection is: $P(\text{intersection}) = \frac{\text{Number of intersecting cases}}{\text{Total number of cases}} = \frac{2}{3}.$

---

Part (b): Expected number of intersections for general $n$

Problem Setup

We now generalize to $2n$ points. After randomly pairing these points into $n$ line segments, we need to compute the expected number of intersections among these $n$ line segments.

Key Insight

Let $\ell_i$ and $\ell_j$ denote two line segments. The probability that $\ell_i$ and $\ell_j$ intersect depends only on the cyclic order of the endpoints, and as in part (a), this probability is $\frac{1}{3}$.

Using Indicator Variables

Define an indicator random variable:

\begin{cases} 1 & \text{if line segments } \ell_i \text{ and } \ell_j \text{ intersect}, \\ 0 & \text{otherwise}. \end{cases}$$ The total number of intersections is: $$X = \sum_{1 \leq i < j \leq n} I_{ij}.$$ The expected value of $$X$$ is given by: \[ \mathbb{E}[X] = \sum_{1 \leq i < j \leq n} \mathbb{E}[I_{ij}]. \] Since $$\mathbb{E}[I_{ij}] = P(\ell_i \text{ and } \ell_j \text{ intersect}) = \frac{1}{3}$$, we have: $$\mathbb{E}[X] = \frac{1}{3} \sum_{1 \leq i < j \leq n} 1.$$ #### Number of Pairs The total number of pairs of line segments is $$\binom{n}{2} = \frac{n(n-1)}{2}$$. Thus: $$\mathbb{E}[X] = \frac{1}{3} \cdot \frac{n(n-1)}{2}.$$ Simplifying: $$\mathbb{E}[X] = \frac{n(n-1)}{6}.$$ --- ### Final Answers 1. **Part (a):** The probability of intersection for $$n = 2$$ is: $$P(\text{intersection}) = \frac{2}{3}.$$ 2. **Part (b):** The expected number of intersections for general $$n$$ is: $$\mathbb{E}[X] = \frac{n(n-1)}{6}.$$ --- ### Follow-Up Questions 1. How does the probability of intersection change if points are not uniformly distributed? 2. What is the variance of the number of intersections for general $$n$$? 3. Can you derive a closed formula for the probability of intersection for $$n = 3$$? 4. How would the solution change if points were chosen randomly in the interior of the circle instead of on its border? 5. Can this approach be extended to higher-dimensional analogs, such as line segments in a sphere? ### Tip When using indicator variables, ensure independence or correctly account for correlations to avoid incorrect expectations.