# 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?

• It seems that I have been asking a closely related question, which suggests that $m$ atoms are sufficient to match (approximately) $2m$ moments: mathoverflow.net/questions/213275/… Aug 9, 2015 at 21:16

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. Apr 10, 2010 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. Apr 10, 2010 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? Apr 16, 2010 at 17:58
• Depends on what you mean by optimal. How exactly do you measure "the worst case error" size? Apr 16, 2010 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}$. Apr 17, 2010 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? Apr 10, 2010 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. Apr 10, 2010 at 11:23