2
$\begingroup$

Let's consider a random variable X that can produce the output $c$ with probability $1/4$. I was told that $-\log_{2}(\frac{1}{4})$ represents the number of bits needed to represent $c$. But, imagine that X can produce the output $c$ with probability $1/4$ and the output $b$ with probability $3/4$, then I only need $1$ bit to express $c$, for example, $0=c$ (and $1=b$). Why am I wrong?

$\endgroup$
  • $\begingroup$ I think this question is stripped badly from the original. You use 1 bit to represent, however actually you have 0.81. Of course, when we turn into representation by bits, we can't use 0.81. You will see the effect more clearly in larger space. $\endgroup$ – kelalaka Dec 8 '19 at 13:15
  • $\begingroup$ Yeah i edited, however in another post in this site i read that "Log2 1/p is the number of bits needed to transmit symbols that occur with probability p. For example, if it occurs 1 times in 8, we need 3 bits to encode all 8 possibilities. Now just take the average number of bits weighted by p for each symbol." But, as i showed in the example this seems not correct $\endgroup$ – AleQuercia Dec 8 '19 at 13:32
  • 1
    $\begingroup$ You're confusing entropy with probability. They're not the same. Clearly X can be encoded with 1 bit as there are only two options spanning the output domain. But I'm still struggling to understand the question exactly. $\endgroup$ – Paul Uszak Dec 8 '19 at 13:35
7
$\begingroup$

Without proof or even a precise definition: when a random variable has independent outputs with $p$ the probability to output $c$, then an optimal encoding of the source's outputs (one that minimizes the expected number of bits consumed to encode all successive values of a large number of outputs, including order) will use on average $-\log_2(p)$ bit to encode the output $c$. For example, $-\log_2(\frac14)=2$ bit for $p=\frac14$, as told to the OP.

As noted in the question, it is possible to make a different encoding that only uses $1$ bit to encode $c$, and that's less than $-\log_2(p)$ when $p<\frac12$. But that different encoding will use more bits on average than an optimal encoding does, thus that observation does not contradict the statement in the previous paragraph.

For example, if the source outputs $c$ with probability $p=\frac14$ and $b$ with $p'=1-p=\frac34$, the encoding that outputs 0 for $c$ and 1 for $b$ requires $1$ bit per output, always, thus also on average. But it is possible to make a different encoding that consume less bits on average, down to the Shannon entropy of the source, which for two outputs is $-p\log_2(p)-(1-p)\log_2(1-p)\approx 0.81$ (see binary entropy function). An example of such encoding is to group outputs two by two, and encode as follows: $$ \begin{array}{cc|l|cc} \text{first} & \text{second} & \text{encoding} & \text{size} & \text{probability}\\ \text{output} & \text{output}& & s & q\\ \hline b & b & \mathtt{0} & 1 & \frac9{16}\\ b & c & \mathtt{10} & 2 & \frac3{16}\\ c & b & \mathtt{110} & 3 & \frac3{16}\\ c & c & \mathtt{111} & 3 & \frac1{16} \end{array} $$

The probabilities $q$ sum to $1$, and it is possible to unambiguously decode a stream of bits output by this encoder.

The average number of bits for encoding two outputs is the sum of the products $s\,q$, that is $\frac{27}{16}$. The average number of bit per output is half that, that is $\frac{27}{32}\approx0.85$, which is less than $1$.


It's possible to prove that we can make encoders that arbitrarily approach the output bit per input symbol ratio of the Shannon entropy, but not encoders below that limit. It's also possible to rigorously define the average number of bits needed to represent an output value for a given encoder, then to show that this quantity must converge to $-\log_2(p_i)$ for encoders that approach optimality. That's involved, but we can at least justify that value.

Whatever sensible definition we give to the average number of bits $r_i$ needed to represent an output value $i$ for a given encoder, it must be such that we can compute the average number of bits produced by the encoder to represent an output of the source as $\sum p_i r_i$. We see that with $r_i=-\log_2(p_i)$, we get the standard formula for Shannon entropy:

$$S=-\sum p_i\log_2(p_i)$$

which justifies that in this formula, $-\log_2(p_i)$ is the average number of bits needed to represent an output value $i$. Which matches what the OP was explained.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Don't you also need another communication channel to make this unambiguous? Something like a strobe or clock signal? So two wires instead of one. Otherwise, how does the decoder know that a b/c transition has taken place if the encoding is of variable length and without any padding? Simple temporal synchronisation won't do without a re-sync mechanism as phase drift will inevitably occur between X and the decoder. $\endgroup$ – Paul Uszak Dec 8 '19 at 16:43
  • $\begingroup$ @Paul Uszak: in the answer I consider an idealization where we have a source that produce discrete outputs with an incremental index, without reference to time; and we evaluate the number of bits to encode that, without reference to time either, and assuming 0 and 1 are the only and reliably recognizable values. Indeed, the problem of transfer of information across a real physical channel is much more complex than this idealization. The nice thing with simple problems is that they are easier to solve, and the results thus obtained are often useful for more complex problems. $\endgroup$ – fgrieu Dec 8 '19 at 18:03
1
$\begingroup$

The other answer covers the Shannon entropy case in the question, but a corollary is perhaps required.

The Shannon entropy of source X, H(X) is of course $ \frac{1}{4} \times\log_2(\frac{1}{4}) + \frac{3}{4} \times\log_2(\frac{3}{4}) $, equating to 0.811 bits/sample. But H is more appropriate in information management studies, whereby it's the theoretically minimum amount of lossless storage/information content for X.

Cryptography studies though tend to deal with min-entropy, H$_\infty$. This is a conservative and lossy measure of information content based on maximum likelihoods. Since your X appears to be an entropy source, you may want to extract it's randomness. Certain randomness extractors (hash based and seeded) require use of the Leftover Hash Lemma, which is predicated only on H$_\infty$. It's also used in other places dealing with key and password security.

So H$_\infty$(X) $ = -\log_2{(P_{max}(X))} $. As $ P_{max} = \frac{3}{4}$, H$_\infty$(X) equates to 0.415 bits/sample. That's a cryptographically useable entropy of only 51% of H(X). The magnitude of this reduction stems from the large skew in X's probability mass function.

|improve this answer|||||
$\endgroup$

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.