3
$\begingroup$

Assume that bits $A$ and $B$ each have .5 bits of entropy per bit.

The two-bit result of the concatenation $A‖B$ has 1 bit of entropy total, and it retains the entropy density of .5 bits of entropy per bit.

How many bits of entropy would the single-bit result of the exclusive-OR of $A$ and $B$, namely $A⊕B$, have per bit?

I'm guessing the formula is something like $\mathord{\mathrm{E}}(A⊕B)=1-(1 - \mathord{\mathrm{E}}(A))(1-\mathord{\mathrm{E}}(B))=.75$ bits of entropy per bit. Is this correct? If so, is there a short proof of this equation that I can refer to?

Also, do I correctly interpret that you can only approach 1 bit of entropy per bit by XOR-ing bits of less dense entropies but never actually attain it?

$\endgroup$
3
$\begingroup$

Assume that bits $A$ and $B$ each have .5 bits of entropy per bit.

Fair enough (and I'll assume that we're talking about Shannon entropy)

The two-bit result of the concatenation $A‖B$ has 1 bit of entropy total, and it retains the entropy density of .5 bits of entropy per bit.

Not so fast. The concatenation has between 0.5 and 1 bits of entropy.

The issue is that the bits may be correlated; if the bits are always exactly the same (or exactly the opposite), the concatenation will never have any more entropy than just one of the bits. If the bits are independent (that is, are uncorrelated), then the concatenation will have 1 bit total. If they are partially correlated, then the entropy will be somewhere between 0.5 and 1.

This is not a pedantic point; when computing the joint entropy of several events, one always needs to be aware of the possible correlations between these events.

How many bits of entropy would the single-bit result of the exclusive-OR of $A$ and $B$, namely $A \oplus B$, have per bit?

This is a somewhat more complicated situation; if we compute the probabilities involved with a source generating a single bit with 0.5 bits of entropy, well, that's the solution to $p \log_2(p) + (1-p) \log_2(1-p) = -0.5$, and those solutions are $p = 0.110028...$ or $p = 0.889972...$. When we translate that into the possible entropies of the xor, that has a low of 0 (if the bits are perfectly correlated) to a maximum of 0.760269... (which happens if neither bit are in their low probability state at the same time); if they are uncorrelated, the entropy is 0.713537... These values were computed by taking the above $p$ values, deriving the corresponding probabilities of the xor, and plugging them into the Shannon entropy formula.

I'm guessing the formula is something like $\mathord{\mathrm{E}}(A⊕B)=1-(1 - \mathord{\mathrm{E}}(A))(1-\mathord{\mathrm{E}}(B))=.75$ bits of entropy per bit. Is this correct?

No, it's not correct (even if we assume independence), at least if $E$ is the entropy function and not the expectation. I'm not sure if there is a simple formula that gives you that; if $p$ is a solution to $p \log_2(p) + (1-p) \log_2(1-p) = -E(A)$, and $r$ is a solution to $r \log_2(r) + (1-r) \log_2(1-r) = -E(B)$, then the Shannon entropy formula applied to $A \oplus B$ would involve the term $\log_2( p \cdot r + (1-p) \cdot (1-r))$, and there's no immediately obvious way to simplify this term, or combine it with other terms.

Also, do I correctly interpret that you can only approach 1 bit of entropy per bit by XOR-ing bits of less dense entropies but never actually attain it?

Oddly enough, with the right amount of correlation, you can actually get 1 bit of entropy. Consider the case where both sources generate a 1 with probability $0.25$ (and so have $0.811278...$ bits of entropy). If they never both generate a 1 bit at the same time, then the probability that exactly one of then generate a 1 bit is $0.5$, and so the xor does yield an entropy of 1.

Of course, if the input bits are uncorrelated, then you are correct (unless one of the input bits already has an entropy of 1).

| improve this answer | |
$\endgroup$
1
$\begingroup$

Actually a stronger statement holds. It is enough for one of two bits to have maximum Shannon entropy, for their XOR to also have maximum Shannon entropy, provided they are statistically independent.

If $A$ has probability distribution $(p,1-p)$ with $\Pr[A=0]=p$ and $B$ has probability distribution $(q,1-q)$ with $Pr[B=0]=q$ and they are independent random variables then $A\oplus B$ has distribution with $$\Pr[A \oplus B=0]=pq+(1-p)(1-q)= 1+2pq-p-q$$

If $A$ has full 1 bit Shannon entropy (so $p=1/2$) then

$$\Pr[A \oplus B=0]=1+2pq-p-q=1+q-(1/2)-q=1/2. $$

The case you give is not maximal, your overall vector has 1-bit entropy but can have up to 2 bits ideally. So you are stretching 1-bit entropy into 2 dimensions. The above formula can be applied to each bit but you need to specify the dependence structure between the bits of your two-dimensional vector. $p\approx 0.2$ or $p\approx 0.8$ gives entropy of around 1/2 bits.

| improve this answer | |
$\endgroup$
  • $\begingroup$ So the result is basically that it doesn't really help to combine bits with XOR if both of them have the same entropy/bit of .5, is that correct? $\endgroup$ – user84052 Oct 6 at 20:57
  • $\begingroup$ No, if you let $p=1/5,$ you can see that the probability of A XOR B is $(4/5)-(4/5)q$, so you can push that towards 1/2 by choosing $q$. The crucial point is that from your statement you assume the total entropy of the vector is fixed at 1, and talk about bit entropy densities. $\endgroup$ – kodlu Oct 6 at 21:12
  • $\begingroup$ see the other answer for more details, thanks to @poncho $\endgroup$ – kodlu Oct 6 at 22:06

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.