Discrete Stein characterizations and discrete information distances

Foreword and notations

The purpose of this work is to construct an explicit connection between discrete Stein characterizations and discrete information functionals (see where similar considerations are discussed for continuous distributions). In doing so we also provide two general Stein characterizations of discrete distributions, as well as a family of identities relating differences between expectations with what we call generalized score functions. In the context of Poisson approximation, our results allow in particular to construct bounds between the total variation distance and (i) the so-called scaled Fisher information used, e.g., in , as well as (ii) the discrete Fisher information used, e.g., in . We refer the reader to and for relevant references and similar inequalities.

First connection

We start with a discrete version of the so-called density approach (see for a description in the continuous case).

Let $Z\sim p$ and let $X$ be a real-valued discrete random variable.

If $X\stackrel{{\scriptstyle\mathcal{L}}}{{=}}Z$ then ${\rm E}\left[\mathcal{T}_{1}(f,p)(X)\right]=0$ for all $f\in\mathcal{F}_{1}(p)$.

If ${\rm E}[\mathcal{T}_{1}(f,p)(X)]=0$ for all $f\in\mathcal{F}_{1}(p)$, then $X\,|\,X\in S_{p}\stackrel{{\scriptstyle\mathcal{L}}}{{=}}Z$.

We draw the reader’s attention to the similarity between the operator $\mathcal{T}_{1}$ and the operators introduced in : in the terminology of , our operator (2.1) allows for a discrete “location”-based parametric interpretation.

Consequently, we can use ${\rm E}\left[\mathcal{T}_{1}(f_{z}^{p},p)(X)\right]=0$ to obtain

Note that the choice of a “connected” support is for convenience only, and straightforward arguments allow to adapt the result to supports of the form $[a,b]\cup[c,d]$ with $c>b$. Likewise the use of a forward difference in the expression of the operator is purely arbitrary and minor adaptations (e.g., setting $f(b)=0$ instead of $f(a)=0$) allow to reformulate (2.1) in terms of backward differences as well.

It is perhaps informative to see how the operator $\mathcal{T}_{1}(f,p)$ spells out in certain specific examples.

Take $p$ to be a member of Ord’s family, i.e. suppose that there exist $s(x)$ and $\tau(x)$ such that

For an explanation on these notations see . The collection $\mathcal{F}_{1}((s,\tau))$ contains the set of all functions of the form $f(x)=f_{0}(x)s(x)$ with $f_{0}$ bounded and, for these $f$, the operator writes out

We retrieve, up to some minor modifications, the operator presented in ; using the backward difference operator and functions $f$ of the form $f_{0}(x)(s(x)+\tau(x))$ yields exactly the operator proposed in that paper.

which corresponds to the Stein operator presented in .

Now recall the product rule for discrete derivatives

Applying this and keeping in mind that we have set $S_{q}\subset S_{p}$, the first term on the rhs of (2.2) becomes

we have just shown that, for all $f\in\mathcal{F}_{1}(p)\cap\mathcal{F}_{1}(q)$, we have the factorization property

The statements above (and their consequences) are easily adapted to situations where $S_{p}\subset S_{q}$; having in mind the context of a Poisson target $p$ explains our willingness to restrict our choice.

is solution of the so-called Stein equation $\mathcal{T}_{1}(f,p)(x)=l(x)-{\rm E}_{p}[l(X)]$, so that, taking expectations and using (2.4), we get

with $e^{N}_{p,q}(l):=q(N)f_{1,l}^{p}(N+1)p(N+1)/p(N).$

We will apply (2.6) in the context of a Poisson target distribution in Section 4. In particular we will show how our approach provides a connection between the so-called total variation distance (as well as many other probability distances) and the scaled Fisher information in use for information theoretic approaches to Poisson approximation problems (see ).

A second connection

The construction from the previous section (i.e. the factorization (2.4), the score function (2.3) and the identity (2.6)) is by no means unique, nor is the initial characterization from Theorem 2.1. There are, in fact, an infinite number of variations on the different steps outlined above, each providing a connection between probability distances and different forms of information distances. Now it appears that, in the world of Poisson approximation, the scaled Fisher information is not the only “natural” measure of discrepancy and (followed later by ) make use of another information distance which they call the discrete Fisher information. We choose to show how this specific distance can be obtained from our Stein characterizations as well.

