Distribution of a maximum

I am reposting a question on math.stackexchange which did not recieve good questions. The orginal questio is at https://math.stackexchange.com/questions/73091/distribution-of-a-maximum.

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.

• 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. Oct 22, 2011 at 10:19
• @DouglasZare This problem is encounted in analysising a algorithm. And how to convert to a continuous version? Oct 22, 2011 at 11:27
• This comes under the general heading of "order statistics." If you search on that term, you should find what you need. Oct 22, 2011 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. Oct 22, 2011 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$. Oct 23, 2011 at 2:32

2 Answers

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 $$\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$$ $$\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}).$$

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.

• Nice approach. You might want to fix the $|X_k-X_k|$. Oct 25, 2011 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}$. Oct 25, 2011 at 18:17
• @JohanWastlund Do you have any suggestion about the case where it can not be approximated to "selection with replacement". Oct 26, 2011 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. Oct 28, 2011 at 7:14
• Brendan, was there a typo? I don't see it. Oct 28, 2011 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.

• How to proof if $n=o(\sqrt{m})$ then with high probability there are no duplicates when sampling with replacement. Oct 24, 2011 at 5:29
• This is a classical birthday paradox argument. I've edited my answer to include the argument. Oct 24, 2011 at 6:42
• And my new question is: how to determine the constant $K$? Oct 24, 2011 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? en.wikipedia.org/wiki/… Oct 25, 2011 at 15:04