# Accuracy of Approximation for Discrete Distributions

Authors: Tamás F. Móri
Journal: Journal of Probability and Statistics
 (2016)

---

## Abstract

The paper is a contribution to the problem of estimating the deviation of two discrete probability distributions in terms of the supremum distance between their generating functions over the interval[0,1]. Deviation can be measured by the difference of the kth terms or by total variation distance. Our new bounds have better order of magnitude than those proved previously, and they are even sharp in certain cases.


---

## Body

## 1. Introduction

Dealing with random combinatorial structures needs to estimate the deviation of two discrete probability distributions in terms of the maximal distance between their generating functions over[0,1]. This is often the case when given a couple of not necessarily independent random events, one needs to estimate the number N of those that occur. Among many popular methods of Poisson approximation, sieve methods with generalized Bonferroni bounds, such as the graph sieve [1], are at hand. They provide estimates not only for the probability that none of the events occur, but also for the difference between the generating function of N and that of the corresponding Poisson distribution over the interval [0,1] (see [2] for more details). This raises the following problem.Letp=(p0,p1,…) and q=(q0,q1,…) be discrete probability distributions with generating functions gp(z) and gq(z), respectively. Given Δ=max0≤z≤1gp(z)-gq(z), estimate the distance |pk-qk| of kth terms, or the total variation distance between p and q defined as p-q=∑k=0∞‍|pk-qk|.The difficulty lies in the constraint that the difference of the generating functions is only available over the real interval[0,1], and not over the whole complex unit disc, which would make it possible to apply standard methods of characteristic functions.Several positive and negative results were achieved in the last three decades, beginning with [3]; see Section 2. Lower and upper estimates got closer and closer, but the final answer is still ahead. The aim of the present note is to provide new bounds that have better order of magnitude than those proved previously. They are even sharp in certain cases.The paper is organized as follows. In Section2 we introduce the necessary notions and notations and cite some earlier results. Section 3 is devoted to the case where |pk-qk| is estimated in terms of Δ, while in Section 4 the total variation distance is treated.


## 2. Preliminaries

The difference of two probability generating function belongs to the following class. LetF denote the set of all functions f:[0,1]→R such that(1)fz=∑k=0∞akzk,∑k=0∞ak≤2,f1=0.On the other hand, every f∈F can be obtained as the difference of two probability generating functions, namely, f(z)=g1(z)-g2(z), where g1 and g2 can be constructed in the following way. Let 0≤bk≤1-|ak|,k=0,1,… (note that |ak|≤1 for f∈F) such that(2)∑k=0∞bk=1-12∑k=0∞ak=1-∑k=0∞ak+=1-∑k=0∞ak-,where x+=max{x,0}, x-=(-ak)+. Then set(3)g1z=∑k=0∞ak++bkzk,g2z=∑k=0∞ak-+bkzk.For f∈F let Δ=Δf=max0≤z≤1fz, and L=log⁡(1/Δ). For d∈(0,1] and k=0,1,… define(4)φkd=sup⁡ak:f∈F,Δf=d.In [2] it was shown that, for every k=0,1,…,(5)CkΔL2k≤φkΔ≤Δexp⁡2kL4/5holds with a suitable positive constant Ck, if Δ is sufficiently small. In fact, the upper estimate is valid for every Δ∈(0,1], but it becomes trivial for Δ≥exp⁡(-32k4) by elementary calculus. Though in both the upper and lower bounds the multiplier of Δ is slowly varying as Δ→0, they are not of the same order of magnitude.It is easy to see that∑k=0∞‍|ak| cannot be estimated in a nontrivial way, because for arbitrary Δ∈(0,1] there exists a function f∈F, such that Δ(f)=Δ and ∑k=0∞‍|ak|=2, maximal. Indeed, let n>1/Δ and(6)fz=Δ-Δz+1-Δzn-1-Δzn+1=Δ-Δz+z1-Δzn-1-zn.Then 0≤f(z)≤Δ for z∈[0,1], because(7)zn-1-zn≤n-1nn-11n<1n-1<Δ1-Δby the choice of n, provided Δ<1. For Δ=1 the estimation obviously holds. Hence Δf=f0=Δ.However, iff=gp-gq, and one of the distributions, say p, is fixed (as in the case of Poisson approximation), then the class of feasible functions is smaller; thus the bounds for |ak| may decrease, and even the total variation distance can be estimated nontrivially. The following results can be found in [2].Letp be a fixed discrete probability distribution such that pk>0 for every k=0,1,…, and(8)lim⁡supk→∞⁡1klog⁡1pk<∞.Letk be a positive integer and C a sufficiently small positive constant. Then for every sufficiently small positive Δ there exists a discrete probability distribution q, such that Δgp-gq=Δ, and(9)pk-qk>CΔL2k.If the tail ofp is lighter than exponential, the lower estimate decreases.Instead of (8), suppose that(10)lim⁡supk→∞⁡1hklog⁡1pkis positive and finite, where h is a positive, continuous, and increasing function, regularly varying at infinity, and limk→∞h(k)/k=∞. Let k be a positive integer and C a sufficiently small positive constant. Then for every sufficiently small positive Δ there exists a discrete probability distribution q, such that Δ(gp-gq)=Δ, and(11)pk-qk>CΔh-1L2k.Particularly, whenp is the Poisson distribution with parameter λ, it follows that for every sufficiently small positive Δ there exists a discrete probability distribution q, such that Δgp-gq=Δ, and(12)pk-qk>CkΔLlog⁡L2k.(The constant Ck does not depend on λ and q. The parameter λ only appears in the bounds implicit in the phrase “sufficiently small.”)Let us turn to the case of total variation. In [2] for every fixed p an increasing function ψ:[0,1]→R was constructed in such a way that limt→0ψ(t)=0 and p-q≤ψΔ for arbitrary q. However, apart from the case where the tail of p was extremely light, the function ψ proved to be slowly varying at 0, which is just a little bit better than nothing. For example, in the case of Poissonian p, the following inequality was obtained:(13)p-q=oexp⁡-L1/4,as q varies in such a way that Δ→0.Sincep-q≥|pk-qk|, every lower estimate obtained for fixed k will do for the total variation. However, if pk does not decrease faster than exponential, that is, condition (8) is fulfilled, there is a lower estimate of the form(14)p-q≥ΔCwith an exponent C∈0,1 depending on p.When the tail ofp is lighter than exponential, namely, condition (10) holds, then for every sufficiently small positive Δ the following lower estimate is valid.(15)p-q≥Δexp⁡Ch-1L,with a constant C depending on p. Particularly, in the case where p is Poisson,(16)p-q>Δexp⁡1.76Llog⁡Lwas proved.


