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)$?

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

Let $S$ be a space of all distributions over a finite set $X$. What is the size of its $\epsilon$-net w.r.t. statistical 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)$?

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)$?