Let $x \in \{0,1\}^n$ be uniformly at random. What is an estimate for the entropy of moments, $H(\sum_i x_i, \sum_i i\cdot x_i, \sum_i i^2\cdot x_i)$ ?

$H(.)$ here is the Shannon entropy

  • $\begingroup$ Can you edit the question to define your H term? $\endgroup$ – Matt Cuffaro Jun 8 at 1:44
  • $\begingroup$ Thanks, fixed it. $\endgroup$ – Jumanji Jun 8 at 1:58
  • $\begingroup$ Do you really want the entropy of the three-tuple $(\sum_i x_i, \sum_i i\cdot x_i, \sum_i i^2\cdot x_i),$, or do you want the entropy of each moment separately? $\endgroup$ – r.e.s. Jun 8 at 14:17
  • $\begingroup$ Thanks. I needed it for the three-tuple, but any technique to estimate either would be insightful. $\endgroup$ – Jumanji Jun 8 at 17:12
  • $\begingroup$ I would use a version of the central limit theorem. Your sum should be close to a multivariate normal random variable for large $n$. Most of the mass should be in a neighborhood of the mean of size roughly $\sqrt n$ in the $x$ direction. $n^{3/2}$ in the $y$ direction and $n^{5/2}$ in the $z$ direction. The entropy should therefore be something like $\frac 92\log n$. $\endgroup$ – Anthony Quas Jun 10 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.