4
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ 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. $\endgroup$ Oct 22, 2011 at 10:19
  • $\begingroup$ @DouglasZare This problem is encounted in analysising a algorithm. And how to convert to a continuous version? $\endgroup$
    – Fan Zhang
    Oct 22, 2011 at 11:27
  • $\begingroup$ This comes under the general heading of "order statistics." If you search on that term, you should find what you need. $\endgroup$ Oct 22, 2011 at 13:11
  • $\begingroup$ @John: Maybe, but I don't recall seeing this particular statistic anywhere. Both the discreteness and the "without replacement" make it unusual. $\endgroup$ Oct 22, 2011 at 13:37
  • 1
    $\begingroup$ @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$. $\endgroup$ Oct 23, 2011 at 2:32

2 Answers 2

3
$\begingroup$

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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