Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I would like to know the limiting distribution when $k \uparrow \infty$ and $k/n \rightarrow \lambda$ of
$$ \max(X_1, \ldots, X_k), \text{ where $X_i$ are IID $B(n,p)$}.$$
This is most likely a Gumbel distribution. If this is indeed the case, what matters the most for me is to know the parameters of this Gumbel as a function of $(k, n, p)$.
The limit with $k/n\rightarrow\lambda$ isn't very interesting. But if you let the sample size increase exponentially with $n$ then you get a limiting distribution, which is a "discrete Gumbel" (pace the comments above). For example, for simplicity, let $p=0.5$, so $X_i$ are IID $B(n,0.5)$, where $n$ is large, and the sample size $k$ increases exponentially (but remains much less than $2^n$) - say $k=2^m$ where $n>m>\frac{n}{2}$. Suppose we are interested in the minimum rather than the maximum (it comes to the same thing but it's a bit easier to write down). The Normal approximation is completely useless with a very large sample - it will usually suggest a negative minimum.
The distribution of the minimum will be clustered around a value $d$ where $\mathbb{P}(X_i\le d)\approx 2^{-m}$, so that $\mathbb{P}(min(X_i)>d)\approx e^{-1}$. The working below shows that $d$ will not approach zero until $m$ is close to $n$ - in fact $\frac{d}{n}$ will be nearly constant for a given ratio $\frac{m}{n}$. And in that region the Binomial distribution will be close to a discrete (reversed) exponential, so the distribution of the minimum will be close to a discretised reversed Gumbel distribution.
Working out the details: using the Stirling approximation for factorial, we can approximate the binomial coefficient as: $$\binom{n}{d}\approx \frac{1}{\sqrt{2\pi n}}\left(\frac{d}{n}\right)^{-d-1/2}\left(1-\frac{d}{n}\right)^{-n+d-1/2}.$$
If $n\gg d\gg 1$, then for $j\ge0$, $$\mathbb{P}(X_i=d-j)\approx \left(\frac{d}{n-d}\right)^j\mathbb{P}(X_i=d)$$ (the successive ratios between binomial coefficients change slowly while the product goes quickly to zero), so $$\mathbb{P}(X_i\le d) \approx \left(1-\frac{d}{n}\right)\left(1-2\frac{d}{n}\right)^{-1}\mathbb{P}(X_i=d).$$
Combining the above to get an expression for the cumulative probability, setting that cumulative probability equal to $2^{-m}$, multiplying through by $2^n$, taking logs and dividing by $n$, we end up with: $$-\left(\frac{d}{n}+\frac{1}{2n}\right)log\left(\frac{d}{n}\right)-\left(1-\frac{d}{n}-\frac{1}{2n}\right)log\left(1-\frac{d}{n}\right)-\frac{1}{n}log\left(1-2\frac{d}{n}\right)=log(2)\left(1-\frac{m}{n}\right)+log(2\pi n)/2n.$$ Writing $\nu=\frac{d}{n}+\frac{1}{2n}$, and noting that $\alpha.log(\alpha+\delta)\approx \alpha.log(\alpha)+\delta$ for small $\delta$: $$-\nu.log(\nu)-(1-\nu)log(1-\nu)-\frac{1}{n}log(1-2\nu)=log(2)\left(1-\frac{m}{n}\right)+log(2\pi n)/2n.$$ This can be solved with Newton-Raphson easily enough. Discounting the small third term (the value of $d$ is affected by at most 0.15 for $n\ge 100, m\ge n/2$) we see that $\frac{d}{n}$ is effectively only dependent on $\frac{m}{n}$ if $n$ is large, and it does not tend to zero as $n$ and $m$ increase in constant ratio.
Having found a continuous solution $d$ we round to the nearest integer $\hat{d}$. (Could be a bit more careful about continuity correction and rounding the right way but it isn't necessary here.) Write $\hat{\lambda}=\frac{n-\hat{d}}{\hat{d}}>1$. Write $\rho=2^m\mathbb{P}(X_i\le\hat{d})$: we expect $1/\sqrt{\hat{\lambda}}\le\rho\le\sqrt{\hat{\lambda}}$. Then: $$\mathbb{P}(X_i=\hat{d}-j)\approx\mathbb{P}(X_i=\hat{d})\hat{\lambda}^{-j},$$ and this approximation gets better as $n$ and $\hat{d}$ increase together. So: $$\mathbb{P}(X_i\le\hat{d}-j)\approx\mathbb{P}(X_i\le\hat{d})\hat{\lambda}^{-j}=2^{-m}\rho\hat{\lambda}^{-j},$$ and so $$\mathbb{P}(min(X_i)>\hat{d}-j)=(1-\mathbb{P}(X_i\le\hat{d}-j))^{2^m}\approx (1-2^{-m}\rho\hat{\lambda}^{-j})^{2^m}=e^{-\rho\hat{\lambda}^{-j}}.$$
If we write $x=\hat{d}-j$ then $$\rho\hat{\lambda}^{-j}=e^{log(\rho)-\hat{d}.log(\hat{\lambda})+x.log(\hat{\lambda})},$$so $$\mathbb{P}(min(X_i)>x)\approx exp(-e^{\frac{x-\mu}{\sigma}}),$$ which is a discrete reversed Gumbel with parameters $\mu=\hat{d}-\frac{log(\rho)}{log(\hat{\lambda})}$ and $\sigma=\frac{1}{log(\hat{\lambda})}$.
$$\hat{\lambda}\approx\lambda=\frac{n-d}{d}\text{, and }\hat{d}-\frac{log(\rho)}{log(\hat{\lambda})}\approx d.$$
Exercise for the reader - $p\ne0.5$?
Since the answer of @Boddle does not give the detail for the case $p \neq 1/2$, I will provide it here.
First off, the geometric approximation still holds for $n \gg d \gg 1$. For $j \geq 0$ we obtain
$$ \mathbb{P}(X_i = d-j) \approx \left(\frac{1-p}{p}\frac{d}{n-d}\right)^j \mathbb{P}(X_i = d).$$
Next, we need to compute $d$ such that $\mathbb{P}(X_i \leq d) \approx 2^{-m}$, which was done by a numerical solving approach, so it will not cause any major difficulty. By summing over all values of $j$, we obtain
$$\mathbb{P}(X_i \leq d) \approx \left(1-\frac{d}{n}\right)\left(1-\frac{1}{p}\frac{d}{n}\right)^{-1}.$$
Following the same procedure as @Boddle suggests, but without multiplying through by $2^n$, we obtain the following equation
$$-\left(\frac{d}{n}+\frac{1}{2n}\right)\log\left(\frac{d}{n}\right) -\left(1-\frac{d}{n}-\frac{1}{2n}\right)\log\left(1-\frac{d}{n}\right) -\frac{1}{n}\log\left(1-\frac{1}{p}\frac{d}{n}\right) +\left(\frac{d}{n}+\frac{1}{2n}\right)\log\left(\frac{p}{1-p}\right) = -\log(1-p) -\frac{m}{n}\log(2) +\frac{1}{2n} \left(\log\left(\frac{p}{1-p}\right) + \log(2\pi n)\right).$$
Again defining $\nu = \frac{d}{n} + \frac{1}{2n}$, we obtain an equation of which the solution can be found numerically
$$-\nu\log(\nu) - (1-\nu)\log(1-\nu) -\frac{1}{n}\log(1-\nu/p) + \nu\log\left(\frac{p}{1-p}\right) \\ = -\log(1-p) -\frac{m}{n}\log(2) +\frac{1}{2n} \left(\log\left(\frac{p}{1-p}\right) + \log(2\pi n)\right).$$
Again, it is clear that the value of $\nu$ depends only on the ratio $\frac{m}{n}$ for large $n$. From the solution of the equation above, we can get to the value of $d$ and $\hat{d}$ and finally we define $\hat{\lambda} = \frac{p}{1-p}\frac{n-\hat{d}}{\hat{d}}$. From here on, the solution is as explained by @Boddle with this change of definition.
It is also useful to give the solution in the case $k \sim \gamma 2^m$, where $\gamma > 0$. We need to find $d$ such that $\mathbb{P}(X_i \leq d) \approx \frac{2^{-m}}{\gamma}$ to maintain $\mathbb{P}(\min X_i > d) \approx e^{-1}$. We can see that nothing changes, except that the equation to solve numerically now becomes
$$-\nu\log(\nu) - (1-\nu)\log(1-\nu) -\frac{1}{n}\log(1-\nu/p) + \nu\log\left(\frac{p}{1-p}\right) \\ = -\log(1-p) -\frac{m}{n}\log(2) +\frac{1}{2n} \left(\log\left(\frac{p}{1-p}\right) + \log(2\pi n) + 2\log(\gamma)\right).$$
For large $n$, the difference becomes negligible and the solution is approximately the same as above.
I computed the values of $d/n$ as a function of $m/n$ for infinitely large $n$ using the equations above. I show the curves on the plot below for different values of $p \geq 1/2$. This gives an idea of the expected value of the minimum as $k=2^m$ increases relative to m.
