Consider $s = \Theta(n^{\delta})$ for a $\delta\in (0,1)$ and let $p\in (0,1)$ with $m = \lfloor pn\rfloor$. Consider the random variable $Y$ which chooses $m$ elements from $\{1,\ldots,n\}$ such that any set of $m$ elements is equally likely. Then define $X$ to be $|Y \cap \{1,\ldots,s\}|$ where $|A|$ denotes the size of $A$. What is the total variation distance between $X$ and $\text{Bin}(s,p)$ in terms of the parameters $s,n,p$? (This is surely in the literature and using Stirling is tricky to work for all parameter ranges)
-
$\begingroup$ How would you measure closeness? $\endgroup$– LeechLatticeDec 22, 2019 at 5:32
-
$\begingroup$ Note that we have a distribution on the power set for the first $s$ elements and let $2^{[s]}$ denote the power set of these elements. Up to an absolute constant the question is asking what is $\sum_{S\in 2^{[s]}}|p(S)-q(S)|$ where $p(S)$ denotes the probability of getting the set $S$ from the first distribution and $q(S)$ is analogous. $\endgroup$– mssmathDec 22, 2019 at 5:36
-
1$\begingroup$ I find your description of the distributions a bit hard to understand. Could you perhaps clean the question up a bit, and make the definitions precise? $\endgroup$– SteveDec 22, 2019 at 9:11
-
$\begingroup$ Modified the question to clarify exactly what I need; this is equivalent to my comment. $\endgroup$– mssmathDec 22, 2019 at 12:30
1 Answer
According to formula (2), the total variation distance in question is bounded from above by $\dfrac{m-1}{n-1}$ assuming that $p=m/n$. Obviously, this bound does not depend on $s$. According to this paper, this bound is optimal, up to a universal constant factor.
(If you insist on having a bound for all values of $p\in[\frac mn,\frac{m+1}n)$, then I think it should be easy to additionally bound the total variation distance between two binomial distributions with the same value of $n$ and two different but close values of $p$, using the fact that the binomial family is stochastically monotone.)