4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Hm, so how about a distribution where $M = X$ with probability $l/k$, otherwise $M$ is null. $\endgroup$
    – usul
    Jun 7, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 12:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.