5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Feb 4 '13 at 16:30
  • $\begingroup$ On the contrary, this is the original von Neumann scheme. $\endgroup$ Feb 4 '13 at 17:33
  • $\begingroup$ You are right in the above. $\endgroup$ Feb 4 '13 at 20:53
  • $\begingroup$ 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). $\endgroup$
    – vonbrand
    Feb 5 '13 at 0:03
  • $\begingroup$ 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. $\endgroup$ Feb 5 '13 at 0:12
3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Hypothetically assuming that one has an almost perfect die, wouldn't that procedure be rather expensive in practice? $\endgroup$ Feb 4 '13 at 14:33
  • $\begingroup$ [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? $\endgroup$ Feb 4 '13 at 14:56
  • $\begingroup$ 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.. $\endgroup$
    – HdM
    Feb 4 '13 at 15:17
  • $\begingroup$ Could you also comment on my addendum? $\endgroup$ Feb 4 '13 at 15:33
  • $\begingroup$ 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$. $\endgroup$
    – HdM
    Feb 4 '13 at 20:25
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Feb 4 '13 at 17:33
  • $\begingroup$ Could you please give some hints of how to show that? $\endgroup$ Feb 4 '13 at 21:50
  • $\begingroup$ 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. $\endgroup$ Feb 4 '13 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.