3
$\begingroup$

Consider a discrete probability distribution over $n$ events. Assume that the probabilistic kernel is a black box, that is, we can only sample from it without knowing anything about the type or parameters of the distribution model.

We want to find a good approximation of the distribution model by taking $k$ independent samples from the distribution.

The questions are:

1 - How can we do this? and is there any theoretical guarantee on this ?

2 - what should $k$ be to get a reasonable approximation ?

I imagine there should be a relation between $n$ and $k$ to get $\epsilon$ approximation.

$\endgroup$
  • $\begingroup$ Probably the most obvious choice for an approximation would be the empirical distribution function. The Glivenko-Cantelli theorem states that it converges almost surely to the true distribution, and there are many results on the rate of convergence in various modes. This is quite classical and not really a research-level question. $\endgroup$ – Nate Eldredge May 16 '14 at 15:31
  • $\begingroup$ This is a fairly active research area in theoretical computer science, but the problems studied might not be what you are looking for. Check recent papers of, say, Ilias Diakonikolas and Rocco Servedio on testing and learning distributions. There is also earlier work by Batu, Fortnow, Rubinfeld, Smith, and White on testing how close to uniform a distribution is, if two unknown distributions are equal, and related problems, using only independent samples. $\endgroup$ – KEW Jul 15 '14 at 16:17
  • $\begingroup$ I'll add that differentiating between the uniform distribution on $\{1,2,\ldots,n\}$ and a distribution whose probability mass function is of $L_1$-distance at least $\epsilon$ from the uniform p.m.f. requires $\Omega(\sqrt{n})$ samples in the worst-case for constant $\epsilon$. $\endgroup$ – KEW Jul 15 '14 at 16:20
3
$\begingroup$

Just saw this question. As KEW says in the comments, questions like these are studied in theoretical CS as it intersects with stats.

It depends on the measure used to define "good". One natural choice is the $\ell_1$ metric, so if the original distribution is the vector $A$, and your samples give the empirical distribution $\hat{A}$, then you want

$$ \|A - \hat{A}\|_1 = \sum_i |A_i - \hat{A}_i| \leq \epsilon .$$

In this case, it is "common knowledge" that $\Theta\left(\frac{n}{\epsilon^2}\right)$ samples are necessary and sufficient to ensure that, with probability $1-\delta$ for fixed $\delta$, $\|A - \hat{A}\|_1 \leq \epsilon$. I really don't think there is an original reference for this statement.

Another measure is the $\ell_{\infty}$ metric, so you want

$$ \|A - \hat{A}\|_{\infty} = \max_i |A_i - \hat{A}_i| \leq \epsilon . $$

In this case, it is "common knowledge" that $\Theta\left(\frac{1}{\epsilon^2}\right)$ samples are necessary and sufficient to ensure that, with probability $1-\delta$ for fixed $\delta$, $\|A-\hat{A}\|_{\infty} \leq \epsilon$. This I can at least attribute to the DKW inequality. (The argument in Ben Barber's answer gives the intuition, but not sure if it gives the exact answer because you would seem to have to union-bound over the coordinates.)


Edit 2015-02: I hope it is ok to mention that I now have a paper published part of which covers this question (arxiv link, Theorems 5.2/5.3) for the $\ell_p$ metrics. You can get very tight constants, e.g. for $\ell_1$ distance, to guarantee an $\epsilon$ approximation with probability at least $1-\delta$, a sufficient number of samples is $4\ln(1/\delta) \frac{n}{\epsilon^2}$. For $\ell_p$ with $2 \leq p \leq \infty$, a sufficient number is $4\ln(1/\delta) \frac{1}{\epsilon^2}$. For $1 < p < 2$ you get an interesting interpolation between these depending on the relationship of support size $n$ and tolerance $\epsilon$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Let $X_i$ be the number of times that you get result $i$ in $k$ trials. Each $X_i$ is binomially distributed, so by Chernoff's inequality is unlikely to differ by substantially more than $\sqrt k$ from its expectation. So if you can tolerate an absolute error of order $\epsilon$ in the estimate of each probability, then taking $k$ to be slightly greater than $1/\epsilon^2$ will give you good enough estimates with high probability. (Exactly how much greater depends on how low you want the failure probability to be, and how large $n$ is.)

| cite | improve this answer | |
$\endgroup$

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.