Combinatorics, Probability, and Gambling

I did not get a chance to blog on this past Wednesday's session in the Beyond Media Computing thread, so here it is. The session was on Combinatorics, a branch of mathematics that is central to computer science. Basically, combinatorics is about how to count things. In computer science, we often need to systematically enumerate something that varies (the states of a data structure, the execution paths in code, etc.). We also often need to use probability and statistics. Combinatorics helps in these kinds of problems.

To make this a fun session, we focused mostly on probability and how it underlies gambling. We began by discussing the "MegaMillions" lottery in California. In this lottery, you select five numbers from the range 1 to 56, and then 1 MEGA number from 1 to 46. The jackpot as of 7/24/07 was $44,000,000. The question is: Is this a good bet? To make this judgement, we need to calculate the odds. Using combinatorics, we determined that the odds are 1 in 175,711,536, which is clearly a losing proposition if the return is only $44 million (for a $1 bet). And, just how hard is it to win? We determined that it is similar to tossing a coin and getting 28 consecutive heads!

We then looked at other probability problems, including those involving dice and the famous "Monty Hall" problem. The latter goes as follows: Suppose you're on a game show and you are to choose one of three doors. Behind one door is a car. Behind each of the other two doors is a goat. After you choose a door, the host opens another door which has a goat. (The host knows what's behind the doors, and always chooses one with a goat). You are then asked whether you'd like to stick to your original choice, or switch doors with the remaining one that is closed. It turns out that it is better to switch, as the probability that you will get a car with your original choice remains 1/3, but by switching, the probability of getting the car is 2/3.

Finally, we discussed the famous Gambler's Ruin problem, which basically says that, in a negative expectation game, if you play long enough, you will eventually lose everything. We closed by tying the discussion back to computer science, and why combinatorics and probability are so useful.