Approximating Probability Distribution by Sampling

Question

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.

Answer 1

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

Answer 2

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