# Asymptotic equivalent of the law of lotto minimal value

This question is inspired by this one, where the law of the minimum $X$ of $m$ elements sampled without replacement from $\{1, \dots, n\}$ was investigated.

In this question we wrote that the number of possible samples is $n\choose m$, and the number of samples with $X = k$ is $n-k \choose m-1$, so the law of $X$ is given by $$\mathbb P(X=k) = { {n-k \choose m-1} \over {n\choose m}}.$$

In the same question, an numerical application was done to compute the probability of the event $\{X \text{ is odd}\}$ in the case $n = 20$ and $m = {1\over 2} n$. The result was suprisingly near to $2 \over 3$, as joriki remarked. I then tried to investigate whether this was a coincidence, or not, hence to find the asymptotic behaviour of this distribution when $n\gg 1$, and $m \simeq pn$. Here is what I’ve done.

Unformal reasonning

When $n\gg 1$, at least for small values of $k$, this is like the first success in a Bernoulli process: you have $X=1$ with probability $p$, and conditionnal to $X>k$, you have $X = k+1$ with probability $p$ again, because as $k$ is small, the event of sampling $k+1$ is "almost independent" of the event $\{\text{we didn’t sample } 1, \dots, k\}$ . This leads to $$\mathbb P(X=k) \simeq (1-p)^{k-1} p.$$ In the case $p={1\over 2}$ this explains well the proximity between the probability for $X$ to be odd and ${2\over 3}$.

Attempt to a formal proof

Here is where I need help... using Stirling formula, I managed to write that for $n \gg 1$ and $m \simeq p n$, $${n \choose m} \simeq {1 \over \sqrt{2\pi p(1-p) n}} \left( p^p (1-p)^{1-p}\right)^{-n}.$$

But I was unable to go further. Moreover if we want convergence in law, is this enough to prove pointwise convergence? Don’t we need to write inequalities and sum up the values to show the convergence of the cdf?

-

You can use your approach to bound both probabilities, for even and odd minimum, from below. Fix $l$ and consider the probability that $X$ is odd and $X\lt l$ for $n$ sufficiently large that $l\lt n-m$. Then the correct probabilities that correspond to your estimate $1-p$ are all greater than $1-\frac m{n-l}$, and the correct conditional probability that corresponds to your estimate $p$ is $\frac m{n-l}$, so

$$\mathbb P(X=k)\gt\left(1-\frac m{n-l}\right)^{k-1}\frac m{n-l}$$

and thus

$$\begin{eqnarray} \mathbb P(X~\text{odd}) &=& \sum_{k~\text{odd}}\mathbb P(X=k) \\ &\gt& \sum_{\scriptstyle k~\text{odd}\atop\scriptstyle k\lt l}\mathbb P(X=k) \\ &\gt& \frac{1-\left(1-\frac m{n-l}\right)^l}{1-\left(1-\frac m{n-l}\right)^2}\frac m{n-l} \\ &=& \frac{1-\left(1-\frac m{n-l}\right)^l}{2-\frac m{n-l}} \\ &\to& \frac{1-\left(1-p\right)^l}{2-p}\;. \end{eqnarray}$$

Since $l$ was arbitrary, the bound gets arbitrarily close to $1/(2-p)$. The same calculation for even $X$ yields lower bounds arbitrarily close to $(1-p)/(2-p)$. Since $1/(2-p)+(1-p)/(2-p)=1$, it follows that the probabilities converge to the suprema of their respective bounds.

-
My question was more general, but I think in this way it will be possible to concludre concerning $\mathbb P(X \le k)$... the $\ell$ trick is beautiful, many thanks. – Elvis Jan 6 '12 at 14:32
In fact, $\left(1-\frac m{n-l}\right)^{k-1}\frac m{n-l} < \mathbb P(X=k) < (1-p)^{k-1} p$, so you get easily a framing of $\mathh b \P(X \le \ell)$ that allows to conclude with the squeeze theorem. This is nice. – Elvis Jan 6 '12 at 15:01
@Elvis: That can't be -- the sum over $\mathbb P(X=k)$ is $1$ whereas the sum over $(1-p)^{k-1}p$ is less than $1$ since it's missing the tail beyond $n$. – joriki Jan 6 '12 at 15:58
Oh god. I was pretty sure that using your $\ell$ trick it was possible to prove $$1 - \left( 1 - {m\over n-\ell} \right)^\ell <\mathbb P(X\le \ell) < 1-(1-p)^\ell.$$ I’am missing something, I’ll have to go back on this later. – Elvis Jan 6 '12 at 16:55