12
$\begingroup$

Simple question, but one to which I could not find the exact answer elsewhere. How many moments of a discrete probability distribution with finite support are required to uniquely identify the exact probability mass function? Suppose we know that the distribution has support on at most $N$ points within a bounded interval (for my purposes the interval is $[0, 1]$), but we do not know the points.

Is it the case that the distribution is uniquely identified by some number of moments? My hypothesis is that it may be the first $2N-1$ moments. Since we have to identify $N$ mass points and their $N$ individual probabilities, one might think we need $2N$ equations and each moment gives us one equation, plus the restriction that the probabilities sum to $1$. But these equations are not linear in the mass points, so it's not immediately obvious to me that we're identified.

I am aware of the Hausdorff Moment Problem, so I know that an infinite sequence of moments uniquely identifies any bounded distribution, but I am particularly interested in further restricting the domain to distributions with finite support. Any references would also be appreciated!

Thanks!

$\endgroup$
5
  • $\begingroup$ If the points of the support set are evenly spaced, I can prove that you only need to know the first $N+1$ moments. This is because the moment generating function will then be a $N$th degree polynomial of $e^t$ in this case, and any polynomial of degree $n$ is uniquely determined if you know the first $n+1$ derivatives at a point, which of course is just what the moments are. I don't see an obvious way to prove this for the more general case where points of support are not evenly spaced. I suspect you need to know the full infinite sequence of moments. $\endgroup$
    – olooney
    Commented Jul 5, 2019 at 17:30
  • $\begingroup$ In the non-evenly spaced case, do you have a simple example where you can't determine the mass points and their weights with $2N + 1$ moments? Or an intuition for why you think one would need the full infinite sequence? $\endgroup$ Commented Jul 5, 2019 at 17:49
  • $\begingroup$ A counter example would be very hard to produce; at a minimum it would require at least three points of support, not all with rational ratios. The set $\{0, \frac{1}{3}, 1\}$ cannot provide a counter example, because this is also a polynomial in $e^{t/3}$. A set like $\{ 0, \frac{\pi}{4}, 1 \}$ might provide a counter example. $\endgroup$
    – olooney
    Commented Jul 5, 2019 at 18:44
  • $\begingroup$ I think it might require an infinite sequence because that is what's true in general. To uniquely determine an analytic function (the characteristic function and m.g.f. of a discrete distribution is analytic because it is the sum of finitely many analytic functions) we need to know either 1) the value of the function at an infinite sequence of points, or 2) all of the derivatives of the function at a single point, or 3) the value of the function in any open disc around a point. A finite sample, or knowing only finitely many derivatives, is not enough to uniquely determine it. $\endgroup$
    – olooney
    Commented Jul 5, 2019 at 18:45
  • $\begingroup$ The reason we can make it works for polynomials is because they have special structure - in particular, every deriviate past a certain point is zero. The structure of the characteristic function is also special: it is of the form $\sum_{k=1}^N p_k e^{{x_k}t}$. But is that special enough? Maybe; I just don't know how to prove it. $\endgroup$
    – olooney
    Commented Jul 5, 2019 at 18:45

1 Answer 1

8
$\begingroup$

Let $F$ be the distribution supported on the numbers $x_1 \lt x_2 \lt \ldots \lt x_n$ that assigns probabilities $p_i \gt 0$ to each $x_i.$ By definition, its (raw) moment of degree $k$ is

$$\mu_k = \sum_{i=1}^n p_i x_i^k.$$

I will begin with a series of observations about this situation, each of interest in its own right. A basic tool is the sequence of vectors $\mathbf{x}_k = (x_1^k, x_2^k, \ldots, x_n^k)$ for $k=0, 1, \ldots,n-1.$ Writing $\mathbf{p} = (p_1,p_2,\ldots, p_n),$ each moment can be expressed as a vector product

$$\mu_k = \sum_{i=1}^n p_i x_i^k = \mathbf{p}\, \mathbf{x}_k^\prime.$$

  1. The collection $\{\mathbf{x}_0,\mathbf{x}_1, \ldots, \mathbf{x}_{n-1}\}$ is linearly independent. To show this, assume the contrary: that is, let coefficients $c_k$ not all zero be such that $$\sum_{k=0}^{n-1} c_k \mathbf{x}_k = \mathbf{0}.\tag{1}$$ Written out component-by-component, $(1)$ asserts that for each $i=1,2,\ldots, n,$ $$\sum_{k=0}^{n-1} c_k x_i^k = 0.$$ That exhibits each $x_i$ as a root of the polynomial $c(T)=c_{n-1}T^{n-1}+c_{n-2}T^{n-2}+\cdots + c_0.$ Such a polynomial has at most $\operatorname{deg}(c)\le n-1$ distinct roots, contradicting the distinctness of the $n$ $x_i.$

  2. All moments are determined by the first $n$ moments $\mu_0,\mu_1,\ldots,\mu_{n-1}.$ The preceding result shows the vectors $\mathcal{X} = \{\mathbf{x}_k,k=0,1,\ldots, n-1\},$ are a basis for $\mathbb{R}^n.$ Therefore for any $m,$ $\mathbf{x}_m$ is a linear combination of the $\mathbf{x}^k,$ $k=0,1,\ldots,n-1;$ that is, there exist coefficients $\,_ma_k$ (determined solely by the $x_i$) for which $$\mathbf{x}_m = \,_ma_0\mathbf{x}_0 + \,_ma_1\mathbf{x}_1 + \cdots + \,_ma_{n-1}\mathbf{x}_{n-1}.$$ Consequently $$\mu_m = \mathbf{p}\,\mathbf{x}_m^\prime = \mathbf{p}\,\sum_{i=0}^{n-1}\,_ma_k \mathbf{x}_k^\prime = \sum_{i=0}^{n-1}\,_ma_k \mathbf{p}\,\mathbf{x}_k^\prime= \sum_{i=0}^{n-1}\,_ma_k \mu_k.$$

  3. The numbers $x_i$ and the first $n$ moments determine $\mathbf{p}.$ Indeed, the first $n$ moments are the coefficients of $\mathbf{p}$ in the basis dual to $\mathcal X.$

  4. The first $n$ moments of $F$ determine, and are determined by, the distribution shifted by a constant $\lambda.$ This is the distribution supported on $x_1-\lambda, x_2-\lambda, \ldots, x_n-\lambda$ with probabilities $p_i.$ The demonstration is straightforward: use the Binomial theorem to expand $(x_i-\lambda)^k$ in terms of $x_i^0, x_i^1, \ldots, x_i^k.$

