7
$\begingroup$

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

$\endgroup$
9
  • 3
    $\begingroup$ how's $n$ going to $\infty$ with $k$? $\endgroup$
    – Xi'an
    Jan 20, 2015 at 12:25
  • $\begingroup$ @Xi'an I think that it does not have to go to infinity. But if $n$ is large we can approximate the binomial by a Gaussian, and the max of $k$ IID Gaussian variables tends to a Gumbel as $k$ goes to infinity. $\endgroup$
    – gui11aume
    Jan 20, 2015 at 12:53
  • 1
    $\begingroup$ If $n$ is bounded by $N$ then asymptotically the max equals some integer less than or equal to $N$. Moreover, for all $k$ its distribution is discrete with support $\{0,1,\ldots,N\}$. $\endgroup$
    – whuber
    Jan 20, 2015 at 13:23
  • 2
    $\begingroup$ The question is not meaningless--but the answer looks trivial. If your situation is more complicated than a fixed $n$ and $p$, you need to be specific about whether and how $n$ and $p$ can vary as a function of $k$, as @Xi'an has asked. The interesting aspect is why your argument fails. Among other things, the Normal approximation to the Binomial is imperfect in the tails and becomes rapidly poorer when used to draw conclusions about extreme values like the maximum. Another reason is that maxima of bounded (continuous) variates do not have a Gumbel distribution in the limit! $\endgroup$
    – whuber
    Jan 20, 2015 at 15:14
  • 4
    $\begingroup$ You won't get an extreme value distribution for fixed $n$ (for that to happen, the underlying distribution must be continuous within a neighborhood of its maximum, which this one is not). Every distribution of $\max(X_1,\ldots,X_k)$ is discrete and the probability piles up onto $n$ as $k$ grows large. (For $k=tp^{-n}$, $\Pr(\max(X_i)=n)\approx 1-e^{-t}$.) No matter how you normalize these distributions they will never look like extreme-value distributions. Their limit is an atom on $n$ itself. $\endgroup$
    – whuber
    Jan 20, 2015 at 16:19

2 Answers 2

11
$\begingroup$

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$?

$\endgroup$
4
  • $\begingroup$ Very well done! And thank you for joining the site in order to answer this question!! This is very useful for me. $\endgroup$
    – gui11aume
    Feb 4, 2015 at 10:00
  • $\begingroup$ Perhaps you can also have a look at this question stats.stackexchange.com/q/136265/10849. If some work has been done to answer it or if this is way too difficult I would be happy to know it as well. $\endgroup$
    – gui11aume
    Feb 4, 2015 at 11:27
  • $\begingroup$ Could you comment on how $$\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}$$ follows from $$\mathbb{P}(X_i=\hat{d}-j)\approx\mathbb{P}(X_i=\hat{d})\hat{\lambda}^{-j}$$? $\endgroup$ Feb 24, 2017 at 18:14
  • $\begingroup$ +1 Used (and partly copied) in this other answer math.stackexchange.com/questions/3152094 I believe that using the entropy approximation for the binomial simplifies some things. $\endgroup$
    – leonbloy
    Mar 23, 2019 at 2:10
5
$\begingroup$

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.

Solution of d/n as a function of m/n for large n

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.