## 3. Estimation for the Difference ofkth Terms

The following important result can be traced back to Markoff, 1892 [4], who dealt with the extremal properties of Chebyshev polynomials over the interval [-1,1]; see Chapter 2 of [5]. The proof can be found in [6] or in [7].Theorem 1.
Letf be a polynomial of degree less than or equal to n, and 0≤k≤n. Then(17)ak≤2n2k2k!Δ.Using this result an upper bound can be proved without any restriction onf, which is of the same order as the lower bound in the left-hand side of (5)Theorem 2.
Let0≤k≤2L. Then(18)ak≤e2k+12k!ΔL2k≤e32ΔL2k.Proof.
Suppose first thatΔ≤e-2k. Let c=e-2 and n=⌊L/2⌋. Then n≥k, and(19)max0≤y≤1⁡∑j=0najcjyj=max0≤t≤c⁡∑j=0najtj≤max0≤t≤1⁡∑j=0∞ajtj+max0≤t≤c⁡∑j=n+1∞ajtj≤Δ+∑j=n+1∞cj=Δ+11-ce-2n+1.
Heree-2(n+1)<e-L=Δ; therefore the right-hand side is less than eΔ. By Theorem 1 we then have(20)akck≤2n2k2k!eΔ≤e2k!ΔL2k,as claimed.
Ife-2k<Δ≤e-k/2, then the upper bound, being greater than 1, is trivial. Indeed, in that interval, ΔL2k is decreasing, hence the upper bound attains its minimum at Δ=e-k/2. Then its value is(21)e2k+12k!ΔL2k=12k!k22ke1+3k/2.Here the right-hand side is equal to e for k=0 and to (1/8)e5/2>1 for k=1. Stepping further from k to k+1, the right-hand side gets multiplied by(22)12k+12k+2·k+12k+1k2k·e3/24>k+1k2ke3/216>e3/24>1,where we used the fact that (k+1/k)k is increasing; hence it is not less than 2.
Finally, it is easy to see thate2k+1/2k! is decreasing for k≥1, from which the second inequality follows.Ifp satisfies (8), that is, pk cannot decrease faster than exponential, then (9) implies that the estimate of Theorem 2 is sharp in the order of magnitude.Theorem 3.
Letak=pi-qk, where p=pkk≥0 and q=qkk≥0 are discrete probability distributions. Suppose that(23)∑k=n∞pk≤Fn,where F is a positive, continuous, and strictly decreasing function tending to zero. Then(24)pk-qk≤38e+4k2k!ΔF-1Δ2k≤22e+12ΔF-1Δ2kfor every k<F-1Δ.Proof.
Letn=⌈F-1(Δ)⌉, and introduce(25)fz=∑k=0∞qk-pkzk,gz=∑k=0∞qkzk-∑k=0n-1qkzk,hz=∑k=0∞qkzk,0≤z≤1.Then(26)fz-gz≤∑k=n∞pk≤Fn≤Δ.Hence(27)sup0≤z≤1⁡gz≤2Δ.
Letc=2e/2e+1, and zi=1-c+ci/n,i=0,…,n. Let us approximate gz with its Lagrange interpolation polynomial pnz over the uniform grid zi:0≤i≤n. That is,(28)pnz=∑i=0ngzi∏j≠inz-zjzi-zj.Then gz-pnz has n+1 zeros in the interval 1-c;1; hence, there exists a ξ∈[1-c;1] such that(29)gnξ=pnnξ=∑i=0ngzinincn-1n-i≤2Δ2ncn<Δ2ecnn!=Δ1-c-nn!.
Sinceh(n) is increasing in the interval [0;1], and it is equal to gn, we have that 0≤hnz≤Δ1-c-nn! for all z∈[0;1-c]. Moreover, h(0)=h′(0)=⋯=h(n-1)(0)=0; thus(30)0≤hz≤Δz1-cn,0≤z≤1-c.From all these it follows that(31)∑k=0n-1pk-qkzk≤3Δfor 0≤z≤1-c. Applying Theorem 1 in the same way as in the proof of Theorem 2 we get that(32)pk-qk≤3Δ1-ck2n-12k2k!≤38e+4k2k!ΔF-1Δ2k,if k<F-1(Δ). Investigating the ratio of consecutive terms one can easily see that(33)38e+4k2k!≤38e+424!=22e+12.Remark 4.
Let us writeF in exponential form: F(n)=e-h(n), where h is nonnegative, continuous, and tends increasingly to infinity. Then F-1(Δ)=h-1(L). The estimate of Theorem 3 is better than that of Theorem 2 in the order of magnitude only if the distribution p has a tail lighter than exponential; that is, h(n)/n→∞.Remark 5.
If1/h(k)log⁡1/pk is bounded away from zero and infinity as well, then both the upper estimate of Theorem 3 and the lower estimate of (11) are applicable and they are of the same order of magnitude. Use the fact that for regularly varying functions h of order α>0 we have ch-1(z)~c-1/αh-1(z) as z→∞.Remark 6.
Reference [6] proved similar bounds with different constants, but of the same order of magnitude. However, they imposed conditions similar to (10) on the sequence ak=pk-qk, rather than on p, which is less useful for applications in probability. Besides, for the estimate of Theorem 2, which is true without any restriction on the coefficients, they needed exponential decay of the sequence (ak).Remark 7.
Ifh is linear, that is, ∑k≥npk≤e-vn, and it holds with a sufficiently large v (v≥2 will do), the upper bound of Theorem 3 is better for k>0 than that of Theorem 2. (For k=0 the bound p0-q0≤Δ is obviously the best possible.)Particularly, letp be the Poisson distribution with mean λ. Then, for n>λ, we have(34)∑k=n∞pk≤e-λλenn(see Theorem A.15 in [8]); hence hx=xlog⁡x+O(x), and(35)h-1x=xlog⁡x-log⁡log⁡x+O1~xlog⁡xas x→∞. In addition, h-1(x)>x/log⁡x eventually. Let us plug this back into Theorem 3 to get the following estimate.Corollary 8.
Ifp is Poisson, then, uniformly in q, one has(36)pk-qk≤48e+4k2k!ΔLlog⁡L2kfor every k<L/log⁡L, if Δ is sufficiently small.Note that the order of this upper bound is the same as that of the lower bound (12).


