Weights of random sets of random 32-bit strings I have random sets of $N$ random 32-bit strings,
where all bits are i.i.d. with $\mathbb{P}(0) = \mathbb{P}(1) = 1/2$.
Define
$\ \ \ \ $weight( 32-bit x ) = number of 1 bits in x, i.e. Hamming distance to 0
$\ \ \ \ $minweight( set $X$ ) = min$_{\text{x} \in X}$ weight( x )
How does the average minweight( $X$ ) vary with $N$, the size of $X$ ?
My $N$ is small enough that it doesn't matter whether $X$ has duplicates, or not.
A back-of-the envelope estimate would be fine.
(A harder question is to analyze the algorithm for
bit-string-nearest-neighbour-searching
on stackoverflow,
but that seems rather specialized.
If anyone could suggest another forum or reference,
I'd appreciate it.)
 A: Given the small length of the strings of interest, providing a (computable) exact solution is straightforward.
As noted in the comments, if $X$ is a random bit-string of length 32, then the weight
$$
W = \mathrm{weight}(X) \>,
$$
the Hamming distance with respect to zero, is just the sum of the digits and so is binomial with parameters $n = 32$ and $p = 1/2$.
Distribution of the minimum
Now, recall that if $W_1,\ldots,W_n$ is a random sample of size $n$ from distribution $F$, then
$$
\renewcommand{\Pr}{\mathbb P}
\Pr\left( \min_{1\leq i \leq n} W_i > w\right) = (1 - F(w))^n \>.
$$
In our case, each $W_i$ is discrete and so it suffices to consider the probability of each atom. 
Let $\newcommand{\Wo}{W_{(1)}}\Wo$ denote the minimum of the sample of size $n$. Then, $\Wo \in \{0,\ldots,32\}$, and so
$$
\Pr(\Wo = w) = \Pr(\Wo > w - 1) - \Pr(\Wo > w) = (1-F(w-1))^n - (1-F(w))^n \>.
$$
Plugging in $F(w) = 2^{-32} \sum_{k=0}^w {32 \choose k}$ will yield the desired probabilities.
Note that this results extends easily to the case of general $n$ and $p$, as well.
A note on the expected value
The expected value can readily be computed by the standard formula 
$$
\mathbb E \Wo = \sum_{w=0}^{32} w \Pr(\Wo = w) \>,
$$
though to get a rough estimate, we can note that
$$
\mathbb E \Wo \leq 32 \Pr(\Wo > 0) = 32 (1 - 2^{-32})^n \>,
$$
so the expected value converges to zero geometrically fast.
