# Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$

In this paper by Tishby, Pereira and Bialek they mention on page 4 in the Relevant quantization chapter the setting is the following; Given some signal space $$X \sim p(x)$$ and a quantized codebook $$\hat{X}$$. They seek a possibly stochastic mapping characterized by the pdf $$p(\hat{x}|x)$$ from every value $$x \in X$$ to a codeword $$\hat{x} \in \hat{X}$$.

1) They mention that the average volume of the elements of $$X$$ that are mapped to the same codeword is $$2^{H(X|\hat{X})}$$ - why is this?

2) They mention that for ease of exposition both $$X$$ and $$\hat{X}$$ are finite, so howcome $$p(\hat{x}|x)$$ is a p.d.f and not a p.m.f?

If I understand right what "average volume" means here, I don't think this is correct. For example, let's say you map $$n$$-bit strings (under uniform distribution) to $$n$$-bit strings as follows: Given an input $$x$$, if the first bit is 0, output $$x$$, and otherwise output "1".

The average volume would be $$\frac{1}{2}(2^{n-1}+1)$$, whereas the $$2^{H(X|\hat{X})} = \sqrt{2^{n-1}}$$.

The correct expression for the average volume should perhaps be the expectation $$\sum p(\hat{x}) 2^{H(X|\hat{X}=\hat{x})}$$.

You are right about p.d.f. vs p.m.f, this kind of mix-up of terminology is quite common (but shouldn't be).