7
$\begingroup$

Consider a random $n$ by $n$ matrix $A$ whose entries are chosen from $\{0,1\}$ and a random $n$ dimensional vector $x$ whose entries are also chosen from $\{0,1\}$. Assume $n$ is large.

What is the (base 2) Shannon entropy of $Ax$? That is, can we give a large $n$ approximation for $H(Ax)$?

It feels like $H(Ax)$ should be at least $n$ as that is the entropy of $x$ and $A$ is very likely to be non-singular. We also know $H(Ax) \leq n \log_2{n}$ as we can encode $Ax$ in $n \log_2{n}$ bits (the entries of $Ax$ are no larger than $n$).

Is the entropy of the form $n$ or of the form $n\log_2{n}$ or something in between?

$\endgroup$
2
+50
$\begingroup$

Let $A$ has size $m\times n$ (more general), $y=A x$, $y=(y_1, y_2, \cdots y_m)$. Let $s=\sum_{i=1}^n x_i$

Then $$H(y)= H(y \mid s) + H(s) - H(s \mid y) \tag{1}$$ and we can bound:

$$ H(y \mid s) \le H(y) \le H(y \mid s) + H(s) \tag{2} $$ To compute, $H(y \mid s)$, note that while $y=(y_1, y_2, \cdots y_m)$ are not independent, they are independent if conditioned on $s$. Hence

$$H(y \mid s) = m \, H(y_1 \mid s)$$

Further, $y_1 |s \sim B(s,1/2)$ (Binomial), and $s$ is also Binomial $B(n,1/2)$ Hence

$$H(y \mid s) = m \sum_{s=0}^n \frac{1}{2^n}{n \choose s} h_B(s) \tag{3}$$

$$H(s) = h_B(n) \tag{4}$$

where $$h_B(t)= - \frac{1}{2^t} \sum_{k=0}^t {t\choose k} \log\left(\frac{1}{2^t}{t \choose k}\right) = t - \frac{1}{2^t} \sum_{k=0}^t {t \choose k} \log\left({t \choose k}\right) \tag{5}$$ is the entropy of a Binomial of size $t$ and $p=1/2$.

(all logs are in base $2$ here).

Expressions $(3)$ $(4)$, together with $(2)$, provide exact bounds. We can obtain an approximation by taking the central term in $(3)$ and using the asymptotic $h_B(t) \approx \frac{1}{2} \log(t \, \pi e /2)$. We then get

$$H(y|s) \approx \frac{m}{2} \log(n \pi e /4) \tag{6}$$

$$H(s) \approx \frac{1}{2} \log(n \pi e /2) \tag{7}$$

This strongly suggests that, when $m=n$, $H(y)$ grows as $\frac{n}{2} \log(n)$

The graps shows both bounds and the approximation $(6)$ for the lower bound.

enter image description here

$\endgroup$
  • $\begingroup$ Thank you for this. Is your best guess currently that it is closer to $n$ or $n\log_2{n}$? $\endgroup$ – dorothy Dec 17 '15 at 12:58
  • 1
    $\begingroup$ Closer to the second. I'd bet for $\frac{n}{2} \log_2(n \, \pi e /4)$ $\endgroup$ – leonbloy Dec 17 '15 at 21:54
  • $\begingroup$ This is a very nice answer! Thank you. Your trick of conditioning on $s$ suddenly makes the problem elegantly tractable. I have asked a related question at math.stackexchange.com/questions/1580679/… which I hope you might also find interesting. $\endgroup$ – dorothy Dec 18 '15 at 13:20

Your Answer

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

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