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|}$.

  • 1
    $\begingroup$ What do you mean by "super polynomial"? $\endgroup$ Jun 12, 2022 at 16:28
  • $\begingroup$ @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$. $\endgroup$ Jun 12, 2022 at 17:09
  • 1
    $\begingroup$ 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$. $\endgroup$ Jun 12, 2022 at 19:53
  • $\begingroup$ @IosifPinelis, yeah, let me fix that, thank you! $\endgroup$ Jun 13, 2022 at 8:09


Your Answer

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