4
$\begingroup$

we have a six-sided dice numbered from 1 to 6, and each has the probability $p =\frac{1}{6}$. My task is to create a unbiased method to generate a random number from 1 to 10 using the given dice. I am aware that the method should maps the following set $$ \{1,\dots 6\}^k\mapsto \{1,\dots, 10\}$$, with $k$ is the number of time we throw the dice. For sure not the 36 elements will be mapped into the set containing 1 to 10. What i mean, the method will use a while loop and only stops if a certain tuple is found. My task then is the find those tuples and prove each thoese 10 tuples has the probaitly of $\frac{1}{10}.$ I think $k$ should be 2 in this case , but then i am not quite sure how to extract the 10 elements from 36 elements ($6^k$,with $k=2$) and have a probability of $p'=\frac{1}{10}$. can we maybe also generalize that for$ n$ elements ?

$$ \{1,\dots 6\}^k\mapsto \{1,\dots, n\} $$ I will appreciate any good ideas.

$\endgroup$
3
$\begingroup$

Here is the algorithm for $n=10$.

  1. Throw the dice twice to get $(x,y)$.
  2. Compute $r=x + 6(y-1)$. If $r\le10$, return $r$ and stop.
  3. If we have reached here, go back to step 1.

Here is the algorithm for general $n$.

  1. Compute $n=\lceil \log_6k\rceil$.
  2. Throw the dice $n$ times to get $(x_1, x_2, \cdots, x_n)$.
  3. Compute $r=x_1+6(x_2-1)+6^2(x_3-1)+\cdots+6^{n-1}(x_n-1)$. If $r\le k$, return $r$ and stop.
  4. If we have reached here, go back to step 2.

There are many variations, of course.

For example, in step 2 for $n=10$, we can return $r=10 - (x + 6(y-1))\%10$ and stop when $x+6(y-1)\le30$ instead. This will reduce the chance to go to step 2. Here % is the remainder operator.

For example, here is gnasher729's algorithm for $n=10$. Throw a dice until we get a number $x\not=6$. Throw the dice once more to get another number $y$. Return ((x - 1) * 6 + (y - 1))%10+1$.


(Exercise 1.) (One minute or less) Devise an algorithm for $n=3$.

(Exercise 2.) Devise an algorithm for $n=7$. Try making its expected number of rolls as small as possible.

(Exercise 3.) Prove that the expected number of rolls in gnasher729's algorithm is the minimum among all algorithms.

(Exercise 4.) Given any $n>1$, devise an algorithm with the least expected number of rolls.

$\endgroup$
2
$\begingroup$

Throw a dice until your number is not a six, giving a number x = one to five. Throw the dice once more, giving a number y = one to six. There are thirty combinations.

Calculate (x - 1) * 6 + (y - 1), take the last digit of the result, then add 1.

$\endgroup$
  • $\begingroup$ Or, you know, return $x$ if $y\in\{1,2,3\}$ and $x+5$ otherwise. $\endgroup$ – David Richerby Feb 1 at 0:14
  • 1
    $\begingroup$ Downvote without stating reason seems futile to me, someone cares to share? BTW @gnasher729 are you sure your probabilities are equal (it seems biased)? $\endgroup$ – Evil Feb 1 at 1:26
  • $\begingroup$ Last digit of a number from 0 to 29, plus 1 to get it in the right range. $\endgroup$ – gnasher729 Feb 1 at 7:41
  • 1
    $\begingroup$ @Evil My downvote was because the scheme is unnecessarily complicated, using a mysterious formula with no explanation (so mysterious that you thought it was wrong!), when a much simpler formula works just fine. $\endgroup$ – David Richerby Feb 1 at 7:51
  • $\begingroup$ Ok, I have checked, it works unbiased. $\endgroup$ – Evil Feb 1 at 8:52
1
$\begingroup$

If you want unbiased result, then:

  1. Throw first dice, this is uniform in {1-6}
  2. Throw another one, check parity if it is odd add 6
    • Here it doesn't matter what split you choose, just aim at $\frac{1}{2}$ probability.
  3. if result is 11 or 12 discard results and start from 1.

$k$ is 2 here, to get one result, but since this is rejection sampling, at average you need more than one pair. We cannot reuse failed sample, as this introduces bias.

By the way, it is tempting to multiply two results, discard anything that is greater than 27 and divide by 3 discarding reminder, but it is cutted $2\sigma$ Gaussian distribution, not uniform.

Solution for 1-10 is hand tailored, but with general procedure you could generalise to 1 to N uniform random distribution with M-sided dice or use bits of entropy extraction to produce bit sequences.

$\endgroup$
  • $\begingroup$ i don t really understand how it is done , can your for example make a small demo ?. thank you $\endgroup$ – Mohbenay Feb 1 at 7:35
  • 1
    $\begingroup$ There’s no reason at all to throw out the second dice throw. $\endgroup$ – gnasher729 Feb 1 at 7:44
  • $\begingroup$ @gnasher729 in rejection sampling from book, there are more throws on average than in your method, this one should be easier to understand (I failed here probably) and straightforward to prove. $\endgroup$ – Evil Feb 1 at 9:09
  • $\begingroup$ @Mohbenay throw one dice (random K6), result was 4. Throw another one, result is 5, so return 4 + 6 = 10. Another trial, (random K6), result is 5, throw another one, result is 1, return 11, which is too big. Rethrow. 1st dice returns 1, throw second one, result is 6, so return 1. The aim of this method is to get uniform number from 1-6, with probability $\frac{1}{6}$ or number 7-10 with probability $\frac{1}{4}$, given $\frac{1}{6}$ just throw away 2 samples, to get desired range. $\endgroup$ – Evil Feb 1 at 9:14
1
$\begingroup$

This is not an answer but a global analysis.

I see 3 answers here which are exactly the same. In any you may have to re-roll infinitly dices. The question is why ?

Just build the prime factorization of:

  • you want 10 = 5 x 2
  • you have 6 = 3 x 2

A dice cannot create a random (with homogeneous probability) choice which is not one of its prime component. Thus build the 2 is easy but the 5 is basically impossible. You have to cancel (re-roll) some values to change the nature of your dice. Here, one side of a dice is re-rolled to build a 5-sided dice.

You can apply this analysis to any values for this problem.

$\endgroup$
  • 3
    $\begingroup$ Yes, sure, but this is an answer to a different question. $\endgroup$ – Gilles 'SO- stop being evil' Feb 1 at 10:19
  • $\begingroup$ @Gilles ... or it goes far deeper in the question ? But if you prefer a ready-to-use algorithm than the method to build it.... $\endgroup$ – Vince Feb 1 at 10:27
0
$\begingroup$

Here's a general solution: Assume you have an unbiased dice with D faces, numbered 0 to D-1 (for example D = 6). Assume you want to find one of N numbers, 0 to N-1.

Start with s = 0, S = 1. s is the current state, S is the number of possible states. We will always have 0 ≤ s < S.

Throw the dice, throwing a number d, 0 ≤ d ≤ D-1. Replace s with sD + d, and S with SD. Calculate m = S % N. If s < S - m then finish with the number s % N (the number of possible values s < S - m is a multiple of N). Otherwise, replace s with s - (S - m), replace S with S - (S - m), and throw the dice again.

$\endgroup$
  • $\begingroup$ I tried to run your algorithm with D=6 and N=10 and it seems to get into an infinite loop with probability 1/6. $\endgroup$ – Valentas Feb 7 at 15:39

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.