This problem is related to my lab's research in robotic coverage:
Randomly draw $n$ numbers from the set $\{1,2,\ldots,m\}$ without replacement, and sort the numbers in ascending order. $1\le n\le m$.
From this sorted list of numbers $\{a_{(1)},a_{(2)},…,a_{(n)}\}$, generate the difference between consecutive numbers and the boundaries: $g = \{a_{(1)},a_{(2)}−a_{(1)},\ldots,a_{(n)}−a_{(n-1)},m+1-a_{(n)}\}$. This gives $n+1$ gaps.
What is the distribution of the maximum gap?
$P(\max(g) = k) = P(k;m,n) = ? $
This can be framed using order statistics: $P(g_{(n+1)} = k) = P(k;m,n) = ? $
See link for the distribution of gaps, but this question asks the distribution of the maximum gap.
I'd be satisfied with the average value, $\mathbb{E}[g_{(n+1)}]$.
If $n=m$ all the gaps are size 1. If $n+1 = m$ there is one gap of size $2$, and $n+1$ possible locations. The maximum gap size is $m-n+1$, and this gap can be placed before or after any of the $n$ numbers, for a total of $n+1$ possible positions. The smallest maximum gap size is $\lceil\frac{m-n}{n+1}\rceil$. Define the probability of any given combination $T= {m \choose n}^{-1}$.
I've partially solved the probability mass function as $ P(g_{(n+1)} = k) = P(k;m,n) = \begin{cases} 0 & k < \lceil\frac{m-n}{n+1}\rceil\\ 1 & k = \frac{m-n}{n+1} \\ 1 & k = 1 \text{ (occurs when $m=n$)} \\ T(n+1)& k = 2 \text{ (occurs when $m=n+1$)} \\ T(n+1)& k = \frac{m-(n-1)}{n} \\ ? & \frac{m-(n-1)}{n} \le k \le m-n+1 \\ T(n+1)& k = m-n+1\\ 0 & k > m-n+1 \end{cases} \tag{1} $
Current work (1): The equation for the first gap, $a_{(1)}$ is straightforward: $$ P(a_{(1)} = k) = P(k;m,n) = \frac{1}{{m \choose n}} \sum_{k=1}^{m-n+1} {m-k-1 \choose n-1} $$ The expected value has a simple value: $\mathbb{E}[P(a_{(1)})] = \frac{1}{ {m \choose n}} \sum_{k=1}^{m-n+1} {m-k-1 \choose n-1} k = \frac{m-n}{1+n}$. By symmetry, I expect all $n$ gaps to have this distribution. Perhaps the solution could be found by drawing from this distribution $n$ times.
Current work (2): it is easy to run Monte Carlo simulations.
simMaxGap[m_, n_] := Max[Differences[Sort[Join[RandomSample[Range[m], n], {0, m+1}]]]];
m = 1000; n = 1; trials = 100000;
SmoothHistogram[Table[simMaxGap[m, n], {trials}], Filling -> Axis,
Frame -> {True, True, False, False},
FrameLabel -> {"k (Max gap)", "Probability"},
PlotLabel -> StringForm["m=``,n=``,smooth histogram of maximum map for `` trials", m, n, trials]]