ECorollary 6.9 in [A Guide to NIP theories](http://arxiv.org/abs/1208.3944v2) by Pierre Simon proves the following



> 
> **Theorem.** For every positive integer $k$ and every positive real $\varepsilon$ there is an integer $n=n(k,\epsilon)$ such that any probability measure $\mu$ on a finite set system $(X,\Delta)$ with VC-dimension $\le k$ admits an $\varepsilon$-approximation of size $\le n$.
> 
> 
> 


Recall that a finite set system is a pair $(X,\Delta)$ where $X$ is a finite set and $\Delta\subseteq{\mathcal P}(X)$. Given a probability measure $\mu$, an $\varepsilon$-approximation is a set $B\subseteq X$ such that


$$\left | \frac{|S \cap B|}{|B|} - \mu(S) \right | \leq \epsilon.$$ 


holds for every $S\in\Delta$.


**Question** I can prove the theorem if working with multi-sets (i.e. sets whose elements are counted with some finite multiplicity). As it is stated it may not be true. Suppose $X$ contains two points of mass $p\_0<p\_1$ with $\varepsilon<p\_0$ and $2\varepsilon<p\_1-p\_0$ it seems there isn't any $\varepsilon$-approximations, no matter what size.


Am I reading things wrongly?




---


EDIT1: I just realize that the proof of the main theorem of Section 6 (the (q,q)-theorem) can be adapted to work with multi-sets. So it is not a major problem. Still, multi-sets make the proofs messier and I would like to know if they are really necessary.


EDIT2: I just realize that in an earlier version of [A Guide to NIP theories](http://arxiv.org/abs/1208.3944v1) Corollary 6.9 was stated with $\epsilon$-net for $\epsilon$-approximation. This version is correct. If one is not interest in good bounds, one can obtain an $\epsilon$-net from a multi-set just forgetting multiplicity. In the proof of the (q,q)-theorem only $\epsilon$-nets are used.



Epsilon-approximations of set systems with finite VC-dimension
Yes, I also noticed that there was a mistake there not too long ago. But I think there's no problem. The proof of the corollary just works as it is. There are two uses of 6.9 in the proof.   

The first one is finding S with measure greater than $1 - \epsilon$. Well, if the set $\{x\_1,...,x\_q\}$ is a multiset, then it's even easier to find a set which contains all these points.  

The second one is in the end, finding the $S\_1',...,S\_N'$. Same thing: if there are repetitions, then it's even better.   

  

I think that there's no way to avoid multisets in general (if $X$ is big enough and the measure is uniform enough, I think that with high probability you would get a set and not a multiset, but in general, that wouldn't be the case). 


