Reconstructing probability distribution with high probability

Sample $$m$$ times from unknown probability distribution $$p=(p_1,p_2,\cdots,p_n)$$, we can construct a probability distribution $$q=(q_1.q_2,\cdots,q_n)$$.

How large $$m$$ should be to achieve that the probability of $$||p-q||_2<\epsilon$$ is at least $$1-\delta$$? We are particularly interested in the case of $$\delta=1/n^2$$.

• I would replace the first paragraph by: “We have a discrete distribution on $\{1,2,\ldots n\}$ with probabilities $p_i$, then sample from it $m$ times, and record the observed probabilities $q_i$ as (number of observed $i$’s) $/m$.” – Matt F. Jan 16 at 19:57


In our case, let $$H=\mathbb R^n$$ with $$|\cdot|:=\|\cdot\|_2$$ and let $$X_i:=(1_{Y_i=1}-p_1,\dots,1_{Y_i=n}-p_n),$$ where $$Y_1,\dots,Y_m$$ are iid random variables (r.v.'s) such that $$P(Y_i=j)=p_j$$ for $$j\in[n]:=\{1,\dots,n\}$$ and $$p_1+\dots+p_n=1$$. Then we can write
$$S_m=m(q-p),$$ where $$p$$ and $$q$$ are as in the OP. So, for all $$\ep\in(0,1/2]$$ and all real $$t\ge0$$, $$P(|q-p|\ge\ep)=P(|S_m|\ge m\ep) \\ \le2\exp\Big(-tm\ep+\sum_{i=1}^m E(e^{t|X_i|}-t|X_i|-1)\Big). \tag{1}$$ Next, almost surely (a.s.) $$|X_i|^2=\sum_{j=1}^n1_{Y_i=j}-2\sum_{j=1}^np_j1_{Y_i=j}+\sum_{j=1}^np_j^2 \le1-2\times0+\sum_{j=1}^np_j^2\le2$$ and $$E|X_i|^2=1-\sum_{j=1}^np_j^2\le1.$$ Also, $$r(u):=\frac{e^u-u-1}{u^2}$$ is increasing in real $$u$$ (with $$r(0):=1/2$$), whence $$r(u)\le r(\sqrt 2/2)=:c=0.64\ldots$$ for $$u\le\sqrt 2/2$$. Letting now $$t_*:=\frac\ep{2c}<\ep\le1/2$$, we have $$t_*|X_i|\le\sqrt2/2$$ a.s. So, a.s. for all $$i\in[m]$$
$$e^{t_*|X_i|}-t_*|X_i|-1=r(t_*|X_i|)t_*^2|X_i|^2\le c t_*^2|X_i|^2.$$ Hence, by (1), $$P(|q-p|\ge\ep)\le2\exp\Big(-t_*m\ep+\sum_{i=1}^m c t_*^2E|X_i|^2\Big) \\ \le2\exp(-t_*m\ep+mct_*^2) =2\exp\Big(-\frac{m\ep^2}{4c}\Big).$$ So, for any $$\delta>0$$, $$P(|q-p|<\ep)\ge1-\delta$$ if $$m\ge\frac{4c}{\ep^2}\,\ln\frac2\delta$$ and $$\ep\in(0,1/2]$$. (Replacing $$1/2$$ in the condition $$\ep\in(0,1/2]$$ by a small enough positive real number, we can replace $$c$$ by a constant factor however close to $$1/2$$.)

Based on this cstheory post's argument from Clément Canonne[1], for $$\delta = O(1)$$ it suffices to draw $$m = O(1/\epsilon^2)$$ samples. This can be extended to show that $$m = O\left(\frac{\log(1/\delta)}{\epsilon^2}\right)$$ samples suffices.

Slightly more details, which are worked out thanks to Clément / folklore in Theorem D.2 of my paper[2]: We can use the cstheory argument to show if $$m \geq \frac{4}{\epsilon^2}$$, then $$\mathbb{E}\|p-q\|_2^2 \leq \frac{\epsilon^2}{4}$$. Jensen’s gives $$\mathbb{E}\|p-q\|_2 \leq \frac{\epsilon}{2}$$. We can use McDiarmid's concentration inequality to show that if $$m \geq \frac{4\ln(1/\delta)}{\epsilon^2}$$, then $$\|p-q\|_2$$ is within $$\frac{\epsilon}{2}$$ of its expectation w.p. $$1-\delta$$. This combines to show $$\|p-q\|_2$$ is at most $$\epsilon$$ w.p. $$1-\delta$$.

It’s surprising at first that this doesn’t depend on the support size n (unlike L1 learning), which was the motivation for [2].

I am assuming you are using the empirical distribution as in the comment by @MattF.

This is a very broad question, and the answer changes quite a bit according to what properties the true distribution $$p$$ has. Note that if $$\min_{i} p_i=\epsilon,$$ which is very small, then you need a very large number of samples before you actually obtain the value $$i,$$ by sampling. If there are a few large probabilities, they will dominate the samples.

A good place to start is Valiant and Valiant's paper Instance Optimal Learning of Discrete Distributions available here. Also have a look at the references there. Most people focus on the distance $$\mid\mid p-q\mid\mid_1$$ which is directly related to the maximal query probability of distinguishing $$p$$ from $$q.$$ Related work includes estimating entropy and other properties of distributions.

Historically, the Good-Turing method is where all this stuff originates.

Edit: The paper by Indyk et al here seems to provide an answer which is to a question very close to your question. The techniques there should help. Basically they state that, for $$\ell_2$$ distance $$\leq \varepsilon$$ between $$p$$ and $$q$$ one needs $$\widetilde{O}((n/\varepsilon)^2 \log n)$$ samples and similar running time. The definition of successful approximation there is the standard one in complexity theory, of probability of error being $$\leq 1/3.$$