Monday, March 31, 2014

NCAA bracket odds

We're down to the "Elite 8" in the 2014 NCAA tournament. I've been hearing some discussion of the odds of filling a "perfect bracket." It has been discussed at On Point Radio, which I listen to frequently. The program aired on March 26, 2014. USA Today has a youtube video up of a DePaul math professor estimating the odds. He comes up with an estimate that a savvy bracket filler has about 1 in 128 billion odds of filling in a perfect bracket. It's March Madness.

Then I thought to myself, how did the professor get there? USA today does not go into the details. I wonder what the odds are of finding real math in USA today on a given today? Probably slimmer than 1 in 1 million. I'll point out that precision does not matter when we're finding astronomically long odds. I'll call this a ballpark estimate. With probabilities this small, the upshot is that you'll never win. It's worse than playing lotto.

Let's do some math. Sixty-four teams compete in the NCAA tournament. There are six rounds, including the final game. So we have 32+16+8+4+2+1 = 63 games played. In order to fill out a perfect bracket, I have to choose 63 winners correctly. If we were flipping a coin, there are

possible sequences of 63 coin flips. A bracket filler would have odds of about 1 in 9 quintillion of filling out the bracket correctly. There is no hope of winning here.

But we are not flipping a coin. Suppose you're a savvy odds maker. You know which teams are ranked highest in the tournament. You study basketball statistics, etc. I will quantify your savvy thusly: you have a 90% probability of picking a winner of 16 games in the first round. You have a 90% probability of picking a winner of 16 games in the second round. Your probability of picking all the other winners is 50/50, the same as flipping a fair coin. What is your probability of filling in the bracket correctly? You have to correctly choose 63 mutually exclusive events with a probability of .9 for 32 of them, and .5 for the other 31. Since the events are mutually independent, the individual probabilities multiply. That gives us a final probability of

or odds of

This is roughly twice as much probability as the DePaul math professor estimated. So, my hypothetical savvy guesser had roughly twice as much savvy, but he is still hopeless when it comes to filling in the bracket correctly.

Here is some R code to calculate and print the numbers here. We're right on the edge of R's basic precision, where p could be rounded down to zero. If I change the numbers slightly, I would need to use the Rmpfr package (or logarithms) to get a non-zero printout.

> p=c(0.9,0.5)
> games=c(32,31)
> prob=prod(p^games)
> prob
[1] 1.598934e-11
> 1/prob
[1] 62541682939
> format(1/prob,dig=3,sci=T)
[1] "6.25e+10"

Friday, March 28, 2014

Gratuitous Friday Food Blogging

I used to occasionally make an omelet for breakfast, but now I make fritattas instead. This one had bell pepper, mushroom, onion, and mozzarella cheese in it. I bake it in a 400° oven for about 14 min. It was pretty good. De gustibus non est disputandum, of course.

Friday, March 14, 2014

Calculating pi with a random number generator

It's π day (3/14), so let's estimate π, the ratio of circle's diameter to its circumference, with a random number generator. This post is a blatant ripoff of Rhett Allain's post on the occasion of π day 2010. We're doing this just for fun, of course. The method used here is terribly inefficient. No doubt anyone reading this knows that google can give you a slice of pi. It's also easy to find a page with 100,000 digits of pi. Most calculators and calculator apps have a π key, of course. If you can't find a few digits of π, you're not looking very hard. There is a very nice page at Mathworld that is loaded with approximations for π. Check it out.

Ok. Let's get down to estimating the first few digits of π with a random number generator. I'll be using R and the default random number generator in R, which is the "Mersenne twister." It's used in R, python, php, ruby, and many other software systems. It has a period of $2^{19937} -1$; its "seed" is a vector of 626 integers. To be technically accurate, we should refer to it as a pseudorandom number generator (PRNG), since it is an algorithm. It is not truly random since its output is determined by initial conditions.

