离散分布近似的精度

摘要

本文是一个贡献的问题，估计偏差的两个离散概率分布之间的母函数在区间上的最大距离．偏差可以通过差值来测量第Th项或总变差距离。我们的新边界比之前证明的有更好的数量级，在某些情况下甚至很尖锐。

1.介绍

处理随机组合结构需要估计两个离散概率分布的偏差，它们的生成函数之间的最大距离．当给定几个不一定独立的随机事件时，通常会出现这种情况，我们需要估计这个数字发生的事情。在许多常用的泊松逼近方法中，具有广义Bonferroni界的筛方法，如图筛[1，就在手边。它们不仅提供了所有事件都不发生的概率的估计，而且还提供了生成函数之间的差值以及相应的泊松分布在区间上的分布(见[2)。这就引出了以下问题。

让和为带有母函数的离散概率分布和,分别。鉴于，估计距离的第Th项，或者说总变化距离和定义为．

其难点在于约束条件，即母函数的差值仅在实区间内可用，而不是整个复杂的单位圆盘，这将使应用特征函数的标准方法成为可能。

在过去30年里取得了一些积极和消极的成果，首先是[3.];参见2．上下估计越来越接近，但最终答案仍在前方。本说明的目的是提供比以前证明的有更好数量级的新界限。在某些情况下，它们甚至很锋利。

论文组织如下。节2我们介绍了必要的概念和符号，并引用了一些早期的结果。部分3.致力于案例的是哪里估计是在Section中4对总变异距离进行了处理。

2.预赛

两个概率母函数之差属于以下一类。让表示所有函数的集合这样 另一方面，每一个可得为两个概率母函数之差，即,在那里和可以按照以下方式构造。让(注意,为),这样 在哪里，．然后设置 为让,．为和定义

在[2结果表明，对于每一个， 适用于适当的正常数,如果是足够小。事实上，最高估计对每一个都是有效的，但它变得微不足道通过初等微积分。尽管在上界和下界的乘数是缓慢变化的在美国，它们的数量级是不同的。

这是很容易看到的不能以非平凡的方式估计，因为为任意存在一个函数,这样和,最大。事实上,让和 然后为,因为 通过选择,只要．为这个估计显然是成立的。因此．

然而,如果，和其中一个分布，是固定的(如泊松近似)，则可行函数类较小;因此可以减小，甚至可以不平凡地估计出总变异距离。以下结果可于[2]．

让是一个固定的离散概率分布对于每一个,

让是一个正整数一个足够小的正常数。对于每一个足够小的正数存在离散概率分布,这样,

如果尾部小于指数，则估计越低越低。

而不是(8),假设 是正的和有限的，在哪里是一个正的、连续的、递增的函数，在无穷远处有规律地变化，并且．让是一个正整数一个足够小的正常数。对于每一个足够小的正数存在离散概率分布,这样,

特别是,当泊松分布有参数吗，对于每一个足够小的正数存在离散概率分布,这样, (常数不依赖于和．的参数只出现在短语“足够小”中隐含的界限中。)

让我们转向完全变化的情况。在[2每个固定的一个递增函数是这样构造的和对于任意的．但是，除了尾巴的情况是极轻，功能呢被证明是慢慢变化的这总比什么都没有强。例如，在泊桑解的例子中，得到如下不等式: 作为以这样的方式变化．

自，每一个较低的估计得到的固定对总变异量是有效的。然而,如果不以指数形式递减，即条件(8)，则有较低的估计形式 用一个指数根据．

当尾部比指数轻，即条件(10)，然后对于每一个足够小的积极以下较低的估计是有效的。 与一个常数根据．特别是在这种情况下是泊松, 是证明。

3.的差异的估计th条款

下面的重要结果可以追溯到1892年的马尔科夫[4他研究了切比雪夫多项式在区间上的极值性质；见[5]．证据可在[6或在[7]．

定理1。让是一个小于或等于次的多项式,．然后

利用这一结果，可以不受任何限制地证明一个上界，其顺序与(5）

定理2。让．然后

证明。第一个假设．让和．然后, 在这里；因此右边小于．由定理1然后,我们有 声称。
如果，则上界大于是微不足道的。的确，在这段时间里，是递减的，因此上界在．那么它的值是 右边等于为和为．走远来，右边乘以 我们在哪里用到了这个事实是增加的;因此它不小于．
最后，很容易看到这一点是减少，由此可得出第二个不等式。

如果满足(8),也就是说,不能以指数形式递减，则(9)意味着定理的估计2在数量级上是尖锐的。

定理3。让,在那里和是离散的概率分布。假设 在哪里是一个正的、连续的、严格递减的趋于零的函数。然后 对于每一个．

证明。让,并介绍 然后 因此 让,．让我们近似用拉格朗日插值多项式在均匀网格上．也就是说, 然后有0在区间内；因此，存在a这样 自在区间内是递增的吗，它等于我们有对所有．此外,；因此 由此可以得出这样的结论 为．应用定理1就像定理的证明一样2我们得到 如果．通过研究连续项的比率，我们可以很容易地看到这一点

备注4。让我们写以指数形式:,在那里是非负的，连续的，并逐渐趋于无穷大。然后．定理的估计3.比定理更好吗2在数量级上只如果分布尾巴轻于指数型;也就是说,．

备注5。如果离零和无穷都有界，那么这两个定理的上估计3.和(11)是适用的，而且它们的数量级相同。使用规律变化的函数的订单我们有作为．

注6。文献[6证明了具有相同数量级的不同常数的相似边界。然而，他们施加了类似于(10)按顺序排列，而不是在，这在概率应用中用处不大。另外，对于定理的估计2，在系数没有任何限制的情况下是正确的，他们需要序列的指数衰减．

注7。如果是线性的，也就是说，，它能容纳足够大的（将会做)，定理的上界3.更适合而不是定理2．(绑定显然是最好的。)

特别是,我们为具有均值的泊松分布．然后,对于,我们有 (见[8]);因此, 作为．此外,最终。我们把这个代回定理3.得到以下估计。

推论8。如果那么泊松是否均匀分布呢,一个 对于每一个,如果是足够小。

注意，这个上界的顺序与下界的顺序相同(12）.

4.总变异距离的估计

再次让,在那里和是离散的概率分布。正如我们所见，如果什么都不知道和，给出总变差距离的非平凡上界是不可能的 然而,当是固定的，情况就完全不同了。

定理9。让,在那里满足条件(23）.然后 在哪里．

右边趋向于作为只如果尾巴不太重;也就是说,．

证明方法将在续集中用不同的参数应用几次。因此，我们用一个单独的引理来表述它的本质，作为一个主不等式。

引理10。让，,为正数;．假设 然后

证明。让,然后．很明显, 我们已经假设过了 因此

定理的证明9．从定理3.，让我们应用引理10与，,．我们得到

特别是,我们为具有均值的泊松分布．正如我们在(35）， 我们把这个代入定理9．写作在的地方在指数中我们可以消去这一项，甚至乘数最终被吸收。因此，我们得到如下估计值。

推论11。让是泊松;然后,统一在,一个 如果是足够小。

这与下界(16)，比(13）.

如果尾部是次指数的，即，，则定理的估计3.是无用的:它趋向于无穷．然而，在主不等式中选择适当的参数，可以得到一个合理的上界:不是很尖锐，但至少不是平凡的。

定理12。假设．然后

证明。这次我们用定理2．让，,．然后引理10给了, 自，右边第一项可以用的正幂估计，而第二项的下降速度比的任何正幂都要慢,因为；因此，它最终将占据主导地位。

推论13。如果th的时刻是有限的,那么；因此

最后，让我们处理指数衰减尾的情况。让,．然后是总方差可以用的正幂来估计．这是由定理得出的9，但只是为了．下列定理对所有正数都成立．

定理14。假设,．然后

由于不尖锐，指数的具体形式没有什么意义;真正重要的是它是积极的，趋向于作为．注意,如果倾向于以指数速度，(14)提供了一个下界，该下界也是的正幂(源自[的定理2.42由此而来可用于exponent)。

证明。首先,假设．基于定理2,应用引理10与，,： 我们来处理右边的第一项 自，这就引出了 其次,让．现在我们应用定理3.．请注意,,并设置，,．然后我们就得到了 同样，第一项可以由第二项估计出来，因为 和．因此，这是必然的 为,如需要。

相互竞争的利益

作者声明本论文的发表不存在利益冲突。

致谢

本研究得到了匈牙利科学研究基金OTKA (no.)的资助。108615 K。定理证明的思想3.是由于Gábor Halász，作者感谢他的宝贵帮助。