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

share|improve this question
    
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
1  
Techniques for doing this are called Decorrelation or "whitening" –  Ben Jackson Feb 2 '12 at 21:37

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer

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

share|improve this answer
3  
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
2  
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
3  
@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
1  
@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
4  
+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.

share|improve this answer

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.