8
$\begingroup$

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?

Improve this question
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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$ – Sasho Nikolov Sep 26 '13 at 1:21
  • $\begingroup$ Yeah, that's an admittedly simpler method. :) $\endgroup$ – Geoffrey Irving Sep 26 '13 at 5:17
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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$ – Suresh Venkat Sep 26 '13 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 Sep 26 '13 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 Sep 26 '13 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$ – Geoffrey Irving Sep 26 '13 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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