# $\epsilon$-net for the set of distributions

Let $$S$$ be a space of all distributions over a finite set $$X$$. What is the size of its $$\epsilon$$-net w.r.t. the total variation distance defined as $$d(P,Q) = \frac12 \sum_{x \in X} |\Pr[P=x] - \Pr[Q=x]|$$ i.e. the size of the smallest subset of distributions such that each distribution from $$S$$ is $$\epsilon$$-close to one of the distributions in the subset.

For small constant $$\epsilon$$ the volume of an $$\epsilon$$-ball is $$(4\epsilon)^n$$ (if we normalize the volume such that the volume of all $$S$$ is 1) so the size of $$\epsilon$$-net should be at least $$(4\epsilon)^{-n}$$ where $$n=|X|$$.

Is there a super polynomial lower bound for the case $$\epsilon = 1 - o(1)$$? I am interested in the case where $$\epsilon = 1 - \frac{1}{\log^\alpha |X|}$$.

• What do you mean by "super polynomial"? Jun 12, 2022 at 16:28
• @IosifPinelis of size $n^{\omega(1)}$, but preferably I would like to show that the smallest possible $\epsilon$-net for $|X|=n$ has size $c^n$ for some $c > 1$. Jun 12, 2022 at 17:09
• I think your $o(1)$ should be specified. Indeed, if $\epsilon>1-1/n$, then the singleton set of the uniform distribution on $X$ is an $\epsilon$-net for $S$. Jun 12, 2022 at 19:53
• @IosifPinelis, yeah, let me fix that, thank you! Jun 13, 2022 at 8:09