+/dice
fun little statistics problem
git clone https://git.julia.blue/+/dice
e8fe672
main
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 ) = { 22set text ( fill : gradient . linear (.. color . map . rainbow )) 23box ( 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 ( 60columns : 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): 116return 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 ^ ( 2 n ) $ 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 ^ ( 2 n ) $ 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): 173print(f"{k=}") 174for n in range(1, n_max): 175totals = (sum(x) for x in product(range(k), repeat=n)) 176numerator = sum(i * i for i in Counter(totals).values()) 177denominator = k ** (n * 2) 178p = 100 * numerator / denominator 179print(f" {n=}", f"{p: 6.2f}%", f"{numerator:>8} / {denominator}") 180print() 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, 189table ( 190columns : 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 ^ ( 2 n ) $ 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 + 2 x y + y ^ 2 $ 216$ ( x + y ) ^ 3 = x ^ 3 + 3 x ^ 2 y + 3 x y ^ 2 + y ^ 3 $ 217$ ( x+y ) ^ 4 =x ^ 4 + 4 x ^ 3 y+ 6 x ^ 2 y ^ 2 + 4 x 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 ( 228columns : 1 , 229align : center , 230stroke : 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 ( 243columns : 1 , 244align : center , 245stroke : 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= 2 n $ and $ b=n $ to finally 262have our clean solution: 263 264$ 265P ( X _ ( n, 2 )) & = ( sum _ ( i=n ) ^ ( 2 n ) | { x in S : ( inline ( sum ) x ) = i } | ^ 2 ) / 2 ^ ( 2 n ) \ 266& = 1 / 4 ^ n binom ( 2 n , 2 ) \ 267& = ( 2 n ) ! / ( 4 ^ n n ! ( 2 n-n ) ! ) \ 268& = ( 2 n ) ! / ( 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] ; 305box ( move ( dx : - 4.2pt , dy : - 1.2pt , box ( scale ( 65% ) [A] ))); 306box ( move ( dx : - 5.7pt , dy : 0pt , [T] )); 307box ( move ( dx : - 7.0pt , dy : 2.7pt , box ( scale ( 100% ) [E] ))); 308box ( 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 .