# simulating a fair random process with an unfair one.

Let's say I have a stochastic process that outputs $1$ or $0$ with probability $p$ or $1-p$ respectively, $p\neq 1/2$. Let's assume this is a repeatable iid process. So I can generate $X_1,X_2\dots$ which are each $1$ or $0$ as above. Can I create a proposition (a logical construction out of the $X_i$s) with probability a half. That is, can I simulate a fair process with this unfair one.

If $p=1$ or $p=0$ then obviously no. But (without loss of generality let's assume $1>p>1/2>1-p>0$. Is there always some such proposition? I can get arbitrarily close, sure. Think about the set of binary strings of length $n$ (you can think of my stochastic process as generating these sequences with certain probabilities). For large enough $n$, even the most likely of them is less than a half, and by picking the right ones to go in my "proposition" I can get as close to $1/2$ as I like, as long as I can increase $n$ as much as I want.

For some values of $p$ you can get to exactly $1/2$. For example, take $p(2-p)=1/2$ and solve for $p$. For this value, $X_1 \lor X_2$ has probability exactly $1/2$. Is it always possible to find a proposition that has exactly probability a half? Or is there a characterisation of the values of $p$ that you can do this for?

(Wasn't entirely sure what tags were appropriate)

-
You can certainly do the simulation, since $01$ has the same probability as $10$. In general, a proposition that uses $\le N$ of the $X_i$ won't work. – André Nicolas Feb 2 '12 at 18:37
Techniques for doing this are called Decorrelation or "whitening" – Ben Jackson Feb 2 '12 at 21:37

If $p$ is a rational with denominator $b$, any event depending on $X_1, \ldots, X_n$ has a probability of the form $k/b^n$ for some integer $k$. in particular, if $b$ is odd you can't obtain exactly $1/2$ from a finite number of trials. If $p$ is transcendental, you can't get any rational probabilities other than $0$ and $1$.

If you are willing to allow a proposition that can take arbitrarily many trials to decide, you can always get exactly $1/2$.

-

Take a coin that has a probability of heads being $p$ and tails being $1-p$. Now, throw the coin twice.

If you get two heads or two tails, discard the result and throw again. If you get head then tail, this happens with probability $p(1-p)$. So does tail then head. But since you discard the results with two heads and two tails, the a posteriori probability of head and tail (or tail and head) is $1/2$.

-
Moreover, with probability 1, this algorithm eventually succeeds. However, the number of flips needed is unbounded (it is geometrically distributed). – Nate Eldredge Feb 2 '12 at 18:42
To reduce (roughly by half) the number of throws, you can discard the old result and keep the recent. I.e., throw the coin till you get two succesive results that are distict. – leonbloy Feb 2 '12 at 19:10
@leonbloy: That doesn't sound right. If you do that, then if the very first throw is heads, then the first distinct pair will be (heads, tails), so it's equivalent to just throwing the coin once. – Jefromi Feb 2 '12 at 20:26
@Jefromi: you're right! It's true that, in a double toss, the sequence TH is as probable as the secuence HT; but that does NOT implies that, if we seek the first distinct pair in a random toss sequence, the TH is as probable as HT. Please, disregard my comment above. – leonbloy Feb 2 '12 at 20:50
+1. This transformation is often called "the von Neumann extractor", after John von Neumann, who introduced it. ("Extractor" in that it "extracts" an unbiased random bit-stream from a biased one.) – ruakh Feb 2 '12 at 20:51

Yes, and the idea of doing things with a target distribution given only access to a different distribution is related to concepts like rejection sampling and importance sampling.

-