Dice probabilities

[David Hayden]

(04-29-2024 06:07 PM)Thomas Klemm Wrote:  We might rather write it: \(x^2+x^1+x^0\)
Thus for an ordinary die we would use: \(x^6+x^5+x^4+x^3+x^2+x^1\)
If these terms get multiplied, their exponents are added.
We're using the distributive law.
Every possible case gets combined with all the others.
And the exponents are added up for us.

I assume that the reason we add up the coefficients of \(x^{10} \cdots x^7\) is clear.

I'm lost. What is x? Why do create \(x^2+x^1+x^0\)? How does it relate to the dice?

Sorry for being dense.

Dave

[Albert Chan]

(04-30-2024 07:30 PM)David Hayden Wrote:  What is x? Why do create \(x^2+x^1+x^0\)? How does it relate to the dice?

It is a convenience tool. Example, with a fair coin:

Coin = (H + T)/2
Coin^2 = (HH + HT + TH + TT)/4

If we don't care permutations, and let number of heads = x exponent, we have

Coin = (x + 1)/2
Coin^2 = (x^2 + 2x + 1)/4

Set x=1, we get total probability of 100% (as expected)

[Thomas Klemm]

(04-30-2024 07:30 PM)David Hayden Wrote:  What is x? Why do create \(x^2+x^1+x^0\)? How does it relate to the dice?

A polynomial in the variable \(x\) can be considered an encoding of vector.
You are probably more familiar using the other direction: a vector can be considered an encoding of polynomial.

If you want to solve \(x^2 - 5x + 6 = 0\) with an HP-48GX you enter:

[1 -5 6]
PROOT

[2 3]

But we have a vectors like [1 1 1] or [1 2 3] and we encode them as polynomials \(x^2+x+1\) or \(x^2+2x+3\).

How are these vectors related to a die?
The position or index marks the value of a side and the coordinate marks how many sides we have with this value.
Similarly for a polynomial the exponent marks the value of a side and the coefficient marks how many sides we have with this value.

Thus [1 1 1] should rather be [2 2 2] for a real die but we can just scale this up or down.
So we don't bother.

An ordinary 6-sided die would be encoded as: [1 1 1 1 1 1 0]

If you roll multiple dice we assume that their outcome is independent from each other.
Every possible event of one die can be combined with every possible event of the other dice.

We simulate the same behaviour with the distributive law when two polynomials are multiplied.
Every term of one polynomial is multiplied by every possible term of the other polynomials.
And that's all there is.

But multiplication of polynomials does more that just that.
Terms of \(x\) with the same exponent are collected and added.
But for the dice this means that events with the same sum are collected and added.
And that is exactly what we want.

Thus by multiplying these polynomials we can simulate throwing the dice.

If that didn't help, I suggest to take two ordinary dice, encode them as polynomials, multiply them and see what happens.
And then compare this result to what you would do with the dice.

---

Here comes the really cool part: multiplication of polynomials is easy.
It is implemented in many libraries or tools.
And if you check my Post #13 you notice that there is a relationship to the Fast Fourier Transform.
This allows us to do these kind of calculations very efficiently using an HP-48GX.

[dm319]

(04-30-2024 07:30 PM)David Hayden Wrote:  I'm lost. What is x? Why do create \(x^2+x^1+x^0\)? How does it relate to the dice?

Sorry for being dense.

Dave

You got to it before me! This is witchcraft to me. When I first looked at it I thought it was some kind of maths abuse but I'm willing to reconsider this after more thought.

[John Keith]

(04-30-2024 12:27 AM)Thomas Klemm Wrote:  Not really: (x^2+x+1)^5

Interesting and informative discussion here. No real need for Wolfram Alpha, though. On the HP 50, 'X^2+X+1' 5 ^ EVAL is almost instantaneous. For larger polynomials, the Haskell program at A027907 is very fast and easy to implement using DOLIST.

[dm319]

(04-29-2024 09:22 PM)Albert Chan Wrote:   1.05153045515E20

This is sorcery.

[Thomas Klemm]

(04-30-2024 10:07 PM)dm319 Wrote:  This is sorcery.

0.9899
1/X

1.010203050813213455904636832003233

Woah, the Fibonacci sequence magically appears.

Try again with 0.998999:

1.001002003005008013021034055089144

[Thomas Klemm]

I've used the programs TO and FRO for the HP-48GX from my older Post #13 to calculate:

TO
5 y^x
FRO

These are the results:

