# Unbiasing of sequences

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?

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.

• 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

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

• 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

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.

• 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