## 4. Estimation for the Total Variation Distance

Let againak=pk-qk, where p=(pk)k≥0 and q=(qk)k≥0 are discrete probability distributions. As we have seen, if nothing is known about p and q, it is impossible to give a nontrivial upper bound for the total variation distance(37)p-q=∑k=0∞pk-qk.However, when p is fixed, the situation is completely different.Theorem 9.
Letak=pk-qk, where p=pk satisfies condition (23). Then(38)p-q<8Δexp⁡κF-1Δ,where κ=2+log⁡(2e+1)=3.861⋯.The right-hand side tends to0 as Δ→0 only if the tail of p is not too heavy; namely, F(x)=o(e-κx).The method of proof will be applied a couple of times in the sequel with different parameters. Therefore we formulate its essence in a separate lemma as a master inequality.Lemma 10.
LetA, B, and C be positive real numbers; C≤B. Suppose(39)pk-qk≤A2B2k2k!,0≤k<C.Then(40)p-q≤2AeBC2C+2FC.Proof.
Letn=⌈C⌉, then n-1<C≤n. Clearly,(41)p-q=∑k=0∞pk-qk=2∑k=0∞pk-qk++∑k=0∞pk-qk=2∑k=0∞pk-qk+≤2∑k=0n-1pk-qk+2∑k=n∞pk.By supposition we have(42)2B2k=2C2kBC2k≤2C2kBC2C.Hence(43)p-q≤2A∑k=0n-12Bk2k!+2Fn≤2ABC2C∑k=0n-12C2k2k!+2Fn≤2AeBC2C+2FC.Proof of Theorem9.
Starting from Theorem3, let us apply Lemma 10 with A=3Δ, B=(2e+1)1/2F-1(Δ), and C=F-1(Δ). We get that (44)p-q≤6Δe2e+11/22F-1Δ+2Δ≤8Δexp⁡κF-1Δ.Particularly, letp be the Poisson distribution with mean λ. As we have seen in (35),(45)F-1Δ=h-1L=1+o1Llog⁡L.Let us plug this into Theorem 9. Writing 4 in place of κ in the exponent we can get rid of the term 1+o(1), and even the multiplier 8 gets eventually absorbed. Thus we obtain the following estimate.Corollary 11.
Letp be Poisson; then, uniformly in q, one has(46)p-q≤Δexp⁡4Llog⁡L,if Δ is sufficiently small.This is already similar to the lower bound (16), and is much better than (13).If the tail ofp is subexponential, that is, ∑k≥n‍pk=exp(-o(n)), then the estimate of Theorem 3 is useless: it tends to infinity as Δ→0. However, with suitably chosen parameters in the master inequality, a reasonable upper bound can be obtained: not really sharp, but at least not trivial.Theorem 12.
SupposeF(n)=e-o(n). Then(47)supp-q:max0≤z≤1gpz-gqz=Δ=OFL8,asΔ⟶0.Proof.
This time we use Theorem2. Let A=eΔ, B=eL/2, and C=L/8. Then Lemma 10 gives that(48)p-q≤2eΔ4e2L/4+2FL8.Since (4e2)1/4=2.331⋯<e, the first term in the right-hand side can be estimated by a positive power of Δ, while the second term decreases slower than any positive power of Δ, as Δ→0; thus it will eventually dominate.Corollary 13.
If theαth moment of p is finite, then ∑k=n∞‍pk=on-α; thus(49)supp-q:max0≤z≤1gpz-gqz=Δ=oL-α,asΔ⟶0.Finally, let us deal with the case of exponentially decaying tails. LetF(n)=e-vn, with v≥0. Then the total variation p-q can be estimated by a positive power of Δ. This follows from Theorem 9, but only for v>κ. The following theorem is valid for all positive v.Theorem 14.
SupposeF(n)≤e-vn, with v>0. Then(50)p-q≤8Δv/v+7.As not sharp, the concrete form of the exponent holds no interest; what really matters is that it is positive and tends to1 as v→∞. Note that if pk tends to 0 at an exponential rate, (14) provides a lower bound which is also a positive power of Δ (from Theorem  2.4 of [2] it follows that C=(v+1/4)/(v+2) can be used for exponent).Proof.
Firstly, supposev≤1.9. Based on Theorem 2, apply Lemma 10 with A=eΔ, B=eL/2, and C=L/(v+7):(51)p-q≤2eΔe2v+722L/v+7+2exp⁡-vLv+7.Let us deal with the first term on the right-hand side(52)Δe2v+722L/v+7=exp⁡-L1-2v+72+log⁡v+72=exp⁡-Lv+7v+3-2log⁡v+72.Since 3-2log⁡v+7/2≥3-2log⁡4.45>0, it follows that(53)p-q≤2e+1Δv/v+7.
Secondly, letv>1.9. Now we apply Theorem 3. Note that F-1(Δ)=L/v, and set A=3Δ, B=(2e+1)1/2L/v, and C=L/(v+7). Then we obtain that(54)p-q≤6Δe2e+11/2v+7v2L/v+7+2exp⁡-vLv+7.Again, the first term can be estimated by the second one, because(55)Δe2e+11/2v+7v2L/v+7=exp⁡-L1-2v+7κ2+log⁡v+7v=exp⁡-Lv+7v+7-κ-2log⁡v+7v,and 7-κ-2log⁡v+7/v>7-3.862-2log⁡4.685>0. Thus, it follows that(56)p-q≤8Δv/v+7for v>1.9, as needed.



---

*Source: 6212567-2016-11-08.xml*