# Learn this distribution from samples? What is the sample complexity?

$$\newcommand{\norm}{\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$$.

• Are you looking for universal values of $m$ or for formulae that depend on the $p_i,$ $p_{ij},$ etc.? – whuber Jun 13 '19 at 22:03
• 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. – jax.adan Jun 13 '19 at 22:22
• $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. – whuber Jun 13 '19 at 22:27
• 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. – jax.adan Jun 14 '19 at 15:43

## 1 Answer

• $$\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).

• 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? – jax.adan Jun 14 '19 at 18:56
• @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 – Clement C. Jun 14 '19 at 19:16
• 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? – jax.adan Jun 14 '19 at 19:19
• 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. – Clement C. Jun 14 '19 at 19:28
• @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). – Clement C. Jun 14 '19 at 19:40