\documentstyle{article} \setlength{\oddsidemargin}{-.5in} \setlength{\textwidth}{7.5in} \setlength{\topmargin}{-1in} \setlength{\textheight}{9in} \begin{document} \parindent=0pt \begin{center} {\Huge \bf On the Derivation of Constrained Number Probabilities \\} \vspace{.075in} {\large \sf \copyright \ 1990 by Jim Vassilakos. All Rights Reserved. \\} \vspace{.075in} {\sf Permission is hereby granted by the copyright holder to copy and freely redistribute copies of this work, so long as no commercial or barter consideration is obtained in exchange for such copies.} \vspace{.3in} \end{center} \section{The General Problem} Given that we roll {\em n} number of {\em s}-sided dice (notated as {\em n}d{\em s}), what is the probability distribution of {\em y} such that {\em y} is the total value of {\em n}d{\em s}.\\ \section{Pascal's Triangle} \begin{center} \begin{tabular}{lccccccccccccccccc} 0 & &&&&&&&&1&&&&&&&&\\ 1 & &&&&&&&1&&1&&&&&&&\\ 2 & &&&&&&1&&2&&1&&&&&&\\ 3 & &&&&& 1&&3&&3&&1&&&&&\\ 4 & &&&& 1&&4&&6&&4&&1&&&&\\ 5 & &&& 1&&5&&10&&10&&5&&1&&&\\ 6 & && 1&&6&&15&&20&&15&&6&&1&&\\ 7 & & 1&&7&&21&&35&&35&&21&&7&&1&\\ 8 & \ \ \ \ \ \ \ \ 1&&8&&28&&56&&70&&56&&28&&8&&1 \\ \end{tabular} \end{center} \end{document} Well, it looks something like that anyway. The numbers along the left-hand side indicate the rank of the row (i.e. row #3 contains the values 1, 3, 3, and 1). The value of n (the number of dice we are rolling) indicates the row # of pascal's triangle we are concerned with. Suppose we are interested in finding the probability distribution of 3d6. We will need to consider the values 1, 3, 3, and 1. Once we have these values, we need to let every 2nd value in the series become its own opposite. Thus, we are now considering the values 1, -3, 3, and -1. Act Two Now that we're done with pascal's triangle (yawn... boring) it's time to introduce jim's parallelogram! Hazzah! Hazzah! Jim's what????! Well, it began as a paralellogram, then it devolved into a rectangle because jim was (as still is) such a messy dude that he couldn't keep his diagonal lines straight. But as they say in the Conan 'flics, that's a whole "nougther" story. Anyhow, suffice it to say that Act Two makes Act One look like a lame teaser. O'course, if I went into half the other probs pascal's triangle sets the stage for solving, Act One would be a full-length creature-feature in and of itself with pop corn and a free diet soft-drink and plenty of blood and gore and dead teenagers to boot. Pascal... what a dude. Anyways, where were we? Oh, I 'member, Jim's rectangle. Okay, here we go.... Jim's rectangle (abbreviated as "Monster" for short) is the method by which we arrive at the top-half of what I'll call the events-distribution for nds. The horizontal axis is n+1 cells long. The vertical axis is k-n+1 cells long where k=n(s+1)/2 & is rounded down to the nearest whole number. So for our example of 3d6, n=3 and s=6. k = 3(6+1)/2 (round down) = 10.5 (round down) = 10 h.a. (horizontal axis) = 3+1 = 4 v.a. (vertical axis) = 10-3+1 = 8 So far, so awful. Here's what our monster looks like just in terms of where the cells are placed. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Now we've got to make the axes, one along the top and one along the right-hand side. Note, these axes are a part of the actual monster. The horizonal axis is composed of the cells of the top-most row. The vertical axis is composed of the cells of the right-most column. We let all the cells of the horizonatal axis carry the value 1. Next, we let all the cells of the vertical axis carry the value 0. Certain cells of the vertical axis are then modified (every sth cell starting from the top-right corner to be precise). Isn't this fun? Now you know why I call it the monster. Every sth cell (6th cell for 3d6 purposes), gets to carry one of those values from Act One. See? Pascal wasn't foolin' when he said his triangle would be important! Our nth (3rd) row values (every 2nd reversed) turned out to be 1, -3, 3, and -1. We deposit value #1 into cell #1 of the vertical axis. What do you know? It just "happenstanced" to be a one. That fits nicely with the horizonal axis. We then stuff value #2 (in this case a -3) into the cell s (6) places down. That would make cell #7 go from 0 to -3. And so the story goes on and on until you're either out of values or you run out of places to stuff them. The latter case will invariably preceed the former. Thus, if you followed half of that, we get a monster looking like this... 1 1 1 1 * * * 0 * * * 0 * * * 0 * * * 0 * * * 0 * * * -3 * * * 0 Neato burrito! Now it's time for the hot sauce. You take each empty cell in the matrix and let its value equal the sum of the value in the cell above and the value of the cell to the right. In otherwords: a v = a + r <------------> v r Now we just fill in the numbers... 1 1 1 1 3 2 1 0 6 3 1 0 10 4 1 0 15 5 1 0 21 6 1 0 25 4 -2 -3 27 2 -2 0 And that's how we get jim's rectangle (aka: the monster). Act Three Okay, now the easy part. The values in the left-hand column represent the first half of our events-distribution (to translate my jargon, they represent the number of times you'd get a particular total y, if you rolled nds s^n times such that you got each possible combination once.) Here they are, just for fun... 1, 3, 6, 10, 15, 21, 25, 27. I'll illustrate the "brute force" method using 2d6 just to show you the value of the monster. With 2d6, there are 36 (6^2) possible combinations. One representation of those combinations might be as follows: Die #1 1 2 3 4 5 6 1 2 3 4 5 6 7 2 3 4 5 6 7 8 Die 3 4 5 6 7 8 9 #2 4 5 6 7 8 9 10 5 6 7 8 9 10 11 6 7 8 9 10 11 12 This, then is the events-distribution map. From here we can see how many times we get a particular total or event. Total Events 2 1 3 2 4 3 5 4 6 5 7 6 8 5 9 4 10 3 11 2 12 1 What the chance of getting an 8? 5 events out of 36 possible combinations = 5/36, or to restate it p(y=8:y=yield(2d6))=5/36. With 3d6, you've got to extend the number of possible combos into a 3rd dimension... kind of hard to show you right now. Instead of having 6^2=36 possibilities, we have 6^3=216 possibilities; the bigger your n, the yuchier it gets. As it turns out (especially with high n's), making the monster and pulling the values off his left arm is much easier than the brute force technique. We've already made monster. Now I'll show you how to pull the values out. First of all, we've got to figure out what the smallest and largest value totals can be, and that's pretty easy. Our smallest possible total is n, the largest in n*s. For 3d6 that equates to a range between 3 and 18. We can start at either extreme and just move toward the midsection. Once we get half the distribution done, we just make the other half a mirror reflection of what we've done, starting from the other extreme and moving in. As a sidebar, there are times when we won't need to copy the lower left-hand vaule and other times when we will. It all depends on whether the number of possible totals is odd or even. Here's what our 3d6 events distribution looks like. Total Events 3 1 4 3 5 6 6 10 7 15 8 21 9 25 10 27 11 27 12 25 13 21 14 15 15 10 16 6 17 3 18 1 So there's only a 21/216 chance of getting an 8 on 3d6. Of course, it's always a good idea to check your events-distribution, and one easy way to do that is to total the number of events. If they do not equal s^n (in this case 6^3=216), then you know you've got a loser. This is not to say that this check will knock out all losers, but its a good check anyway. The Programs What follows are two programs written in GW-Basic for the IBM-PC. The first runs a simulation of nds and the second runs monster's analysis. As a footnote, the "fix" command is used to round numbers down. Most "int" commands will do this, but not all so watch out if you decide to substitute. In reality (at least as far as I perceive it), fix rounds all numbers toward zero (negatives includes). Since these programs should never provide fix with negative numbers, the point is moot... but happy nevertheless. As another note, many versions of basic will stick an exclamation point at the end of large (or is is long?) numbers in the expressions (for example, lines 725 in both programs, the number 1000000 becomes 1000000!. Don't be too alarmed if your basic does this. Apparently for some odd reason, it's normal, and so isn't I. Huh? Anyways, here we go... The Simulation Program Using all the versions of basic, fortran, and pascal I've ever had the conspicuous pleasure of trying out, it is just plain impossible to write a dice-simulation program which covers the general case "nds" because... I'm getting long winded... "n" determines the number of nested loops necessary to conduct the simulation, and all these languages don't allow for this number to be variable. In otherwords, you can't say, "Hey youze guyz... I want fifty nested loops, now do it." Y'see, the computers got together and formed a union and decided they didn't have to take that sort of cr*p. So, here's what we've got, we've got a simulator which only does its job for n<=10. Bummer! 5 DIM C(100) 6 DIM P(100) 10 PRINT"DICEY.SIM: THE DICE SIMULATOR BY JPV" 30 PRINT"WHAT'S P(Y=>X: Y=YIELD(NDS), N=# OF DICE, S=SIDEDNESS)?" 70 INPUT"ENTER N,S,X:";N,S,X 100 REM ROLL 'EM! 110 FOR A1=1 TO S 115 IF N=1 GOTO 300 120 FOR A2=1 TO S 125 IF N=2 GOTO 300 130 FOR A3=1 TO S 135 IF N=3 GOTO 300 140 FOR A4=1 TO S 145 IF N=4 GOTO 300 150 FOR A5=1 TO S 155 IF N=5 GOTO 300 160 FOR A6=1 TO S 165 IF N=6 GOTO 300 170 FOR A7=1 TO S 175 IF N=7 GOTO 300 180 FOR A8=1 TO S 185 IF N=8 GOTO 300 190 FOR A9=1 TO S 195 IF N=9 GOTO 300 200 FOR A10=1 TO S 300 REM 310 D=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10 320 C(D)=C(D)+1 410 IF N=1 GOTO 600 420 IF N=2 GOTO 590 430 IF N=3 GOTO 580 440 IF N=4 GOTO 570 450 IF N=5 GOTO 560 460 IF N=6 GOTO 550 470 IF N=7 GOTO 540 480 IF N=8 GOTO 530 490 IF N=9 GOTO 520 510 NEXT A10 520 NEXT A9 530 NEXT A8 540 NEXT A7 550 NEXT A6 560 NEXT A5 570 NEXT A4 580 NEXT A3 590 NEXT A2 600 NEXT A1 700 REM TOTALS 702 PRINT 705 PRINT"SUM EVENTS PROBABILITY" 710 FOR B=N TO N*S 720 P(B)=C(B)/(S^N) 725 P(B)=INT(P(B)*1000000)/10000 750 PRINT B;" ";C(B);" ";P(B);"%" 770 NEXT B 800 REM P(Y=>X) 810 FOR B=X TO N*X 820 Z=Z+P(B) 830 NEXT B 840 PRINT 860 PRINT"P(Y=>";X;") =";Z;"%" 870 PRINT 1000 END The Monster Program 5 DIM T(20,20) 6 DIM C(50,50) 7 DIM E(100):DIM P(100) 10 PRINT"MONSTER: DICE PROBABILITY ANALYZER BY JPV" 20 PRINT"WHAT'S P(Y=>X: Y=YIELD(NDS), N=# OF DICE, S=SIDEDNESS)?" 30 INPUT"ENTER N,S,X:";N,S,X 100 REM CONSTRUCT PASCAL'S TRIANGLE 110 T(0,1)=1 120 FOR A=1 TO N 130 FOR B=1 TO A+1 140 T(A,B)=T(A-1,B-1)+T(A-1,B) 160 NEXT B 170 NEXT A 180 FOR A=1 TO N+1 190 IF A/2=FIX(A/2) THEN T(N,A)=T(N,A)*(-1) 210 NEXT A 300 REM CONSTRUCT AXES OF MONSTER 310 FOR A=1 TO N 320 C(A,1)=1 330 NEXT A 340 D=FIX(N*(S+1)/2)+1-N 350 FOR B=1 TO D 360 C(0,B)=0 370 IF (B-1)/S=FIX((B-1)/S) THEN C(0,B)=T(N,((B-1)/S)+1) 380 NEXT B 400 REM NOW THE HOT SAUSE 410 FOR A=2 TO D 420 FOR B=1 TO N 430 C(B,A)=C(B-1,A)+C(B,A-1) 440 NEXT B 450 NEXT A 490 GOTO 600 500 REM SHOW MONSTER 510 FOR A=1 TO D 515 FOR B=N TO 0 STEP -1 520 PRINT C(B,A); 530 NEXT B 535 PRINT 540 NEXT A 600 REM CONSTRUCT EVENT & PROBABILITY DATA 610 FOR A=1 TO D 620 E(A+N-1)=C(N,A) 630 P(A+N-1)=E(A+N-1)/(S^N) 640 E(N*(S+1)-A-N+1)=E(A+N-1) 650 P(N*(S+1)-A-N+1)=P(A+N-1) 660 NEXT A 700 REM GO PERCENT WITH THE PROBS 710 FOR A=N TO N*S 725 P(A)=INT(P(A)*1000000)/10000 730 NEXT A 799 GOTO 900 800 REM PRINT PROB CHART 801 PRINT 805 PRINT"SUM EVENTS PROBABILITY":PRINT 810 FOR A=N TO N*S 820 PRINT A;" ";E(A);" ";P(A);"%" 830 NEXT A 900 REM P(Y=>X) 910 FOR A=X TO N*S 920 Z=Z+P(A) 930 NEXT A 940 PRINT:PRINT"P(Y=>";X;") =";Z;"%" 950 PRINT 1000 END Just some additional notes on the programs... Unlike our three-act solution which finds the probability of totaling a specific value on nds, these programs go an extra step and find the probability of totaling a particular value or getting above that value. Sounds alot like the p-value in 100B, come to think of it. The reason the programs were designed to do this relates more to my specific application than to any idle theory (yes... I'm doing all this for a reason). If you want to see the full process as per the three-act solution, just delete lines 490 and 799 from monster, and it'll show you the whole speel of how it's getting what its getting. If "out of range" errors start cropping up, you may have to extend the variable dimensions, but other than that, the progs should work just fine. As a final sidenote, beware that for high n's the simulation program will get real slow. Just a little warning there. For the time it took to get an answer, it really didn't make sense to extend the n=<10 constraint. Anyways, that's all she wrote, or rather that's all he wrote, it being the case that it is. So long... End of Chapter Questions: hee... hee... 1) Does it work? 2) Why or why not? 3) Is there an easier method than monster? 4) Has this ever been shown before, and if so, where? Jim Vassilakos University of California, Riverside jimv@ucrmath.ucr.edu