Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a set of naturals [n]:{1,2,3,...,n}, we repeatably select m elements from [n] to make a sorted set ${x_1,x_2,...,x_m}$ satisfying $x_i >= x_j$ for i>=j.

What the probability $p(i<=k)$ where i satisfies (1) $x_i-x_{i+1}>=L$ and (2) $x_j-x_{j+1} < L$ for $j < i$.

Usually, $m << n$, $k << n$, and L~n/m.

share|improve this question

1 Answer 1

Assuming you are interested in the asymptotics as n goes to infinity, it is probably easier to look at choosing $m$ samples from the unit interval $[0,1]$ and try to check the probability that there exists some $i \leq k$ so that $x_{i+1} - x_{i} \geq \frac{\alpha}{m}$, while $x_{j+1} - x_{j} < \frac{\alpha}{m}$ for all $j < i$, and where $\alpha$ does the scaling that $L$ used to do. Of course, $n$ sort of disappears here - it will just show up as an error bound for this approximation.

Let's do some basic calculations, to see what sort of answer we expect. We know that if you choose $y_{i} = exponential(1)$ an iid sequence of exponential random variables with mean 1, then $z_{i} = \frac{y_{i}}{\sum_{j} y_{j}}$ give you a sequence of differences for $m$ sorted $U[0,1]$ random variables. For now, assuming that $k << m$, we can look at $z_{i}' = \frac{y_{i}}{m+1}$ . Our condition, for the difference variables $z_{i}$, will boil down to:

$P[\exists i \leq k \, s.t. \, y_{i} \geq \alpha]$

since if there exists such an $i$, there exists a first one. But we can calculate that explicitly:

$p = 1 - P[\forall i \in [k], y_{i} \leq \alpha] = 1 - \prod_{i=1}^{k} P[y_{i} \leq \alpha] = 1 - e^{-\alpha k}$

To get back to the original case, we do:

1) Going from $z_{i}'$ to $z_{i}$: use a concentration inequality to bound the difference in the individual probabilities in the product above. This is good as long as $m$ is fairly large and $k$ isn't too close to $m$.

2) Going from $z_{i}$ to $x_{i}$: use the obvious coupling of the two sequences, for which $\vert x_{i} - z_{i} \vert = O(n^{-1})$, to get a bound for large $n$.

Ok, I suspect I have made at least one calculation error in there... but I hope it is enough to get you going, or to clarify which assumptions about your scaling are wrong.

share|improve this answer

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.