Unbiased random number generator
Clash Royale CLAN TAG#URR8PPP
$begingroup$
we have a six-sided dice numbered from 1 to 6, and each has the probability $p =frac16$. 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^kmapsto 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 $frac110.$
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'=frac110$.
can we maybe also generalize that for$ n$ elements ?
$$ 1,dots 6^kmapsto 1,dots, n $$
I will appreciate any good ideas.
random-number-generator
$endgroup$
add a comment |
$begingroup$
we have a six-sided dice numbered from 1 to 6, and each has the probability $p =frac16$. 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^kmapsto 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 $frac110.$
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'=frac110$.
can we maybe also generalize that for$ n$ elements ?
$$ 1,dots 6^kmapsto 1,dots, n $$
I will appreciate any good ideas.
random-number-generator
$endgroup$
add a comment |
$begingroup$
we have a six-sided dice numbered from 1 to 6, and each has the probability $p =frac16$. 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^kmapsto 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 $frac110.$
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'=frac110$.
can we maybe also generalize that for$ n$ elements ?
$$ 1,dots 6^kmapsto 1,dots, n $$
I will appreciate any good ideas.
random-number-generator
$endgroup$
we have a six-sided dice numbered from 1 to 6, and each has the probability $p =frac16$. 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^kmapsto 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 $frac110.$
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'=frac110$.
can we maybe also generalize that for$ n$ elements ?
$$ 1,dots 6^kmapsto 1,dots, n $$
I will appreciate any good ideas.
random-number-generator
random-number-generator
edited Feb 1 at 0:14
Mohbenay
asked Jan 31 at 23:27
MohbenayMohbenay
797
797
add a comment |
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
Here is the algorithm for $n=10$.
- Throw the dice twice to get $(x,y)$.
- Compute $r=x + 6(y-1)$. If $rle10$, return $r$ and stop.
- If we have reached here, go back to step 1.
Here is the algorithm for general $n$.
- Compute $n=lceil log_6krceil$.
- Throw the dice $n$ times to get $(x_1, x_2, cdots, x_n)$.
- Compute $r=x_1+6(x_2-1)+6^2(x_3-1)+cdots+6^n-1(x_n-1)$. If $rle k$, return $r$ and stop.
- 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 $xnot=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$
add a comment |
$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 $yin1,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
|
show 7 more comments
$begingroup$
If you want unbiased result, then:
- Throw first dice, this is uniform in 1-6
- Throw another one, check parity if it is odd add 6
- Here it doesn't matter what split you choose, just aim at $frac12$ probability.
- 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 $2sigma$ 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 $frac16$ or number 7-10 with probability $frac14$, given $frac16$ just throw away 2 samples, to get desired range.
$endgroup$
– Evil
Feb 1 at 9:14
add a comment |
$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♦
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
add a comment |
$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
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f103695%2funbiased-random-number-generator%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here is the algorithm for $n=10$.
- Throw the dice twice to get $(x,y)$.
- Compute $r=x + 6(y-1)$. If $rle10$, return $r$ and stop.
- If we have reached here, go back to step 1.
Here is the algorithm for general $n$.
- Compute $n=lceil log_6krceil$.
- Throw the dice $n$ times to get $(x_1, x_2, cdots, x_n)$.
- Compute $r=x_1+6(x_2-1)+6^2(x_3-1)+cdots+6^n-1(x_n-1)$. If $rle k$, return $r$ and stop.
- 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 $xnot=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$
add a comment |
$begingroup$
Here is the algorithm for $n=10$.
- Throw the dice twice to get $(x,y)$.
- Compute $r=x + 6(y-1)$. If $rle10$, return $r$ and stop.
- If we have reached here, go back to step 1.
Here is the algorithm for general $n$.
- Compute $n=lceil log_6krceil$.
- Throw the dice $n$ times to get $(x_1, x_2, cdots, x_n)$.
- Compute $r=x_1+6(x_2-1)+6^2(x_3-1)+cdots+6^n-1(x_n-1)$. If $rle k$, return $r$ and stop.
- 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 $xnot=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$
add a comment |
$begingroup$
Here is the algorithm for $n=10$.
- Throw the dice twice to get $(x,y)$.
- Compute $r=x + 6(y-1)$. If $rle10$, return $r$ and stop.
- If we have reached here, go back to step 1.
Here is the algorithm for general $n$.
- Compute $n=lceil log_6krceil$.
- Throw the dice $n$ times to get $(x_1, x_2, cdots, x_n)$.
- Compute $r=x_1+6(x_2-1)+6^2(x_3-1)+cdots+6^n-1(x_n-1)$. If $rle k$, return $r$ and stop.
- 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 $xnot=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$
Here is the algorithm for $n=10$.
- Throw the dice twice to get $(x,y)$.
- Compute $r=x + 6(y-1)$. If $rle10$, return $r$ and stop.
- If we have reached here, go back to step 1.
Here is the algorithm for general $n$.
- Compute $n=lceil log_6krceil$.
- Throw the dice $n$ times to get $(x_1, x_2, cdots, x_n)$.
- Compute $r=x_1+6(x_2-1)+6^2(x_3-1)+cdots+6^n-1(x_n-1)$. If $rle k$, return $r$ and stop.
- 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 $xnot=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.
edited Feb 1 at 20:36
answered Feb 1 at 8:04
Apass.JackApass.Jack
11.4k1939
11.4k1939
add a comment |
add a comment |
$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 $yin1,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
|
show 7 more comments
$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 $yin1,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
|
show 7 more comments
$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$
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.
answered Jan 31 at 23:57
gnasher729gnasher729
10.8k1217
10.8k1217
$begingroup$
Or, you know, return $x$ if $yin1,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
|
show 7 more comments
$begingroup$
Or, you know, return $x$ if $yin1,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
$begingroup$
Or, you know, return $x$ if $yin1,2,3$ and $x+5$ otherwise.
$endgroup$
– David Richerby
Feb 1 at 0:14
$begingroup$
Or, you know, return $x$ if $yin1,2,3$ and $x+5$ otherwise.
$endgroup$
– David Richerby
Feb 1 at 0:14
1
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$
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
$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
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$
@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
$begingroup$
Ok, I have checked, it works unbiased.
$endgroup$
– Evil
Feb 1 at 8:52
|
show 7 more comments
$begingroup$
If you want unbiased result, then:
- Throw first dice, this is uniform in 1-6
- Throw another one, check parity if it is odd add 6
- Here it doesn't matter what split you choose, just aim at $frac12$ probability.
- 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 $2sigma$ 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 $frac16$ or number 7-10 with probability $frac14$, given $frac16$ just throw away 2 samples, to get desired range.
$endgroup$
– Evil
Feb 1 at 9:14
add a comment |
$begingroup$
If you want unbiased result, then:
- Throw first dice, this is uniform in 1-6
- Throw another one, check parity if it is odd add 6
- Here it doesn't matter what split you choose, just aim at $frac12$ probability.
- 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 $2sigma$ 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 $frac16$ or number 7-10 with probability $frac14$, given $frac16$ just throw away 2 samples, to get desired range.
$endgroup$
– Evil
Feb 1 at 9:14
add a comment |
$begingroup$
If you want unbiased result, then:
- Throw first dice, this is uniform in 1-6
- Throw another one, check parity if it is odd add 6
- Here it doesn't matter what split you choose, just aim at $frac12$ probability.
- 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 $2sigma$ 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$
If you want unbiased result, then:
- Throw first dice, this is uniform in 1-6
- Throw another one, check parity if it is odd add 6
- Here it doesn't matter what split you choose, just aim at $frac12$ probability.
- 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 $2sigma$ 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.
answered Feb 1 at 1:07
EvilEvil
7,78342446
7,78342446
$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 $frac16$ or number 7-10 with probability $frac14$, given $frac16$ just throw away 2 samples, to get desired range.
$endgroup$
– Evil
Feb 1 at 9:14
add a comment |
$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 $frac16$ or number 7-10 with probability $frac14$, given $frac16$ just throw away 2 samples, to get desired range.
$endgroup$
– Evil
Feb 1 at 9:14
$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
$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
1
$begingroup$
There’s no reason at all to throw out the second dice throw.
$endgroup$
– gnasher729
Feb 1 at 7:44
$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$
@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 $frac16$ or number 7-10 with probability $frac14$, given $frac16$ just throw away 2 samples, to get desired range.
$endgroup$
– Evil
Feb 1 at 9:14
$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 $frac16$ or number 7-10 with probability $frac14$, given $frac16$ just throw away 2 samples, to get desired range.
$endgroup$
– Evil
Feb 1 at 9:14
add a comment |
$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♦
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
add a comment |
$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♦
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
add a comment |
$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$
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.
answered Feb 1 at 9:50
VinceVince
47926
47926
3
$begingroup$
Yes, sure, but this is an answer to a different question.
$endgroup$
– Gilles♦
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
add a comment |
3
$begingroup$
Yes, sure, but this is an answer to a different question.
$endgroup$
– Gilles♦
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
3
3
$begingroup$
Yes, sure, but this is an answer to a different question.
$endgroup$
– Gilles♦
Feb 1 at 10:19
$begingroup$
Yes, sure, but this is an answer to a different question.
$endgroup$
– Gilles♦
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
$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
add a comment |
$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
add a comment |
$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
add a comment |
$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$
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.
answered Feb 2 at 15:22
gnasher729gnasher729
10.8k1217
10.8k1217
$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
add a comment |
$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
$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
$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
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f103695%2funbiased-random-number-generator%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown