# Worked out example of Slepian-Wolf Theorem

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.

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: