Expected number of random diagonals before intersection

Question

Background Motivation: There are various questions asked about randomly drawn chords and their number of intersections in a circle; for example, MSE 73033 and MO 284124. I am interested here as to a discretized version where the circle is replaced by an $n$-gon and, if all goes well, then one can consider what happens as $n \rightarrow \infty$. (I originally asked this question on twitter, and, although there are some proposed small case computations, I cannot vouch for their correctness. See the thread here.)

Question: Consider an $n$-gon ($n \geq 4$) and a list of all non-adjacent vertex pairs. Pick an unchosen pair from the list at random and connect the vertices. If you continue this process without replacement, then what is the expected number of diagonals drawn before two intersect in the interior of the $n$-gon?

(I am, in particular, looking for a formula that is a function of $n$.)

Note 1: If there is an alternative formulation of the problem with a different method of choosing the diagonals "at random" that yields a different result, then I would welcome such answers in that direction, too.

Note 2: If this result is already known, then a pointer to its answer would be appreciated! I did not locate an answer in my exploration of MSE, but it seems a natural enough question for me to have missed it here (or elsewhere).

Answer 1

Unless I'm mistaken, the asympotic expected number (for large $n$) of non-inserting chords seems quite simple to compute.

In that range, the restriction that we can't select neighbours vertexes should be negligible. Then, we can consider $2n$ points over a circle and consider the event that, for a random pairing, the resulting $n$ chords do not intersect.

In this setup, the total number of pairings is $$T_n=\frac{(2n)!}{2^n n!}= 2^{-n} \binom{2n}{n}n!\,$$

And the number of pairings that do not cross is given by the Catalan number

$$C_n = \binom{2n}{n}\frac{1}{n+1}$$

Hence the probability that $n$ chords do not intersect is

$$P_n = \frac{C_n}{T_n}=\frac{2^n}{(n+1)!}$$

This formula is valid also for the initial trivial values $P_0=P_1=1$.

Let $X$ be the number of chords drawn when the first crossing occurs.

Then $P(X>n)=P_n$ and

$$E[X] = \sum_{n=0}^\infty P_n =\frac12 \sum_{m=1}^\infty \frac{2^m}{m!} =\frac12 \left(\sum_{m=0}^\infty \frac{2^m}{m!}-1 \right) =\frac{1}{2}(e^2-1) = 3.1945\cdots $$

Answer 2

Let $X_n$ be the number of diagonals drawn until two intersect in the interior of the $n$-gon.

We can write $\mathbb{E}X_n$ as $$\mathbb{E}X_n = \sum_{k=1}^{\infty}P(X_n\geq k)=\sum_{k=1}^{n-2}P(X_n\geq k).$$

Note that event $\{X_n\geq k\}$ occurs iff the first $k-1$ sampled diagonals don't intersect.

The probability $P(X_n\geq k)$ can be written as $$P(X_n\geq k)= \frac{s_{n,k-1}}{d_{n,k-1}},$$

where $d_{n,k-1}$ is the number of ways to choose $k-1$ diagonals, and $s_{n,k-1}$ is the number of ways to dissect the $n$-gon with $k-1$ non-crossing diagonals.

The first term is given by: $$d_{n,k-1} =\binom{\binom{n}{2}-n}{k-1}=\binom{\frac{n(n-3)}{2}}{k-1}.$$

The second term is given by a generalization of the Catalan numbers, called the Kirkman-Cayley dissection numbers [1]:

$$s_{n,k-1}=\frac{1}{k}\binom{n+k-2}{k-1}\binom{n-3}{k-1}.$$

Putting this together gives

$$\mathbb{E}X_n = \sum_{k=1}^{n-2}P(X_n\geq k)=\sum_{k=1}^{n-2}\frac{\binom{n+k-2}{k-1}\binom{n-3}{k-1}}{k\binom{\frac{1}{2}n(n-3)}{k-1}}.$$

I'm not sure if there is a way to simplify this further.

Update (1/1): Sil found that WA gives a closed form for this sum in terms of the hypergeometric function:

$$\frac{1}{2}(_{2}F_{1}(−n+2,n−1;−\frac{(n−1)(n−2)}{2};1)−1).$$

The first few values:

$n$	$\mathbb{E}X_n$	$\text{approx.}$
4	$2$	2.0
5	$\frac{5}{2}$	2.5
6	$\frac{11}{4}$	2.75
7	$\frac{413}{143}$	2.888
8	$\frac{3839}{1292}$	2.971
9	$\frac{1809}{598}$	3.025
10	$\frac{374329}{122264}$	3.061
10000	-	3.193

Which agrees with leonbloy's answer for large $n$.

Answer 3

For the square, pentagon, hexagon, heptagon and octagon, the number of diagonals is $2$, $5$, $9$, $14$, and $20$. Systematic counting reveals the pattern:$$2(n-3)+(n-4)(n-3)/2=\frac{n^2-3n}{2}$$

