1
$\begingroup$

From Wikipedia:

Each universal code, like each other self-delimiting (prefix) binary code, has its own "implied probability distribution" given by $ p(i) ={2}^{-\ell(i)} $ where $\ell(i)$ is the length of the $i$th codeword and $p(i)$ is the corresponding symbol's probability

What is "implied probability"?

Given that prefix code are not fix-length codes, then I don't get what "implied probability" means, for example, given a 3 bits length code, implied probability is ${2}^{-3} = \frac{1}{8}$ but what does it mean? is it about choosing the code between others? or choosing random between all possible of three bits? as here we are talking about prefix codes, so length will vary among codes, so there could be only one code of three bits, so probability of get it would be 1? Any clarification will help!

$\endgroup$
  • $\begingroup$ Why isn't it just that when you randomly guess three bits, the chance that they're equal to your three bits is $1/8$? $\endgroup$ – Albert Hendriks Jun 1 at 7:28
  • $\begingroup$ @AlbertHendriks because it's a prefix code, so there are not 2^8 codes for 3 bits. $\endgroup$ – Hernan_eche Jun 1 at 14:22
2
+50
$\begingroup$

The idea is the following:

the following tree $T$

$ \\ \emptyset \\ | \ \setminus \\ | \ \ \ \setminus \\ 0 \ \ \ \ \ 1 \\ | \ \setminus \\ | \ \ \ \setminus \\ 00 \ \ \ \ \ 01\\ \\ \ \ \ \ \ \ \ \ \ \ | \ \setminus \\ \ \ \ \ \ \ \ \ \ \ | \ \ \ \setminus \\ \ \ \ \ \ \ \ \ \ \ 010 \ \ \ \ \ 011 $

of depth 3 is constructed by

  1. Taking an object labeled as $\emptyset$ that has probability 1 and splitting it in half into two pieces which we label as $0,1$; who each acquire equal probabilities 1/2 individually.
  2. Taking the object labeled as $0$ that has probability 1/2 and splitting it in half into two pieces which we label as $00,01$; who acquire equal probabilities 1/4 individually.
  3. Taking the object labeled as $01$ that has probability 1/2 and splitting it in half into two pieces which we label as $010,011$; who each acquire equal probabilities 1/8 individually.

This is essentially the "unwrapping the Huffman algorithm in reverse." You are asking the wrong question, you should be asking "Why label it this way?"

The idea behind the Huffman coding scheme is that

  1. $0,1$ each cost 1 unit of "communication complexity" or "space complexity" depending on your interests
  2. $00,01$ each cost 2 units of "communication complexity"
  3. $010,011$ each cost 3 units of "communication complexity"

You should read chapter 5 of Cover and Thomas

and this Wikipedia article on the kraft inequality is probably helpful too. however, if you want a proof of the infinite kraft inequality you need chapter 5 of Cover and Thomas.

The idea is to continue this (type of) procedure unto infinity so that we get a something the following tree $T_\infty$

$ \\ \emptyset \\ | \ \setminus \\ | \ \ \ \setminus \\ 0 \ \ \ \ \ 1 \\ | \ \setminus \\ | \ \ \ \setminus \\ 00 \ \ \ \ \ 01\\ \\ \ \ \ \ \ \ \ \ \ \ | \ \setminus \\ \ \ \ \ \ \ \ \ \ \ | \ \ \ \setminus \\ \ \ \ \ \ \ \ \ \ \ 010 \ \ \ \ \ 011 \\ \ \ \ \ \ \ \ \ \ \ | \ \setminus \\ \ \ \ \ \ \ \ \ \ \ | \ \ \ \setminus \\ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ 0101 $

which has infinite depth. Each time you "split" a string, you maintain a "partition of unity" i.e., you maintain a probability distribution. The kraft inequality states that if your code was constructed in this manner, i.e., $$ \sum_{i : \text{leaf of }T_\infty} 2^{-l(i)} = 1 $$ then the code is optimal.

In other words if you have a set of binary strings $\mathcal{S}$ and the function $$p(s) = 2^{-l(s)}$$ turns out to actually satisfy the kraft inequality, i.e., $$ \sum_{s \in \mathcal{S}} 2^{-l(i)} = 1, $$ then it is an optimal code. Therefore forming a probability distribution and being an optimal code are equivalent.

One can further prove that all such codes have a tree that witnesses their optimality.


| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you give an particular example of actual coding with that properties? is it necessary to go to infinity to get that properties, is that an assumption/requirement? $\endgroup$ – Hernan_eche Jun 3 at 21:12
  • $\begingroup$ Yea, sure. Suppose that I send you a text message every day and I always send one message from the following set {"hello", "goodbye", "thank you", "that's cool"} and suppose that p("hello") =1/2, p("goodbye")=1/4, p("thank you")=1/8, and p("that's cool")=1/8. If I apply the Huffman algorithm to this I will get a tree equivalent to the example I gave, i.e., the code p("hello") =1, p("goodbye")=00, p("thank you")=010, p("that's cool")=011 is an optimal code. You may check that this code satisfies the Kraft inequality. It is not necessary to go to infinity to get those properties. $\endgroup$ – Pedro Juan Soto Jun 4 at 2:56
  • $\begingroup$ I gave you an infinite example because you posted this link en.wikipedia.org/wiki/Universal_code_(data_compression) which led me to believe you wanted to understand some asymptotic property about universal codes. But the Kraft inequality applies to any code, finite or infinite. You can apply it to understanding the Huffman coding scheme or any other coding scheme. The main idea I wanted to leave you with is that the "deeper meaning of the implied probability" is much ado with the optimality of coding schemes as a matter of fact the Kullback–Leibler divergence between the ... $\endgroup$ – Pedro Juan Soto Jun 4 at 3:03
  • $\begingroup$ ... the en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence between the implied distribution of the code and the true distribution of the messages you are encoding is a measure of how good or bad your coding scheme is. For example, check out the following links en.wikipedia.org/wiki/… en.wikipedia.org/wiki/… the following en.wikipedia.org/wiki/Kolmogorov_complexity is also cool $\endgroup$ – Pedro Juan Soto Jun 4 at 3:10
  • $\begingroup$ Sorry, no, there is cherrypicking in your example, you have chosen symbols probabilities exactly as power of -2, so no surprise in the result. But real probabilities of symbols are independent of coding, particularly don't have to be power of -2, could be 1/3, 1/88, or 1/whatever, so after coding them, you assign prefix codes of a determinate length. Symbol probability for you, Shannon and me, is about source, as in you example it will depend on ratios of hello, goodbye, etc.. we send, not in the encoding.So your example is equating both definitions, my question is exactly about the difference $\endgroup$ – Hernan_eche Jun 4 at 14:45
1
$\begingroup$

It has to do with information theory. Suppose we have a random source that outputs symbols with some fixed probability distribution $P$ over an alphabet $X$. Shannon's theory says that any coding scheme must use at least $H(P) = \sum_{x \in X} P(x) \log_2 (1/P(x))$ bits per symbol on average. The value $H(P)$ is called the entropy $P$. A full prefix code is always optimal for some distribution $P$, in the sense that it matches the $H(P)$ lower bound. That distribution is called the implied distribution of the code.

For example, suppose we have a prefix-code over the alphabet $\{a,b,c,d\}$ with code words $a$ = "000", $b$ = "001", $c$ = "01" and $d$ = "1". By your formula, the implied probability distribution is $P(a) = 1/8$, $P(b) = 1/8$ and $P(c) = 1/4$ and $P(d) = 1/2$. The entropy of this distribution is

$$\frac{1}{8} \log 8 + \frac{1}{8} \log 8 + \frac{1}{4} \log 4 + \frac{1}{2} \log 2 = \frac{3}{8} + \frac{3}{8} + \frac{2}{4} + \frac{1}{2} = \frac{7}{4}$$

The expected length of the code words is the sum of code lengths, each weighted by their probability:

$$ \frac{1}{8} \cdot 3 + \frac{1}{8} \cdot 3 + \frac{1}{4} \cdot 2 + \frac{1}{2} \cdot 1 = \frac{7}{4} $$

This matches the entropy bound, and hence the code is optimal for this distribution.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So, as I read in your answer "a full prefix code is always optimal for some distribution P", good point, then it seems Universal Codes to be a kind of hypothetical ideal codes that fit that distribution P $\endgroup$ – Hernan_eche May 27 at 14:28
0
$\begingroup$

First of all, you are mis-parsing the phrase 'implied probability distribution'. There is no such thing as 'implied probability'. What Wikipedia is saying is: Given a self-delimiting coding scheme, there is an 'obvious' or 'natural' (here a mathematician would, I suspect, use the term 'canonical') way to assign numbers to legal codewords, in such a way that the numbers constitute a probability distribution over the set of all legal codewords. The naturalness of this assignment means that it is not necessary to expend any great mental effort to explicitly construct this distribution, which is why it is 'implied'.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok, forget about the term implied, I want to ask what does it mean "symbol probability" here, I can understand a probability of a symbol for an specific use, for example, in a language, every letter on english has a different probability ok, but how is it defined a probability just over symbols when no particular use is defined? It seems that definition suppose coding is efficiently defined so longer symbols are less probable? How can I see it in an example for prefix codes? $\endgroup$ – Hernan_eche May 26 at 16:51

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.