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