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

<p>The average volume would be <span class="math-container">$\frac{1}{2}(2^{n-1}+1)$</span>, whereas the <span class="math-container">$2^{H(X|\hat{X})} = \sqrt{2^{n-1}}$</span>.</p>

<p>The correct expression for the average volume should perhaps be the expectation <span class="math-container">$\sum p(\hat{x}) 2^{H(X|\hat{X}=\hat{x})}$</span>.</p>

<p>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).</p>

CC BY-SA 4.0
2020-04-12T17:26:39.663Z
2020-04-17T13:35:13.980Z
2020-04-17T13:35:13.980Z
Mahdi Cheraghchi
<p>In <a href="https://www.cs.huji.ac.il/labs/learning/Papers/allerton.pdf" rel="nofollow noreferrer">this paper</a> by Tishby, Pereira and Bialek they mention on page 4 in the <em>Relevant quantization</em> chapter the setting is the following; Given some signal space <span class="math-container">$X \sim p(x)$</span> and a quantized codebook <span class="math-container">$\hat{X}$</span>. They seek a possibly stochastic mapping characterized by the pdf <span class="math-container">$p(\hat{x}|x)$</span> from every value <span class="math-container">$x \in X$</span> to a codeword <span class="math-container">$\hat{x} \in \hat{X}$</span>. </p>

<p>This has made me wonder about the following:</p>

<p>1) They mention that the average volume of the elements of <span class="math-container">$X$</span> that are mapped to the same codeword is <span class="math-container">$2^{H(X|\hat{X})}$</span> - why is this? </p>

<p>2) They mention that for ease of exposition both <span class="math-container">$X$</span> and <span class="math-container">$\hat{X}$</span> are finite, so howcome <span class="math-container">$p(\hat{x}|x)$</span> is a p.d.f and not a p.m.f? </p>

<it.information-theory><st.statistics><shannon-entropy>
Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$
sn3jd3r
# Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$

(Asked by: username_0 on 2020-04-09)

In [this paper](https://www.cs.huji.ac.il/labs/learning/Papers/allerton.pdf) 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}$.

This has made me wonder about the following:

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?

**Tags:** it.information-theory, st.statistics, shannon-entropy

---

## 1 answers

### Answer by username_1 on 2020-04-12. Score: 1

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).


---

