2
$\begingroup$

I want to get random decimal digits out of a 6-faced die.

Let's say the die is fair, with an equal probability for each outcome. (But feel free to share any consequences of that not being true, if you feel like it.)

I will represent the outcome of a die roll as a base-6 number:

  • In base-6 there are only 6 possible digits: $\{0,1,2,3,4,5\}$.
  • The die has faces numbered 1 to 6.
  • Face $f$ corresponds to digit $f-1$.

Thus, I can represent as many die rolls as I like with a base-6 number:

  • If the die is rolled once:
    • Let's say the die stopped on face $5$.
    • The final base-6 number will be $4$.
  • If the die is rolled twice:
    • Let's say the die stopped on face $5$.
    • And then on face $3$.
    • The final base-6 number will be $42$.
  • If I roll the dice 10 times:
    • Let's say the die stopped sequentially on faces $5$, $3$, $4$, $6$, $2$, $3$, $3$, $3$, $2$, and $4$.
    • The final base-6 number will be $4235122213$.

Since I want decimal digits, I need to convert to base-10.

  • Base-6: $4235122213$
  • Base-10: $44753985$

For any given number of die rolls, how many different combinations exist? If there are $r$ die rolls, the total of possible combinations is $6^r$.

  • $r$ rolls — $6^r$ different combinations.
  • $0$ rolls — only $1$ combination.
  • $1$ roll — $6$ different combinations.
  • $2$ rolls — $36$ different combinations.
  • $3$ rolls — $216$ different combinations.
  • $4$ rolls — $1296$ different combinations.
  • $5$ rolls — $7776$ different combinations.
  • $6$ rolls — $46656$ different combinations.
  • $7$ rolls — $279936$ different combinations.
  • $8$ rolls — $1679616$ different combinations.
  • $9$ rolls — $10077696$ different combinations.

$n_r$ ($\in \mathbb{N_0}$) is the number obtained after $r$ die rolls through the process described previously: "If the die is rolled once, twice, ..."

It is impossible for $n_r$ to reach the number of possible different combinations ($6^r$). It will be always short by least $1$:

$$ 0 \leqslant n_r < 6^r $$

  • $r$ rolls — $n_r$ never surpasses $6^r-1$.
  • $0$ rolls — $n_r$ never surpasses $0$.
  • $1$ roll — $n_r$ never surpasses $5$.
  • $2$ rolls — $n_r$ never surpasses $35$.
  • $3$ rolls — $n_r$ never surpasses $215$.
  • $4$ rolls — $n_r$ never surpasses $1295$.
  • $5$ rolls — $n_r$ never surpasses $7775$.
  • $6$ rolls — $n_r$ never surpasses $46655$.
  • $7$ rolls — $n_r$ never surpasses $279935$.
  • $8$ rolls — $n_r$ never surpasses $1679615$.
  • $9$ rolls — $n_r$ never surpasses $10077695$.

I can never trust the leftmost nor the rightmost digit (fringe digits), since the possible values are potentially restricted.

  • For $0$ rolls, the outcome is always $0$.
  • For $1$ roll, the fringe digit never surpasses $5$.
  • For $2$ rolls, the leftmost digit never surpasses $3$, and the rightmost, $5$.
  • For $3$ rolls, the leftmost digit never surpasses $2$, and the rightmost, $5$.
  • For $4$ rolls, the leftmost digit never surpasses $1$, and the rightmost, $5$.
  • For $5$ rolls, the leftmost digit never surpasses $7$, and the rightmost, $5$.
  • For $6$ rolls, the leftmost digit never surpasses $4$, and the rightmost, $5$.
  • For $7$ rolls, the leftmost digit never surpasses $2$, and the rightmost, $5$.
  • For $8$ rolls, the leftmost digit never surpasses $1$, and the rightmost, $5$.
  • For $9$ rolls, the leftmost digit never surpasses $1$, and the rightmost, $5$.

The other digits seem perfectly random to me though. Am I wrong?

