Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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
1  
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.