+/dice

fun little statistics problem

git clone https://git.julia.blue/+/dice

Joseph RyanInitial commite8fe672

main
12.3 KiB312 linesraw
1// this might just be a way simpler solution: https://math.stackexchange.com/questions/3308672/probability-of-two-pairs-giving-equal-sum
2#import "@preview/rose-pine:0.1.0": apply, rose-pine-dawn
3#show: apply(variant: "rose-pine-dawn")
4// #show: apply()
5
6#let author = "Joseph Ryan"
7#let title = "Kyle and David roll some dice"
8#set document(author: author, title: title)
9#set text(font: "Noto Serif", lang: "en", size: 13pt)
10#set page(numbering: "1", number-align: center)
11#set par(justify: true)
12#align(center)[
13  #block(text(weight: 700, 1.75em, title))
14  #v(1em, weak: true)
15  #"October 30, 2023"
16]
17#pad(top: 0.5em, bottom: 0.5em, x: 2em, align(center, strong(author)))
18
19#show link: underline
20#set highlight(fill: blue)
21#let rainbow(content) = {
22  set text(fill: gradient.linear(..color.map.rainbow))
23  box(content)
24}
25
26#align(center, image("impetus.png", width: 300pt))
27
28= Introduction
29Our friends Kyle and David are #rainbow[rolling dice together]/*(gay)*/. When they both
30roll a die, sometimes they get the same number. They wonder: "would we be more likely to
31roll the same number if we used _two_ dice instead of one?"
32
33= Defining terms
34
35David knows intuitively that he and Kyle have a $1/6$ chance of rolling the same number
36when they use a single die, but lets break down why exactly that is.
37
38$ underbrace(X_d, "David") tilde.op U(1,6) #h(20pt) underbrace(X_k, "Kyle") tilde.op U(1,6) $
39
40$ P(X_d = X_k) = sum_(i=1)^6 P(X_d = i) * P(X_k = i) $
41
42$ P(X_d = X_k) = sum_(i=1)^6 1/6 * 1/6 = 1/6 $
43
44It may seem a bit silly that we're splitting it up and then summing just to get back to
45$1/6$, but it's a good representation of what's happening. For every possible $i$ that one
46could roll, we take the chance that both David and Kyle rolled that number and add up all
47those chances which gives us the probability that they roll the same number as each other.
48
49Unfortunately adding a second die isn't as simple because with $6^2=36$ possible rolls and
50only $11$ values ($2$-$12$) the distribution of numbers you can roll with a pair of dice
51isn't uniform. Many people know that $7$ is the most common number to roll with two dice,
52but here's the full set of possibilities:
53
54#pagebreak()
55
56// TIL: unicode has die faces (but only for the d6) and they're in the
57// "Miscellaneous Symbols" block
58#let nums = range(2, 13)
59#figure(caption: [All possible rolls], numbering: none, text(17pt, table(
60  columns: 11,
61  ..nums.map(n => [#n]),
62  [ ⚀⚀ ],
63  [ ⚀⚁ \ ⚁⚀ ],
64  [ ⚀⚂ \ ⚁⚁ \ ⚂⚀ ],
65  [ ⚀⚃ \ ⚁⚂ \ ⚂⚁ \ ⚃⚀ ],
66  [ ⚀⚄ \ ⚁⚃ \ ⚂⚂ \ ⚃⚁ \ ⚄⚀ ],
67  [ ⚀⚅ \ ⚁⚄ \ ⚂⚃ \ ⚃⚂ \ ⚄⚁ \ ⚅⚀ ],
68  [ ⚁⚅ \ ⚂⚄ \ ⚃⚃ \ ⚄⚂ \ ⚅⚁ ],
69  [ ⚂⚅ \ ⚃⚄ \ ⚄⚃ \ ⚅⚂ ],
70  [ ⚃⚅ \ ⚄⚄ \ ⚅⚃ ],
71  [ ⚄⚅ \ ⚅⚄ ],
72  [ ⚅⚅ ],
73)))
74
75== Brute force solution
76
77// cool calculator: https://topps.diku.dk/torbenm/troll.msp
78With that table, we can write out all the terms of the sum to compute the probability of
79Kyle and David rolling the same number with their pairs of dice:
80
81$ P(X_d = X_k) = sum_(i=2)^12 P(x_d = i) * P(x_k = i) $
82$ underbrace(1/36 * 1/36, "chance that they" \ "both rolled a 2") + 2/36 * 2/36 + 3/36 * 3/36 + ... $
83
84Hold on, that's going to be a pretty big and nasty sum to write out, lets try to compact
85it a bit. We can square each $P(X_d = X_k = i)$ term because David and Kyle should have
86the same probability of rolling a certain number, and then we can "fold" the list on
87itself because the chance of rolling a 2 through 6 mirrors that of 12 through 8. Here's a
88more concise version of that same sum:
89
90$ underbrace(2(1/36)^2, "both rolled" \ "2s or 12s") + 2(2/36)^2 + 2(3/36)^2 + 2(4/36)^2 + 2(5/36)^2 + underbrace((6/36)^2, "both rolled 7s") $
91
92$
93&= (2*1)/1296 + (2*4)/1296 + (2*9)/1296 + (2*16)/1296 + (2*25)/1296 + 36/1296 \
94&= (2+8+18+32+50+36)/1296 \
95&= 146/1296 = 73/648 tilde.equiv 0.1126543210
96$
97
98And there we have it: there's about an $11%$ chance that David and Kyle roll the same
99number, so they're _less_ likely to do so than if they'd just rolled a single die ($1/6 = 16.overline(6)%$)
100
101== Experimental verification
102
103But wait: was our result actually right? Did we make a mistake in the arithmetic? Lets
104double check with some hastily written python:
105
106#set raw(block: true, theme: "gruvbox.tmTheme")
107#show raw: it => block(fill: rgb("#1D2021"), inset: 8pt, radius: 5pt, text(fill: rgb("#fdf4c1aa"), it))
108```python
109from itertools import product
110from random import choice as roll
111
112die = [i+1 for i in range(6)]
113two_dice = [a+b for a,b in product(die, die)]
114
115def test(dice, n=1000000):
116    return sum(roll(dice) == roll(dice) for _ in range(n)) / n
117
118print("Single:", test(die))
119print("Pair:  ", test(two_dice))
120```
121
122Which gives us:
123
124```
125Single: 0.16661
126Pair:   0.11231
127```
128
129Hey, that's pretty close! Having the computer roll a million dice for us sure is
130convenient.
131
132= Going deeper
133
134Manually computing the odds _works_, but it doesn't feel sufficiently _beautiful_ (and
135aesthetics is of course what math is all about).
136
137Lets start by doing away with such concretions as _dice_, for what is a die but a
138uniformly distributed discrete random variable? We can abstract away the dice by thinking
139about the size of their uniform range (how many sides they have) which we'll denote
140$k$, and how many of those variables we're adding together (how many dice we're rolling)
141which we'll call $n$.
142
143Now we can write our iterative solution from before in more general terms:
144
145$ S = {x in ZZ^+ : x <= k}^n $
146
147$ A =^d B = inline(sum) x : x attach(in, br: r) S $
148
149$ P(X_(n,k)) = P(A = B) $
150
151$ = (sum_(i=n)^(k n) |{x in S : (inline(sum) x) = i}|^2)/k^(2n) $
152
153In other words, take $S$ as the $n$-fold Cartesian product of the set of integers in $[1,k]$
154which gives you $k^n$ $n$-tuples. For any two randomly selected tuples from that set, to
155get the probability that the sum of their elements is equal you take each number from $n$ to
156$k n$ and:
157
158+ Count how many members in $S$ are made up of elements which sum to that number
159+ Square that count
160+ Sum those squared counts
161+ Divide by $k^(2n)$
162
163With this formal definition, we can write some code to compute the exact solution for any
164$n$ and $k$ instead of approximating it by running lots of simulations like we did last
165time. Let's write a function that fixes $k$ and shows the results for many values of $n$.
166This approach starts to choke if you ask for higher values like $k=20$ but we're just
167gonna use it to explore some smaller cases.
168
169```python
170from collections import Counter
171
172def solve(k, n_max=8):
173    print(f"{k=}")
174    for n in range(1, n_max):
175        totals = (sum(x) for x in product(range(k), repeat=n))
176        numerator = sum(i * i for i in Counter(totals).values())
177        denominator = k ** (n * 2)
178        p = 100 * numerator / denominator
179        print(f"  {n=}", f"{p: 6.2f}%", f"{numerator:>8} / {denominator}")
180    print()
181```
182
183It's often helpful to reduce a problem to its simplest case, so lets set $k=2$ (which you
184can think of as flipping coins instead of rolling dice) and see what the results look
185like:
186
187// typstfmt::off
188#figure( // caption: [results for $k=2$], numbering: none,
189  table(
190    columns: 4,
191    [$n$], [$%$ chance], [numerator], [denominator],
192    [$1$], [$50%$], [$2$], [$4$],
193    [$2$], [$37.50%$], [$6$], [$16$],
194    [$3$], [$31.25%$], [$20$], [$64$],
195    [$4$], [$27.34%$], [$70$], [$256$],
196    [$5$], [$24.61%$], [$252$], [$256$],
197    [$6$], [$22.56%$], [$924$], [$4096$],
198    [$7$], [$20.95%$], [$3432$], [$16348$],
199    [$8$], [$19.64%$], [$12870$], [$65536$],
200    [$9$], [$18.55%$], [$48620$], [$262144$],
201    ),
202)
203// typstfmt::on
204
205The denominators are pretty easy to derive, $k^(2n)$ means that in this case it's just
206consecutive powers of $4$. The question is how we can calculate the numerator without
207having to enumerate the whole set? For this we can turn to the
208#link("https://oeis.org/")[Online Encyclopedia of Integer Sequences] for some hints on
209where else in number theory this sequence shows up. When we enter $2,6,20,70,252,924,3432$
210it tells us that these are the _"central binomial coefficients"_.
211
212What does that even mean? It's referring to the way that binomials expand when
213exponentiated:
214
215$ (x + y)^2 = x^2 + 2x y + y^2 $
216$ (x + y)^3 = x^3 + 3x^2 y + 3x y^2 + y^3 $
217$ (x+y)^4=x^4+4x^3y+6x^2y^2+4x y^3+y^4 $
218$ ... $
219
220If you squint at it long enough this has the same _vibe_ as our table of possible dice
221rolls on page 2, and when you think about the mechanics of binomial expansion it really is
222a similar process where coefficients near the middle "overlap" more just like rolling
223numbers in the middle with a pair of dice. One way to make the parallels more obvious is
224to drop all the variables and just look at the coefficients on each term, this becomes the
225famous diagram Pascal's Triangle:
226
227#align(center, grid(columns: 2, gutter: 4em, table(
228  columns: 1,
229  align: center,
230  stroke: none,
231  // TODO: generate programmatically
232  [$1$],
233  [$1$ $1$],
234  [$1$ #strong[$2$] $1$],
235  [$1$ $3$ $3$ $1$],
236  [$1$ $4$ #strong[$6$] $4$ $1$],
237  [$1$ $5$ $10$ $10$ $5$ $1$],
238  [$1$ $6$ $15$ #strong[$20$] $15$ $6$ $1$],
239  [$1$ $7$ $21$ $35$ $35$ $21$ $7$ $1$],
240  [$1$ $8$ $28$ $56$ #strong[$70$] $56$ $28$ $8$ $1$],
241  [$1$ $9$ $36$ $84$ $126$ $126$ $84$ $36$ $9$ $1$],
242), table(
243  columns: 1,
244  align: center,
245  stroke: none,
246  ..range(10).map(i => [#for j in range(i + 1) {
247      [ $binom(#[#i], #[#j])$ ]
248    }]),
249)))
250
251// TODO: coin head tails, talk about summing the squares of a row
252
253Now it's clear why our sequence was called "central binomial coefficients": they run along
254the center of Pascal's triangle which is an arrangement of binomial expansion
255coefficients. On the right we have the binomial expression used to compute each
256coefficient. $inline(binom(a, b))$ (also known as $a$ _choose_ $b$) has a closed-form
257solution:
258
259$ a!/(b!(a-b)!) $
260
261Looking at the center column, it appears that we want to use $a=2n$ and $b=n$ to finally
262have our clean solution:
263
264$
265P(X_(n,2)) &= (sum_(i=n)^(2n) |{x in S : (inline(sum) x) = i}|^2)/2^(2n)\
266&= 1/4^n binom(2n, 2)\
267&= (2n)! / (4^n n! (2n-n)! )\
268&= (2n)! / (4^n n!^2)\
269$
270
271That's starting to look kind of beautiful! Plugging in $n=9$ we get the same $18.55%$ that
272we previously calculated (at the bottom of page 4), so it looks like our solution is good.
273
274// TODO: write section attributing this to George Polya from his 1981 book "Mathematical Discovery" somewhere around page 90. specifically "Polya introduced the sum of the squares of each entry in row n is equal to the middle entry of row 2n in" from this random masters thesis I bumped into: https://scholarworks.lib.csusb.edu/cgi/viewcontent.cgi?article=1957&context=etd
275// also show that it generalizes not to pascal's tetrahedron, but to n-way triangles (need to double check 4)
276
277= Cooking with gas
278
279With our solution tied so closely to binomials and Pascal's triangle, you might worry that
280this wont generalize to other values of $k$, but in fact it's almost trivial to use the
281same approach for _trinomials_. Not only that, there are
282fully general equations that represent _multinomials_ and a construct known as
283"Pascal's $m$-simplex"! As an aside, the fact that mathematicians come up with names like _simplex_ to
284generalize the _notion_ of a triangle or tetrahedron to arbitrary dimensions is pretty
285rad. Anyways the equation for the central multinomial coefficients is as follows:
286
287$ "TODO" $
288
289Now that we have the general solution, we can calculate the odds of rolling the
290same number with any number of dice with any number of sides! A single six sided die is
291often denoted "1d6" ($n=1$, $k=6$ in our formulation), so by plugging in those values we
292can get the odds for 3d8 (TODO), 10d20 (TODO), 314d159 (TODO) or whatever combination we want.
293
294== Scope creep
295
296We can also answer related questions like the inverse of David and Kyle's original query
297doing some algebra: how many d6's would they have to roll for the chance of them getting
298the same number to be $~1%$? That's left as an exercise to the reader.//#emoji.face.wink.
299
300= Closing remarks
301
302// https://github.com/typst/typst/discussions/1732
303#let LATEX = {
304  [L];
305  box(move(dx: -4.2pt, dy: -1.2pt, box(scale(65%)[A])));
306  box(move(dx: -5.7pt, dy: 0pt, [T]));
307  box(move(dx: -7.0pt, dy: 2.7pt, box(scale(100%)[E])));
308  box(move(dx: -8.0pt, dy: 0pt, [X]));h(-8.0pt)
309}
310
311Thanks for sniping me with this problem David! I've been looking for an excuse to try
312#link("http://typst.app")[typst] forever, and it's _such_ a breath of fresh air compared to #LATEX.