$\endgroup$
  • $\begingroup$ What are you trying to accomplish? $\endgroup$ – Aksakal Jul 11 '16 at 16:03
  • $\begingroup$ "I can never trust the leftmost nor the rightmost digit (fringe digits), since the possible values are potentially restricted." I think you ought to clarify what you mean by this - I presume you mean that any digit (0, 1, 2, ..., 9) has an equal probability, 0.1, of occurring. Now actually that won't turn out quite to be the case but I still think this is an interesting question (+1). $\endgroup$ – Silverfish Jul 11 '16 at 16:06
  • $\begingroup$ You may can try to make a code to see if it's on the right way $\endgroup$ – el Josso Jul 11 '16 at 16:08
  • $\begingroup$ And the rightmost can surpasse 5, for example you rolls twice, imagine you have 21. so th final base-6 number will be 10, and so 6 in base-10. $\endgroup$ – el Josso Jul 11 '16 at 16:12
  • $\begingroup$ And it's the same for the leftmost ,for examplefor 4 rolls, imagine you have 1121. so th final base-6 number will be 0010, and so 6 in base-10, it's more than 1 $\endgroup$ – el Josso Jul 11 '16 at 16:14
2
$\begingroup$

I want to get random decimal digits out of a 6-faced die.

I assume you mean that you want a uniform distribution.

Following this Rosetta Code task, here's a method that's easy to implement and obviously correct, although it doesn't use input entropy with maximum efficiency. Roll two zero-based six-sided dice, let $x$ and $y$ be the respective results, and let $n = 6x + y$. If $n ≥ 30$, reroll and start over. Otherwise, return the floor of $n/3$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ +1 A good and appropriate answer. Your reference to "maximum efficiency" inspired me to supplement this answer with a description of such an algorithm. A full explanation takes a little more space than allowed in comments, though, so I posted it as a separate answer. $\endgroup$ – whuber Jul 11 '16 at 22:25
2
$\begingroup$

A fast and efficient method to generate $m$ independent uniform digits in base $r$ using a $d$-sided die is to label the faces of the die with the digits $0$ through $d-1$ and roll the die repeatedly (say $n$ times) to generate a string of such digits

$$a_1\,a_2\,a_3\,\cdots\,a_n.$$

Interpret this sequence as the interval of all numbers $$[X,Y)$$ for which

$$X = [0. a_1a_2a_3\cdots a_n]_d = \sum_{i=1}^n a_i d^{-i}$$

and $Y = X + d^{-n}$ is the next largest $n$-digit number in base $d$. There are $d^n$ such intervals, each of equal probability, partitioning the unit interval $[0,1)$. Thus, any method of selecting a number $U\in[X,Y)$ will approximate a continuous uniform distribution up to an error of no greater than $d^{-n}$. We may therefore use $U$ in the usual way to generate a random sequence of nearly independent uniform random base-$r$ digits: namely, expand $U$ in base $r$

$$U = [0. b_1b_2b_3\cdots]_r = \sum_{i=1}^\infty b_i r^{-i}$$

and read off the first $k$ digits $b_1, b_2, \ldots, b_k$. Stop when $r^{-k}$ becomes appreciable in size compared to $d^{-n}$.

We don't actually need to construct $X, Y,$ or $U$ explicitly. Let $X_i$ be the partial sum of $X$ out to $i$ base-$d$ digits. The initial output $b_1$ will be determined once the interval $[X_i,X_i+d^{-i-1})$ is found to lie between $b_1$ and $b_1 + r^{-1}$. At this point, output $b_1$ and replace $X_i$ by $rX_i - b_1$ (which strips the first base-$r$ digit off $X$). Repeating this procedure $m$ times simultaneously expands $U$ in base $d$ and converts it to base $r$ until $m$ base-$r$ digits are reliably produced.

The number of random base-$d$ digits used to generate $m$ base-$r$ digits will, with extremely high probability, be extremely close to $m\log(r)/\log(d)$. In the case $d=6$ and $r=10$ it amounts to $1.28509\ldots$ rolls of the die for each decimal digit of output on average. That's the best that can be done.

