ECorollary 6.9 in A Guide to NIP theories 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 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.

  • $\begingroup$ You are right, but working with multisets is normally easier in these kinds of problems anyways. Many authors write "set" when they should have written "multiset". $\endgroup$
    – Boris Bukh
    May 20 '15 at 1:52

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

  • $\begingroup$ Indeed, the mistake has no consequences for the proof of the (q,q)-theorem. Thank you very much. $\endgroup$ May 20 '15 at 6:41
  • $\begingroup$ Btw. in version 1 of Simon's article, Corollary 6.9 was stated for $\epsilon$-nets. This was correct and sufficient for the (q,q)-theorem. $\endgroup$ May 20 '15 at 11:03

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.