
Pat Sajak (after a contestant won all 3 tossups): You know, some people just have a knack for tossups. That happens more than you'd think. (after a commercial break, to Vanna): So after I mentioned the bit about winning 3 tossups, our statistitian ran out with a slip of paper. 11% of all shows last season had someone win all 3 tossups. Vanna: Huh, interesting. Me: Uh, yeah, that's about what you'd expect if all three contestants had an equal, random chance of winning any given tossup (You'd expect that to happen 1 out of ever 9 shows, or 11.1111% of the time.)
Fri, Jan. 21st, 2011, 01:30 pm
The Republicans are complaining that Obama has spent the last week working out trade agreements with President Hu Jiantao of China. The result of this seems to be $45 billion worth of new contracts for American companies, and increased protection of intellectual property so that our companies can compete more effectively in China in general. What seems to be the problem? Well, the Republicans complain, China has a less than stellar (to say the least) record with respect to human rights. (Never mind the fact that Obama managed to coax, for the first time, an aknowlegement of this fact out of President Hu). These are the same Republicans who, just a year ago, were complaining that because we were in a recession, that we shouldn't be worrying about health care, and just 2 weeks ago were pointing at job growth (or lack thereof) and saying that Obama wasn't doing enough to help end that recession. So let me get this straight. Being in a recession means that we shouldn't do anything to ease suffering at home by trying to provide health care to OUR OWN CITIZENS. But, you know, god forbid we take concrete steps to help end that recession at the expense of CHINA'S CITIZENS. (and not even, really, at their expense, but without doing anything to improve their lives)
Sun, Dec. 5th, 2010, 09:31 am
I have a solution to the last problem from my last post: What is E(max(d4!, d6!))? The technique is generalizable, but I have yet to reduce it to a closed form solution. The problem that I ran into solving this problem is that using a simple 4x6 table (as I used a 6x6 table to solve the E(max(d6!,d6!)) problem) with a recursive step in the bottom right corner (the case in which both dice explode) doesn't work because the entry in that square is either 4 + E(max(d4!,d6!) or 6 + E(max(d4!,d6!) (depending on whether you roll higher at least 2 higher on the d4! than you do on the d6!, and it's quite difficult to find the probability distribution for the two outcomes to weight the square appropriately. Expanding to additional 4x6 charts doesn't help because each is different from the previous. The solution is to create a 12x12 chart (12 = lcm(4, 6)) with weighted probabilities for later entries:  1  2  3  4  5  6  7  8  9  10  11  12+  1  1/24  2/24  3/24  4/24  5/24  0  7/144  8/144  9/144  10/144  11/144  16.2/144  2  2/24  2/24  3/24  4/24  5/24  0  7/144  8/144  9/144  10/144  11/144  16.2/144  3  3/24  3/24  3/24  4/24  5/24  0  7/144  8/144  9/144  10/144  11/144  16.2/144  4  0  0  0  0  0  0  0  0  0  0  0  0  5  5/96  5/96  5/96  5/96  5/96  0  7/576  8/576  9/576  10/576  11/576  16.2/576  6  6/96  6/96  6/96  6/96  6/96  0  7/576  8/576  9/576  10/576  11/576  16.2/576  7  7/96  7/96  7/96  7/96  7/96  0  7/576  8/576  9/576  10/576  11/576  16.2/576  8  0  0  0  0  0  0  0  0  0  0  0  0  9  9/384  9/384  9/384  9/384  9/384  0  9/2304  9/2304  9/2304  10/2304  11/2304  16.2/2304  10  10/384  10/384  10/384  10/384  10/384  0  10/2304  10/2304  10/2304  10/2304  11/2304  16.2/2304  11  11/384  11/384  11/384  11/384  11/384  0  11/2304  11/2304  11/2304  11/2304  11/2304  16.2/2304  12+  15.333/384  15.333/384  15.333/384  15.333/384  15.333/384  0  15.333/2304  15.333/2304  15.333/2304  15.333/2304  15.333/2304  (12+E(max(d4!,d6!)))/2304 
Along the top and left, we have the possible outcomes (up to 12) of rolling d6! and d4!. The interior entries are the expected result of each combination of rolls divided by the probability of rolling that combination. For example, the probability of rolling a 6 on a d4! is 1/16  you have to roll a 4 on the first roll (probability 1/4) and a 2 on the exploding roll (1/4). The probability of rolling a 5 on a d6! is 1/6 (roll 5 on the first roll, no exploding roll). The outcome of rolling a 6 on a d4! and 5 on a d6! is known  6  and the probability of running into that situation is 1/96, so the entry in the table is 6/96. A more complicated example: The probability of rolling a 10 on a d4! is 1/64 (you have to roll, each with probability 1/4 a 4, a second 4, and a 2). The probability of rolling a 12 or more (12+) on a d6! is 1/36 (you have to roll 2 6's, each with probability 1/6). The expected outcome of this combination is 12+E(d6!) = 16.2 (see previous problems), so the entry in that square is 16.2/2304 (64*36=2304). Also, note that P(4 on a d4!) = P(8 on a d4!) = P(6 on a d6!) = 0 since you wouldn't stop rolling in any of those cases, so there are two rows, and 1 column of 0's for those outcomes. Finally, the probability of rolling 12+ on a d4! and 12+ on a d6! is 1/2304, and the expected outcome of that eventuality is 12 + E(max(d4!,d6!)). Now, we can write an equation for E = E(max(d4!,d6!)): E = sum of table entries = 182809/34560 + E/2304 So E = (182809/34560)*(2304/2303) ~= 5.2919091 Clearly, this technique can be adapted to calculate E(max(dM!,dN!)). For example, if you roll a d6! and a d10!, you would create a table with dimensions 30x30 since lcm(6,10) = 30. However, I have yet to see how to sum up the entries in terms of M and N, so I can't present the reader with a closedform solution at this time.
Savage Worlds is a role playing system. My RPG group started playing an adventure in it last night. We had a lot of fun, and the game has an interesting dice mechanic which features the ominous sounding "exploding dice" (for me, this was part of the fun). Each character has several attributes (Strength, Faith, etc... think ability scores in D&D). However, instead of a number, each ability is represented as a die size (up to d12) (which I guess is a number, but you see the difference). So you can have d6 in Strength, d10 in Faith, d4 in Smarts etc etc. To resolve the outcome of an action, you roll two dice. The first is the attribute die for the appropriate attribute, and the second is the "wild" die which is always a d6. The higher value of the two rolls is kept. However, (and this is the interesting part) there is an "exploding die" rule. If you roll the maximum value for a particular die (4 on a d4, 6 on a d6, 8 on a d8 etc), that die "explodes" which means that you roll the die again, and add that result to previous result. If you roll another max on the die, the die "explodes" again and so on. If both dice explode, then you reroll both, but add keep the corresponding totals from corresponding dice. In other words, you usually roll the dice together, but the result you get is equivalent to rolling one of the dice (with explosions) and getting a total, then rolling the other die (with explosions) and getting a second total, then keeping the larger of the two totals. So, for example, if the character described above decides to try to bash in a door (a strength based action), the player would roll 2d6. Suppose he gets a 4 and a 6. The 6 explodes, so he rerolls, getting another 6 which he then rererolls, getting a 3. The first die gives him a 4, the second die gives him a 6+6+3=15. The higher result is 15. If the toughness of the door is less than 15, then the action is a success, if not, the character bounces off the door and crumbles into a heap of broken bones and spirits. Another example: if the same player wants to convert a heathen (a faith based action) he'll roll a d6 and a d10. This time, he gets a 6 on the d6 and a 10 on the d10. He explodes the 6, getting 6, then explodes again getting a 3. Exploding the 10 yields a 1. The higher result is 15 (the d6 yields 6+6+3 = 15, the d10 yields 10 + 1 = 11). If the heathen is friendly and not particularly strong willed, this would probably represent a success. If the heathen happens to be Christopher Hitchens, then the action would probably result in a failure. As a side note, if you roll snakeeyes (ie 1's on both dice), that represents a critical failure. In this case, that might mean that Hitchens converts you to atheism instead (cue Yakov Smirnoff joke about conversions in Soviet Russia). At any rate, being the math geek of the group, I want to analyze what the expected outcome of a particular roll will be. Expected value is a weighted average of all the possible outcomes (each outcome is weighted according to the probability of that outcome). Here are some warmups if you (my hypothetical reader) wants to play along: 1. What is the expected result of making a single (ie nonexploding) roll on a d4? d6? d8? d10? d12? (Generalize to dN) ( solutionCollapse )2. What is the expected result of rolling a (nonexploding) d4 and a d6, keeping the maximum result? (Generalize to dM and dN) ( solutionCollapse )3. What is the expected result of an exploding d4? d6? d8? d10? d12? Generalize to (dN). ( solutionCollapse )4. The exploding dice mechanic raises an interesting question. On smaller dice, you expect to roll smaller numbers. However, you also expect to explode more often. Is there ever an advantage, in terms of expected result in rolling an exploding M sided die instead of an exploding N sided die where M < N? ( solutionCollapse )5. What is the expected result when you roll two exploding d6's and keep the higher result? (Generalize to dN... is there a pair of integers, M<N such that you would prefer the M sided die to the N sided die?) ( solutionCollapse )And now, the difficult problem (for which I have yet to find a solution): 6. What is the expected value of rolling a d4 and a d6 with explosions?
Here's a program to calculate factorials: (2^n > 3^(n!), provided that n>0): 115/38 19/23 17/19 4147/51 17/29 31/17 259/155 41/31 129/481 37/43 17/37 47/533 41/47 53/41 177/583 53/59 61/53 67/427 1/61 355/469 67/71 17/67 57/2 Of course, the numbers involved here are very large. It took my emulator (written in Racket  formerly PLT Scheme) about 75 seconds (and 82342 iterations) to calculate that 7!=5040. The numbers involved are very large. The final state is, of course, 3^5040. However, the largest state at any time was 11^5040 * 13^5040 * 41  a number with 10865 digits. I'd like to write a program to calculate Catalan Numbers. Unfortunately, recursion (using the formula C(0) = 1 and C(n+1) = Sum (i = 0, n, C(i)C(ni))) is probably right out since all variables are global. That leaves formula C(n) = choose(2n, n)  choose(2n, n+1), but since both of those terms require multiplying large numbers, the execution time will be astronomical just to check the smallest cases.
Tue, Nov. 2nd, 2010, 09:08 am
Here's a FRACTRAN program to compute Fibonacci numbers. Input is 2^n, output is 3^fib(n) 13/11 133/85 17/19 23/17 1015/69 23/29 31/23 111/217 31/37 13/31 17/26 33/2 1/13 1/5 And one that sums up the first n integers (input: 2^n , output: 3^(1+2+3+...+n)): 165/14 7/11 13/7 17/65 38/85 17/19 1/17 105/2 And one that squares a number (2^n > 3^(n^2)) 2415/38 19/23 285/2 561/65 13/17 1/13 5/11 13/7 1/5 1/19 And one that adds the first n squares (2^n > 3^(1+4+9+...+n^2)) 7315/34 17/19 23/17 1131/115 23/29 31/161 185/403 31/37 17/31 41/23 43/533 41/43 47/41 106/517 47/53 85/2 1/47
Mon, Nov. 1st, 2010, 05:47 pm FRACTRAN
This is simultaneously the most useless and the coolest thing I've learned in (at least) the last year. FRACTRAN is a ridiculously esoteric programming language. But it's Turring complete. It's almost impossible to write anything but the simplest programs in it, but theoretically, you can write a program to compute any quantity that you could compute using any other programming language. A program in FRACTRAN is a list of fractions. You take the input to the program, find the first fraction in the list which, when multiplied by the input gives an integer, and then repeat with the product of this fraction and the integer until no fraction in the list will produce an integer when multiplied by the input. At that point, the output is whatever the current input is. The key to understanding a FRACTRAN program is to realize that the state of the program (ie the current input) uses the prime factorization of the input to store information as state, then uses the fractions to modify the state by increasing or decreasing various exponents in the factorization. That's a pretty terse mouthful. Here's a better explanationI just spent last hour or so writing a FRACTRAN program to compute gcd(a,b). The input is 2^a x 3^b and the output is 5^(gcd(a,b)). For example, to compute the gcd(24,18) you would input 2^24 x 3^18, and the output of the program would be 5^6. Here's the program: 22/19 , 21/23 , 51/55 , 11/17 , 26/35 , 7/13 , 1/11 , 1/7 , 5/6 , 23/3 , 19/2
Sun, Oct. 31st, 2010, 04:21 pm
Another Hidden Skyscraper Sudoku
Wed, Oct. 27th, 2010, 06:20 pm
Edit: Here's the rules: Sudoku Constraint: Fill in the grid with the digits 19 such that each row, each column and each 3x3 box contains each digit once. Skyscraper Constraint: The grid represents a city and each box in the grid contains a building, and the number in the grid represents the height of that building. If you stand on a particular square and look in one of the cardinal directions (NSEW), you will see some of the other buildings, taller buildings block shorter buildings. If the number of buildings that you can see in a particular direction matches the height of the building on the square, then that square has an arrow pointing in that direction. If not, then it doesn't.
Move the penalty kicks to the beginning of the game. Every game of soccer should start with penalty kicks. Use the same format that they currently use to break ties at the beginning of the game (ie each team gets 5, then if still tied, go to sudden death kicks), just do them at the beginning of the game instead of the end. Then, award the team that won the penalty kick phase 0.5 goals.
There are several reasons this should be done: 1. Breaking a tie by playing a fundamentally different game is stupid. By moving the penalty kick phase to the beginning of the game and making it part of every game, you don't have a situation where the teams are now playing checkers instead of chess. 2. Teams will be able to recover from a bad penalty kick phase. Right now, there is a lot of variance in penaltykick phases because a single fluke (a blocked or errant shot for example) can decide the whole thing. When entire games ride on this outcome, the outcomes of games are more random. If the penaltykick phase happened at the beginning, the losing team would have time to recover from the randomness. 3. If you award the team which wins the penaltykick phase half a goal, then the teams will never be tied during the regular play. This means that one team will always be behind and needing a goal. One team will always have an incentive to play harder and open up the game which will create more goal scoring in regulation.
Hockey would similarly benefit from this system, although it doesn't seem that hockey is as much in need of this fix as soccer is.
