Randomly select $n$ numbers from ${\{1,2,\dots,m\}}$ without replacement, and order the chosen elements increasingly: $X_1 < X_2 < \dots < X_n$

And we can view each $X_i$ as a random variable, and we can get $\mathbb{E}(X_i) = \frac{(m+1)i}{n+1}$

And we can define $Y_i=|X_i-\mathbb{E}(X_i)|$ which is the distance of each variable to its corresponding expectation.

And we can also define $Z = \max_{1 \le i \le n} Y_i$

So what is the distribution of $Z$?


Any bound of $Z$ is helpful.

[Updated] I have re-posted the question at Mathoverflow: https://mathoverflow.net/questions/78822/distribution-of-a-maximum

People there gave some new ideas.

  • $\begingroup$ @MartinSleziak This is the problem I think is interesting. $\endgroup$
    – Fan Zhang
    Oct 16, 2011 at 17:16
  • $\begingroup$ Is the choice of numbers done with replacement or without? $\endgroup$ Oct 16, 2011 at 17:24
  • $\begingroup$ You haven't said what the distribution of the original randomly selected numbers is. Often people say "randomly" when they mean "uniformly distributed", but I think that's on the sloppy side; I don't know that I've ever seen a probabilist or statistician do that. Whether this is with or without replacement should also be made explicit. $\endgroup$ Oct 16, 2011 at 17:36
  • $\begingroup$ I have updated that the selection is without replacement. $\endgroup$
    – Fan Zhang
    Oct 16, 2011 at 17:49
  • 1
    $\begingroup$ @MichaelHardy I've been guilty of using "randomly" to mean "uniformly distributed", although generally only for uniform distributions over a finite set. $\endgroup$ Oct 16, 2011 at 21:28

3 Answers 3


Yours is an interesting question to ask, but hardly simple to answer. The following is not an answer to your question, but is given to offer certain insight into the distribution.

I ran several simulations to get an idea about distribution of $Z$. I did that for $m=100$ and $m=50$ for different values of $1 \le n < m$.

enter image description here

The code used to simulate histograms is as follows:

MathSE73091Histogram[m_Integer, n_Integer, samples_Integer, 
  opts : OptionsPattern[ListPlot]] := 
 Module[{means = (m + 1)/(n + 1) Range[n], data, omega = Range[m]},
  data = Tally[
    Table[Max@Abs[Sort[RandomSample[omega, n]] - means], {samples}]];
  data[[All, 2]] /= Total[Part[data, All, 2]];
  ListPlot[data, opts]
  • $\begingroup$ what software do you use? $\endgroup$
    – Fan Zhang
    Oct 17, 2011 at 8:41
  • $\begingroup$ @FanZhang Sorry for not mentioning this in the post. I used Mathematica, v8. $\endgroup$
    – Sasha
    Oct 17, 2011 at 12:53

This is a partial answer to an analogous problem. Assume the numbers are chosen independently and uniformly in the continuous interval $[0,m]$. Then, $\mathrm E(X_i)=x_i$ with $x_i=im/(n+1)$ for every $1\leqslant i\leqslant n$.

For small enough values of $z$, $[Z\leqslant z]$ is realized if and only if each interval $[x_i-z,x_i+z]$ contains exactly one value of the sample. More precisely, these intervals are disjoint for every $z\leqslant z_*=m/(2(n+1))$ and, for such values of $z$, $\mathrm P(Z\leqslant z)=n!(2z/m)^n$.

Thus, the density of the distribution of $Z$ on the interval $(0,z_*)$ is $f(z)=n!n(2/m)^nz^{n-1}$. The situation for larger values of $z$ is more complicated.


This answer addresses your update "Any bound of $Z$ is helpful." It does not give the probability distribution of $Z$.

For fixed $m$ and $n$ with $n < m$, we have $$Z \leq n \left(\frac{m+1}{n+1}-1\right),$$ and for fixed $m$, where $n$ is allowed to range over all possible values from $1$ to $m$, we have $$Z \leq \left(\sqrt{m+1}-1\right)^2.$$

For the first inequality, let $m$ and $n$ be fixed with $n < m$. So $\frac{m+1}{n+1} > 1$. Thus the maximum possible value of $\left|X_i - \frac{(m+1)i}{n+1}\right|$ occurs for one of the extreme values in an extreme in the other direction sample. In other words, the largest possible value of $Z$ occurs with $Y_n$ when the sample $\{1, 2, \ldots, n\}$ is chosen or with $Y_1$ when the sample $\{m-n+1, m-n+2, \ldots, m\}$ is chosen. By symmetry, these two values should be equal, and that is the case: In the first sample, we have $Y_n = \left|n - \frac{(m+1)n}{n+1}\right| = n \left(\frac{m+1}{n+1}-1\right)$, and in the second sample we have $Y_1 = \left|m-n+1 - \frac{m+1}{n+1}\right| = (m+1)\left(1 - \frac{1}{n+1}\right) - n = n \left(\frac{m+1}{n+1}-1\right).$ Thus $Z \leq n \left(\frac{m+1}{n+1}-1\right).$

To see the second inequality, just use calculus to maximize the expression $f(n) = n\left(\frac{m+1}{n+1}-1\right)$. We get that $f(n)$ is maximized when $n = \sqrt{m+1}-1$, and thus $Z \leq \left(\sqrt{m+1}-1\right)^2$.

As an illustration of this last result, consider the numerical work posted by Sasha. The largest values of $Z$ occur on the plots for which $n$ is closest to $\sqrt{m+1}-1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.