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