2
$\begingroup$

$\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$

We have an $n$-variate distribution $X\in\{0,1\}^n | \sum_i^n X_i = k$. Or, in other words, we are guaranteed that only $k$ variables will be $1$ in any given trial. Therefore, there are only $n \choose k$ possible outcomes. We will call $P(X_i = 1) = p_i$, $P(X_i=1 ~\land~X_j=1) = p_{ij}$, and so on.

We are given $m$ samples from this distribution. With the samples, we can estimate the true distribution using an empirical estimator (or MLE, maximum likelihood estimator). We call the estimated distribution $\hat{X}$. What is the smallest $m$ can be for which we can make sure that $\hat{X}$ is close to $X$? Specifically, how small can $m$ be such that $P(\norm{\hat{X} - X}_1 \geq \epsilon) \leq \delta$ for some $\epsilon$ and $\delta$? How small can $m$ be such that $P(\norm{\hat{X}-X}_2 \geq \phi) \leq \gamma$ for some $\phi$ and $\gamma$?

I'm interested in the case where $n$ is known and there is no restriction on $k$.

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you looking for universal values of $m$ or for formulae that depend on the $p_i,$ $p_{ij},$ etc.? $\endgroup$ – whuber♦ Jun 13 '19 at 22:03
  • $\begingroup$ I'm looking for values of $m$ specific to this type of distribution. I assumed $p_i, p_{ij},etc.$ would be relevant in the analysis but not appear in the final result. The final result should be in terms of $n, k, \epsilon, \delta$ (or $\phi, \gamma$ for the L2 distance). Side note: I feel like $m$ shouldn't depend on $n$ but that's a guess...I'm pretty stuck on how to proceed. $\endgroup$ – jax.adan Jun 13 '19 at 22:22
  • $\begingroup$ $m$ will depend strongly on $n$ and $k,$ so don't drop them from consideration. Because you are looking for a universal bound, the $p_i$ etc. are wholly irrelevant. I suspect, without having checked, that the worst situation (in both metrics) is the highest-entropy one, where all of the subsets are equally likely. $\endgroup$ – whuber♦ Jun 13 '19 at 22:27
  • $\begingroup$ I'm trying to find the expectation values of $d_{l1}(\hat{X}, X)$ and $d_{l2}(\hat{X}, X)$. I think that should be good enough -- at least to claim $\epsilon$ accuracy after a certain number of samples. $\endgroup$ – jax.adan Jun 14 '19 at 15:43
1
$\begingroup$

  • $\ell_2$ won't be "interesting." You can learn any discrete distribution to $\ell_2$ distance $\phi$ with probability $1-\gamma$ with $O( \log(1/\gamma)/\phi^2 )$ samples, with no dependence on the domain size. And this will be tight even with your constraint (pretty much any estimation, even on a single bit, will require that many samples).

  • Now, in total variation/$\ell_1$. You basically have, as you say, an arbitrary distribution on $M = \binom{n}{k}$ elements. Learning this to total variation distance $\varepsilon$, w.p. $1-\delta$, can be done with $$ O\left( \frac{M + \log(1/\delta)}{\varepsilon^2} \right) $$ samples, and this is tight (up to constants). So the answer is $$ \Theta\!\left( \frac{\binom{n}{k} + \log(1/\delta)}{\varepsilon^2} \right) $$ Note: the upper bound is not going to be efficient in $n$ (but is efficient in the number of samples, and achieved by the empirical estimator) if $k$ is not a constant, as then you have a sample complexity super-polynomial in $n$ (e.g., $k=n/2$ leads to roughly a $2^{n}/\sqrt{n}$ dependence).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yea, I was hoping there was something better than reducing to the univariate case. Does this change if we are only interested in learning p_i's and p_{ij}'s? $\endgroup$ – jax.adan Jun 14 '19 at 18:56
  • $\begingroup$ @jax.adan that would be much cheaper (something like $\log(n/\delta)/\varepsilon^2$ to simultaneously approximate these ~$n^2$ values up to an additive $\varepsilon$), but that won't give you any meaningful guarantee about approximating the distribution itself $\endgroup$ – Clement C. Jun 14 '19 at 19:16
  • 1
    $\begingroup$ Got it. Can you give me more info on how you got $log(n/ \delta) / \epsilon^2$? And what distance metric is being used in that case? That any $p_i$ or $p_{ij}$ is within $\epsilon$ from the approximation? $\endgroup$ – jax.adan Jun 14 '19 at 19:19
  • $\begingroup$ Just take enough samples to estimate all these parameters (basically, they are Bernoulli coin flips to an additive $\varepsilon$, with failure probability $\delta'=\delta/n^2$ (using the same samples for all) then take a union bound over all $n(n+1)/2$ possible failures. You only need $O(\log(1/\delta')/\varepsilon^2)$ samples for that. $\endgroup$ – Clement C. Jun 14 '19 at 19:28
  • $\begingroup$ @jax.adan there is no natural metric there, though you can phrase it as $\ell_\infty$ for the vector of $n(n+1)/2$ parameters considered (marginal and pairwise means). $\endgroup$ – Clement C. Jun 14 '19 at 19:40

Your Answer

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

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