Assume I have a random vector $X = \{x_1, x_2, ..., x_N\}$, composed of i.i.d. binomially distributed values. If it would simplify the problem substantially, we can approximate them as normally distributed. Given that all other parameters are fixed, I want to know how $E[min(X)]$ (the expected value of the smallest number in the vector $X$) scales with $N$.
I don't care about a precise answer. I just want to know how it scales, i.e. linearly (obviously not), exponentially, power law, etc.
Assume that the random variables $x_k$ are i.i.d., nonnegative, integer valued, bounded by $n$, and such that $P(x_k=0)$ and $P(x_k=1)$ are both positive. For every $N\ge1$, let $$ X_N= \min\{x_1,\ldots,x_N\}. $$ Then, when $N\to+\infty$, $$ E(X_N)=c^N(1+o(1)), $$ where $c<1$ is independent of $N$ and given by $$ c=P(x_k\ge1). $$ Hence $E(X_N)$ is exponentially small. When each $x_k$ is Binomial $(n,p)$ with $n\ge1$ and $p$ in $(0,1)$ fixed, the result holds with $c=1-(1-p)^n$.
To see this, note that $[X_N\ge i]=[x_1\ge i]\cap\cdots\cap[x_N\ge i]$ for every $i$ and that, since $X_N$ is nonnegative and integer valued, $E(X_N)$ is the sum over $i\ge1$ of $P(X_N\ge i)$, hence $$ E(X_N)=\sum_{i\ge 1}P(x_1\ge i)^N. $$ For every $i\ge n+1$, $P(x_1\ge i)=0$. For every $2\le i\le n$, $0\le P(x_1\ge i)\le P(x_1\ge 2)$. Hence $$ c^N\le E(X_N)\le c^N+(n-1)d^N, $$ with $$ c=P(x_1\ge1),\quad d=P(x_1\ge 2). $$ Because $P(x_k=1)$ is positive, one knows that $d<c$, hence $E(X_N)\sim c^N$ when $N\to+\infty$.
The table in this page of this book might help you. The explicit formulas for the expectation of minimum of sample of binomial distributions is given in the page before.
The distribution of the minimum of any set of N iid random variables is:
$$f_{min}(x)=Nf(x)[1-F(x)]^{N-1}$$
Where $f(x)$ is the pdf and $F(x)$ is the cdf (this is sometime called a $Beta-F$ distribution, because it is a compound of a Beta distribution and an arbitrary distribution). Hence the expectation (in this particular case) is given by:
$$E[min(X)] = N\sum_{x=0}^{x=n} xf(x)[1-F(x)]^{N-1}$$
Which means that $E[min(X)]=NE(x_1[1-F(x_1)]^{N-1})$. Using the "delta method" to approximation this expectation $E[g(x)]\approx g(E[X])$ gives
$$E[min(X)]=NE(x_1[1-F(x_1)]^{N-1})\approx N(E(x_1)[1-F(E(x_1))]^{N-1})$$
Substituting $np=E[x_1]$ then gives the approximation:
$$E[min(X)]\approx Nnp[1-F(np)]^{N-1}$$
Note that $F(np)\approx \frac{1}{2}$ (via normal approx.) to give
$$E[min(X)]\approx \frac{Nnp}{2^{N-1}}$$
