Expected second moment for random points on a circle

Question

Let $S$ be a circle with unit circumference. Suppose that $n$ random points are chosen independently uniformly from $S$; choosing one arbitrarily as $x_1$, label the rest $x_2, \dots, x_n$ in clockwise order. What is the expected value of $$ \max |x_{i}-x_{i-1}| $$ (where $x_0$ is interpreted as $x_n$)? Or even more, what is the distribution of this maximum?

(As written, the expression $|x_{i}-x_{i-1}|$ represents distance in the Euclidean plane; I'd prefer to use the distance along the circumference of the circle, which isn't that different when $n$ is large.)

Trivially the maximum (using distance along the circumference of the circle) is at least $1/n$; I'm mostly interested in whether this is the correct order of magnitude (although the exact constant is an interesting question as well).

Answer 1

The problem is equivalent to choosing $n-1$ points at random on the unit interval and considering the length of the longest resulting subinterval. Given that, the distribution of the maximum and its expected value are in my answer to this recent math.SE question on Average Length of the Longest Segment. It's closely related to the one given in the comments above by Shai Covo. I'll reproduce the answer here (which is given in terms of making $n-1$ cuts randomly chosen on a rope of unit length).

---

If $X_1, X_2, \ldots, X_{n-1}$ denote the positions on the rope where the cuts are made, let $V_i = X_i - X_{i-1}$, where $X_0 = 0$ and $X_n = 1$. So the $V_i$'s are the lengths of the resulting pieces of rope.

The key idea is that the probability that any particular $k$ of the $V_i$'s simultaneously have lengths longer than $c_1, c_2, \ldots, c_k$, respectively (where $\sum_{i=1}^k c_i \leq 1$), is $$(1-c_1-c_2-\ldots-c_k)^{n-1}.$$ This is proved formally in David and Nagaraja's Order Statistics, p. 135. Intuitively, the idea is that in order to have pieces of size at least $c_1, c_2, \ldots, c_k$, all $n-1$ of the cuts have to occur in intervals of the rope of total length $1 - c_1 - c_2 - \ldots - c_k$. For example, $P(V_1 > c_1)$ is the probability that all $n-1$ cuts occur in the interval $(c_1, 1]$, which, since the cuts are randomly distributed in $[0,1]$, is $(1-c_1)^{n-1}$.

If $V_{(n)}$ denotes the largest piece of rope, then $$P(V_{(n)} > x) = P(V_1 > x \text{ or } V_2 > x \text{ or } \cdots \text{ or } V_n > x).$$ This calls for the principle of inclusion/exclusion. Thus we have, using the "key idea" above, $$P(V_{(n)} > x) = n(1-x)^{n-1} - \binom{n}{2} (1 - 2x)^{n-1} + \cdots $$ $$+ (-1)^{k-1} \binom{n}{k} (1 - kx)^{n-1} + \cdots,$$ where the sum continues until $kx > 1$.

Therefore, $$E[V_{(n)}] = \int_0^{\infty} P(V_{(n)} > x) dx = \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \int_0^{1/k} (1 - kx)^{n-1} dx $$ $$= \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \frac{1}{nk} = \frac{1}{n} \sum_{k=1}^n \frac{\binom{n}{k}}{k} (-1)^{k-1} = \frac{H_n}{n},$$ where the last step applies a known binomial sum identity.

---

For much more on this problem, see Section 6.4 ("Random Division of an Interval") in David and Nagaraja's Order Statistics, pages 133-137, and the corresponding exercises on pages 153-155.

As a side note, the distribution of $V_{(n)}$ was apparently first obtained by Ronald Fisher in "Tests of Significance in Harmonic Analysis," Proceedings of the Royal Society of London, Series A, 1929, pp 54-59. (Sorry for the JSTOR link.)

Answer 2

Working with distance along the circumference (much easier to treat). Here's a nice way to get at least the asymptotics of the maximum.

Another way to obtain the distribution of the interpoint distances is as follows. Let $W_1, W_2, \dots, W_n$ be i.i.d. exponential random variables with mean 1, and let $S_n$ be their sum. Then $(W_1, W_2,\dots, W_n)/S_n$ has the same distribution as the interpoint distances you describe.

This is because, conditional on the sum $S_n=s$, the distribution of $W_1, W_2,\dots, W_n$ is uniform on the simplex $\{\sum w_i=s\}$.

Let $M_n$ be the maximum of the $W_i$. Then we want to know about $M_n/S_n$.

$M_n$ has mean $h_n=1+1/2+\dots+1/n$ and variance $1+1/2^2+\dots+1/n^2$. An easy way to get this is to note that the maximum of $n$ i.i.d. exponential mean 1 random variables has the same distribution as $E_1+E_2+\dots+E_n$ where the $E_i$ are independent exponentials and $E_i$ has mean $1/i$. (By the memoryless property, you can get the distribution of the maximum of $n$ i.i.d. exponential mean 1 random variables as follows: take the minimum, which is exponential with mean $1/n$, and then add it to the maximum of $n-1$ new i.i.d. exponentials with mean 1; the claim follows by induction).

So $M_n$ behaves like $\log n+O(1)$ as $n$ grows. Meanwhile by the central limit theorem $S_n$ behaves like $n+O(\sqrt{n})$.

So $M_n/S_n$ behaves like $\frac{\log n}{n}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right)$ as $n$ grows.

In fact $\frac{n^{3/2}}{\log n}\left(\frac{M_n}{S_n}-\frac{\log n}{n}\right) \to {N}(0,1)$ in distribution as $n\to\infty$.

Answer 3

Assuming that the distance is measured along the circle, you are asking about distribution of the maximum value in a Dirichlet distribution with concentration parameter 1. The results you are looking for should follow from parameterization of this distribution in terms of independent exponentails (this section of the same Wikipedia page) and the order statistics for the exponential distribution.