4
$\begingroup$

I hope I'm using the right terminology below.

I have access to the moments statistics of a large sample. That is, I have $\sum(x)$, $\sum(x^2)$, ..., $\sum(x^k)$. I also have access to max and min, and I can probably access some other information (e.g., the log-moments).

I want to estimate the Information entropy that is usually computed as

$h[f] = \operatorname{E}[-\ln (f(x))] = -\int_\mathbb X f(x) \ln (f(x))\, dx$

Is this possible? What could be the pseudocode for that operation?

Edit: One thing that I overlooked is the difference between the continuous case and the discrete case. In the discrete case the Entropy is computed

$H(X) = \sum_{i=1}^n {\mathrm{P}(x_i)\,\mathrm{I}(x_i)} = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)}$

Example: Assuming my variable is accounting for the number of people with height $y$. This is a discrete case, where I can have for example $x=153cm$ and $f(x)=24$, and $f(x)=0$ for $x=0cm$.

This case should be different.

$\endgroup$
7
  • 1
    $\begingroup$ Although Boltzmann's theorem (en.wikipedia.org/wiki/…) provides a maximum value for $h[f],$ a minimum may be hard to come by. In any event, generally there will be many distributions with the given moments, so to solve this problem you need to provide additional criteria or constraints. $\endgroup$
    – whuber
    Dec 13, 2018 at 20:12
  • $\begingroup$ What if I have percentiles/quantiles? $\endgroup$
    – Kuzeko
    Dec 13, 2018 at 21:21
  • $\begingroup$ I would expect the same issues to arise, although the computations probably become much more difficult when you try to combine moment information with quantile information. The problem is that entropy of continuous distributions is not very stable or nicely behaved, because you just cannot get at it directly by means of a discrete sample unless you're willing to make some assumptions about the underlying distribution. $\endgroup$
    – whuber
    Dec 13, 2018 at 21:29
  • $\begingroup$ thanks for the comment. what kind of assumptions could be needed? $\endgroup$
    – Kuzeko
    Dec 14, 2018 at 23:05
  • $\begingroup$ By preference, parametric ones. Another option is just to assume the underlying distribution maximizes the entropy. The entropy you calculate from that assumption scarcely could be called an "estimate," though! $\endgroup$
    – whuber
    Dec 14, 2018 at 23:11

1 Answer 1

3
$\begingroup$
  1. If the distribution is of compact support, the moments, equivalent to the Fourier series expansion, uniquely determines the distribution. The uniqueness is even more directly shown by the Stone-Weierstrass theorem. As a matter of fact the Stone-Weierstrass theorem provides just the arbitrarily close approximation of the distribution. Without loss of generality, suppose the target distribution $p(x)$ is nonzero only on $[0,1]$. Let the approximating $n$'th order polynomial be $$P_n(x)=\sum_{i=0}^n c_ix^i.$$ Substituting this polynomial into the given $n+1$ moment integrals, with the help of the Beta functions, gives an $(n+1)\times (n+1)$ linear system of equation. Solving it gives $P_n$.

One can also use the Bernstein polynomial approximation $$B_n[p](x) = \sum_{i = 0}^n p\left( \frac{i}{n} \right) b_{i,n}(x)$$ and solve directly for the target function value at $p(\frac in), \,\forall i\in\{0,1,\cdots,n\}$.

Then the entropy is uniquely determined.

  1. If the distribution is discrete, the moment equation is just the power sum. The distribution is also uniquely determined. Newton's identity gives the elementary symmetric polynomials of $\{x_i\}$ which in turn gives a polynomial. Solving the $n$'th order polynomial gives the distribution.
$\endgroup$
6
  • $\begingroup$ Thanks. Could you spell it out more operationally? I'm not familiar with the terminology you use? What is compact support? Given the moments, how do I proceed? $\endgroup$
    – Kuzeko
    Dec 21, 2018 at 9:31
  • $\begingroup$ @Kuzeko: I have added the explicit construction as well as the links to the definitions and theorems therein. $\endgroup$
    – Hans
    Dec 21, 2018 at 10:55
  • $\begingroup$ @Kuzeko: If you are satisfied with the answer, please do not forget to accept it and award the bounty as well as upvote it, as the grace period will end in a few minutes. $\endgroup$
    – Hans
    Dec 21, 2018 at 19:05
  • $\begingroup$ Thank you for you effort. I was travelling and could not access my SE account. Nonetheless, given my ignorance of the subject, I'm not able to understand your answer. $\endgroup$
    – Kuzeko
    Dec 22, 2018 at 9:26
  • $\begingroup$ @Kuzeko: I can understand your difficulty accessing the account. However, the appearance of a bait-and-switch operation of putting up a bounty only to attract attention then not bothering to check the answers until the bounty expires, not only does not exactly give much incentive for people to put effort to answering your question but also leaves a bad after-taste of being played if not exactly cheated. Anticipating a coming trip and the difficulty of accessing the internet and the expiration time of the bounty, maybe you could have posted the bounty at a more convenient time for yourself. $\endgroup$
    – Hans
    Dec 23, 2018 at 2:16

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.