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)

  • 0
    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.2012-02-02
  • 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$.

  • 3
    Moreover, with probability 1, this algorithm eventually succeeds. However, the number of flips needed is unbounded (it is geometrically distributed).2012-02-02
  • 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.2012-02-02
  • 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.2012-02-02
  • 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.2012-02-02
  • 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.)2012-02-02
  • 0
    For a better optimization, whenever you throw away a pair of equal outcomes, feed their common value into an auxiliary extractor (which needs to be separate because its input has a different bias) and see if _it_ happens to give you an unbiased bit out. Continue recursively for a few dozen levels. This ought to yield you almost all of the information content of the original bit stream. (And each level contains at most one bit at any point in time, so it takes up finite space).2012-02-02
  • 0
    So this has the advantage of your not need to know the value $p$, which is nice. However, the "throw away $HH$ and $TT$" part of the procedure means that there isn't really a _proposition_, a set of binary strings, that has probability 1/2.2012-02-03
  • 0
    Why not? You could rephrase the event into a proposition, no?2012-02-04
  • 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$.