估计概率分布的准确性和样本数量有何关系？

已知分布类型，对某个参数的进行估计已经有人说了 Cramer-Rao bound 了。 我就说一下未知概率分布类型。对于未知概率分布类型，就是 信息论 领域研究的 Property Estimation ，Distribution Estimation ，Property Testing 问题 。并且这类问题近一两年 和 Communication complexity 结合起来，研究 分布式 的情形。分布式情形下即考虑 Communication complexity c 和 某个误差度量下的估计准确度 \epsilon 的 trade off。

对于未知概率分布，通过 n 个 独立同分布样本对该分布的某个性质进行估计，研究 样本数量 n 和 某个误差度量下的 估计准确度 \epsilon 的 trade off 的问题应该叫 Property Estimation 。信息论里面常见的性质有 熵，支撑集，互信息量 等。（其他回答里面的 hoeffding inequality 属于估计分布的均值）

对于未知概率分布，利用 n 个 独立同分布样本对该分布进行估计，研究 样本数量 n 和 某个误差度量下的估计准确度 \epsilon 的 trade off 的问题应该叫 Distribution Estimation。

对于未知概率分布，通过 n 个 独立同分布样本 判断 该分布是否具有某种性质，判断该分布具有这种性质 或者 远离这个性质 。研究 样本数量 n 和 某个误差度量下的 估计准确度 \epsilon 的 trade off 的问题应该叫 Property Testing 。比如判断该分布是不是均匀分布，是不是等于某个给定分布(identity testing)，概率密度函数是不是monotone的等。

注：Property Testing 在 理论计算机科学 里面也有研究，但是 一般不是判断某个 Distribution 具有某种性质，而是判断某个 function （一般看成黑盒，只能通过 query 得到 function 的值） 是不是具有某种性质 考虑 query complexity 和 接受或拒绝概率。比如经典的 BLR Test ，判断一个 function 是不是 linear 或者 近似 linear 的。 当然，这两个研究是有关系的，这个以后补充。

由于 篇幅关系，本篇回答主要简单介绍一下 离散分布的 Distribution Estimation 的两个例子。

推荐资料：

首先是定义，考虑一个随机变量 X ，其取值域为离散集合 \mathcal{X} ，其概率分布为 p(x) , x \in \mathcal{X} ， |\mathcal{X}| = k 。对于 X_1 ,...X_n 为独立同分布的随机变量，其概率分布为 p(x^n) = \prod_{i=1}^{n}p(x_i) ,(x_1,...x_n) \in \mathcal{X^n} 。

Distribution Estimation 问题就是 给定样本 x^n \sim p(x^n) ，我们需要找到一个分布 q=q(x^n) ， q\in \Delta_k 。要求 q 在 ”某个度量“ 下 最接近 p 。

”某个度量“ 我们先考虑 Min-Max Criterion , 即 r_{k,n}^L = \min \limits_{q} \max \limits_{ p \in \Delta_k} E_{X^n \sim p} [L(p,q(X^n))] 。我们选取 q，使得对于任意 p ，最小化 Loss function L 的期望， r_{k,n}^L 就用来衡量 估计的准确度。其中 Loss function L 有多种选择：

\mathcal{l}^2_2: || p - q||_2^2 = \sum_{i}^k(p_i - q_i)^2 ，

\mathcal{l}_1: || p - q||_1 = \sum_{i}^k|p_i - q_i| ，

KL-Divergence ： D(p||q) 。

一个很自然的想法就是根据 频率 估计 分布 p ( Empirical Estimator ) ，给定样本 x^n ,我们计算 i\in \mathcal{X} 在 x^n 中出现的频数： T_i = |\{j\in [n]:x_j = i\}| ，则 q_i(x^n) = \frac{T_i}{n} 。显然， q_i(x^n) \geq 0 , \sum_i q_i(x^n) = 1 。我们知道 E[T_i] = np_i , Var(T_i) = E(T_i - np_i)^2 = np_i(1 - p_i) 。

但是 在某些 Loss function 下 ，这并不是最优的估计。

对于 Loss function \mathcal{l}^2_2 ， r_{k.n}^{q^{emp}}= E[\sum_{i=1}^k (\frac{T_i}{n} - p_i)^2] = \sum_{i=1}^k \frac{Var(T_i)}{n^2} = \sum_{i=1}^k \frac{p_i(1 - p_i)}{n} = \sum_{i=1}^k \frac{1 - \sum_{i=1}^kp_i}{n} \leq \frac{1 - \frac{1}{k}}{n} 。