Let $Z\sim p$ and let $X$ be a real-valued discrete random variable.

If $X\stackrel{{\scriptstyle\mathcal{L}}}{{=}}Z$ then ${\rm E}\left[\mathcal{T}_{2}(f,p)(X)\right]=0$ for all $f\in\mathcal{F}_{2}(p)$.

If ${\rm E}[\mathcal{T}_{2}(f,p)(X)]=0$ for all $f\in\mathcal{F}_{2}(p)$, then $X\,|\,X\in S_{p}\stackrel{{\scriptstyle\mathcal{L}}}{{=}}Z$.

Theorem 3.1 allows to recover the well-known Stein operators and characterizations of the Poisson, geometric, binomial distributions, to cite but these; we refer the reader to for intuition about the perhaps unusual form of the operator, as well as for explicit computations and examples.

Proceeding as in Section 2 (and keeping all supports implicit) we readily obtain

Straightforward simplifications then yield for $f\in\mathcal{F}_{2}(p)\cap\mathcal{F}_{2}(q)$ the factorization

Then clearly $\mathcal{T}_{2}(f_{2,l}^{p},p)(x)=l(x)-{\rm E}_{p}[l(X)]$ so that, taking expectations on both sides of (3.1) for this choice of test function, we obtain

As will be shown in Section 4, specifying a Poisson distribution for the target $p$ in (3.4) yields the scaled score function whose variance is the so-called discrete Fisher information introduced in .

Applications to a Poisson target

Working as in it is easy to obtain, from (2.6) and (3.4), inequalities of the form

where $\mathcal{H}$ is, as usual, a suitably chosen class of functions, $\kappa(p,q)$ are constants depending on both $p$ and $q$ and $\mathcal{J}(p,q)$ is a so-called information distance between $p$ and $q$, which is given by the variance of one of the score functions (2.3) or (3.2) introduced in the two previous sections. The main difficulty then resides in computing the constants appearing in these inequalities and in putting the information distance $\mathcal{J}$ to good use. Such computations are not the primary purpose of the present paper. Hence we choose to focus on a Poisson target, for which much is already known. From here onwards we therefore only consider $p=Po(\lambda)$, the mean-$\lambda$ Poisson density.

We first adapt the results from Section 2. The score function (2.3) becomes

One recognizes, in the rhs of (4.1), the scaled score function whose variance yields the scaled Fisher information

This information distance is subadditive over convolutions; this is useful when computing rates of convergence for sums towards the Poisson distribution (see, e.g., ). Using a Poincaré inequality, show that, for $q$ a discrete distribution with mean $\lambda$,

with $\|\cdot\|_{TV}$ indicating the total variation distance. From (4.1) and Hölder’s inequality we obviously recover a much more general result, namely

is some kind of general Stein (magic) factor. The notation $H$ for these constants is borrowed from where similar relationships are obtained, within the context of compound Poisson approximation.

One recognizes, in the rhs of (4.3), a special instance of the Katti-Panjer score function introduced in [1, equation (3.1)] and whose variance yields our second information distance, namely the discrete Fisher information

This is easily shown to be related to the discrete Fisher information distance $I(q):={\rm E}_{q}[({q(X-1)}/{q(X)}-1)^{2}]$ introduced in . The information distance (4.4) has been shown to be subadditive over convolutions (see ). From (4.3) and Hölder’s identity we obviously recover the following general relationship

is, again, some kind of general Stein (magic) factor.

We conclude the paper with explicit computations.

Take $p=Po(\lambda)$ and $q$ a pdf with support $[0,\ldots,N]$. Then

where the error term $e^{N}_{q}$ is of order $q(N)/(N+1)$ and $H(\lambda)=1\wedge\sqrt{\frac{2}{e{\lambda}}}$. The second bound in (4.6) only holds if $N=\infty$.

Then obviously ${\rm E}_{p}[h(X)]$ and ${\rm E}_{q}[h(X)]$ exist, and

so that, by definition of the total variation distance, we get

It now suffices to apply (4) and (4), respectively, to obtain the announced relationships. All that remains is to compute bounds on the constants.

