Tuesday, March 17, 2009

How Big is That Number? Special "March Madness" Episode 2^63.

Dear Dr. Math,
How many possible NCAA basketball tournament brackets are there? If I just guessed randomly, what are the odds I'd get it exactly right?

Ah yes. I love March Madness for many reasons:

1) the wide assortment of team names and mascots,
2) Dick Vitale, and
3) it's the one time of the year when people care about the number 2^63, because that's the number of possible ways of filling out a tournament bracket prediction.

Even then-future-President Barack Obama couldn't resist giving it a try! Let's see how it works, baby!

To begin with, the NCAA officials select 64 teams to play in the tournament (actually 65--there's a traditional preliminary game to determine the last team in the field, but we'll ignore that). They divide the teams up into 4 groups of 16 and then rank the teams within each group, from 1 to 16. Each group holds a single elimination tournament, with the high-ranking teams pairing off initially against the low-ranking teams, and the 4 winners (the Final Four) go on to play two more games to determine the national champion. At some point, the players cut down the nets with scissors for some reason. Predicting the way the entire tournament will unfold (that is, the "bracket") has become a popular office tradition; legend has it that no one has ever predicted the entire bracket exactly right, although some websites like Yahoo! have offered prizes of up to $1 million if anyone does it. But if they charged even a penny to play, I wouldn't take that bet. Here's why:

Each game played has 2 possibilities for a winner. Considering just the first round of games, of which there are 32, this means the number of possible ways of predicting the winners is 2^32, or 4,294,967,296. Assuming you had guessed the first round correctly, there would now be 16 games to determine the winner of, so the number of possible predictions for the second round would be 2^16 = 65,536. And so on. In the third round, there would be 2^8 = 256 possibilities; in the fourth round, 2^4 = 16; in the fifth round, 2^2 = 4, and in the final game, you'd still have to guess which of the 2 remaining teams would be the champion.

Altogether then, the number of possible ways to fill out a bracket is 2^32 * 2^16 * 2^8 * 2^4 * 2^2 * 2 = 2^(32+16+8+4+2+1) = 2^63. Another way to arrive at this number is to consider the fact that in total, 63 of the 64 teams have to lose a game over the course of the tournament, meaning there are 63 total games played. So, by the same reasoning as before, the number of outcomes of these games is 2^63 = 9,223,372,036,854,775,808, about 9.2 * 10^18. In words, that's 9.2 quintillion, a.k.a. 9.2 million trillion.

How big is that number?

Well, if you were to write out each bracket prediction on a sheet of standard paper (thickness = .1mm), you would have a stack of paper (9.2 * 10^18 * .1 * .001) = 9.2 * 10^14 meters tall, which is about 6200 times farther than the distance from the Earth to the Sun. If you stole 1 paperclip (mass approx. 1 gram) for each sheet, you'd end up with 9.2 * 10^18 * 1 * .001 = 9.2 * 10^14 kilograms of paperclips, which is the equivalent weight of 46 billion blue whales. Every person on Earth could have 7 blue whales' worth of paperclips. If, instead of working, you filled out 1 bracket per second, 24 hours a day, it would take you (9.2 * 10^18)/(60*60*24*365) = 29 million years. You'd be so busy filling out brackets that you wouldn't even notice that the tournament had ended millions of years ago, along with all of human civilization! (Probably.)

Now, does that mean your odds of picking a perfect bracket are 9.2 quintillion-to-1? Hold on just a second there, shooter. That would only be correct if you were assuming that all possible brackets were equally likely to occur. However, with a little thought, we can probably improve on that assumption considerably. For example, in the 24 years since the tournament was expanded to include 64 teams, a #1 ranked team has never lost in the first round to a #16 seed. So, even if we take the ranking as the only meaningful predictor, we can say that some brackets, namely those in which the high-ranked teams always win, are more likely than others.

Using data I found on www.hoopstournament.net, I was able to estimate the probabilities of the higher-ranked team winning each game in the tournament based on the results of past years (remind me sometime to talk about estimating bias, will you?), and my guess at the probability of the "no upsets" bracket is 1.64 * 10^-11, so the odds against the occurrence of this bracket are "only" 1.64*10^11 = 164 billion-to-1. Since we're assuming that it's always more likely for the higher ranked team to win any given game, this bracket is our best hope. Those odds are still pretty long, though. For comparison, let's say your ATM code were reset to a random 4 digit number; you'd be about as likely to win the bracket challenge as you would be to win the Powerball and then guess the new PIN on the first try (presumably to deposit your winnings).

Many of you sports fans out there are no doubt hurling expletives at the screen right about now, because, as you know, there are always some upsets. I mean, who could forget Coppin State over South Carolina in 1997, right? There's a bit of an odd paradox here: even though the "no upsets" tournament prediction is the most likely (based on our assumptions), the number of upsets is more likely to be greater than 0 than otherwise. In fact, the most likely number of upsets over the course of the tournament, according to my predictions, is about 18. (Note: I'm including "upsets" like the #9 seed beating the #8 seed--an event that has happened about as often as it hasn't over the years.)

