Dice Equivalance

[Frozen_Feet]

I want to create random numbers on a range from 0 to 18. Now, I could do this with 2d10-2, or 2d10 with 0s (or 10s) read as, well, 0s. The question is, are these two methods mathematically equivalent? Do they create a similar curve for their results?

[hymer]

I'll stick my neck out here and say they are not merely equivalent, they are mathematically equal.

Edit: To explain, both cases have a set of two dice, which go from 0 to 9, with the same chance of each result.

[Fortuna]

I'll stick my neck out here and say they are not merely equivalent, they are mathematically equal.

Edit: To explain, both cases have a die which goes from 0 to 9, with the same chance of each result.

I'm fairly certain that you're drawing a distinction that doesn't exist.

In short, yes. These methods are interchangeable in every sense of the word. Other possible interchangeable methods would be 1d10-1d10+9, 20-2d10, and numerous others.

[hymer]

As long as the matter seems settled (and I have all this extra confidence from being right for once), I'll say that equivalent and equal are not the same. You could say with some fairness that Hawaii is America's equivalent to Russia's Kaliningrad, in that they are non-contiguous states. But they are not equal to each other. :)

[Frozen_Feet]

Okay. Thanks. The reason I asked is because 2d10-2 started to look a bit inelegant when I realized the 10s on the dice are 0s anyway.

[Fortuna]

As long as the matter seems settled (and I have all this extra confidence from being right for once), I'll say that equivalent and equal are not the same. You could say with some fairness that Hawaii is America's equivalent to Russia's Kaliningrad, in that they are non-contiguous states. But they are not equal to each other. :)

While true in general use, as I understand it, mathematical equivalence is in fact logically equivalent to equality - that is, there are no objects mathematically equivalent that are not also equal, and vice versa.

[hymer]

@ Frozen_Feet: You're welcome.

