# 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?

• Does it work to use the set $\{h(1),h(2),\dots,h(1/\epsilon^2)\}$ where $h:\mathbb{N} \to [n]$ is a randomly chosen 2-universal function? What about $\{i \in [n] : h'(i) \le p/n\epsilon^2\}$ where $h':\mathbb{N} \to [p]$ is a randomly-chosen 2-universal function? This should let you get a bound on the bias of $f$ (since you control the mean and variance). – D.W. Dec 10 '18 at 22:20
• You need to bound the size of the sets in ${\cal F}$ for the question to be meaningful, otherwise ${\cal F} = \{[n]\}$ suffices. – daniello Dec 11 '18 at 4:47
• Using your bounds, if you choose about $O(n)$ independent random sets of size $O(1/\epsilon^2)$, they will have this property with respect to any fixed coin $f$ with probability, say $2^{-n-1}$, hence by the union bound, they will have this property wrt all coins with probability at least $1/2$, hence there exists a family of $O(n)$ sets of size $O(1/\epsilon^2)$ that will do the job. – Emil Jeřábek Dec 11 '18 at 9:30

• 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 .