Distribution of a maximum

Question

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.

Answer 1

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.

Answer 2

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.