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.

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?

Many thanks in advance for your help.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

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.