# approximate a probability distribution by moment matching

Suppose we want to approximate a real-valued random variable $X$ by a discrete random variable $Z$ with finitely many atoms. Suppose all moments of $X$ is finite. We want to match the moments of $X$ up to the $m^{\rm th}$ order:

(1) $\mathbb{E}[X^k] = \mathbb{E}[Z^k]$ for $k = 1, \ldots m$.

Here is a positive result, which is a simple consequence of convex analysis (Caratheodory's theorem): there exists $Z$ with at most $m+1$ atoms such that (1) holds.

Here are my questions:
1) Is there a converse result about this? Say $X$ has an absolutely continuous distribution supported on $\mathbb{R}$ (e.g. Gaussian). When $m$ is large, given that $Z$ has only $m$ atoms, can we conclude that we cannot approximate all $2m$ moments of $X$ well, i.e., can we lower bound the error $\max_{1 \leq k \leq 2m}|\mathbb{E}[X^k] - \mathbb{E}[Z^k]|$? My intuition is the following: for a Gaussian $X$, $\mathbb{E}[X^k]$ grows like $k^{\frac{k}{2}}$ superexponentially. When we find a $Z$ who matches all moments of $X$ up to $m$, it cannot catch up with higher-order moments $X$; if $Z$ matches all moments from $m+1$ up to $2m$, then its low-order moments will be quite different from $X$.

2) Is there an efficient algorithm to compute the location and weights of the approximating discrete distribution? Does there exist a table to record these for approximating common distribution (e.g. Gaussian) for each fixed $m$? It could be very handy...

3) I heard from folklore that when (1) holds, the total variation distance between their distributions can be upper bounded by, say, $e^{-m}$ or $1/m!$. Of course, this won't be true for a discrete $Z$. But let's say $X$ and $Z$ both has smooth and bounded density on $\mathbb{R}$. Could this be true? Now two characteristic functions matches at $0$ up to $m^{\rm th}$ derivatives. They should be pretty close?

-

For (1) and (2) just forget about probability and recall everything you ever learned about orthogonal polynomials and the Gauss quadrature formulae.

3) is false as stated: there are plenty of Schwartz functions orthogonal to all polynomials, so you can have all moments coincide and still have a large distance (in any sense). Something like that may be true but I cannot think of any good formulation right away.

-
thanks fedja! I understand (2) now: just place the atoms at the roots of the $m^{\rm th}$-order orthogonal polynomial. For the converse in (1), can you elaborate a bit more please? I haven't been able to see how to lower bound the approximate error for any choice of locations and weights. –  mr.gondolier Apr 10 '10 at 0:04
Sure. If the nodes are $x_j$, integrate $\prod_j(x-x_j)^2$ which is a polynomial of degree $2m$. You get something strictly positive showing that the quadrature formula cannot hold exactly. You can also estimate the integral if you know the weight thus getting some lower bound. –  fedja Apr 10 '10 at 3:44
hi fedja, I recalled a theorem about Gauss quadrature states that placing the nodes at the roots of the orth. poly. $p_m$ approximates the integral of all poly. up to order $2m-1$ exactly but there exists poly. of order $2m$ (e.g. the one you gave, $p_m^2$) that cannot be. Therefore the error of approximating $x^{2m}$ is the same as approximating $p_m^2$. However, this gave the approximation error of one particular method. My original question is about the worst case error of approximating $x^i$ for $i=1,\ldots, 2m$ regardless of the node locations. Is it optimal to put the nodes at the roots? –  mr.gondolier Apr 16 '10 at 17:58
Depends on what you mean by optimal. How exactly do you measure "the worst case error" size? –  fedja Apr 16 '10 at 19:17
The error is measured either by $e_{2m} = \max_{k = 1, \ldots, 2m} |\mathbb{E}[X^k]-\mathbb{E}[Z^k]|$ (worst case) or $\sum_{k = 1}^{2m} |\mathbb{E}[X^k]-\mathbb{E}[Z^k]|^2$ (square error). Since I am only interested in the asymptotics when $m$ is large, these two do not differ much. If only $m$ nodes (in $Z$) are allowed, is it optimal to place them at the roots to minimize $e_{2m}$? Let's say $X$ is standard normal, then $\mathbb{E}[|X|^k]$ grows very fast like $k^{\frac{k}{2}}$. Moments of a discrete $Z$ cannot follow this growth. This is my intuition of lower bounding $e_{2m}$. –  mr.gondolier Apr 17 '10 at 8:43

In the context of 3), what I have heard from folklore is that when (1) holds, the Kolmogorov distance (not total variation) is bounded by something like $1/\sqrt{m}$. This bound follows if (1) holds only approximately, and exact equality in (1) suggests that a much stronger bound holds but does not formally imply it, even under the assumption of smooth bounded densities.

See the introduction of this paper, and observe that a lot more work is necessary to prove the main results.

-
Under exactly what conditions? I gave an example of two different probability distributions with densities in $S$ and exactly the same moments of all order. You need some fairly strong decay of tails to get any bound at all. Are you talking about compactly supported distributions? –  fedja Apr 10 '10 at 3:49
I'm just repeating rumor here; I haven't seen the exact statement. Clearly you at least need the distributions to be determined by their moments. I guess I assumed the OP was assuming that but I see now it was never stated. I don't think compact support is necessary since whatever result is true is applicable when one distribution is Gaussian. –  Mark Meckes Apr 10 '10 at 11:23