1
$\begingroup$

Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic.

The Slepian-Wolf theorem states that sequences of outputs from two separate random variable sources A and B that have a joint probability distribution defined on them, if encoded with the following rates, can be completely retrieved when decoded together:

$$ R_A \geq H(A|B) \\ R_B \geq H(B|A) \\ R_A + R_B \geq H(A,B) $$

$R_x$ refers to the bits required for encoding one symbol of $X$, assuming all logarithms are taken to the base 2.

Given this, I wanted to try out an example, especially because I find fractional number of bits per symbol slightly confusing to think about.

Consider two sources $A$ and $B$, that either sprout out 0 or 1 following this probability distribution:

A \ B 0 1
0 0.5 0
1 0.25 0.25

We calculate the entropies as follows: $$ H(A,B) = 3/2 = 15/10\\ H(A|B) = 7/10 \\ H(B|A) = 1/2 = 5/10\\ $$

Now, assume that the a certain sequence of bits that A and B give out are as follows:

A B
0 0
0 0
1 0
1 1
1 0
0 0
0 0
1 1
1 0
0 0

I should be able to find an encoding that allows A to send atleast 7 bits, B atleast 5 and a total of atleast 15, such that they can be decoded completely, right?

Unfortunately I am unable to think of an encoding where they send less than 10 bits each.

For example, B does not have to send anything when A sends 0, however B does not know when A sends 0.

I would also like to know if this is the wrong way to interpret the theorem (perhaps a longer sequence is required), or if there is another way to see its working.

$\endgroup$
1
$\begingroup$

Here's a simpler example. Consider the binary erasure channel which erases its input with probability $1/2$. The channel capacity is $1/2$, so you should be able to send one bit of information by sending two bits on the channel. Or should you?

Shannon's theorem only guarantees that for every $\epsilon > 0$, you can send $(1/2-\epsilon) N$ bits of information by sending $N$ bits across the channel, with failure probability approaching zero as $N\to\infty$. There are two features of this theorem (shared by Slepian–Wolf) that you didn't take into account:

  • The theorem talks about asymptotic rates.
  • The theorem allows for some small failure probability.

The article you link to assumes you are already aware of all this. Since you appear not to be, I suggest reading a textbook on information theory, where all the relevant concepts are defined and explained.

$\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.