# Smoothly leaking information over time

Say I have a one bit random variable $X \in \{0,1\}$, and let $n$ be a natural number. I want a sequence of random variables $0 = X_0, X_1, \ldots, X_n = X$ s.t.

$$H\left(X~|~\{X_0,\ldots,X_k\}\right) = 1-\frac{k}{n}$$

That is, each additional $X_k$ provides $1/n$ of the information of $X$, until everything is revealed by $X_n = X$. Is there a nice construction for this sequence?

Via Michael Kass: let $Y(t)$ be a Wiener process starting at $Y(0) = X$, and define

$$f(t) = H(X~|~Y(t))$$

Then $f(0) = 0$, $f(\infty)=1$, and $f(t)$ is smoothly strictly increasing in between. Thus, for any $k$ we can find $0 \le t \le \infty$ s.t. $X_k = Y(t)$ has the desired conditional entropy ($t$ will be a decreasing function of $k$).

• Couldn't you simply take $X_k = X \oplus Y_k$ where $\oplus$ is XOR and $Y_k$ is independent Bernoulli with mean $p_k$? – Sasho Nikolov Sep 26 '13 at 1:21
• Yeah, that's an admittedly simpler method. :) – Geoffrey Irving Sep 26 '13 at 5:17

The problem with the previous construction is that there is no guarantee that $X$ is unequivocally revealed after $n$ bits are transmitted (which seems to be a requirement). Here is a similar construction that works if $n$ is odd. Generate $n$ random bits with probability of 1/2, $S=Y_0, Y_1,...$. Let $N(0)$ and $N(1)$ be the number of 1 and 0 in $S$. Now, transmit S if either $X=1$ and $N(1)>N(0)$ or $X=0$ and $N(1)<N(0)$; otherwise transmit the one complement of $S$.

• I'm confused though. In this process, say that $n=3$. If the first two bits sent are 01 or 10, then the probability of X being 1 conditioned on seeing these bits is 1/2. The same is true if we see 11 or 00. Then the entropy of the conditional distribution is not 1/3 as required. – Suresh Venkat Sep 26 '13 at 21:27
• If $X$ is 1, the first two transmitted bits cannot be 00. Then the last bit adds 1/2 bits of information with a probability of 2/3 (the first two bits 01 or 10) and 0 bits of information with a probability of 1/3 (11, because no matter what the result is 1). – siravan Sep 26 '13 at 21:59
• Correction. My previous analysis is not correct. I think there are two ways to look at it. The algorithm is symmetrical on bits and transmits one total bit of information, so each bit should contribute 1/n bits of information. But if we want to calculate the conditional probabilities, things gets messy. I believe the situation is a variant of the Monty Hall problem (en.wikipedia.org/wiki/Monty_Hall_problem). – siravan Sep 26 '13 at 23:08
• The random walk method does unconditionally reveal X by the end, since the final value sent would be $Y(0) = X$. However, it requires sending real numbers rather than bits. – Geoffrey Irving Sep 26 '13 at 23:21