This procedure is related to a method to flip one (biased) coin to emulate another coin with a different bias: see https://stats.stackexchange.com/a/209229/919.

Note that the case $d=2$ corresponds to how binary digital computers already generate uniform random variates $U$. This algorithm merely describes how we could go about generating base-$r$ digits on a computer that operates natively in base $d$ (and therefore will have a pseudorandom number generator that produces $X$ directly).


Here is working R code. It is unvectorized and therefore relatively slow--but it's not too bad: it takes around $9$ seconds per million output digits. It ends by displaying the histogram of the output and performing a chi-squared test of uniformity of the distribution.

m <- 1e5 # Number of base-r digits to output
d <- 6
r <- 10

p <- 0 # Start of the working interval
q <- 1 # End of the working interval
m.0 <- ceiling(m * log(r)/log(d)) + 10 # Generate a few digits more than needed.
a <- sample.int(d, m.0, replace=TRUE) - 1
x <- rep(NA, m)
i <- 0 # Indexes the base-d digits
j <- 0 # Indexes the base-r digits
while (j < m) {
  i <- i+1
  delta <- (q-p)/d
  p <- p + a[i]*delta
  q <- p + delta
  b <- floor(p*r)
  while (b == floor(q*r)) {
    j <- j+1
    x[j] <- b
    p <- r*p - b
    q <- r*q - b
    b <- floor(p*r)
  }
}
#
# Test the homogeneity of the output.
#
hist(x[1:j], breaks=0:r-1/2)
chisq.test(tabulate(x+1, nbins=r))
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ A failed chi-squared test isn't evidence of uniformity, because failure to reject a null hypothesis isn't evidence in favor of the null hypothesis—right? $\endgroup$ – Kodiologist Jul 12 '16 at 0:52
  • $\begingroup$ @Kodiologist What do you mean by a "failed" test? Regardless, failure to reject the null is not proof of the null. But it's the only way one has of testing random number generators. The standard method is to apply several dozen tests--of uniformity, correlation, and so on--in an effort to prove the RNG is not random. If you apply enough tests to a pseudo RNG, you will be able to demonstrate it is not random. The important question therefore is how does any pseudo RNG deviate from random behavior. This one at least produces uniform digits. $\endgroup$ – whuber Jul 12 '16 at 12:57
  • $\begingroup$ A failed test is one that failed to reject the null hypothesis. $\endgroup$ – Kodiologist Jul 12 '16 at 15:07
  • 1
    $\begingroup$ @Kodiologist Since "failed to reject" is a double negative, I believe many people would understand a "failed test" to be one where the null "failed": that is, it was rejected. This is a good example of why statistics adopts technical terms in favor of colloquial terms for communication. In this instance, the result is called "positive" when the null is rejected and otherwise is called "negative." Although that terminology, too, can be confusing, it is standard and well-defined. $\endgroup$ – whuber Jul 12 '16 at 15:23
1
$\begingroup$

Edit: My answer uses binning just like @gunes' answer, but my algorithm uses uniformly distributed numbers instead of a bell curve distribution. The binning is also done by taking mod 10 instead of a more complicated procedure that a bell curve would require. In fact, the fast version of the following algorithm is so simple it can actually be done with a real die and mental arithmetic if you know your times table for 6 up through $6 \times 6$. I tested it myself with a real die and it takes only a few seconds with $N = 4$ rolls to actually generate an emulated value of rolling a 10-sided die.

A Simple Algorithm

