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).
Best Answer
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.)