Tag: binomial

Let’s say the robot cuts $n$ random chords. Due to the way in which the chords are randomly chosen, two different chords will never begin or end at the exact same point along the circumference. Moreover, any time chords intersect inside the circle, that intersection will involve exactly two chords. We don’t need to worry about cases where three cuts perfectly intersect in a single point (i.e. the way you’d normally cut a pizza!), since that will never happen.

Instead of counting the number of pieces $S$, we can count the number of intersections instead! By Euler’s Formula, we have that

\[
(\text{# vertices } V)\, -\, (\text{# edges }E) + (\text{# faces }F) = 2
\]

We have to be a bit careful to apply this formula correctly. If we have $n$ chords and $p$ intersections, there will be $V = 2n+p$ vertices (count the ones on the circumference). Each internal intersection adds an edge, and we must count the arcs between cuts along the circumference as edges, so we have a total of $E = 3n+2p$. Finally, there will be $F = S+1$ faces, since the entire circle counts as a face in Euler’s formula. Substituting these into the formula $V-E+F=2$, we obtain: $S = n+p+1$. So instead of counting the number of pizza pieces, we’ll count the number of intersections and then add $n+1$.

To find the expected number of intersections, suppose we have $n$ chords and let $X_{ij} = 1$ if chords $i$ and $j$ intersect, and $0$ otherwise. We’ll let $C$ be the set of all pairs of chords $(i,j)$. Then the expected number of intersections is:

\begin{align}
\mathbb{E} \left[ \sum_{(i,j) \in C} X_{ij} \right]
= \sum_{(i,j) \in C} \mathbb{E}\bigl[X_{ij}\bigr]
= {n \choose 2} \mathbb{E}\bigl[X_{12}\bigr]
\end{align}

Although the $X_{ij}$ are not mutually independent, linearity of expectation holds regardless. By symmetry each $\mathbb{E}\bigl[X_{ij}\bigr]$ is the same, and is equal to the probability that two random chords intersect. We show in the next solution that this probability is $\tfrac{1}{3}$, so the expected number of pieces is $\tfrac{1}{3}{n \choose 2} + n + 1$, which is equal to:

$\displaystyle
\mathbb{E}\bigl[\text{number of pieces}\bigr] = \frac{(n+2)(n+3)}{6}
$

In the case where we have $n=3$ cuts, the expected number of pieces is $5$.

We can think of the cutting process as happening in two stages. First, we choose $2n$ points randomly along the circumference. Then, we assign labels to the points: $A_1$, $A_2$, $B_1$, $B_2$, and so on. Then, we draw chords from $A_1$ to $A_2$, $B_1$ to $B_2$, and so on. The key observation is that the placement of the points (the first step) is irrelevant. Only the label assignment is relevant to determining the number of intersections points.

For example, consider the case $n=2$. If we assign labels to points in a clockwise fashion as: $A_1, B_2, A_2, B_1$ to the four points, then there will always be one intersection point. Similarly, if we assign the labels in the order: $A_2,A_1,B_1,B_2$, there will always be zero intersections. It doesn’t matter where the four points are, the only thing that matters is the order of the labels!

Due to symmetry, the number of intersections doesn’t change if we swap $A_1$ and $A_2$, or even if we swap $A$ and $B$. So ultimately, we only need to count the number of different pairs of points that can be chosen!

Here is a diagram showing the breakdown for $n=2$. Keep in mind that the location of each point doesn’t change. We’re merely choosing how we pair the points up.

So there are $3$ possible ways to choose pairs, two of which have $3$ pieces and one of which has $1$ piece. So the expected number of pieces is

\[
S_2 = \left(\tfrac{2}{3}\times 3\right) + \left(\tfrac{1}{3} \times 4\right) = \tfrac{10}{3}
\]

The probability of the two chords intersecting is $\tfrac{1}{3}$ (we make use of this in the first solution to the problem). The $n=3$ case is a bit more complicated because there are more ways to choose pairs, but the idea is the same. Here is a diagram showing the breakdown.

The expected number of pieces is therefore:

\[
S_3 = \left(\tfrac{5}{15}\times 4\right) + \left(\tfrac{6}{15} \times 5\right) + \left(\tfrac{3}{15} \times 6\right) + \left(\tfrac{1}{15} \times 7\right) = 5
\]

The expected number of pieces is 5.

One final point of interest: the way in which the chords are randomly chosen is important! If we had used a different method, e.g. by picking a random radius and a random point on that radius, and then constructing a chord perpendicular to the radius through this chosen point, then we would obtain a different answer! The approach above works because the way the chords are chosen allows us to decouple how endpoints are chosen from how labels are assigned. To learn more about why the randomization method is important, take a look at Bertrand’s Paradox.

This genre of problem involving chords of circles, intersections, regions, and so on, has quite a history. The specific problem of characterizing intersections was first posed and solved in the 1930’s, and since then, some elegant solutions have been found for the general case where there are $n$ chords. The solution I’ll summarize below is drawn mostly from the following 1975 paper:

The approach described in Riordan’s paper uses generating functions. Define $T_{nk}$ to be the number of ways of choosing $n$ pairs of points among $2n$ general points such that there are $k$ intersections, and let $T_n(x)$ be the polynomial with $T_{nk}$ as coefficients:

\[
T_n(x) = \sum_{k=0}^{K} T_{nk} x^k,\qquad\text{where }K = {n \choose 2}
\]

The reason the sum goes up to $K$ is that since each pair of chords can intersect at most once, $n$ chords will produce at most $n \choose 2$ intersections. The key result from the paper above is that

\[
T_n(x) = \frac{1}{(1-x)^n} \sum_{j=0}^n (-1)^j a_{n+j,n-j}\, x^{j(j+1)/2}
\]

Here, $a_{nm}$ is a ballot number, which counts the following thing: suppose there is an election where candidate $A$ has $n$ votes and candidate $B$ has $m$ votes, with $n \ge m$. Then $a_{nm}$ is the number of ways the election results can come in (one vote at a time) such that $A$ always has at least as many votes as $B$ in the cumulative count. Another interpretation is that $a_{mn}$ is the number of “North-East” lattice paths from $(0,0)$ to $(n,m)$ that do not cross the diagonal points $(i,i)$. A closed-form expression is:

\[
a_{n+j,n-j} = \frac{2j+1}{n+j+1}{2n \choose n+j} %=\frac{2j+1}{2n+1}{2n+1 \choose n-j}
\]

In the case where $j=0$, we recover the so-called Catalan numbers, which show up in a variety of combinatorial problems.

Using the above formula for $T_n(x)$, we can expand the right-hand side as a series and compare coefficients in order to obtain $T_{nk}$. Here are the result obtained for $T_n(x)$ for $n=1,\dots,4$:

\begin{align}
T_1(x) &= 1 \\
T_2(x) &= 2 + x \\
T_3(x) &= 5 + 6 x + 3 x^2 + x^3 \\
T_4(x) &= 14 + 28 x + 28 x^2 + 20 x^3 + 10 x^4 + 4 x^5 + x^6
\end{align}

Examining the coefficients, we see that the cases $n=2$ and $n=3$ match up with what we found in the first solution. To turn these counts into probabilities, simply divide each coefficient by $T_n(1)$, which is the total number of ways of choosing pairs of points. This sum turns out to have the closed-form expression $T_n(1) = \tfrac{n!}{2^n}{2n \choose n}$. The Catalan numbers show up as the constant coefficients $C_n = T_n(0)$. In other words, $C_n$ is the number of ways of assigning chords such that there are no intersections.

The expected number of pizza pieces also has a closed-form expression, which is $S_n = \frac{1}{6}(n+2)(n+3)$. Here are some plots of the distribution of pieces for different values of $n$.

In the limit as $n\to\infty$, the distribution approaches a Gaussian with mean $S_n$ and variance $\tfrac{1}{45}n(n-1)(n+3)$. For more information on these limits and how to derive them, there is a more recent paper here: