MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am reposting a question on math.stackexchange which did not recieve good questions. The orginal questio is at

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$? And any bound of $Z$ is helpful.

share|cite|improve this question
It seems odd that you are taking the maximum of the $Y_i$ which usually are not integers. What is the motivation for this? A continuous version seems much simpler. – Douglas Zare Oct 22 '11 at 10:19
@DouglasZare This problem is encounted in analysising a algorithm. And how to convert to a continuous version? – Fan Zhang Oct 22 '11 at 11:27
This comes under the general heading of "order statistics." If you search on that term, you should find what you need. – John D. Cook Oct 22 '11 at 13:11
@John: Maybe, but I don't recall seeing this particular statistic anywhere. Both the discreteness and the "without replacement" make it unusual. – Brendan McKay Oct 22 '11 at 13:37
@Fan: Maybe I wasn't careful - I didn't do the actual calculations. But anyway, just take a single (continuous) order statistic and find the value $a$, for which $\mathbb{P}(Y_i>a) =o(1/n)$. Then with high probability $Z<a$. – Ori Gurel-Gurevich Oct 23 '11 at 2:32
up vote 3 down vote accepted

If, as suggested by Ori Gurel-Gurevich, we sample from uniform distribution on $[0,1]$, then $Z$ will typically be of order $1/\sqrt{n}$.

A convenient way of generating the points $X_1,\dots,X_n$ in order is letting $W_1,\dots,W_{n+1}$ be independent exponential(1) variables with partial sums $S_k = W_1+\cdots+W_k$, and finally letting $X_k = S_k / S_{n+1}$. We have $$ \left|X_k - \frac{k}{n+1}\right| = \left|\frac{S_k}{S_{n+1}} - \frac{k}{n+1}\right| \leq \left|\frac{S_k}{n+1} - \frac{k}{n+1}\right| + \left|\frac{S_k}{n+1} - \frac{S_k}{S_{n+1}}\right| $$ $$ \leq \frac{\left|S_k-k\right|}{n+1} + \frac{S_{n+1}}{S_k}\cdot \left| \frac{S_k}{n+1} - \frac{S_k}{S_{n+1}}\right| = \frac{\left|S_k-k\right| + \left|S_{n+1} - (n+1)\right|}{n+1},$$ and in particular $$\max_{k\leq n} \left|X_k - \mathbb{E}X_k\right| \leq \frac2{n+1}\cdot\max_{k\leq n+1} \left|S_k - k\right|.$$ It is relatively easy to see that $\mathbb{E}\max_{k\leq n} \left|S_k-k\right| = O(\sqrt{n})$ and consequently that $\mathbb{E} \max_{k\leq n} \left|X_k - \mathbb{E}X_k\right| = O(n^{-1/2})$. This is because $S_n-S_k$ is independent of $S_k$. Therefore if $S_k$ deviates wildly from its mean, then with decent probability (namely when $S_n-S_k$ deviates ever so slightly in the same direction), $S_n$ will deviate just as wildly from its mean. More precisely, $$Pr\left(\left|S_n - n\right| > t\right) \geq C\cdot Pr\left(\left|S_k-k\right| > t \ \text{for some $k\leq n$}\right),$$ where $C$ is simply a positive lower bound on the probability that a sum of independent exponentials deviates from its mean in a given direction. Consequently \begin{equation} \mathbb{E} \max_{k\leq n} \left|S_k-k\right| = \int_0^\infty Pr\left(\max_{k\leq n}\left|S_k-k\right| > t\right) \, dt \end{equation} \begin{equation} \leq \frac1C \int_0^\infty Pr\left(\left|S_n-n\right| > t\right)\, dt = \frac1C\cdot \mathbb{E}\left|S_n-n\right| = O(\sqrt{n}). \end{equation}

EDIT: To return to the original problem, we choose $n$ numbers independently and uniformly in the interval $[0,m-n+1]$ and let $$U_1\leq U_2 \leq \cdots \leq U_n$$ be the sorted sequence. Now let $$X_i = \left\lfloor U_i+i\right\rfloor.$$ The sequence $X_1,\dots,X_n$ is now generated according to the question (and therefore not the same as the $X_i$'s earlier in this post).

Scaling up the result above by a factor $m-n+1$, we see that the maximum deviation of a $U_i$ from its mean is of order $$O\left(\frac{m}{\sqrt{n}}\right),$$ while the difference between $X_i$ and $U_i$ is of order $n$. Therefore the maximum deviation of $X_i$ from its mean is of order $$O\left(\frac{m}{\sqrt{n}}+n\right),$$ where the first term will dominate when $m>>n^{3/2}$. On the other hand if $m$ is smaller, say of the same order as $n$, it must clearly be possible to achieve sharper bounds.

share|cite|improve this answer
Nice approach. You might want to fix the $|X_k-X_k|$. – Brendan McKay Oct 25 '11 at 15:30
Very nice. I somehow missed the fact that the $Y_i$'s behave like Brownian motion, so there are strong dependencies and maximum is only $\sqrt{n}$. – Ori Gurel-Gurevich Oct 25 '11 at 18:17
@JohanWastlund Do you have any suggestion about the case where it can not be approximated to "selection with replacement". – Fan Zhang Oct 26 '11 at 5:40
To return to the discrete problem, we can start by choosing points uniformly in the interval $[0,m-n+1]$, then mapping them to the set $\{1,\dots,m-n+1\}$ in the obvious way (which may lead to repetitions), and finally map to a set of $\{1,\dots,m\}$ without repetitions in the standard way (pushing the $i$th ball $i-1$ bins up). This moves each point another $O(n)$ away from its mean, so we get a high-probability upper bound of $O(m/\sqrt{n} + n)$, where the first term dominates when $m>>n^{3/2}$. On the other hand, if $m$ is only slightly larger than $n$, it must be possible to do better. – Johan Wästlund Oct 28 '11 at 7:14
Brendan, was there a typo? I don't see it. – Johan Wästlund Oct 28 '11 at 7:15

First, if $n=o(\sqrt{m})$ then with high probability there are no duplicates when sampling with replacement, since the probability of choosing the same number at time $i$ and $j$ is $1/m$ so the expected number of duplicates is $O(n^2/m)$. So for this parameter range we can use the with replacement model instead.

Second, assuming we are interested in asymptotic results, we can use the continuous model, where we sample from $U[0,1]$ and then rescale, and this will change $Z$ by at most $O(1/m)$ which will be negligible.

So we have $X_i$ which are the order statistics of $n$ i.i.d. $U[0,1]$ RVs, $Y_i=|X_i-\frac{i}{n+}|$ and $Z=\max_i Y_i$. We ask what are the typical values of $Z$.

Now, $X_i$ has a variance which is roughly $\min(i,n-i)/n^2$ and a Gaussian tail (this can be seen directly from the density function of $X_i$). This means that the probability of $X_i$ being more than $K \sqrt{\log{n}/n}$ away from its expectation is much less than $1/n$, for a large enough $K$, so a union bound gives that $\mathbb{P}(Z>K\sqrt{\log{n}/n}) \to 0$.

EDIT: removed the erroneous lower bound. The correct value of $Z$ is about $\sqrt{n}$ as pointed by Johan Wästlund.

share|cite|improve this answer
How to proof if $n=o(\sqrt{m})$ then with high probability there are no duplicates when sampling with replacement. – Fan Zhang Oct 24 '11 at 5:29
This is a classical birthday paradox argument. I've edited my answer to include the argument. – Ori Gurel-Gurevich Oct 24 '11 at 6:42
And my new question is: how to determine the constant $K$? – Fan Zhang Oct 24 '11 at 15:47
@Ori Gurel-Gurevich I saw from wiki that "Then the probability distribution of X(k) is a Beta distribution with parameters k and n − k + 1" And how you get Xi has the above variance and Gaussian tail?… – Fan Zhang Oct 25 '11 at 15:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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