What is the average lowest value from N random binomial experience

Question

Let $X_1,\ldots,X_n$ be indepedent Bin(n,1/2), and let M be their minimum. What is $E[M]$? (or an upper bound for it).

Answer 1

Its easy to write a summation for it:

$P (\min_i X_i >m ) = P(X_1,\ldots,X_n >m) = P(X_1 >m) P(X_2 >m) \ldots P(X_n >m)$ when $X_1,\ldots,X_n$ are independent.

In the i.i.d. case, $P(\min_i X_i >m) = (P(X_1 >m))^n$. Now, you can use the fact that $\min_i X_i$ is non-negative integer valued to note that $E[\min_i X_i] = \sum_{m >0} P[\min_i X_i > m] = \sum_{m=0}^n (P(X_1 > m))^n$.

If you want to upper bound it, substitute a binomial tail bound for $P(X_1 > m)$.