0
$\begingroup$

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)

$\endgroup$
4
  • $\begingroup$ How would you measure closeness? $\endgroup$ Dec 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$
    – mssmath
    Dec 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$
    – Steve
    Dec 22, 2019 at 9:11
  • $\begingroup$ Modified the question to clarify exactly what I need; this is equivalent to my comment. $\endgroup$
    – mssmath
    Dec 22, 2019 at 12:30

1 Answer 1

3
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.