<p>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 <a href="http://www.wisdom.weizmann.ac.il/~oded/COL/samplers.pdf" rel="nofollow noreferrer">this survey</a>.</p>

<p>The notion of averaging samplers was introduced in <a href="https://www.cs.utexas.edu/~diz/pubs/sampler.pdf" rel="nofollow noreferrer">this paper</a>, 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.</p>

<p>Here are a few relatively simple ways to construct such families:</p>

<ul>
<li><p>Take a random family, as pointed out by Emil Jerabek in the comments.</p></li>
<li><p>Construct a family using a <span class="math-container">$k$</span>-wise independent hash function, as pointed out in the comments by D.W.</p></li>
<li><p>Construct a family by considering an expander graph over the vertex set [n] and taking the neighborhood of radius <span class="math-container">$r$</span> around every vertex (for some sufficiently large values of <span class="math-container">$r$</span>) - see for example <a href="http://sites.math.rutgers.edu/~sk1233/courses/topics-S18/lec2.pdf" rel="nofollow noreferrer">this lecture</a>. Alternatively, take the family obtained from the set of random walks of length <span class="math-container">$r$</span> on the graph. -- see for example <a href="http://sites.math.rutgers.edu/~sk1233/courses/topics-S18/lec3.pdf" rel="nofollow noreferrer">this lecture</a>  .</p></li>
</ul>

CC BY-SA 4.0
2018-12-12T06:36:53.290Z
2018-12-14T08:13:56.220Z
2018-12-14T08:13:56.220Z
Or Meir
<p>Say we have a "coin" <span class="math-container">$f : [n] \to \{\pm 1\}$</span> so that either <span class="math-container">$f$</span> is balanced, or <span class="math-container">$f$</span> is <span class="math-container">$\epsilon$</span>-far from being balanced.</p>

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

<p>Are there smaller families <span class="math-container">$\mathcal{F}$</span> that have the same property? For example, is it possible to find a collection of poly(<span class="math-container">$n, 1/\epsilon)$</span> sets where 2/3 of the sets have bias close to the bias of <span class="math-container">$f$</span>, for any <span class="math-container">$f$</span> either balanced or <span class="math-container">$\epsilon$</span>-far from balanced? </p>

CC BY-SA 4.0
2018-12-10T22:20:39.400Z
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.
CC BY-SA 4.0
2018-12-11T04:47:05.547Z
You need to bound the size of the sets in ${\cal F}$ for the question to be meaningful, otherwise ${\cal F} = \{[n]\}$ suffices.
daniello
CC BY-SA 4.0
2018-12-11T09:30:25.797Z
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
<property-testing>
Distinguishing a biased coin with a small set of tests
Chris Jones
# Distinguishing a biased coin with a small set of tests

(Asked by: username_0 on 2018-12-10)

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?

**Tags:** property-testing

> **Comments:**
> **username_1**: 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).  
> **username_2**: You need to bound the size of the sets in ${\cal F}$ for the question to be meaningful, otherwise ${\cal F} = \{[n]\}$ suffices.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2018-12-12. Score: 8 | Accepted answer

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](http://www.wisdom.weizmann.ac.il/~oded/COL/samplers.pdf).

The notion of averaging samplers was introduced in [this paper](https://www.cs.utexas.edu/~diz/pubs/sampler.pdf), 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 username_1
* 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](http://sites.math.rutgers.edu/~sk1233/courses/topics-S18/lec2.pdf). Alternatively, take the family obtained from the set of random walks of length $r$ on the graph. -- see for example [this lecture](http://sites.math.rutgers.edu/~sk1233/courses/topics-S18/lec3.pdf) .


---

