Say we have a random variable $X$ that contains $k$ bits of information, and a message $M = f(X)$ ($M$ is deterministic given $X$) that is $l$ bits long, where $l<k$. This implies $H(X) = k$ and $H(M) \le l$. Hence, we know on average $M$ leaks at most $l$ bits of information about $X$:

$H(X \mid M) = H(X) - I(X;M) \geq H(X) - H(M) \geq k - l$.

Now, can we get an upper bound to the probability (over $X$) that $M$ leaks $l + t$ bits of information about $X$, or $\Pr_{M}[H(X) - H(X \mid M = m) \geq l + t]$?

Obviously, we can use Markov inequality to bound the probability down to $\epsilon$ when $t = (1/\epsilon - 1)l$. But can we get something better, or even something as good as $2^{-t}$?

This sounds like something really basic when you want to talk about deterministic protocol on random input, but I cannot find material that talks about this... Many thanks in advance.

  • $\begingroup$ Hm, so how about a distribution where $M = X$ with probability $l/k$, otherwise $M$ is null. $\endgroup$ – usul Jun 7 at 17:45
  • 2
    $\begingroup$ I don't think you can encode $l/k$ fraction of $X$ with only $l$ bits. You need at least $\log (2^{k} l/k)$ for that. $\endgroup$ – Dawei Huang Jun 7 at 19:41
  • 1
    $\begingroup$ Intuitively, you only need that many bits with probability $l/k$, otherwise you need $O(1)$ bits, so the average number of bits used is still $\approx l$. More formally, let $X$ be uniform on $\{1,...,2^k\}$. Let $M = X$ if $X \leq \frac{l-1}{k}2^k$, otherwise $M=0$. Then $H(X) = k$ while $H(M) \leq l$ by my calculations. $\endgroup$ – usul Jun 9 at 17:47
  • $\begingroup$ @usul: If $M=X$ for $X \leq \frac{l-1}{k} 2^k$, then you need $\frac{l-1}{k}2^k \leq 2^l$. Or $\frac{l-1}{k}\leq 2^{-(k-l)}$. Which means that $k$ is pretty close to $l$. $\endgroup$ – Peter Shor Jun 10 at 1:40
  • 2
    $\begingroup$ How about the following case: $X$ takes the all-zeroes string of length with probability 0.5, otherwise it is uniformly distributed over all strings of length $n$ except the all-zeroes string. $M$ is $0$ if $X$ is the all-zeroes string, and $1$ otherwise. In this case, the entropy of $X$ is roughly $n/2$, but conditioned on $M = 0$, its probability drops to $0$. Hence, if we take $l = 1, t = \frac{n}{2} - 1$, the probability over $m$ that conditioning on $M = m$ makes the entropy of $X$ drop by more than $l + t$ is $0.5 \gg 2^{-t}$. $\endgroup$ – Or Meir Jun 11 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.