Part of the question is whether there exist $n^\prime,$ a positive probability vector $\mathbf{q},$ and support points $y_1\lt y_2\lt \ldots \lt y_{n^\prime},$ determining a distribution $G$ having the same moments as $F.$ Suppose there is. Shift both distributions by $\lambda=-\min(x_1,y_1),$ simplifying the situation to distributions with nonnegative support. By taking $m$ arbitrarily large, the largest support points eventually dominate the moments: $$q_{n^\prime} y_{n^\prime}^m \approx \mu_m \approx p_n x_n^m$$ This is possible only when $q_{n^\prime}=p_n$ and $y_{n^\prime} = x_n.$ Continuing inductively, we conclude $n=n^\prime,$ $\mathbf{q}=\mathbf{p},$ and $\mathbf{x}_1=\mathbf{y}_1:$ that is, $G=F.$

Finally, how many moments need to be known to determine $\mathbf{p}$ and $\mathbf{x}$? Consider the map $f:\mathbb{R}^n\times \mathbb{R}^n\approx \mathbb{R}^{2n}\to\mathbb{R}^{2n}$ defined by $$f(\mathbf{p}^\prime, \mathbf{x}^\prime) = (\mathbf{p}\mathbf{x}_0^\prime, \mathbf{p}\mathbf{x}_1^\prime, \ldots, \mathbf{p}\mathbf{x}_{2n-1}^\prime)^\prime.$$ Its derivative is the $2n\times 2n$ matrix

$$Df(\mathbf{p}^\prime, \mathbf{x}^\prime) = \pmatrix{1 & \cdots & 1 & 0 & \cdots & 0 \\ x_1 & \cdots & x_n & p_1 & \cdots & p_n \\ x_1^2 & \cdots & x_n^2 & 2p_1x_1 & \cdots & 2p_n x_n \\ \vdots & \cdots & \vdots & \vdots & \cdots & \vdots \\ x_1^{2n-1} & \cdots & x_n^{2n-1} & (2n-1)p_1x_1^{2n-2} & \cdots & (2n-1)p_nx_n^{2n-2}}$$

with a Vandermonde-like structure, enabling us to obtain a simple formula for its determinant,

$$\operatorname{Det}\left(Df(\mathbf{p}^\prime, \mathbf{x}^\prime)\right) = -(p_1p_2\cdots p_n)^{2n} \left(\prod_{1\le i\lt j \le n}(x_i-x_j)\right)^4.$$

Because none of the $p_i$ is zero and all the $x_i$ are distinct, this is nonzero. The Inverse Function Theorem implies $f$ is locally invertible: that is, provided $\mathbf{\mu}=(\mu_0,\mu_1,\ldots,\mu_{2n-1})$ is in the range of $f$, there exists an inverse $f^{-1}\subset\mathbb{R}^n\times \mathbb{R}^n$ in a neighborhood of $\mathbf{\mu}.$ That is,

The first $2n$ moments $\mu_0,\mu_1,\ldots,\mu_{2n-1}$ determine a discrete set of solutions $(\mathbf{p},\mathbf{x})$ corresponding to those moments.

As we have already shown, all such solutions correspond to the same distribution: they differ only by permuting the indexes $1,2,\ldots, n$ of the variables.

$\endgroup$
2
  • 1
    $\begingroup$ How do we go from locally invertible to unique? The function $\sin(x)$ is locally invertible near 0, but that doesn't prevent $\sin(\pi) = 0$ from also being true, because $\pi$ is outside the neighborhood $(-\pi/2, \pi/2)$ where $\sin^{-1}$ works. Why could there not be some point $(\mathbf{p}'', \mathbf{x}'')$ outside the neighborhood such that $f(\mathbf{p}'', \mathbf{x}'')$ also equals $(\mu_0, ..., \mu_{2n-1})$? $\endgroup$
    – olooney
    Commented Jul 6, 2019 at 14:01
  • 1
    $\begingroup$ @olooney I proved uniqueness first in the sense that there is a unique distribution determined by the information: see the paragraph beginning "part of the question." You are correct that locally invertible does not define a unique function $f:$ that is the point of the final remark. In fact, there are as many as $n!$ solutions. $\endgroup$
    – whuber
    Commented Jul 6, 2019 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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