Fdtxjr

Let $Y=minX_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.

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 binomny-I_frac12(n-y,y+1)+1right)^2^beta n-left(1-I_frac12(n-y,y+1)right)^2^beta n$$

when $0leq y<n$ and

$$Pr(Y=n)=left(2^-n binomnyright)^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"]

$$
beginarraycccc
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 \
endarray
$$

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_ile 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 $ntoinfty$.

Let's use the approximation $log_2 binomnd 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(fracx1-x)$, or

$$hleft(fracd-jnright)approx h(d/n) + log_2left(fracdn-dright) fracjn tag2$$

then

$$P(X_i=d-j)approx P(X_i=d) left(fracdn-dright)^j tag3$$

and

$$P(X_i le d) = sum_j=0^d P(X_i=d-j) approx P(X_i=d) left(fracn-dn-2dright) tag 4$$

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

$$ log_2left(frac1- 2 t1-tright)=n left(h(t) - 1 +beta right) tag5$$

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

$$ h(t)=1-beta tag6$$

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

So we take $d = n hatt $ , 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)$.