4
$\begingroup$

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)

  • 1
    Techniques for doing this are called [Decorrelation](http://en.wikipedia.org/wiki/Decorrelation) or "whitening"2012-02-02

3 Answers 3

1

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.

7

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

  • 0
    @Raskolnikov well, you could, but it would be infinitely long…2012-02-22
4

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