@ Random-person: Not really correct it would seem (http://stackoverflow.com/questions/311936/what-is-the-difference-between-equality-and-equivalence).
Equal is a specific math term. Equivalent isn't, by itself, a math term.

[VariSami]

If you want equal possibility on the curve, they do not seem to be the same. I would rather not draw it myself, but basically you could do a 10x10 grid and apply to it all the results from the dice (2d10), summing the result from each die in each part of the grid. As in, the left upper corned being 1+1 = 2, and the right lower corner being 10+10 = 20 (or 0+0 if you opt for that). Then you would only need to remove the results which do not sit within the range of 1-18 and compare the rest: if the chances are equal, each result should appear in the grid as often as the others. If even one result is shown more often than any of the others, the chances are biased in its favor.

1d20-2 is a sure way to get an equal distribution so I would still prefer going with it.

[hymer]

Since Frozen_Feet mentions the curve of the method, I doubt the intent is to get the same chance on all results.

[Fortuna]

@ Frozen_Feet: You're welcome.

@ Random-person: Not really correct it would seem (http://stackoverflow.com/questions/311936/what-is-the-difference-between-equality-and-equivalence).
Equal is a specific math term. Equivalent isn't, by itself, a math term.

The question thread you link to is talking about computer science, rather than mathematics. In a mathematical sense, if you say 'mathematically equivalent' then that is, where both concepts are defined, logically equivalent to 'equal'.

[Khedrac]

OK I thought there might be a slightly different distribution decided to check it. The distributions are identical and I probably need to wake up a bit more not to make silly mistakes.

[Frozen_Feet]

Khedrac, I know the feeling. I literally dreamt of this system, and when I woke up, I started to get second thoughts. "Wait... are they really the same? My intuition and everything I know of math says they should be, but are they?" I didn't really have ability to compute it myself, hence this thread.

Here's what I'm going to use it for. (http://www.giantitp.com/forums/showthread.php?p=15844358#post15844358)

[hymer]

@ Random_person: I thought I was on a roll there, but I was soooo wrong! Wrroooong! Thanks for setting me straight.

[NichG]

I wonder if there are in fact any distributions of 'standard' dice (e.g. 1 thru N) that are equivalent to eachother. I think its pretty easy to show that XdN and YdM can only be equivalent if X=Y and N=M, because the shape of the curve changes towards a Gaussian as you add more dice, and you can't easily fix up those details of the curve shape.

I'm not sure that the same is true if you allow adding/subtracting dice of different sizes though. Is there some combination of two dice of different sizes that is exactly equivalent to 2d6, for example?

If not, its kind of interesting since it means that given some distribution of results, you can derive the single combination of dice that produced it.

[Radar]

The question thread you link to is talking about computer science, rather than mathematics. In a mathematical sense, if you say 'mathematically equivalent' then that is, where both concepts are defined, logically equivalent to 'equal'.
If we are talking strict mathematics, then equality and equivalence are two very different terms. Equality is just a specific example of equivalence relation. Sometimes mathematics is subtle and meticulous to a fault. :smallwink:

And if I'm on a nitpicking rampage, then the precise term comparing the two random variables presented in the thread is not 'mathematical equivalence', but equality in distribution. :smalltongue:

edit:

If not, its kind of interesting since it means that given some distribution of results, you can derive the single combination of dice that produced it.
As far as I can tell, you totaly can, since summation of dice rolls is just a convolution. If you start with N flat distributions (which can be described as a 0th order polynomials), then after the summation of results you will obtain a distribution, which can be fitted piecewise by an Nth order polynomial. Furthermore you'll always have exactly N+1 pieces to fit. Manualy it can be a bit tedious, but it should be very easy to program.

[Khedrac]

I didn't really have ability to compute it myself, hence this thread.Actually I just opened up a spreadsheet ( in this case Excel, but it's inability to add up doesn't matter) and ran the numbers as it is only 100 different combinations for the two dice, the put a count formula in for each possible result for the two methods and got identical results.


I'm not sure that the same is true if you allow adding/subtracting dice of different sizes though. Is there some combination of two dice of different sizes that is exactly equivalent to 2d6, for example? Not of 2 dice - d4 + d8 gives the same 2-12 range but the distribution is different (for one thing there are fewer combinations).


I wonder if there are in fact any distributions of 'standard' dice (e.g. 1 thru N) that are equivalent to each other.
I was going to answer this bit first and say "no" for the reasons you give, but this could be one of those where it becomes really really hard to prove a negative, and when you are allowed combinations like Nd6-Md6 proving that you cannot replicate 2d6 is getting a bit complicated. I would guess it might either be impossible to prove, or it's the sort of proof you meet at university or later (and yes, I do have a maths degree, but it's a bit dusty).


If not, its kind of interesting since it means that given some distribution of results, you can derive the single combination of dice that produced it.
Yes, but does the term "recursively enumerable" mean anything to you?

[Slipperychicken]

When I want to see distributions of various dice, I use anydice (http://anydice.com/). Once you figure out the interface, it's pretty useful for hashing out dice statistics. Not just for dnd either, I've used it to help figure out strategies for dice-based board games too.

For basic stuff, you type in "output 10d6 + 2" or whatever. It then shows you a distribution, and other stats like mean, median, standard deviation, variance, etc. There are other functions in there, like exploding dice (like in shadowrun or WoD).

[warty goblin]

I was going to answer this bit first and say "no" for the reasons you give, but this could be one of those where it becomes really really hard to prove a negative, and when you are allowed combinations like Nd6-Md6 proving that you cannot replicate 2d6 is getting a bit complicated.

That case is very easy to eliminate. Dice rolls are independent, so the mean of the differences is the difference of means, and the variance of the difference is the sum of the variances. Any combination of Nd6 - Md6, such that M - N = 2 (which is necessary to guarantee equality of means) will have minimal variance when N = 2, M = 0. All other N, M values will have larger variances and unequal distribution, as the variance is given by (N + M)*Var(1d6). Since the variances are perforce different, the distributions cannot be equal.

(Intuitively, 10d6 - 8d6 will have the same mean as 2d6 since 'on average' all but 2d6 will cancel each other out. The former expression has a lot more variability though, because 2d6 only has range 2 - 12, while 10d6 - 8d6 has a range of all integers between -38, 52 inclusive. In short those 8d6 that on average fall out are random and so don't necessarily cancel.)

This logic obviously generalizes easily to arbitrary difference K = N - M, so long as one restricts oneself to linear combinations of the same size of dice. I believe similar logic also could trivially eliminate a lot of cases for unequal dice, by observing that any equal distribution must necessarily have the same range, mean and variance. Of course the equality of these parameters does not guarantee equality of distribution.

I'll see if I can't wrangle up an actual proof later. I suspect equality of mgfs may prove useful.

[Slipperychicken]

That case is very easy to eliminate. Dice rolls are independent, so the mean of the differences is the difference of means, and the variance of the difference is the sum of the variances. Any combination of Nd6 - Md6, such that M - N = 2 (which is necessary to guarantee equality of means) will have minimal variance when N = 2, M = 0.

What? We all know that two minus zero equals two.

[Fortuna]

If we are talking strict mathematics, then equality and equivalence are two very different terms. Equality is just a specific example of equivalence relation. Sometimes mathematics is subtle and meticulous to a fault. :smallwink:

And if I'm on a nitpicking rampage, then the precise term comparing the two random variables presented in the thread is not 'mathematical equivalence', but equality in distribution. :smalltongue:

Really? I'd be interested to hear of other equivalence relations. I've yet to meet them in my (admittedly limited) studies.

[DeIdeal]

Really? I'd be interested to hear of other equivalence relations. I've yet to meet them in my (admittedly limited) studies.

Cf. Wikipedia (http://en.wikipedia.org/wiki/Equivalence_relation) for definition.

As an example, the concept of isomorphism is usually introduced quite early in linear algebra / study of vector spaces; it fulfills the definition of an equivalence on the set of algebraic structures.

(I haven't even checked these forums for ages, and this is what I post when I do... I don't even.)

[warty goblin]

What? We all know that two minus zero equals two.

I reversed M and N apparently. My bad. Doesn't really change the argument though.


So after about two or three hours of scratchwork, I have what I think constitutes a proof that there exists no sum of differently sided dice that equals the sum of a number of same sided dice. It's rather involved, so here's the outline for the curious.

First note that for the distributions to be equal, they must have the same minimum and maximum. The minimum equality condition immediately guarantees that there's no way to substitute M dice of once size for N dice of some combination of sizes when M != N. The maximum condition will be used below.

Now I can proceed to define some notation. Let n be the number of sides per dice for the dice in the simple case of Kdn, and n1, n2, etc the number of sides for each of the dice in the other case. Note that the variance of a discrete uniform distribution with n possible values is (n^2 - 1)/12.

Consider p = j + 1 dice. The notation gets somewhat hairy here, so hang on.

Any p = j + 1 dice substitution must satisfy the variance equation:

(n1^2 - 1)/12 + .... + (nj^2 - 1)/12 + (np^2 - 1)/12 = (n^2 -1)/12, or

(np^2 - 1)/12 = (n^2 -1)/12 - {(n1^2 - 1)/12 + .... + (nj^2 - 1)/12)}

At this point note that the maxima must also be the same, which gives
n1 + ... + nj + np = p*n.

This can be solved for np, and substituted into the left hand side of the above equation. The result is a quadratic in n, and use of the quadratic formula gives an extremely ugly expression for the roots. Without trying to write out all the notation, which would take a long time in a forum page, only the (b^2 - 4ac) term needs to be considered, which will be decreasing in the sum (n1, .... nj) - roughly speaking, if you do the algebra it should be clear. Since the dice are supposed non-degenerate, each of the n's must be at least two, and it follows from this that the equation has no real roots for p > 2.

If p = 2, then
n1^2 + n2^2 = n^2 + 1, (1)
subject to
n1 + n2 = 2n, or n2 = 2n - n1. (2)

Substituting the (2) into (1), and solving for n1 gives

n1 = (3n^2 - 1)/4n, or n1 = 3/4*n - 1/(4n). Transparently no positive integer value of n gives an integer n1.

That is enough to imply that there exists no sum of dice with potentially unequal numbers of sides that has the same distribution as the sum of a number of the same sided dice.

...now I need food.

[NichG]

I appreciate the proofs. You guys took this a lot further than I expected! I was going to say, if each distribution corresponds to a unique dice-pattern you could use them for encryption (because it seems like it should be harder to get the dice pattern from distribution than vice-versa), but Radar's comment about it being a convolution means that extracting the dice distribution is a linear problem, so it can trivially be split up into subproblems that are all cheap to solve.

To Khedrac's question, I'm not familiar with 'recursively enumerable'. I looked it up, but I still don't think I see the connection. Are you getting at the Turing part of the definition, in that some distributions do not correspond to dice patterns and others do, and whether or not one can determine whether a distribution is or is not a string of the 'dice' language with a Turing machine?

[warty goblin]

I appreciate the proofs. You guys took this a lot further than I expected! I was going to say, if each distribution corresponds to a unique dice-pattern you could use them for encryption (because it seems like it should be harder to get the dice pattern from distribution than vice-versa), but Radar's comment about it being a convolution means that extracting the dice distribution is a linear problem, so it can trivially be split up into subproblems that are all cheap to solve.

I'm not sure if you can do this particularly rapidly backwards - e.g. given the distribution find the component parts, though obviously given the pieces the sum is fairly rapidly computable. Particularly since what you'd observe as somebody trying to break the code wouldn't be the actual distribution, but the sample distribution - assuming I'm understanding how you're thinking of using this. If you use a large pool of large dice, the extrema won't be observed very often, making it difficult to correctly divine the probabilities in the tail, and the number of dice used.

Actually, thinking on this, for maximum difficulty in working out the distribution, use a small number of very large dice. That makes it very hard to figure out the max and min, and without those the total number of dice being used would be very difficult to figure out.


Note also that my proof does not cover the case of whether there exist multiple ways to define sums of discrete uniforms with unequal numbers of outcomes. I think that follows, but summing random variables is weird. I also didn't cover the case of what happens when one includes subtraction, since that effectively sabotages my starting point of working with the extrema.

[NichG]

I'm not sure if you can do this particularly rapidly backwards - e.g. given the distribution find the component parts, though obviously given the pieces the sum is fairly rapidly computable. Particularly since what you'd observe as somebody trying to break the code wouldn't be the actual distribution, but the sample distribution - assuming I'm understanding how you're thinking of using this. If you use a large pool of large dice, the extrema won't be observed very often, making it difficult to correctly divine the probabilities in the tail, and the number of dice used.

Actually, thinking on this, for maximum difficulty in working out the distribution, use a small number of very large dice. That makes it very hard to figure out the max and min, and without those the total number of dice being used would be very difficult to figure out.

Well, if you're actually measuring the distribution then I think you can't do this at all. The noise will bury the chances of actually doing it, since the difference between 18d6+1d8+1d4 and 20d6 is going to be pretty hard to measure in noisy data.

But, if you have perfect knowledge of the distribution, then you can basically 'factor' it into its component dice because of the properties of convolutions. In the 'real space' of the distribution, adding a new die means doing an integral between the previous distribution and the distribution of the new die. In Fourier space, however, this is simply addition.

So the way to 'solve' the problem is to take a Fourier transform of the full distribution, and then you're just decomposing a vector into a sum of known vectors (the distributions of each individual die type), with the added wrinkle that you know that the coefficients of each vector are integers. So its basically at worst going to be a 6x6 matrix inversion (if you restrict yourself to common dice sizes: d4,d6,d8,d10,d12,d20). If you allow wonky dice like a d12761, then it would get harder I suppose.

[Radar]

I'm not sure if you can do this particularly rapidly backwards - e.g. given the distribution find the component parts, though obviously given the pieces the sum is fairly rapidly computable. Particularly since what you'd observe as somebody trying to break the code wouldn't be the actual distribution, but the sample distribution - assuming I'm understanding how you're thinking of using this. If you use a large pool of large dice, the extrema won't be observed very often, making it difficult to correctly divine the probabilities in the tail, and the number of dice used.
It can't be done precisely or at all from a sample distribution (maybe from a large enough sample one could run some statistics, but I'm not sure), but the actual distribution is actually possible to untangle, because it's finite. It means you only need to check a finite number of possible fits.

Actually, thinking on this, for maximum difficulty in working out the distribution, use a small number of very large dice. That makes it very hard to figure out the max and min, and without those the total number of dice being used would be very difficult to figure out.
This leads exactly to large prime numers as the best encryption keys known. :smallsmile:

Note also that my proof does not cover the case of whether there exist multiple ways to define sums of discrete uniforms with unequal numbers of outcomes. I think that follows, but summing random variables is weird. I also didn't cover the case of what happens when one includes subtraction, since that effectively sabotages my starting point of working with the extrema.
I didn't study the proof, but subtraction can be accounted for quite easily: 1d8-1d6 has the same distribution as 1d8+1d6-7. In the end subtracting dice instead of adding them just shifts the average.

[Khedrac]

To Khedrac's question, I'm not familiar with 'recursively enumerable'. I looked it up, but I still don't think I see the connection. Are you getting at the Turing part of the definition, in that some distributions do not correspond to dice patterns and others do, and whether or not one can determine whether a distribution is or is not a string of the 'dice' language with a Turing machine?
What I was trying to imply (without having looked at the maths to go from distributions to dice sets) was that it might well be a situation where it can take what seems like forever to come back with an answer.

[CarpeGuitarrem]

Hmm. This would be an interesting penalty mechanic for a d10-based system. I'm not positive on a situation that'd make it make total sense, but...where you have to count the "0" as an actual zero instead of a 10.

[endoperez]

I used http://anydice.com/ to check this out, and yes, they're equivalent. It makes fancy graphs too, and it's an awesome resource for all dice probability discussions.

2d10-2 is simply:

output 2d10-2



1d10 with 0s instead of 10s is a custom dice, marked d{1,2,3,4,5,6,7,8,9,0} or {0..9}, and 2 such dice are marked like so:

output 2d{0..9}

[Eulalios]

If not, its kind of interesting since it means that given some distribution of results, you can derive the single combination of dice that produced it.

We're rolling straight to pure mathematics here , and I hope I haven't been ninja'd, but ...

presuming true dice, can we construct a proof of that derivation and of the required sample size?

I believe we'd need a sample large enough to fill the set of possible results, and even then, if it's a pure random sample, we would have at best a statistical confidence that the set is filled - i.e. there is (vanishingly small) finite probability that d100 will roll a sequence of thirty results in the range 2-12.


... if each distribution corresponds to a unique dice-pattern you could use them for encryption (because it seems like it should be harder to get the dice pattern from distribution than vice-versa), but Radar's comment about it being a convolution means that extracting the dice distribution is a linear problem, so it can trivially be split up into subproblems that are all cheap to solve.

But the dice distribution cannot be absolutely determined for a finite sample size, it is inherently "fuzzy." A classic characteristic of a fuzzy measurement is that it lends itself to recognition by a trained observer, i.e. one who expects a particular set of results. Thus, it could be possible to use relatively complex set of dice in second pass of lend itself to a dual-pass encryption scheme where the frequencies of the first pass are known to the receiver, and can be used for training a neural network algorithm to guess the dice distribution of the second pass.

Crypto's really *not* my bag, though.


Are you getting at the Turing part of the definition, in that some distributions do not correspond to dice patterns and others do, and whether or not one can determine whether a distribution is or is not a string of the 'dice' language with a Turing machine?

This is really beyond my depth. I'd love to read further explanation.

[NichG]

We're rolling straight to pure mathematics here , and I hope I haven't been ninja'd, but ...

presuming true dice, can we construct a proof of that derivation and of the required sample size?

I believe we'd need a sample large enough to fill the set of possible results, and even then, if it's a pure random sample, we would have at best a statistical confidence that the set is filled - i.e. there is (vanishingly small) finite probability that d100 will roll a sequence of thirty results in the range 2-12.


Required sample size gets messy, I don't know if there's a simple way to derive this in general since it has to do with how close two particular distributions can end up being given all possible combinations of dice. I'm not even sure how it scales in general. I was assuming perfect knowledge of the distribution.



But the dice distribution cannot be absolutely determined for a finite sample size, it is inherently "fuzzy." A classic characteristic of a fuzzy measurement is that it lends itself to recognition by a trained observer, i.e. one who expects a particular set of results. Thus, it could be possible to use relatively complex set of dice in second pass of lend itself to a dual-pass encryption scheme where the frequencies of the first pass are known to the receiver, and can be used for training a neural network algorithm to guess the dice distribution of the second pass.

Crypto's really *not* my bag, though.


The encryption thing was more about the general case of 'I have a one-to-one mapping between this function, described by some number of bits, and these other objects'. I wasn't suggesting doing anything using real dice, just transmitting the distribution as the cypher and using the fact that, e.g., the intended recipient knows that there's a d71543 in the mix in order to decipher it much more quickly than someone without that knowledge could.



This is really beyond my depth. I'd love to read further explanation.

Well, I can write a distribution that does not correspond to any particular sum of dice. For example, 50% chance of a '2' and a 50% chance of a '4' would require multiplication to achieve - you can't do it by adding 1d2 + 1d2, you need 2*result(1d2).

So there's the question of how hard it is to tell for a computer to determine if a distribution came from summation of dice, or if its just some other arbitrary distribution.

I'm guessing there's a short-cut because of the convolution property. Fourier transform the distribution and look at the power-law tail to see if its consistent with a flat distribution, because adding together any number of dice (flat distributions) will just add the fourier transform of their distributions, and the sharp cutoff at the edge of flat distributions always gives you a 1/k power-law I think.

That said, thats a necessary condition, not a sufficient one.