4
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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$.” $\endgroup$
    – user44143
    Jan 16, 2020 at 19:57

3 Answers 3

3
$\begingroup$

$\newcommand\ep{\epsilon}$ $\newcommand\ch{\operatorname{ch}}$ This answer is based on Theorem 3 and formula (2), which yield $$P(|S_m|\ge x) \le2\exp\Big(-tx+\sum_{i=1}^m E(e^{t|X_i|}-t|X_i|-1)\Big), \tag{0} $$ where $x$ and $t$ are any nonnegative real numbers, $S_m:=X_1+\dots+X_m$, and $X_1,\dots,X_m$ are any independent zero-mean random vectors in any separable Hilbert space $H$ with norm $|\cdot|$. Inequality (0) is also a special case of Theorem 3.1 for martingales in $(2,D)$-smooth separable Banach spaces; note that a Hilbert space is $(2,1)$-smooth.

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

$\endgroup$
2
$\begingroup$

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

[1] https://cstheory.stackexchange.com/a/18498/8243 [2] https://arxiv.org/abs/1412.2314

$\endgroup$
2
0
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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