[ 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
{ 1 5 15 30 45 51 45 30 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }

[ 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
{ 243 810 1485 1800 1590 1052 530 200 55 10 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }

The array is the input and the list is the output of that calculation.

[Thomas Klemm]

(04-30-2024 10:00 PM)John Keith Wrote:  No real need for Wolfram Alpha, though. On the HP 50 (…)

True. But I can't post a link to your HP-50, can I?

(04-30-2024 10:00 PM)John Keith Wrote:  (…) the Haskell program at A027907 is very fast and easy to implement using DOLIST.

Please don't leave us hanging here. Just post your program.

[Thomas Klemm]

(04-30-2024 07:30 PM)David Hayden Wrote:  I'm lost. What is x? Why do create \(x^2+x^1+x^0\)? How does it relate to the dice?

Grant Sanderson does a much better job than me:



There's a section starting at 14:40 where he talks about polynomial multiplication.
And then following that, one about speeding up with FFTs, which is what I did with the programs for the HP-48GX.

[Albert Chan]

(04-30-2024 10:07 PM)dm319 Wrote:  This is sorcery.

Dice = (x^2 + x + 1)/3
With uniform distribution, center has probability of 1/3

Dice^2 = (x^4 + 2x^3 + 3x^2 + 2x + 1)/9
We have triangular distribution. Again, center probability = 3/9 = 1/3

Dice^n, n→∞, will approach normal distribution.
Center still has highest probability, but less than 1/3.

P(Dice^5, sum=5) < 1/3 = 81/3^5

With x=100, we can numerically evaluate all coefficients of Dice^5 without overlap.

(04-29-2024 09:22 PM)Albert Chan Wrote:  >10101^5                     // (x^2+x+1)^5, for x=100
 1.05153045515E20

P(Dice^5, sum=5) = 51/3^5 ≈ 0.2099

Interestingly, this equals P(Dice^5, sum≥7) too.

[John Keith]

(05-01-2024 04:41 AM)Thomas Klemm Wrote:  

(04-30-2024 10:00 PM)John Keith Wrote:  No real need for Wolfram Alpha, though. On the HP 50 (…)

True. But I can't post a link to your HP-50, can I?

(04-30-2024 10:00 PM)John Keith Wrote:  (…) the Haskell program at A027907 is very fast and easy to implement using DOLIST.

Please don't leave us hanging here. Just post your program.

Simpler than I thought using ADD instead of DOLIST.

Given n on stack, returns row n of A027907 (2n + 1 coefficients).

Code:


/<< { 1 1 1 } 2 ROT
  START 0 OVER + 0 +
    { 0 0 } ROT DUP2 SWAP + UNROT +
    ADD ADD
  NEXT
\>>

For HP48G, use ROT ROT instead of UNROT, also some coefficients will not be exact if n > 27 because they are > 10^12.

And now a dumb question: Why can trinomial coefficients be used for any number of dice and faces per die? Are there cases where one may need tetranomial or higher order coefficients?

[Thomas Klemm]

(05-01-2024 06:56 PM)John Keith Wrote:  Simpler than I thought using ADD instead of DOLIST.

It appears to be similar to my Post #5.

(05-01-2024 06:56 PM)John Keith Wrote:  And now a dumb question: Why can trinomial coefficients be used for any number of dice and faces per die? Are there cases where one may need tetranomial or higher order coefficients?

They can't. Member dm319 initially asked for dice like these:



We list their faces as [0 0 1 1 2 2] and encode them as \(2x^2 + 2x + 2\).
But since the coefficients are all the same we can use \(x^2 + x + 1\) instead.

If however you use one of these:



There are multiple possibilities for quadrinomial coefficients:

• Tetrahedron: [1 2 3 4]
• Octahedron: [1 1 2 2 3 3 4 4]
• Dodecahedron: [1 1 1 2 2 2 3 3 3 4 4 4]
• Icosahedron: [1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4]
  

All of them can be encoded with \(x^4 + x^3 + x^2 + x\).
Or then we rather use \(x^3 + x^2 + x + 1\) to match A008287.
Again this doesn't matter much as the coefficients are only shifted.

Check in Post #8 how "for extra fun (…) such a formula could be extended to rolling a pool of non-standard, mixed dice".

[John Keith]

(05-01-2024 08:45 PM)Thomas Klemm Wrote:  

(05-01-2024 06:56 PM)John Keith Wrote:  Simpler than I thought using ADD instead of DOLIST.

It appears to be similar to my Post #5.

Indeed, and your elegant program can be generalized into a program to produce m-nomial coefficients, which I call MNOM

Code:


@ Given integers m on level 2 and n on level 1, returns row n
@ of a triangle of m-nomial coefficients. Row n has n*(m-1)+1 terms.
@ Relevant OEIS sequences:
@   m    seq
@   2  A007318   Binomial coefficients (Pascal's triangle, slow)
@   3  A027907   Trinomial       "
@   4  A008287   Quadrinomial    "
@   5  A035343   Pentanomial     "
@   6  A063260   Hexanomial      "
@   7  A063265   Heptanomial     "
@   8  A171890   Octonomial      "
@   9  A213652   Nonanomial      "
@  10  A213651   Decanomial      "
\<< \-> m n
  \<< 1 m
    START 1
    NEXT m \->LIST 2 n
    START DUP 2 m
      START 0 SWAP + SWAP 0 + OVER ADD SWAP
      NEXT DROP
    NEXT
  \>>
\>>

And a version optimized for the 49 and 50 with ListExt:

Code:


\<< I\->R SWAP I\->R \-> n m
  \<< 1 m LMRPT 2. n
    START DUP 2. m
      START 0 SWAP + SWAP 0 + OVER ADD SWAP
      NEXT DROP
    NEXT
  \>>
\>>

Now, typing 6 9 MNOM 14 GET will return your result.

[Thomas Klemm]

(05-02-2024 02:46 PM)John Keith Wrote:  Now, typing 6 9 MNOM 14 GET will return your result.

Indeed, that is true:

145899

Very nice!

[Albert Chan]

(05-02-2024 02:46 PM)John Keith Wrote:  ... Now, typing 6 9 MNOM 14 GET will return your result.

Code:

function MNOM(m, n) -- ((x^m-1)/(x-1))^n coefficients
    local P = setmetatable({1}, {__index = function(t,k) return 0 end})
    for i=1,n do
        for j=#P+m-1,1,-1 do
            for k=j-m+1,j-1 do P[j]=P[j]+P[k] end
        end
    end
    return P
end

lua> pprint(MNOM(3,5))
{ 1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1 }

lua> MNOM(6,9)[14]
145899