Diagonals have $\frac{n-3}{2}$ different sizes for odd $n$, and $\frac{n}{2}-1$ for even $n$. Thus in the regular heptagon diagonals have two different lengths, an equal number of each. Shorter diagonal $AC$ intersects only with the four diagonals drawn from adjacent point $B$. But longer diagonal $AD$ intersects with six: three drawn from $B$ and three from $C$. Of the $7+7=14$ diagonals in the heptagon, depending on whether our randomly chosen first diagonal is short or long, the odds of randomly choosing a second diagonal that intersects it will be either $\frac{4}{13}$ or $\frac{6}{13}$. Since there are an equal number of long and short diagonals, can we take the arithmetic mean and say the odds are $\frac{5}{13}$ in this case?

Continuation, Elaboration & Conclusion

A second random diagonal in an $n$-gon may cross the first, but the $(n-2)th$ diagonal must cross one of the preceding diagonals, whether all radiate from one vertex or proceed across the polygon in stepwise fashion, as may be seen in the example below. This at least gives a boundary for the number $N$ of diagonals possible before an intersection occurs:$$2\le N\le n-2$$

But this window can be narrowed. As already noted, regular polygons (for $n>5$) have diagonals of different lengths, on which different numbers of crossings may occur. But for odd $n$ there are $n$ diagonals of each different length, so that none is favored in a random selection. For even $n$ there are likewise $n$ diagonals of each length, except for the greatest, the "spokes" of the wheel, which are $\frac{n}{2}$ in number. An array may help here. $$\begin{array}{c|cccccc}n & \text{number of diagonals} & d_1 & d_2 & d_3 & d_4 & d_5\\\hline4 & 2 & 2\\5 & 5 & 5\\6 & 9 & 6 & 3\\7 & 14 & 7 & 7\\8 & 20 & 8 & 8 & 4\\9 & 27 & 9 & 9 & 9\\10 & 35 & 10 & 10 & 10 & 5\\11 & 44 & 11 & 11 & 11 & 11\\12 & 54 & 12 & 12 & 12 & 12 & 6\\13 & 65 & 13 & 13 & 13 & 13 & 13\end{array}$$Guaging the probability of a second diagonal crossing a first requires taking into account the number of possible crossings for each $d_k$ in the $n$-gon. The next array shows the number of crossings possible on the various diagonals.$$\begin{array}{c|ccccc}n & \text{crossings for:} & d_1 & d_2 & d_3 & d_4 & d_5\\\hline4 & & 1\\5 & & 2\\6 & & 3 & 4\\7 & & 4 & 6\\8 & & 5 & 8 & 9\\9 & & 6 & 10 & 12\\10 & & 7 & 12 & 15 & 16\\11 & & 8 & 14 & 18 & 20\\12 & & 9 & 16 & 21 & 24 & 25\\13 & & 10 & 18 & 24 & 28 & 30\end{array}$$If the number of crossings$$d_1=n-3$$$$d_2=2n-8$$$$d_3=3n-15$$$$d_4=4n-24$$$$d_5=5n-35$$then generally the number of crossings for$$d_k=kn-k^2-2k$$If he probability of any one of the $k$ different diagonals crossing another is the number of possible intersections on that diagonal divided by the remaining $n-1$ diagonals, and the probability of a random second diagonal crossing the first is the arithmetic mean of those $k$ different probabilities, then e.g.for $n=13$ we have$$\frac{10+18+24+28+30}{5\cdot 64}=\frac{22}{64}=.344$$Using the rules derived above we can accordingly compute probabilities for larger $n$. E.g. there are $\frac{n^2-3n}{2}=1034$ diagonals in the $47$-gon, in which there are $22$ different groups of $47$ diagonals each. Summing the twenty-two numerators we get$$\frac{7590}{22\cdot 1033}=\frac{345}{1033}=.334$$This confirms——and is confirmed by——the more elegant argument in the comment of @Misha Lavrov, that the probability should converge to $\frac{1}{3}$ as $n$ increases. If this line of argument is sound, it seems three diagonals should yield an interior crossing.

Addendum: Expressed generally as a function of $n$, I find the numerator, e.g. for $n=13$, $10+18+24+28+30=110$ to be$$\frac{n^3-6n^2+11n-6}{12}$$and the denominator $$\frac{n-3}{2}\cdot \frac{n^2-3n-2}{2}=\frac{n^3-6n^2+7n+6}{4}$$Thus, inverting the denominator and multiplying, the ratio is$$\frac{n^3-6n^2+11n-6}{12}\cdot \frac{4}{n^3-6n^2+7n+6}$$ which gets increasingly close to $\frac{4}{12}= \frac{1}{3}$ with increasing $n$, for example $.3334796$ for $n=97$, $.3333675$ for $n=199$, and $.3333347$ for $n=997$.