So, the most likely scenario is that there are no upsets, and yet the most likely number of upsets is 18. How can both statements be true? The answer lies in the fact that we're not being asked to predict just the number of upsets, but the actual sequence of events:

Consider the simpler example of rolling a 6-sided die. Let's assume all faces are equally likely, but let's say we really don't want any sixes, and that's all we care about. We'll label the six-side as "L" and the other 5 sides as "W." So, the chance of winning any particular roll is 5/6. Not bad. Now let's imagine rolling this die 60 times. Since the most likely occurrence in each roll is that we'll win, the most likely sequence of 60 rolls is a sequence of 60 wins, with probability (5/6)^60, about 1.77 * 10^-5, roughly 1 in 57,000. If we put a loss in the sequence in any location (first, second, third, etc.), the probability would go down to (5/6)^59 * (1/6) = 3.54 * 10^-6, which is 5 times less likely. However, according to basic probability, the number of losses would follow what's called a binomial distribution, which has its peak (the most likely number) at the value equal to the number of rolls times the probability of losing each one. In our setup, that's 60*(1/6) = 10. If we repeated this experiment a bunch of times, the most common result would be that we'd lose 10 times out of 60.

What's going on here is that although the chance of any particular sequence of dice-rolls containing a loss is less than the perfect "all wins" sequence, there are so many more possible sequences with a loss--in fact, there are 60, versus only the 1 perfect sequence--that their probabilities accumulate to make the chance of having a loss somewhere greater than not having one anywhere. And continuing in this manner, you can see that the number of sequences containing 2 losses is even greater, despite the fact that each one is even less likely, and so on. Eventually, the two effects balance each other and the combined probability maxes out at 10 losses.

But that's not what we're being asked to predict! In order to win Yahoo!'s bracket tournament or just your office's measly little pool with a perfect bracket, you'd have to predict the precise sequence of wins and losses. People resist picking the most likely bracket because it doesn't "look random enough,"* but really they're just reducing their chances by several orders of magnitude.

In a related experiment, if a person is presented with a flashing light that can be either red or green but is red twice as often, and the subject is asked to predict the color of the next flash, most people will "mix it up," mostly guessing red but occasionally guessing green, because they feel that their predictions need to match the "pattern" of occasionally being green. They're correct to think that it's likely that the light will sometimes be green; their mistake is assuming that they can improve their odds by guessing any particular realization of that notion. As a result, they generally do worse in the experiment than lab rats, who will, reasonably enough, just keep betting on red and winning 2/3 of the time.

And that's why I'm going with the rat strategy: Louisville, Connecticut, Pittsburgh, and North Carolina in the Final Four, baby!**


*Or perhaps they feel that they have more information about a given game than the rankings would indicate. For example, a star player could have been recently injured, or a particular team's playing style might be well-suited to beating an otherwise better team. That being said, I think it's more common for people to just pick the teams they want to win and find some way to justify that prediction.

**Personal note: Once, as a nerdy kid who knew nothing about basketball, I employed this strategy in a middle school bracket challenge, picking all four #1 seeds to advance. And as it happened, I got 3 out of 4 right, more than any of my classmates, because they were all clinging to their inferior human-brained approaches. Take that, millions of years of evolution!


Scattercat said...

I would just like to point out that, as a former nerdy kid who knew nothing about math OR basketball, this was still fascinating and highly entertaining.

Mr. July said...

A ha. But some tournament brackets will skew scoring in favor of picking upsets. What happens if I get two points for every upset (higher seed beats lower seed) vs. only one for every non-upset?

How many upsets should I pick?

kngbshpp said...

So it seems that I will get a perfect A in relational algebra as it applies to the probability that anyone who has any knowledge on relational algebra will get an A. I have some knowledge on the subject but I cant predict how the emotions of players, the reputation of the school, or who will win the 8 and 9 seeds. You could say that if I guessed every 8 and 9 seed correctly my odds of winning are better than those who just guessed 3/4 of those possibilities. What I want to know is, how close is Obama to being right? If he is: does he really do enough to run our country? If he doesnt: does he have enough "Joe" in him to do what he says he can do? That is the real question my friend!!!!!!

kngbshpp said...

Oh by the way you answered my question of how many possible right answers you could have in the bracket picks because I am following Obama's picks in the road to the final four. Its 63 right!

kngbshpp said...

Mr July you need to decide if no. 8 beating no. 9 is an upset. The probability of a no. 9 beating a no. 8 increases as you spread the spread ie 7 and 10, 6 and 11, 5 and 12, 4 and 13, 3 and 14, 2 and 15 1 and 16. In my view safe picks are 1, 2, 3... just betting on the acceptance that the best ranked team will win. Thanks to know ya! lol.

kngbshpp said...

Give me your thoughts!

drmath said...

Mr. July, it's probably no longer relevant to you (sorry), but I think under the rules you describe, you'd maximize your expected value by picking any upset where you felt the probability of the upset was greater than 1/3. Your expected number of points would then be greater than the expected number if you picked the favorite. From the data I have, it looks like this is generally true of the 9-8 seed upset (probability .5) and the 10-7 seed upset (probability .38), but no others.