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

<p>$$f(t) = H(X~|~Y(t))$$</p>

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

CC BY-SA 3.0
2013-09-26T01:21:12.893Z
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
CC BY-SA 3.0
2013-09-26T05:17:47.510Z
Yeah, that's an admittedly simpler method. :)
Geoffrey Irving
CC BY-SA 3.0
2013-09-26T00:00:21.463Z
2013-09-26T00:00:21.463Z
Geoffrey Irving
<p>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)&gt;N(0)$ or $X=0$ and $N(1)&lt;N(0)$; otherwise transmit the one complement of $S$.</p>

CC BY-SA 3.0
2013-09-26T21:27:28.760Z
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
CC BY-SA 3.0
2013-09-26T21:59:24.723Z
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
CC BY-SA 3.0
2013-09-26T23:08:25.567Z
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 (http://en.wikipedia.org/wiki/Monty_Hall_problem).
siravan
CC BY-SA 3.0
2013-09-26T23:21:07.393Z
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
CC BY-SA 3.0
2013-09-26T20:27:13.883Z
2013-09-26T20:27:13.883Z
siravan
<p>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.</p>

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

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

<it.information-theory><shannon-entropy>
Smoothly leaking information over time
Geoffrey Irving
# Smoothly leaking information over time

(Asked by: username_0 on 2013-09-25)

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?

**Tags:** it.information-theory, shannon-entropy


---

## 2 answers

### Answer by username_0 on 2013-09-26. Score: 2 | Accepted answer

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

> **Comments:**
> **username_1**: 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$?  
> **username_0**: Yeah, that's an admittedly simpler method. :)  

---

### Answer by username_2 on 2013-09-26. Score: 0

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)

> **Comments:**
> **username_3**: 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.  
> **username_2**: 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).  
> **username_2**: 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 (http://en.wikipedia.org/wiki/Monty_Hall_problem).  
> **username_0**: 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.  

---

