3

I am assuming that we can increase the number of dice based on $n$, but they have to be $k$-sided, $k\ge3$.

When I say die types, I mean that we are allowed to use non-standard dice such as non-transitive dice, but we cannot create more die types as we increase $n$. i.e. we have a fixed set of dice from which we can choose from, and we can choose as many as necessary from this set for a given $n$, but we are restricted to choose from this set of dice.

Also, all numbers from $1$ to $n$ should be equally likely in our simulation.

Obinna Okechukwu
  • 1,869
  • 2
    You can do so in a very 'wasteful' matter. As long as the dice produce two outcomes $A_1,A_2$ (possibly more, but we ignore other outcomes) we can simulate a coin toss by considering two outcomes at a time ($A_1 \setminus A_2$ means a zero and $A_2 \setminus A_1$ means a one). Then simulate $\lceil \log_2 n \rceil$ tosses, compute the resulting binary number and add one (and discard any results $>n$). – copper.hat Feb 21 '14 at 23:10
  • Are you requiring that there be finitely many types of dice? (You don't say so, but, if not, then your restriction on increasing types as $n$ increases is no restriction at all.) – msh210 Feb 21 '14 at 23:19
  • Yes. There are finitely many types of dice. We can choose as many as we want of each type. – Obinna Okechukwu Feb 21 '14 at 23:23
  • @copper.hat Is there a solution that involves a fixed number of throws? – Obinna Okechukwu Feb 22 '14 at 00:20
  • @obinna No, of course it cannot be done in fixed number of throws, unless $n$ happens to divide into some fixed power of $k$ (replace $k$ by "product of $k$-values" if there are multiple die types). – Erick Wong Aug 18 '14 at 09:32

2 Answers2

3

Hint:

  • You can simulate a $n$-sided die with only fair-coin throws (a biased coin would also work, but with more throws).
  • Throw a coin $k = \lceil\log_2 n\rceil$ times and create a number $x$ in $\{0,1,\ldots, 2^k-1\}$.
  • If $x+1 > n$ then repeat the previous bullet.
  • The expected number of throws is $\Theta(\log n)$.

I hope this helps $\ddot\smile$

dtldarek
  • 37,381
  • @obinna Also, see here. – dtldarek Feb 21 '14 at 23:15
  • 1
    This only works if $n=2^t-1$ for some $t$. Also, since we have a restriction on the number of die faces, we have to use base $3$ instead of $2$. Thanks anyways. – Obinna Okechukwu Feb 21 '14 at 23:21
  • 3
    @obinna This works for any $n$. As for the base, this is a hint, but I see you already guessed the solution. – dtldarek Feb 21 '14 at 23:24
  • @dtldarek, I'm struggling to see how this works, as if this did, then you could do all simulation dice questions, say if n = 12, I throw a coin k = 3 times, then I don't really get what you are suggesting, those 3 throws produce 2^k outcomes , 0,...7, , how can I get this to simulate 12? – JimSi Jun 12 '18 at 17:03
  • @JimSi $2^3 < 12 < 2^4$, so $\lceil \log_2 12 \rceil = 4$, and then you have $0\ldots 15$ which is enough to simulate 12-sided die. – dtldarek Jun 12 '18 at 19:37
  • @dtldarek, ah ok, thanks, yes I see. I was being dumb. So this method can solve all simulation questions if simulation die has even number of values? Say if I wanted to simulate 12 sided die with 10 sided die? I can just roll a 10 sided die if (1-5) counts as H, (6-10) as T. – JimSi Jun 13 '18 at 07:46
  • Also where did you get the expected number of throws is logn. For the n = 12 case log(12) = 1.079. I believe it will take 16/12 throws to get a simulated value, which is similar. – JimSi Jun 13 '18 at 07:48
  • @JimSi Observe that this is a hint, not a full solution. For example if you want to use 3-sided die, then you should throw it $k = \lceil \log_3 n \rceil$ times. Regarding the expected number of throws, to simulate $n$-sided die using $d$-sided die you get something of order $\frac{d \log n}{\log d}$. – dtldarek Jun 13 '18 at 08:46
  • yes, I understand that any d sided die can be used to simulate. I was looking at a simulation of a 12 sided die by a 10 sided die. so k = 2, then there would be 100 possibilities, when you only want 12, so nearly 90% of the time you would have to reroll.

    Ok cool I’ll have to think about the formula. I thought the expected value of no o f rolls is $\dfrac {d^{k}}{n}$, as it is a geometric distribution and E(X) = 1/p

     – JimSi Jun 13 '18 at 10:29
  • @JimSi It is $k$ times that (because each "roll" is actually a batch of $k$ rolls). Also, observe that $n/d^k > 1/d$ so it the expected number of throws is at most $kd$. With a slight complication you can actually get it down to at most $2k$, because if $n$ fits within $d^k$ several times, then you can use modulo and discard only if throw happens in the top $d^k \bmod n$ possible values. – dtldarek Jun 13 '18 at 10:29
  • @dtldarek Ah ok of course thanks, this is actually a very nice method . So E = $k\dfrac {d^{k}}{n}$ if you don't use the mod fact. ah I see, clever, so with my example of a 10 sided die simulating a 12. You get k = 2, you dont discard the 88 of the 100 possibilities, as 81 would be 81mod12=9, so you only need to discard 97 98 99 100. Im glad I kept asking you where I wasn't getting it as I wouldn\t have appreciated the problem. But now I get E = $k\dfrac {d^{k}}{d^{k}-d^{k}modn}$ – JimSi Jun 13 '18 at 11:04
2

Do $0$ through $n-1$ rather than $1$ through $n$; it's a little easier to work through the arithmetic.

If you have a 10-sided die, you can simply roll it repeatedly to get the digits of the random number you're trying to generate. If the result gives you a number that's too big, you try again.

If you have a 6-sided die, then you can do the same thing, except you write numbers in base $6$ rather than base $10$, and so forth.

There are simplifications you can do: e.g. if you have a 10-sided die, you can use it as a five-sided die by simply reducing the result modulo $5$. This would also help if you're trying to simulate a $50$-sided die: roll it as a 10-sided die for the units digit, then as a 5-sided die for the tens digit.

A 12-sided die can work as a 4-sided die similarly, and so forth.

  • (Sorry for resurrecting-- just found this while searching and saw this wrong answer has not been corrected.) Unfortunately, rolling for the digits will (usually-- depends on the specific numbers being used) not work. For example, consider faking an 11-sided (0, 1, ..., 10) die, by rolling a 10-sided (0, 1, ..., 9) die. Rolling a 0 for the 10's digit is as likely as rolling a 1, but in the first case (00, 01, ..., 09) it should have 10 times the probability of happening as the second case (only 10). – B. Eckles Dec 30 '19 at 17:51
  • @B.Eckles Why is the answer wrong? If we roll the D10 twice, the chance of getting a 10 is 1/100, just as the chance of getting a 00 is 1/100. – mic Jun 15 '20 at 18:47
  • @mic In order to roll any single-digit number, you would need to roll a 0 for the first digit. But the chances of a 0 or a 1 for the first digit are equally likely. This makes rolling a 10 far more likely than rolling any of those numbers. Once you roll that 1 for the first digit, the only valid second digit is a 0. – B. Eckles Jun 16 '20 at 23:08
  • Unless (and it's possible I misread the answer in the first place, and that this is what was meant) the algorithm is to roll both die, and if their result is not a valid number (00 through 10), then you roll both again. And again. And again. Until you finally get a valid result. This may or may not be practical depending on the numbers involved and the application. – B. Eckles Jun 16 '20 at 23:09
  • Reading it again I see that I probably misread it. I think you're right, that's the algorithm, and it works. My apologies! It still may or may not be the best algorithm based on the specific use-case, however. – B. Eckles Jun 16 '20 at 23:12