2

Let $X_i$ with $i\in\mathbb N$ be a sequence of independent binary random variables with uniform distribution $\operatorname{Pr}(X_i=1)=\operatorname{Pr}(X_i=0)=0.5$. For $p\in[0,1]$ with $p2^n\in \mathbb N$, it is easy to transform this sequence into a sequence $Y_j$ with $j\in\mathbb N$ of independent binary random variables with biased distribution $\operatorname{Pr}(Y_j=1)=p$, $\operatorname{Pr}(X_i=0)=1-p$. Just take $n$ consecutive outcomes of $X_i$ together (i.e. $X_{nj}, X_{nj+1},\ldots, X_{nj+n-1}$) to produce one outcome of $Y_j$.

But is it possible to also produce a biased distribution for a $p$ not of the form $p2^n\in \mathbb N$, for example for $p=\frac{1}{3}$?

Thomas Klimpel
  • 7,396

1 Answers1

4

No deterministic rule deciding the output based on $n$ consecutive outcomes can work since these yield only binary probabilities. If rejection is allowed though, one can get every $p$. For example, to get $p=\frac13$, take two $X$ outputs, answer $1$ if they are $11$ and $0$ if they are $10$ or $01$. If they are $00$, start again with two new $X$ outputs.

The number of $X$ outputs needed to produce one bit $Y$ is unbounded but the mean number of $X$ per $Y$ output is $\frac83$, which is quite reasonable.

For every rational $p=\frac{a}b$, choose some $k$ such that $2^k\geqslant b$, consider groups of $k$ successive $X$ outputs, allocate $a$ of them to the answer $1$, $b-a$ of them to the answer $0$ and start again if you get any of the $2^k-b$ remaining ones. The mean number of $X$ outputs needed to produce one $Y$ bit is at most $2k$.

For every $p$ in $[0,1]$, a general procedure is available if one knows the binary expansion $p=0.p_1p_2p_3\ldots$ of $p$. Start producing $X$ outputs $x_1$, $x_2$, $x_3$, and so on. As soon as the numbers $p=\sum\limits_{n=1}^\infty\frac{p_n}{2^n}$ and $x=\sum\limits_{n=1}^\infty\frac{x_n}{2^n}$ can be compared, stop and answer $1$ if $x\lt p$ and $0$ otherwise. Note that the process stops almost surely after a finite number of $X$ outputs.

Exercise: Compute the mean number of $X$ outputs per $Y$ output in the general procedure (if you really do the computations, you are in for a surprise).

Did
  • 279,727
  • Cool, I'm glad I asked. But you surely mean one can get every $p\in \mathbb Q\cap[0,1]$, not every $p\in[0,1]$. Or what would you do for $p=1/\sqrt{2}$? – Thomas Klimpel Jul 07 '14 at 08:23
  • If one knows the binary expansion of $p$, this procedure can be adapted to work nicely, see expanded answer. – Did Jul 07 '14 at 08:28
  • The expanded answer is even more awesome. And it is actually a quite canonical procedure, in a certain sense. – Thomas Klimpel Jul 07 '14 at 08:30