Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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 7 at 8:23
    
If one knows the binary expansion of $p$, this procedure can be adapted to work nicely, see expanded answer. –  Did Jul 7 at 8:28
    
The expanded answer is even more awesome. And it is actually a quite canonical procedure, in a certain sense. –  Thomas Klimpel Jul 7 at 8:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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