3
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by "super polynomial"? $\endgroup$
    – Iosif Pinelis
    Commented 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$
    – Artur Riazanov
    Commented 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$
    – Iosif Pinelis
    Commented Jun 12, 2022 at 19:53
  • $\begingroup$ @IosifPinelis, yeah, let me fix that, thank you! $\endgroup$
    – Artur Riazanov
    Commented Jun 13, 2022 at 8:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .