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?


2 Answers 2


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

  • 3
    $\begingroup$ 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$? $\endgroup$ Commented Sep 26, 2013 at 1:21
  • $\begingroup$ Yeah, that's an admittedly simpler method. :) $\endgroup$ Commented Sep 26, 2013 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$.

  • $\begingroup$ 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. $\endgroup$ Commented Sep 26, 2013 at 21:27
  • $\begingroup$ 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). $\endgroup$
    – siravan
    Commented Sep 26, 2013 at 21:59
  • $\begingroup$ 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). $\endgroup$
    – siravan
    Commented Sep 26, 2013 at 23:08
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Sep 26, 2013 at 23:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.