To calculate π, we'll focus on the first quadrant of the x,y plane within the square (0,0),  (1,0),  (1,1), and (0,1). We'll use our PRNG to generate $N = 2^{17}$ random pairs and then graph them. We'll be using a uniform random number generator, of course. Here is the R code used to generate the graph:

r = function(z) { return(sqrt(z[1]^2 + z[2]^2)) }
x = runif(N) ; y = runif(N)
color = rep(c1,N)
dists = apply(cbind(x,y),1,r)
color[dists > 1] = 1
plot(y ~ x, pch=".", col = color)
ins = length(color[color == c1])
est = 4 * ins / N
cat(sprintf("estimate for pi = %.4f",est))

The apply() function is used here to calculate the distance from each point to the origin. Our interface to the PRNG is runif(), which returns a random uniform deviate. If the point lies within the unit circle, it is colored. If it lies outside, it will be black. When run, the following graph is generated:

Now, since the points were chosen with a uniform distribution, we expect a fraction π/4 of them to be colored, and 1 - π/4 to be black. The program simply counts the number of colored points and estimates π as 4 times this number divided by N. When I ran it just now, the program printed

estimate for pi = 3.1428.

So that's our Monte Carlo estimate for π.

Sunday, March 2, 2014

Hyperreal Numbers and Calculus without Limits

Once upon a time, I stumbled into a hyperreal number field on the internet when searching for something related to calculus. Maybe I was calculating the volume of a Steinmetz Solid? The so-called hyperreals can be used to develop the calculus without limits. The claim is made that, perhaps, the use of "infinitesimals" is less confusing than the concept of the limit for struggling calculus students. In fact, there is a calculus text using this approach that one can download for free from this page. The author, H. Jerome Keisler, is a professor emeritus of mathematics at UW-Madison.

What are the hyperreals? They are an extension R* of the field of real numbers, which is usually denoted by RR is a subset of R*. Without going in to too much detail, R* is obtained from R by adding in infinitesimals and infinitely large numbers. An infinitesimal number is infinitely small. What does this mean? For every real number a, a number ε > 0 is infinitesimal if -a < ε < a. That's it. In contrast, 1/ε is infinitely large (a "hyperinteger"). Conceptually, hyperreals are similar to complex numbers. However, unlike the complex numbers, they are depicted in one linear dimension, not a two-dimensional plane. The nitty gritty is all in Keisler's book. With the concept of the infinitesimal available, we can have the hyperreal quantity x + ε that is infinitely near x. This hyperreal x + ε can then be used to formulate the derivative, which won't be surprising to anyone who has studied calculus.

Here's figure 1.4.3 from Keisler's book. An "infinitesimal microscope" has been used to zoom in on the hyperreal number line:

The infinitesimal microscope is a captivating pedagogical concept. I claim that it's easier to grasp than the concept of a limit. Children learn about microscopes in grade school. Maybe they learn about it nowadays by zooming in on their iPads. In any case, R* is a useful mathematical concept that can be used to formulate the calculus without that ungainly Σ thing. All you need is a little ε guy. :-)  Keisler's book provides more than 800 pages of evidence.

The history of infinitesimals is interesting. The epilogue [pdf] to the aforementioned calculus text lays out the story. Archimedes anticipated both infinitesimals and the ε, δ approach of limits in some of his proofs. In the 17th century, the modern calculus was developed independently by Newton and Leibniz. In his reasoning, Newton used both infinitesimals and the concept of a limit as well as the so-called velocity method. Leibniz used infinitesimals. So there were three competing methods for doing calculus: infinitesimals, limits, and the velocity method. Jumping ahead (see Keisler's epilogue for whole story), the first truly rigorous treatment of calculus was formulated by Karl Weierstrass in the 1870's. I believe it was Weierstrass who introduced the  ε, δ notation that we still use today.

There can be little doubt that the limit approach is firmly entrenched in the current pedagogy. Other than Keisler's book, I am unaware of any other textbook that uses this approach. I never heard it in Altgeld Hall or Van Vleck. Mathematics teachers should be aware of this alternative approach and should consider using it to introduce students to derivatives and integrals.