Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

[Updated]

Any bound of $Z$ is helpful.

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

People there gave some new ideas.

share|improve this question
    
@MartinSleziak This is the problem I think is interesting. –  Fan Zhang Oct 16 '11 at 17:16
    
Is the choice of numbers done with replacement or without? –  Chris Taylor Oct 16 '11 at 17:24
    
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. –  Michael Hardy Oct 16 '11 at 17:36
    
I have updated that the selection is without replacement. –  Fan Zhang Oct 16 '11 at 17:49
1  
@MichaelHardy I've been guilty of using "randomly" to mean "uniformly distributed", although generally only for uniform distributions over a finite set. –  Michael Lugo Oct 16 '11 at 21:28
show 1 more comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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]
  ]
share|improve this answer
    
what software do you use? –  Fan Zhang Oct 17 '11 at 8:41
    
@FanZhang Sorry for not mentioning this in the post. I used Mathematica, v8. –  Sasha Oct 17 '11 at 12:53
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

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.