Some football probabilities

Back in September I answered a question about probabilities in Major League Baseball's wild-card race..

John Armstrong (of The Unapologetic Mathematician fame) asked me about NFL football: assuming all teams are evenly matched, what is the probability that a division sends three teams to the playoffs? For those of you who aren't familiar with the NFL's playoff structure, there are two conferences of sixteen teams each (the NFC and the AFC); each conference is divided into four divisions of four. The winner of each division gets into the playoffs, and the two best teams among non-division winners in each conference get in as "wild cards". (For an example, see this year's final standings at nfl.com.)

This is equivalent to the following question: what is the probability that both wild cards in a conference come from the same division? I suspect that this question is inspired by the fact that this actually happened in both conferences this year, in the AFC South and NFC East respectively. (This must be especially frustrating for fans of the fourth-place team in each of those divisions. The fourth-place team in the NFC East was the Philadelphia Eagles. I think I'll avoid Eagles fans today. But that might be hard.)

Anyway, the probability that this event happens in any given conference in any given year is 2/11. Let the teams play out their season. Consider the twelve non-division winners in a given conference, and rank them in order from 1 to 12. (You might think: in the NFL each team only plays sixteen games, so won't there be ties? Perhaps, but the NFL's wild card tiebreakers don't care what division a team is in.) The top two teams get in. The divisions of the twelve teams (from top to bottom) form a word with three N's, three E's, three S's, and three W's, picked uniformly at random. Say without loss of generality that the first letter that the word starts with an N; then the remainder of the word is picked uniformly at random from permutations of NNEEESSSWWW. The chances that starts with an N are 2/11.

Alternatively, there are words which contain three each of N, E, S, and W. The number of these that begin with the same letter twice is -- pick the letter that appears twice at the beginning in one of four ways, then arrange the ten remaining letters however you like. So the probability of the two division winners coming from the same division is 67200/369600, or 2/11. I don't like this approach quite as much, though, because it involves big numbers that cancel out; it seems cleaner to me to not invoke the big numbers in the first place.

By the way, the NFL has had its current structure since 2002, and the years and conferences in which this event has actually occurred are the 2007 AFC South, 2007 NFC East, and 2006 NFC East, making three out of twelve.

The question I asked in September was not the analogue of this one (MLB only has one wild card, so there is no analogue); there I found the probability that the four MLB teams making the playoffs from any league were actually the four teams with the best records. But I don't have a general method to find the solution for some league with arbitrary structure, and the NFL would require slogging through more cases than MLB (two wild cards instead of one) so I won't bother for now. (Or probably ever -- I don't particularly care about that number.)

Why are knots so common?

Why are knots so common? This article in Science News, which I found from Slashdot, gives a bit of an explanation. (There are links to further, more scholarly, articles in the Science News piece; it's Sunday morning, though, so I'm not bothering to read them.)

My instinct is that any measure of knottedness is bounded below, but not above. You can't get more unknotted than, well, an unknotted string, but conventional measures of knottedness (say, the crossing number) can get arbitrarily large. So we can imagine a random walk on the positive half-line, which takes values which are the crossing numbers of some random process which generates knots; the crossing number will tend to be some medium-sized positive number, just because whenever it's zero it gets forced away.

Unparadoxes

I just discovered Scott Aaronson's blog, Shtetl-optimized. You should discover it as well.

I am currently being amused by the comments to his post soliciting unparadoxes, which are what they sound like -- results that superficially resemble well-known paradoxes, but are actually not paradoxes at all. For example, "The Banach-Tarski Unparadox: If you cut an orange into five pieces using a standard knife, then put them back together, the result will have exactly the same volume as the original orange." This seems to me to be a new class of mathematical jokes; only someone who had heard of the Banach-Tarski paradox would appreciate why one would ever expect it to be possible to cut an orange up in any other way!

Take a look through the comments to Aaronson's post, which give about a hundred more examples; I won't try to come up with any of my own.

Gravity pods

The game Gravity Pods is a very fun game, and it vividly illustrates the principle of sensitive dependence on initial conditions. You're asked to fire a projectile in an area which includes some gravitational attractors, in an attempt to hit a given target. (At later levels you can move some of the attractors around. At even later levels there are repulsive objects, a nice twist. There might be even more tricks later, but I haven't gotten that far.)

It was an even more vivid illustration of sensitivity before, because in earlier incarnations of the game there were levels that could not be beaten -- it would be possible to fire at an angle of 10 degrees from the horizontal, or 10.1 degrees (0.1 degrees is the finest control you get over the angle at which the projectile is fired), but 10.05 degrees (say) is what you really needed. Similarly, the movable attractors and repellers can only be placed to the nearest pixel. I don't think this problem exists any more, but there are still annoying (although perhaps fascinating as well) levels in which sub-pixel positioning abilities would be nice.

On the Mian-Chowla sequence

An interesting problem from Additive Combinatorics by Terence Tao and Van Vu. (This is almost a direct quote; I've modified it slightly in order to be able to render it entirely in HTML.)

Exercise 6.2.5. Let S = {1, 2, 4, 8, 13, 21, 31, ...} be the Sidon set of positive integers constructed by the greedy algorithm (this set is sometimes known as the Mian-Chowla sequence). Show that the kth element of S does not exceed (k-1)³ + 1, and hence the number of elements of S which are less than n is Ω(n^1/3) as n goes to infinity.

A Sidon set, for those of you who don't know, is a set for which all the pairwise sums are distinct. Tao and Vu credit this result to Stöhr; see below. A rough translation of the title of that paper is "Solved and unsolved questions on bases of sequences of natural numbers", although my German isn't so good. (I've been looking for mathematics written in German, though, because my department requires me to be able to read two of mathematical French, German, and Russian -- I've already passed the French and I know a little German and no Russian -- so I might try to read this, or at least parts of it.)

First, an example of where these numbers are coming from. Let s₁ = 1, s₂ = 2, s₃ = 4, and so on form the sequence S. Say we know the first four terms, s₁ through s₄, are 1, 2, 4, 8. Then 9 can't be in the sequence, because 9 + 1 = 8 + 2. 10 can't be in it, because 10 + 2 = 8 + 4. 11 can't be in it, because 11 + 1 = 8 + 4. And 12 can't be in it, because 12 + 4 = 8 + 8. But none of 13 + 1, 13 + 2, 13 + 4, and 13 + 8 are pairwise sums of {1, 2, 4, 8}, so the fifth term is 13. It turns out to be easier, I think, to think in terms of differences instead of sums; we say that 9 can't be in the sequence because 9 - 2 = 8 - 1, and so on. So if s₁, ..., s_k are known, we choose s_k+1 to be the smallest integer N such that the intersection

is empty.

The solution is straightforward. Now, by the "greedy algorithm" it's meant that if we know s₁ through s_k, then s_k+1 is the smallest integer greater than s_k which doesn't violate the definition of our sequence. Then it's enough to minimize the difference t_k = s_k+1 - s_k; this is the smallest positive integer which does not occur among pairwise differences of elements of {s₁, ..., s_k}. There are k(k-1)/2 such differences, and they're not necessarily distinct, so the smallest positive integer which doesn't occur is at most (k(k-1)/2) + 1, or . Then the s_k are just the partial sums of the t_k, so we get

which is asymptotically equal to k³/6.

The same method gives a lower bound -- all the differences s_k - s_i for i < k are distinct, so t_k is at least k+1. This gives a lower bound for s_k of order k²/2.

The continuation of the sequence can be found in the Encyclopedia of Integer Sequences; it shares its first eight terms with this sequence, with which I confused it at first. The condition for computing this "impostor sequence" is that

be empty. The impostor sequence begins {1, 2, 4, 8, 13, 21, 31, 45, 60, ...} and it's at the term "60" that it first differs from the Mian-Chowla sequence. We have 60-45 = 15, and 15 never occurs as a difference between any of the first eight terms. But 60 - 31 = 31 - 2 = 29, so 60 isn't the ninth term of the Mian-Chowla sequence; that turns out to be 66. The divergence only gets wider after that. But the upper and lower bounds that I gave above still apply!

It appears (from computations of Frank Chu) that the nth term of the Mian-Chowla sequence grows like n^2.8. I don't know why this should be, though. However, the sequence I confused it with is the partial sums of the segmented numbers; the nth segmented number is about n lg lg n (this is just a conjecture, but a reasonable one) and so my impostor sequence should grow like (n² lg lg n)/2, which fits the known values reasonably well. Since my impostor sequence has fairly weak conditions allowing us to extend it, I would conjecture that its growth rate is close to the lower bound, of order n², and so n² times a subpolynomial function seems nice. I'd actually conjecture that the Mian-Chowla sequence grows like n³ divided by some subpolynomial function -- but which one? Finally, something about the fact that we're looking at collisions between the difference sets makes me think that there might be a probabilistic model for this problem.

References
Frank Chu. Notes on the Mian-Chowla Sequence. http://www.cumc.math.ca/2004/mc.pdf
A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe, I, II. J. Reine Angew. Math. 194 (1955), 40-65; 111-140.
Terence Tao and Van Vu, Additive Combinatorics. Cambridge: Cambridge University Press, 2006.
Encyclopedia of Integer Sequences: A004978, A005282.

A couple articles from the Princeton Companion to Mathematics

Differential forms and integration (10 pp.), from the forthcoming Princeton Companion to Mathematics. (From Terence Tao, who has also written other articles for the PCM. I think it would have been rather nice to receive such an article at the outset of the class in which I learned about this stuff, as it would have helped to give some context; although one can often get context from a textbook, it's difficult to do so because all the little explanatory bits are often mingled with the details. The PCM articles I've seen do not suffer from this flaw; indeed, one might describe a lot of them as what the preface of a textbook covering the same material should be.

In a less theoretical, and less general, vein, here's Frank Kelly's The Mathematics of Traffic in Networks, also from the PCM, which I learned about from a post from Tao last week. One thing this mentions is the paradox that under certain conditions, adding roads to a road network can make trips slower, even though each driver tries to minimize their own time spent on the road. (Fortunately, my life is arranged so that I walk almost everywhere; thus at the moment I only appreciate the weirdness of traffic on a theoretical level. But I know it won't always be like that.) I'd be interested to see if this paradox occurs in actual road networks or only in the contrived example that Kelly gives.

The PCM will sell for about $100, so I probably won't buy it when it comes out. But I suspect I will spend some time browsing it when our library gets it.

A postal nomogram

Nomograms are collections of curves drawn on a sheet of paper that are used to do a specific calculation. See, for example, this Google Image Search. A typical example calculates some real-valued function of two variables by having three scales. Two of these scales, usually, are straight lines (although they don't have to be); these lines are marked with values of the two inputs to the function. To compute a value of the function f(a,b), you find the point marked "a" on the first scale, and the point marked "b" on the second scale; then you draw a straight line between those two points, and the marking of the point where that intersects the third scale is the value of f(a,b).

The simplest possible example would probably be the nomogram that computes the function f(a,b) = ab/(a+b); to obtain this, the "input scales" are just the x and y axes marked off as usual, and the "output scale" is the line y=x, with the marking z at the point (z,z). The line from (a, 0) to (0, b) intersects the line y = x at (ab/(a+b), ab/(a+b)). This is known as the "parallel resistance nomogram", since the resistance of an a-ohm resistor and a b-ohm resistor in parallel is ab/(a+b). More complicated computations can be done with more complicated curved scales.

You might think that these don't exist any more, since isn't it possible to compute things to any desired accuracy with modern computers? But today I saw an example of something similar at a United States Post Office. Apparently the Post Office has regulations saying that packages with volume under one cubic foot are to be treated differently than those with volumes over one cubic foot. You could ask the people behind the counter to do the multiplication, but that might be asking for trouble. So the postal service has made a mat which has the curves xy = 1728/h plotted on it, for various values of h; the curves are labelled with h. (So, for example, the curve passing through (16, 12) is marked 9, since a 16-by-12-by-9 package is one cubic foot, or 1728 cubic inches.) The postal employee can place a package on the mat, with one corner at (0, 0); the opposite corner will be at (l, w) where l and w are the length and width of the package. Then the curve which passes through the opposite corner is the maximum height allowed for the package. I wish I could find a picture of it online, but I can't. This isn't exactly a nomogram (at least under the definition I've seen), but it's very much the same principle. And it's quite interesting to see one "in the wild".