Asymptotics of the minimum of Binomial random variables

Question

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.

Answer 1

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

Answer 2

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<n$ 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: