I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some arbitrary event $\mathcal{E}$: $$ H[ Z \mid W ] \ge n - d\ \Longrightarrow\ H[ Z \mid W, \mathcal{E}] \ge n - \frac{d+1}{\Pr[\mathcal{E}]}. $$

The proof is very short, but I'm unable to follow one of the derivations, which seems to be using a general property of conditional entropy that I'm unfamiliar with.

Proof of Lemma 19: We know that the entropy of $Z$ can be at most $n$ no matter on what we condition. Let $H_b$ denote the binary entropy. It follows that $$ \begin{align} n -d &\le H[ Z \mid W] \\ &= \Pr[ \mathcal{E} ] H[Z \mid W, \mathcal{E}] + \Pr[\neg \mathcal{E}]\ H[Z \mid W, \neg \mathcal{E}] + H_b(\Pr[\mathcal{E}]) \quad (2)\\ &\le \Pr[ \mathcal{E}]\ H[Z \mid W, \mathcal{E}] + \Pr[\neg \mathcal{E}]\cdot n + 1. \end{align} $$ QED

My Questions:

  1. Why does (2) hold? Is this some general property of conditional entropy?
  2. How exactly is $H[ Z \mid W, \mathcal{E} ]$ defined? Is it equivalent to $\sum_w \Pr[W=w\mid \mathcal{E}]\ H[ Z \mid W=w,\mathcal{E}]$ or $\sum_w \Pr[W=w]\ H[ Z \mid W=w,\mathcal{E}]$?
  • $\begingroup$ Fixed the reference to the lemma in the paper. $\endgroup$
    – New_In_CS
    Jun 22 at 7:49

We treat $\mathcal{E}$ as an indicator random variable for the event $\mathcal{E}$ (so $\mathcal{E}$ stands for two different things). The derivation is $$ H(Z|W) \leq H(Z,\mathcal{E}|W) = H(Z|\mathcal{E},W) + H(\mathcal{E}|W) \leq H(Z|\mathcal{E},W) + H(\mathcal{E}). $$


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.