// this might just be a way simpler solution: https://math.stackexchange.com/questions/3308672/probability-of-two-pairs-giving-equal-sum #import "@preview/rose-pine:0.1.0": apply, rose-pine-dawn #show: apply(variant: "rose-pine-dawn") // #show: apply() #let author = "Joseph Ryan" #let title = "Kyle and David roll some dice" #set document(author: author, title: title) #set text(font: "Noto Serif", lang: "en", size: 13pt) #set page(numbering: "1", number-align: center) #set par(justify: true) #align(center)[ #block(text(weight: 700, 1.75em, title)) #v(1em, weak: true) #"October 30, 2023" ] #pad(top: 0.5em, bottom: 0.5em, x: 2em, align(center, strong(author))) #show link: underline #set highlight(fill: blue) #let rainbow(content) = { set text(fill: gradient.linear(..color.map.rainbow)) box(content) } #align(center, image("impetus.png", width: 300pt)) = Introduction Our friends Kyle and David are #rainbow[rolling dice together]/*(gay)*/. When they both roll a die, sometimes they get the same number. They wonder: "would we be more likely to roll the same number if we used _two_ dice instead of one?" = Defining terms David knows intuitively that he and Kyle have a $1/6$ chance of rolling the same number when they use a single die, but lets break down why exactly that is. $ underbrace(X_d, "David") tilde.op U(1,6) #h(20pt) underbrace(X_k, "Kyle") tilde.op U(1,6) $ $ P(X_d = X_k) = sum_(i=1)^6 P(X_d = i) * P(X_k = i) $ $ P(X_d = X_k) = sum_(i=1)^6 1/6 * 1/6 = 1/6 $ It may seem a bit silly that we're splitting it up and then summing just to get back to $1/6$, but it's a good representation of what's happening. For every possible $i$ that one could roll, we take the chance that both David and Kyle rolled that number and add up all those chances which gives us the probability that they roll the same number as each other. Unfortunately adding a second die isn't as simple because with $6^2=36$ possible rolls and only $11$ values ($2$-$12$) the distribution of numbers you can roll with a pair of dice isn't uniform. Many people know that $7$ is the most common number to roll with two dice, but here's the full set of possibilities: #pagebreak() // TIL: unicode has die faces (but only for the d6) and they're in the // "Miscellaneous Symbols" block #let nums = range(2, 13) #figure(caption: [All possible rolls], numbering: none, text(17pt, table( columns: 11, ..nums.map(n => [#n]), [ ⚀⚀ ], [ ⚀⚁ \ ⚁⚀ ], [ ⚀⚂ \ ⚁⚁ \ ⚂⚀ ], [ ⚀⚃ \ ⚁⚂ \ ⚂⚁ \ ⚃⚀ ], [ ⚀⚄ \ ⚁⚃ \ ⚂⚂ \ ⚃⚁ \ ⚄⚀ ], [ ⚀⚅ \ ⚁⚄ \ ⚂⚃ \ ⚃⚂ \ ⚄⚁ \ ⚅⚀ ], [ ⚁⚅ \ ⚂⚄ \ ⚃⚃ \ ⚄⚂ \ ⚅⚁ ], [ ⚂⚅ \ ⚃⚄ \ ⚄⚃ \ ⚅⚂ ], [ ⚃⚅ \ ⚄⚄ \ ⚅⚃ ], [ ⚄⚅ \ ⚅⚄ ], [ ⚅⚅ ], ))) == Brute force solution // cool calculator: https://topps.diku.dk/torbenm/troll.msp With that table, we can write out all the terms of the sum to compute the probability of Kyle and David rolling the same number with their pairs of dice: $ P(X_d = X_k) = sum_(i=2)^12 P(x_d = i) * P(x_k = i) $ $ underbrace(1/36 * 1/36, "chance that they" \ "both rolled a 2") + 2/36 * 2/36 + 3/36 * 3/36 + ... $ Hold on, that's going to be a pretty big and nasty sum to write out, lets try to compact it a bit. We can square each $P(X_d = X_k = i)$ term because David and Kyle should have the same probability of rolling a certain number, and then we can "fold" the list on itself because the chance of rolling a 2 through 6 mirrors that of 12 through 8. Here's a more concise version of that same sum: $ 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") $ $ &= (2*1)/1296 + (2*4)/1296 + (2*9)/1296 + (2*16)/1296 + (2*25)/1296 + 36/1296 \ &= (2+8+18+32+50+36)/1296 \ &= 146/1296 = 73/648 tilde.equiv 0.1126543210 $ And there we have it: there's about an $11%$ chance that David and Kyle roll the same number, so they're _less_ likely to do so than if they'd just rolled a single die ($1/6 = 16.overline(6)%$) == Experimental verification But wait: was our result actually right? Did we make a mistake in the arithmetic? Lets double check with some hastily written python: #set raw(block: true, theme: "gruvbox.tmTheme") #show raw: it => block(fill: rgb("#1D2021"), inset: 8pt, radius: 5pt, text(fill: rgb("#fdf4c1aa"), it)) ```python from itertools import product from random import choice as roll die = [i+1 for i in range(6)] two_dice = [a+b for a,b in product(die, die)] def test(dice, n=1000000): return sum(roll(dice) == roll(dice) for _ in range(n)) / n print("Single:", test(die)) print("Pair: ", test(two_dice)) ``` Which gives us: ``` Single: 0.16661 Pair: 0.11231 ``` Hey, that's pretty close! Having the computer roll a million dice for us sure is convenient. = Going deeper Manually computing the odds _works_, but it doesn't feel sufficiently _beautiful_ (and aesthetics is of course what math is all about). Lets start by doing away with such concretions as _dice_, for what is a die but a uniformly distributed discrete random variable? We can abstract away the dice by thinking about the size of their uniform range (how many sides they have) which we'll denote $k$, and how many of those variables we're adding together (how many dice we're rolling) which we'll call $n$. Now we can write our iterative solution from before in more general terms: $ S = {x in ZZ^+ : x <= k}^n $ $ A =^d B = inline(sum) x : x attach(in, br: r) S $ $ P(X_(n,k)) = P(A = B) $ $ = (sum_(i=n)^(k n) |{x in S : (inline(sum) x) = i}|^2)/k^(2n) $ In other words, take $S$ as the $n$-fold Cartesian product of the set of integers in $[1,k]$ which gives you $k^n$ $n$-tuples. For any two randomly selected tuples from that set, to get the probability that the sum of their elements is equal you take each number from $n$ to $k n$ and: + Count how many members in $S$ are made up of elements which sum to that number + Square that count + Sum those squared counts + Divide by $k^(2n)$ With this formal definition, we can write some code to compute the exact solution for any $n$ and $k$ instead of approximating it by running lots of simulations like we did last time. Let's write a function that fixes $k$ and shows the results for many values of $n$. This approach starts to choke if you ask for higher values like $k=20$ but we're just gonna use it to explore some smaller cases. ```python from collections import Counter def solve(k, n_max=8): print(f"{k=}") for n in range(1, n_max): totals = (sum(x) for x in product(range(k), repeat=n)) numerator = sum(i * i for i in Counter(totals).values()) denominator = k ** (n * 2) p = 100 * numerator / denominator print(f" {n=}", f"{p: 6.2f}%", f"{numerator:>8} / {denominator}") print() ``` It's often helpful to reduce a problem to its simplest case, so lets set $k=2$ (which you can think of as flipping coins instead of rolling dice) and see what the results look like: // typstfmt::off #figure( // caption: [results for $k=2$], numbering: none, table( columns: 4, [$n$], [$%$ chance], [numerator], [denominator], [$1$], [$50%$], [$2$], [$4$], [$2$], [$37.50%$], [$6$], [$16$], [$3$], [$31.25%$], [$20$], [$64$], [$4$], [$27.34%$], [$70$], [$256$], [$5$], [$24.61%$], [$252$], [$256$], [$6$], [$22.56%$], [$924$], [$4096$], [$7$], [$20.95%$], [$3432$], [$16348$], [$8$], [$19.64%$], [$12870$], [$65536$], [$9$], [$18.55%$], [$48620$], [$262144$], ), ) // typstfmt::on The denominators are pretty easy to derive, $k^(2n)$ means that in this case it's just consecutive powers of $4$. The question is how we can calculate the numerator without having to enumerate the whole set? For this we can turn to the #link("https://oeis.org/")[Online Encyclopedia of Integer Sequences] for some hints on where else in number theory this sequence shows up. When we enter $2,6,20,70,252,924,3432$ it tells us that these are the _"central binomial coefficients"_. What does that even mean? It's referring to the way that binomials expand when exponentiated: $ (x + y)^2 = x^2 + 2x y + y^2 $ $ (x + y)^3 = x^3 + 3x^2 y + 3x y^2 + y^3 $ $ (x+y)^4=x^4+4x^3y+6x^2y^2+4x y^3+y^4 $ $ ... $ If you squint at it long enough this has the same _vibe_ as our table of possible dice rolls on page 2, and when you think about the mechanics of binomial expansion it really is a similar process where coefficients near the middle "overlap" more just like rolling numbers in the middle with a pair of dice. One way to make the parallels more obvious is to drop all the variables and just look at the coefficients on each term, this becomes the famous diagram Pascal's Triangle: #align(center, grid(columns: 2, gutter: 4em, table( columns: 1, align: center, stroke: none, // TODO: generate programmatically [$1$], [$1$ $1$], [$1$ #strong[$2$] $1$], [$1$ $3$ $3$ $1$], [$1$ $4$ #strong[$6$] $4$ $1$], [$1$ $5$ $10$ $10$ $5$ $1$], [$1$ $6$ $15$ #strong[$20$] $15$ $6$ $1$], [$1$ $7$ $21$ $35$ $35$ $21$ $7$ $1$], [$1$ $8$ $28$ $56$ #strong[$70$] $56$ $28$ $8$ $1$], [$1$ $9$ $36$ $84$ $126$ $126$ $84$ $36$ $9$ $1$], ), table( columns: 1, align: center, stroke: none, ..range(10).map(i => [#for j in range(i + 1) { [ $binom(#[#i], #[#j])$ ] }]), ))) // TODO: coin head tails, talk about summing the squares of a row Now it's clear why our sequence was called "central binomial coefficients": they run along the center of Pascal's triangle which is an arrangement of binomial expansion coefficients. On the right we have the binomial expression used to compute each coefficient. $inline(binom(a, b))$ (also known as $a$ _choose_ $b$) has a closed-form solution: $ a!/(b!(a-b)!) $ Looking at the center column, it appears that we want to use $a=2n$ and $b=n$ to finally have our clean solution: $ P(X_(n,2)) &= (sum_(i=n)^(2n) |{x in S : (inline(sum) x) = i}|^2)/2^(2n)\ &= 1/4^n binom(2n, 2)\ &= (2n)! / (4^n n! (2n-n)! )\ &= (2n)! / (4^n n!^2)\ $ That's starting to look kind of beautiful! Plugging in $n=9$ we get the same $18.55%$ that we previously calculated (at the bottom of page 4), so it looks like our solution is good. // 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 // also show that it generalizes not to pascal's tetrahedron, but to n-way triangles (need to double check 4) = Cooking with gas With our solution tied so closely to binomials and Pascal's triangle, you might worry that this wont generalize to other values of $k$, but in fact it's almost trivial to use the same approach for _trinomials_. Not only that, there are fully general equations that represent _multinomials_ and a construct known as "Pascal's $m$-simplex"! As an aside, the fact that mathematicians come up with names like _simplex_ to generalize the _notion_ of a triangle or tetrahedron to arbitrary dimensions is pretty rad. Anyways the equation for the central multinomial coefficients is as follows: $ "TODO" $ Now that we have the general solution, we can calculate the odds of rolling the same number with any number of dice with any number of sides! A single six sided die is often denoted "1d6" ($n=1$, $k=6$ in our formulation), so by plugging in those values we can get the odds for 3d8 (TODO), 10d20 (TODO), 314d159 (TODO) or whatever combination we want. == Scope creep We can also answer related questions like the inverse of David and Kyle's original query doing some algebra: how many d6's would they have to roll for the chance of them getting the same number to be $~1%$? That's left as an exercise to the reader.//#emoji.face.wink. = Closing remarks // https://github.com/typst/typst/discussions/1732 #let LATEX = { [L]; box(move(dx: -4.2pt, dy: -1.2pt, box(scale(65%)[A]))); box(move(dx: -5.7pt, dy: 0pt, [T])); box(move(dx: -7.0pt, dy: 2.7pt, box(scale(100%)[E]))); box(move(dx: -8.0pt, dy: 0pt, [X]));h(-8.0pt) } Thanks for sniping me with this problem David! I've been looking for an excuse to try #link("http://typst.app")[typst] forever, and it's _such_ a breath of fresh air compared to #LATEX.