<p>Say we have a random variable <span class="math-container">$X$</span> that contains <span class="math-container">$k$</span> bits of information, and a  message <span class="math-container">$M = f(X)$</span> (<span class="math-container">$M$</span> is deterministic given <span class="math-container">$X$</span>) that is <span class="math-container">$l$</span> bits long, where <span class="math-container">$l&lt;k$</span>. This implies <span class="math-container">$H(X) = k$</span> and <span class="math-container">$H(M) \le l$</span>. Hence, we know on average <span class="math-container">$M$</span> leaks at most <span class="math-container">$l$</span> bits of information about <span class="math-container">$X$</span>:</p>

<p><span class="math-container">$H(X \mid M) = H(X) - I(X;M) \geq H(X) - H(M) \geq k - l$</span>. </p>

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

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

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

CC BY-SA 4.0
2019-06-07T17:45:23.657Z
Hm, so how about a distribution where $M = X$ with probability $l/k$, otherwise $M$ is null.
usul
CC BY-SA 4.0
2019-06-07T19:41:44.243Z
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.
Dawei Huang
CC BY-SA 4.0
2019-06-09T17:47:48.233Z
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.
usul
CC BY-SA 4.0
2019-06-10T01:40:35.973Z
@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$.
Peter Shor 
CC BY-SA 4.0
2019-06-11T12:12:59.523Z
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}$.
Or Meir
<it.information-theory><communication-complexity>
Expected vs actual amount of information leaked by an $l$-bits message
Dawei Huang
# Expected vs actual amount of information leaked by an $l$-bits message

(Asked by: username_0 on 2019-06-06)

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

**Tags:** it.information-theory, communication-complexity

> **Comments:**
> **username_1**: Hm, so how about a distribution where $M = X$ with probability $l/k$, otherwise $M$ is null.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_2**: @username_1: 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$.  
> **username_3**: 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}$.  

---

## 0 answers

