1
$\begingroup$

Let $X=x_1\ldots x_n$ be a random variable. Assume that every $x_i$ takes values in $\{0,1\}$.

Assume also that for every $I \subseteq \{1,\ldots, n\}$ the Shannon entropy of random value $X_I$ [if $I = \{i_1, \ldots, i_k\}$ then $X_I = x_{i_1}\ldots x_{i_k}$] is equal to $|I| \cdot h(p) + O(\log n)$ for some $p$, where $h(p)= -p\log p - (1-p)\cdot \log (1-p)$.

What can we say about $X$? If the term $O(\log n)$ is just zero then all is simple: the variables $x_1, \ldots, x_n$ are independent and have the same entropy. So, $X$ has a Binomial distribution with parameters $n$ and $p$ that is shifted by some vector in $\{ 0,1\}^n$.

In general case I think that $X$ can be approximated by a mixture of several random variables with Bernoulli distribution with the same distribution. More precisely my conjecture is the following: there is a random variable $Y$ that is a mixture of poly($n$) Binomial distribution (with parameters $n$ and $p$; that are shifted by some vectors in $\{0,1\}^n$) and polynomial $q$ such that the following is true for 99% (according to probability measure $X$) $z \in \{0,1\}^n$: $\Pr[Y=z] \cdot p(n) \ge \Pr[X=z]$.

$\endgroup$
1
  • $\begingroup$ One interpretation of MGL is that outputs of the form (codeword + noise) expose more of the system's entropy when the input codebook is structured compared to when the codebook is all the words with iid letters. (In the first case you can (partially) decode and get a noise vector estimate, in the second case the codeword and noise are undifferentiated.) $${}$$ In light of this, to approach your question I would first try and understand more precisely how your $X$ falls between a "optimal-for-decoding" dictionary and the "noise" dictionary. $\endgroup$ Commented Jul 22, 2021 at 6:05

0

You must log in to answer this question.

Browse other questions tagged .