即：在 Min-Max Criterion 和 Loss function为 \mathcal{l}^2_2下，我们用 n 个独立同分布的样本利用频率（Empirical Estimator ）去估计分布 p，要求期望的估计误差小于 \epsilon下，我们的样本数目 n \approx \Theta(\frac{1 - \frac{1}{k}}{\epsilon}) 。

但是 在 Loss function \mathcal{l}^2_2 下，如果 我们采用 在 频率的基础上 Add constant 的方法，可以得到更优甚至最优的估计。 考虑 q_i^{+ \sqrt{n} / k}(x^n) = \frac{T_i+ \sqrt{n}/k}{n + \sqrt{n}} 。即将 每个 i \in \mathcal{X} 的频数 加上一个常数 \sqrt{n}/k 。我们可以证明 : r_{k.n}^{q^{+\sqrt{n}/k}}= E[\sum_{i=1}^k (\frac{T_i+ \sqrt{n}/k}{n + \sqrt{n}} - p_i)^2] = \frac{1 - \frac{1}{k}}{(\sqrt{n}+ 1)^2}。

并且这是最优的。我们可以证明 r_{k,n} = \min \limits_{q} \max \limits_{ p \in \Delta_k} E_{X^n \sim p} [\sum_{i=1}^k (p_i - q_i(x^n))^2 ] \geq \frac{1 - \frac{1}{k}}{(\sqrt{n}+ 1)^2} 。

对于 Loss function \mathcal{l}_1 ，Empirical Estimator 则是最优的： r_{k,n} = \min \limits_{q} \max \limits_{ p \in \Delta_k} E_{X^n \sim p} [\sum_{i=1}^k |p_i - q_i(x^n)| ] ,15 年的时候，[KOPS15] 证明了：

其中 当 采用 Empirical Estimator 估计时，
r_{k.n}^{q^{emp}}= E[\sum_{i=1}^k |\frac{T_i}{n} - p_i|] = \sum_{i=1}^k \sqrt{E[ |\frac{T_i}{n} - p_i|^2]} \leq \sqrt{\frac{k-1}{n}} 。可以达到下界。

于是，我们有 以 Loss function 为 \mathcal{l}_1 距离下 去 通过 Empirical Estimator 估计 p ，在估计的期望误差小于 \epsilon 情况下，我们需要 n = \Theta(\frac{k -1 }{\epsilon^2}) 个样本。

对于 Loss function KL-Divergence，同样采用 在 频率的基础上 Add constant 的方法，可以证明 当 n \rightarrow \infty 则 \frac{k}{n} \rightarrow 0 时， q^{+\frac{3}{4}} 是最优的[BS04]。当 n \rightarrow \infty 则 \frac{k}{n} \rightarrow 0 时 ， q^{+{log \frac{n}{k}}} 是最优的 [Paninski 04]。

在 Min-Max Criterion下， 我们对于给定分布 p ，在 Loss function 标准下得到最优的 Estimator。但是 我们可以发现 对于 不同的分布 p 和 Loss function，我们的估计并不是那么稳定。并且，上述 Add constant 的方法的最坏情况分布是在实际中很少遇到的均匀分布，因此 Add constant 的方法 在实际中的性能很差。实际中，通常会使用其他估计器，如 absolute-discounting，cross-validation based estimators ， Good-Turing estimator 。

虽然 Good-Turing based estimators 广泛应用于实践中，但是理论最近才得到解释。

\Delta_k 为所有可能分布的集合。用 P 将 \Delta_k = \cup_jP_j 做 partition。我们改用 Competitive distribution estimation ：

r^P_{n,k} = \min \limits_{q} \max \limits_{j}[\max \limits_{p\in P_j} L(p,q) - \min \limits_{q'}\max \limits_{p'\in P_j} L(p',q')]

即 对于每个 区域 P_j 的最优估计 q' ，我们优化 q 使得与所有 q' 的最大距离最小。

其他的，有空再写吧。

待填的坑有：

1）Competitive distribution estimation

2) Property Estimation

3) 分布式 Property Estimation

4）Property Testing