In the first case, known results on the properties of ${f}_{1,h}^{p}$ show that the claim on the error term is evident. The expression for the constant $\sqrt{\lambda}H(\lambda)$ is derived from the quantity

with $h$ specified (and bounded by 2). Indeed, from (2.5) and [5, Theorem 2.3], we get

The constant $H(\lambda)$ in the second case is derived from

Actually, from (3.3) and [5, Theorem 2.3] we get

For $\lambda<2/e$, $H(\lambda)=1$ and hence the bounding constant for the scaled Fisher information $\mathcal{K}_{1}(Po(\lambda),q)$ becomes $\sqrt{\lambda}<\sqrt{2/e}$; in case $\lambda>2/e$, this constant equals $\sqrt{2/e}$. Since the error term $e^{N}_{q}$ is either null for $N=\infty$ or negligible in comparison to the term involving the scaled Fisher information, our bounds on the total variation distance corresponding to the first inequality in (4.6) improve on those proposed in , where the bounding constant is given by $\sqrt{2}$, while ours are inferior to $\sqrt{2/e}$. For the sake of illustration we conclude this section by applying Proposition 4.1 to the three examples studied in .

Take $X_{i}$ i.i.d. Bernoulli $(\lambda/n)$ random variables and let $S_{n}=\sum_{i=1}^{n}X_{i}$. Put $q=P_{S_{n}}$, the density associated with the sum $S_{n}$. Then straightforward calculations reveal that $\mathcal{K}_{1}(Po(\lambda),q)=\lambda^{2}/(n(n-\lambda))$ and $e^{n}_{q}$ is of order $\lambda^{n}/n^{n+1}$. Consequently, we have

for some positive constant $c$ and sufficiently large $n$. This is an improvement over the $(2+\epsilon)\lambda/n,\epsilon>0,$ bound obtained in .

Consider the same situation as above, but with $\lambda$ replaced by $\mu\sqrt{n}$ for some $\mu>0$. From the previous example, we directly deduce that

for some positive constant $c$ and sufficiently large $n$. Although the rate is good and the constant above is again an improvement over the one obtained in , it is still not as good as the optimal constant $\sqrt{1/(2\pi e)}$ derived in .

where $P_{X_{i}}$ is the density associated with $X_{i}$ and $e_{i}={\rm E}[X_{i}]$. Straightforward computations show that $\mathcal{K}_{1}(Po(e_{i}),P_{X_{i}})=(1-q_{i})^{2}/q_{i}$. Since here $e^{\infty}_{q}=0$, it follows that

for sufficiently large $n$. Again we improve on the constant obtained in . Note that restricting, as in , to the case where $q_{i}=n/(n+\lambda)$ yields a rate of $\sqrt{2/e}(\lambda/\sqrt{n(n+\lambda)})$.

Next consider the second information functional $\mathcal{K}_{2}$. Direct computations yield an expression for $\mathcal{K}_{2}(Po(\lambda),P_{S_{n}})$ which we will dispense of here, and hence an explicit bound on $\|P_{S_{n}}-Po(\lambda)\|_{TV}$ can also easily be obtained in terms of this functional as well. The general expression appears inscrutable, and hence we restricted our attention to the case where $q_{i}=n/(n+\lambda)$. There, numerical evaluations in Mathematica 7 encourage us to suggest that the second information distance provides a better rate than the $\sqrt{2/e}(\lambda/\sqrt{n(n+\lambda)})$ mentioned above, at least for moderate values of $\lambda$ and large values of $n$ (that is, $n\geq 100)$.

Final comments

The results reported in the present work are to be read in conjunction with those reported in . The main message of these two papers is that all the so-called Fisher information functionals used in the literature on Gaussian and Poisson approximation bear an interpretation in terms of a specific Stein characterization. As concluding remark to the present paper we wish to stress the fact that our method applies to many more distributions than just the Gaussian or the Poisson (e.g., the compound Poisson, allowing comparisons with the results of ), and in particular provides generalized scaled Fisher information distances between any two (nice) distributions. Of course much remains to be explored, in particular on the properties of these generalized information functionals. However the freedom of choice for the densities as well as for the test functions in (2.6), (3.4) and [10, Theorem 2.3] makes us confident that there remains much to be gained from a crafty usage of such identities.

References