Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

There is the well-known method of unbiasing of bit sequences due to von Neumann. Are there similar schemes applicable to other sequences, e.g. the result of throwing a normal die?

share|improve this question
add comment

3 Answers

You can generalize the von-Neumann procedure canonically. Assume you have a discrete RV $X$ which you want to make fair, i.e., each event in the event space $\Omega$ of $X$ shall occur with the same probability. Then you can redraw $X$ exactly $n:=| \Omega|$ times, yielding $x_1, \ldots, x_n$. In case $x_1 \not = \ldots \not = x_n$, you return $x_1$. Otherwise, you repeat the above procedure.

Since the probability of drawing $x_1, \ldots, x_n$ differently is just a product of probabilities, the order of the elements does not matter. Hence, the probability of drawing an element $x$ at position $1$ is just $1/n$.

share|improve this answer
    
Hypothetically assuming that one has an almost perfect die, wouldn't that procedure be rather expensive in practice? –  Mok-Kong Shen Feb 4 '13 at 14:33
    
[Addendum] Maybe a dumb question: Wouldn't the result of applying the procedure to repetitions of a segment of length n, in which all elements are different, lead to something evidently inacceptable? –  Mok-Kong Shen Feb 4 '13 at 14:56
    
The above procedure is of course very expensive, even to correct an already fair RV you need an expected number of $n!$ tries. With bias, it only gets worse. The question didn't involve efficienty though.. –  HdM Feb 4 '13 at 15:17
    
Could you also comment on my addendum? –  Mok-Kong Shen Feb 4 '13 at 15:33
    
I don't understand what you are asking in your addendum. What will be inacceptable? What exactly do you want to repeat? The von Neumann method does not repeat sequences, in each step there are $n$ values drawn according to $X$. –  HdM Feb 4 '13 at 20:25
show 2 more comments

The following simpler adaptation of von Neumann's trick is more efficient than the one described in HdM's answer. Throw your die twice. If the two answers $x,y$ are different, write $0$ if $x<y$ and $1$ if $x>y$. This way, you get an unbiased bit source. If you are so inclined, you can use this bit source to simulate fair die throws.

share|improve this answer
    
I have a little problem of understanding: If one were to apply the same principle to a bit sequence, one wouldn't obtain the original scheme of unbiasing of von Neumann, right? –  Mok-Kong Shen Feb 4 '13 at 16:30
    
On the contrary, this is the original von Neumann scheme. –  Yuval Filmus Feb 4 '13 at 17:33
    
You are right in the above. –  Mok-Kong Shen Feb 4 '13 at 20:53
    
I read somewhere that you can't create e.g. an unbiased 3-die with an unbiased bit source (essentially, $1 / 3$ hasn't got a finite binary expansion). –  vonbrand Feb 5 '13 at 0:03
    
That's correct, if you're only allowed to use a bounded number of bits, then it's impossible. But there is an algorithm which uses $\log_2 3$ (or so) bits in expectation. I believe there was a question regarding this on cs. –  Yuval Filmus Feb 5 '13 at 0:12
add comment

It seems to me that presumably the only viable satisfactory solution would be: Obtain a bit sequence from the sequence from the die, apply the von Neumann unbiasing, then generate from that a sequence for the die.

share|improve this answer
    
No, my solution (for example) is superior than this, since the probability that you don't extract information from two throws is larger in your scheme compared to mine. –  Yuval Filmus Feb 4 '13 at 17:33
    
Could you please give some hints of how to show that? –  Mok-Kong Shen Feb 4 '13 at 21:50
    
Suppose you convert die throws to coin throws by parity. Then my bad throws are 11,22,33,44,55,66 while yours also include 13,15,24,26,31,35,42,46,51,53,62,64. –  Yuval Filmus Feb 4 '13 at 21:53
add comment

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.