# Asymptotics of the minimum of Binomial random variables [closed]

Let $$Y=\min\{X_1, X_2 \cdots X_k\}$$ be the minimum of $$k$$ iid Binomial $$(n,1/2)$$ random variables.

I'm interested in the asymptotics of $$Y$$ (distribution, or mean and variance) for large $$n$$ and $$k = 2^{ \beta n }$$, with $$\beta < 1/2$$.

Any suggestions or pointers would be appreciated.

• $Pr(Y=y)=\left(2^{-n} \binom{n}{i}-I_{\frac{1}{2}}(n-i,i+1)+1\right){}^{2^{\beta n}}-\left(1-I_{\frac{1}{2}}(n-i,i+1)\right){}^{2^{\beta n}}$ if $0\leq y <n$ and $2^{n \left(-2^{\beta n}\right)}$ if $y=n$ (according to Mathematica).
– JimB
Commented Mar 22, 2019 at 5:12
• And $I_{z}(a,b)$ is the regularized incomplete beta function.
– JimB
Commented Mar 22, 2019 at 5:20
• @JimB Perhaps you should add that as answer, perhaps commenting on its derivation. Commented Mar 22, 2019 at 15:10

This is just a partial answer in that it gives the probability mass function for finite values of $$n$$ (i.e., no asymptotics).

Using Mathematica one can find the probability mass function for a specific $$n$$ and $$\beta$$ with the following commands:

distY = OrderDistribution[{BinomialDistribution[n, 1/2], 2^(beta n)}, 1];
pmf = PDF[distY, y]


with the following result:

$$Pr(Y=y)=\left(2^{-n} \binom{n}{y}-I_{\frac{1}{2}}(n-y,y+1)+1\right){}^{2^{\beta n}}-\left(1-I_{\frac{1}{2}}(n-y,y+1)\right){}^{2^{\beta n}}$$

when $$0\leq y and

$$Pr(Y=n)=\left(2^{-n} \binom{n}{y}\right)^{2^{\beta n}}$$

when $$y=n$$ where $$I_z (a,b)$$ is the regularized incomplete beta function.

If $$\beta=1/20$$, then one can construct a table of the means and variances for values of $$n$$:

beta = 1/20;
distY = OrderDistribution[{BinomialDistribution[n, 1/2], 2^(beta n)}, 1];
data = Table[{n, 2^(beta n), Mean[distY] // N, Variance[distY] // N}, {n, 20, 240, 20}]
TableForm[data, TableHeadings -> {None, {"n", "k", "Mean", "Variance"}}]


$$\begin{array}{cccc} 20 & 2 & 8.74629 & 3.42822 \\ 40 & 4 & 16.7558 & 4.91162 \\ 60 & 8 & 24.5034 & 5.56277 \\ 80 & 16 & 32.1274 & 5.85087 \\ 100 & 32 & 39.6867 & 5.97801 \\ 120 & 64 & 47.2088 & 6.03288 \\ 140 & 128 & 54.7079 & 6.05502 \\ 160 & 256 & 62.1913 & 6.06233 \\ 180 & 512 & 69.6636 & 6.06297 \\ 200 & 1024 & 77.1272 & 6.06068 \\ 220 & 2048 & 84.5839 & 6.05716 \\ 240 & 4096 & 92.0349 & 6.05319 \\ \end{array}$$

With larger values of $$n$$, there will likely be numerical overflow issues unless some care is taken. However, so far the relationship with $$n$$ and the mean seems pretty linear:

This attempts to get the asymptotical behaviour of $$P(Y)$$, making some adaptations (and, I think, some simplifications and improvements) to this answer in other SE site, which corresponds to essentially this problem with $$\beta < 1/2$$.

We seek to find some $$d$$ such that $$P(X_i\le d) \approx 1/k$$, so that $$P(Y>d) \approx (1-1/k)^k \to e^{-1}$$.

We expect (hope) that $$d/n$$ will be asymptotically constant, as $$n\to\infty$$.

Let's use the approximation $$\log_2 \binom{n}{d} \approx n \, h(d/n)$$, where $$h()$$ is the binary entropy function, so

$$P(X_i=d)\approx 2^{-n(1-h(d/n))} \tag1$$

Noticing that for $$\delta \ll x$$ we have $$h(x+\delta) \approx h(x) - \delta \log_2(\frac{x}{1-x})$$, or

$$h\left(\frac{d-j}{n}\right)\approx h(d/n) + \log_2\left(\frac{d}{n-d}\right) \frac{j}{n} \tag2$$

then

$$P(X_i=d-j)\approx P(X_i=d) \left(\frac{d}{n-d}\right)^j \tag3$$

and

$$P(X_i \le d) = \sum_{j=0}^d P(X_i=d-j) \approx P(X_i=d) \left(\frac{n-d}{n-2d}\right) \tag 4$$

Plugging $$(1)$$ into $$(4)$$ and equating it to $$1/k= 2^{-\beta n}$$, calling $$t=d/n$$, we get

$$\log_2\left(\frac{1- 2 t}{1-t}\right)=n \left(h(t) - 1 +\beta \right) \tag{5}$$

If we impose that $$t$$ is (asympotically) constant wrt $$n$$, then this implies that (asympotically) this constant (which we call $$\hat{t}$$) must be a root of

$$h(t)=1-\beta \tag{6}$$

In this case, it should be the lower ($$t<1/2$$) root. For example, for $$\beta=1/4$$ we get $$\hat{t}=0.2145017$$.

So we take $$d = n \hat{t}$$ , rounded to the nearest integer.

This implies (details here) that the distribution of $$Y$$ corresponds to a Gumbel distribution, with mean tending asymptotically to $$d$$ (hence growing linearly with $$n$$) and constant variance. Hence $$Y$$ is asymptotically concentrated around the root of $$(6)$$.