We start with the standard 6-sided die with faces from the set $[1:6] = \{ 1, 2, 3, 4, 5, 6\}$. Choose the number $N$ which will be the number of times we roll this 6-sided die (larger $N$-values will make the resulting emulated roll of a 10-sided die closer to being uniformly distributed. There's a formula below for exactly what these probabilities will be in terms of $N$). Then let $d_n$ denote the result of the $n^\text{th}$ roll. The algorithm is as follows:

  1. Let $r \leftarrow d_1 - 1$
  2. For $n = 2, \dots , N$, let $r \leftarrow \text{mod} (r + 6(d_n - 1), 10)$
  3. Return the result $r + 1$, which will be approximately uniformly distributed on the values $[1:10]$. (Alternatively, since $r$ is a number in $[0:9]$, you could just interpret $0$ as $10$ instead of adding 1 to $r$).

Note: I have the minus 1's in the algorithm to help explain how it works, but they aren't necessary. For a truly fast algorithm, you can simply do

  1. Let $r \leftarrow d_1$
  2. For $n = 2, \dots , N$, let $r \leftarrow \text{mod} (r + 6(d_n), 10)$
  3. Return the result $r + 1$.

An Example Run

Let's choose $N = 4$. Then suppose we roll the 6-sided die once and our first roll is $d_1 = 6$. We set $r \leftarrow d_1 - 1 = 5$.

Now roll a second time and supposed we get $d_2 = 4$. We compute $6(d_2 - 1) = 18$. Because we are only interested in the sum mod 10, we can "forget" the tens place at each step. Interpret all "=" as equal mod 10 from this point forward. So the update for $r$ is $r \leftarrow r + 6(3) = 5 + 18 = 5 + 8 = 13 = 3$.

We repeat this process. If the third roll is $d_3 = 1$, then $6(d_3 - 1) = 0$, and we update $r \leftarrow r + 0 = 3$, which happens to be the same as the previous step.

If the last roll is $d_4 = 5$, we update $r \leftarrow r + 6(d_4 - 1) = 3 + 6(4) = 3 + 24 = 3 + 4 = 7$.

The result of the emulation is then $r + 1 = 7 + 1 = 8$ in this example.

Why it Works

First, note that the following Lemma holds:

Lemma: For all integers $n \ge 1$, $\text{mod}(6^n, 10) = 6$. In other words, every power of 6 (with $n \ge 1$) has a 6 in the ones place.

Proof: The proof is a simple induction proof. See here for details.

Now, each roll minus one of the 6-sided die is a uniformly random digit in $\{ 0, 1, 2, 3, 4, 5 \}$. Put the $N$ digits together and you get the senary (base-6) representation of a number in $\{ 0, 1, \dots, 6^N - 1\}$. In the above example with $N = 4$ and $(d_4, d_3, d_2, d_1) = (5, 1, 4, 6)$, we first subtract one from every roll to get the numbers $(4, 0, 3, 5)$. Interpret these as the senary number $$4035_6 = 4(6^3) + 0(6^2) + 3(6^1) + 5(6^0) = 887,$$ which we take mod 10 of to get $r = 7$, and the resulting roll is $r + 1 = 8$. The Lemma above lets us simplify the computation by "forgetting" the tens place repeatedly in the powers of 6 (which will then always give us 6 in the ones place), which makes the shortcut of updating $r \leftarrow \text{mod} (r + 6(d_n - 1), 10)$ instead of having to calculating the full base 10 representation of the senary number.

Because each digit of the senary number is uniformly distributed and independent, the senary number is itself uniformly distributed as well on the set $[0:6^N - 1]$. Taking mod 10 then partitions this set into 10 bins. Unfortunately, because of the Lemma above, the last four bins will always be one possibility short of the first six, so each bin won't quite have the same probability. However, we can compute these probabilities exactly as $$ P(r + 1 = i) = \begin{cases} \left( \left\lfloor{6^N / 10}\right\rfloor + 1 \right)/6^N , & \text{ if } i = 1, 2, \dots, 6 \\ \left \lfloor{6^N / 10}\right \rfloor /6^N , & \text{ if } i = 7, 8, 9, 10 \\ \end{cases} $$ where $\lfloor{\cdot}\rfloor$ is the floor function. With $N = 4$, these probabilities are $0.1003086$ and $0.0995370$ respectively, which is a pretty good approximation of the desired value of $0.1$. In my subjective opinion, for a tabletop game $N = 2$ and $N = 3$ don't seem like good enough approximations, but $N = 4$ seems passable.

A Julia Simulation for $N = 2, 3, 4$

Here's some simulation code in the Julia Language to test the algorithm

"""Run one emulated roll of a 10-sided die using a 6-sided die"""
function emulate_10_sided(N)
    r = rand(1:6) - 1
    for n = 2:N
        r = mod(r + 6(rand(1:6) - 1), 10)
    end
    return r + 1
end

"""Run `iters` emulated rolls of a 10-sided die using a 6-sided die"""
function emulate_10_sided(N, iters)
    [emulate_10_sided(N) for i = 1:iters]
end

# Plot the results histogram
using Plots
n_trials = 1000000 # Number of trials to average over
theme(:dark)
histogram(emulate_10_sided(2, n_trials), legend=false, normalize=:probability,
    ylim=(0, .12), title="Simulated Probabilities with N = 2")
histogram(emulate_10_sided(3, n_trials), legend=false, normalize=:probability,
    ylim=(0, .12), title="Simulated Probabilities with N = 3")
histogram(emulate_10_sided(4, n_trials), legend=false, normalize=:probability,
    ylim=(0, .12), title="Simulated Probabilities with N = 4")

which generates the following plots:

enter image description here

enter image description here

enter image description here

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Assuming you can differentiate the six-sided dice (or just roll them one at a time) there are 36 ordered pairs in two rolls. So a simple method to get what you want is to roll a pair of six-sided dice, choose 6 outcomes that you will reroll, and then divide the remaining 30 outcomes into three lots of 10, corresponding to the number for your 1D10 roll. There are many ways you can do this, but here is one simple way:

  • Roll 2D6 and denote the rolls by $X_1$ and $X_2$.

  • If $X_2=6$ then reroll that die; continue re-rolling that die until $X_2 \neq 6$.

  • Set your outcome value to:

$$Y = \begin{cases} X_2 & & \text{ if } X_1 \text{ is odd}, \\[6pt] X_2 + 5 & & \text{ if } X_1 \text{ is even}. \\[6pt] \end{cases}$$

It is easy to show that $Y \sim \text{U} \{ 1,...,10 \}$ which meets your requirements.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

One simple algorithm I could think of is using the distribution of sum of $N$ dice. It'll have a bell shaped distribution, and you can bin the results so that they correspond to regions with specified probabilities for the 10-face die. For example, for a fair 10-face die, we'd split the distribution into ten equal pieces (in terms of probability masses).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very interesting. It will have to be tested with different N to see which N is closest to the fair 10-face dice with added constraints such as N "not too large" which remains to be defined but N > 4 seems impractical. $\endgroup$ – Rodolphe Sep 9 at 11:37
  • $\begingroup$ I think it’ll get better as $N$ increases $\endgroup$ – gunes Sep 9 at 11:38
0
$\begingroup$

If re-rolls are allowed (which is unclear from your question, but nothing seems to prevent it from the problem setup), there is a fairly easy solution.

For simplicity (but it's not required), suppose you can distinguish two 6-sided dice (e.g., one red and one blue die). Then roll both dice:

  1. If the red die is 6, re-roll again until you get a number between 1-5.
  2. If the blue die is between 1-3, the result you want is the result of the red die.
  3. If the blue die is between 4-6, add 5 to the red die.

There is no approximation here: this algorithm returns a random draw $\sim$ DiscreteUniform(1,10), as per rolling a 10-sided die.

Remarks:

  • The only disadvantage is that you may have to re-roll sometimes, but the other solutions here seem much more complicated.

  • Even if you cannot physically distinguish dice, you can still run the above algorithm. Do the same thing as above, just call the first die you roll "the red die" and then you roll "the blue die".

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Quick and dirty solution, if you don't mind rerolling the dices sometimes:

  1. Throw one dice. If it displays 6, reroll it, until you get number between 1 - 5.
  2. Throw second dice. If the number is even, add +5 to the result.(If it's odd, do nothing).

--> By summing the results from both throws, you get number from uniform distribution between 1-10.

edit: I see that my answer is esentially the same as by @lacerbi.

| cite | improve this answer | |
$\endgroup$

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.