10
$\begingroup$

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:

$$\mathbb{E}[X^k] = \mathbb{E}[Z^k] \text{ for } k = 1, \ldots, m.\tag{1}\label{1}$$

Here is a positive result, which is a simple consequence of convex analysis (Carathéodory's theorem): there exists $Z$ with at most $m+1$ atoms such that \eqref{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 \eqref{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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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/… $\endgroup$
    – Bill Bradley
    Commented Aug 9, 2015 at 21:16

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – gondolier
    Commented Apr 10, 2010 at 0:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Apr 10, 2010 at 3:44
  • $\begingroup$ 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? $\endgroup$
    – gondolier
    Commented Apr 16, 2010 at 17:58
  • $\begingroup$ Depends on what you mean by optimal. How exactly do you measure "the worst case error" size? $\endgroup$
    – fedja
    Commented Apr 16, 2010 at 19:17
  • $\begingroup$ 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}$. $\endgroup$
    – gondolier
    Commented Apr 17, 2010 at 8:43
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – fedja
    Commented Apr 10, 2010 at 3:49
  • $\begingroup$ 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. $\endgroup$
    – Mark Meckes
    Commented Apr 10, 2010 at 11:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .