7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – D.W. Dec 10 '18 at 22:20
  • 1
    $\begingroup$ You need to bound the size of the sets in ${\cal F}$ for the question to be meaningful, otherwise ${\cal F} = \{[n]\}$ suffices. $\endgroup$ – daniello Dec 11 '18 at 4:47
  • 3
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek supports Monica Dec 11 '18 at 9:30
8
$\begingroup$

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 .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.