Distinguishing a biased coin with a small set of tests Say we have a "coin" $f : [n] \to \{\pm 1\}$ so that either $f$ is balanced, or $f$ is $\epsilon$-far from being balanced.

It's a classic result that sampling $O(1/\epsilon^2)$ random points of $f$ are enough to determine if $f$ is biased. That is, if $\mathcal{F} = \binom{[n]}{O(1/\epsilon^2)}$ is the collection of all subsets of size $O(1/\epsilon^2)$, then with probability at least $2/3$ over a random choice of a set $S$ from $\mathcal{F}$, the bias of $S$ will be within $\epsilon/2$ of the true bias of $f$ (correctly determining if $f$ is balanced/unbalanced).

Are there smaller families $\mathcal{F}$ that have the same property? For example, is it possible to find a collection of poly($n, 1/\epsilon)$ sets where 2/3 of the sets have bias close to the bias of $f$, for any $f$ either balanced or $\epsilon$-far from balanced?
Yes. Such families are called "averaging samplers", and there are plenty of constructions for them. You can find a more information about them (and about the more general notion of sampler) in this survey.

The notion of averaging samplers was introduced in this paper, which also showed that they are equivalent to randomness extractors. There are many constructions of extractors, and you can use any of them to construct samplers.

Here are a few relatively simple ways to construct such families:


Take a random family, as pointed out by Emil Jerabek in the comments.
Construct a family using a $k$-wise independent hash function, as pointed out in the comments by D.W.
Construct a family by considering an expander graph over the vertex set [n] and taking the neighborhood of radius $r$ around every vertex (for some sufficiently large values of $r$) - see for example this lecture. Alternatively, take the family obtained from the set of random walks of length $r$ on the graph. -- see for example this lecture  .