A third of my life

I’m 28 years old. A perfect age! (Don’t wish me a happy birthday, I’ve been 28 for a few months.)

Recently it occurred to me that I’ve lived a third of my life, at least if you believe the classic biography of Diophantus:

‘Here lies Diophantus,’ the wonder behold.
Through art algebraic, the stone tells how old:
‘God gave him his boyhood one-sixth of his life,
One twelfth more as youth while whiskers grew rife;
And then yet one-seventh ere marriage begun;
In five years there came a bouncing new son.
Alas, the dear child of master and sage
After attaining half the measure of his father’s life chill fate took him. After consoling his fate by the science of numbers for four years, he ended his life.’

(translation from Wikipedia)

I’m pretentious enough to quote this in Latin, except that I don’t know Latin. If you are pretentious enough to know Latin (and I think I have at least one reader who is), go to the Wikipedia article for the original.

But there are other classical amounts of time that are cited as the typical lifespan: “three score years and ten” Psalm 90:10 is the most frequently mentioned. Genesis 6:3 suggests that the maximum human liefspan is 120 years. My father says he’ll live until 100 (I think he started saying this in his forties, so he could convince himself that he wasn’t middle-aged yet).

So what proportion of my life have I lived? Or, because you don’t care about me, what proportion of one’s life has one lived at age X? We can’t just divide by the life expectancy. Let’s say life expectancy is 70; then I’d have lived two-fifths of my life by now. But that means that when I am 70, I will have lived my entire life. And when I’m 77, I will have lived 110% of my life! Clearly the proportion of my life that I’ve lived, at 28, is 28 divided by the expected age at which a 28-year-old dies.  A quick look at a life table says that the “expectation of life at age [28]” is 50.8 — so a typical 28-year-old should expect to live to 28 + 50.8 = 77.8. Therefore I have lived 28/78.8 of my life, or about 35.5 percent. The life expectancy at birth, according to the same table, is 77.4, and 28/77.4 is about 36.2 percent. I just got 0.7 percent of my life back by doing this calculation! But I’ve probably spent more than 0.7 percent of my life learning how to do such calculations.

Vladimir Bulatov, Conformal models of hyperbolic geometry.

The chance shirt machine (auf Deutsch).

Laura McLay, The conditional probability of being struck by lightning, parts one and two.

Foursquare asks: What neighborhood is the ‘East Village’ of San Francisco?, based on what type of establishments people check into in various neighborhoods.

Duels, truels, and game theory gunslinger rules, by David Barash, author of The Survival Game: How Game Theory Explains the Biology of Cooperation and Competition (which I have not read).

Galperin’s billiard method of computing pi, from Calculus VII.

Spiked Math IQ Test. I got a zero. Perhaps knowing this will help you get better than zero.

Taking PhD comics too literally

March 14 PhD comics includes a plot. The x-axis is “time spent staring at your computer” and the y-axis is “probability you’ll come up with a brilliant idea”. The graph is a horizontal line.

This has two possible interpretations:

• the intended one: at least at the time depicted in the comic, no ideas come. this corresponds to interpreting the y-axis as the cumulative probability that an idea will come by time x.
• the hopeful one: let’s say I stare at my computer for 24 hours straight, starting now. The probability that I come up with a brilliant idea between 11:00 AM and 11:01 AM, say, is the same as the probability that I come up with a brilliant idea between 11:00 PM and 11:01 PM. In other words, brilliant-idea-having is a Poisson process. But then if I wait long enough, I should almost certainly come up with a good idea. This corresponds to interpreting the y-axis as the rate of a Poisson process at time x.

The truth is probably somewhere in between: 40 hours a week is as productive as 55. And Cham, we’re meant to understand, is depicting that part after 40 hours in a week where the brain just won’t get more done.

My name is supervocalic

So it was pointed out to me yesterday that my name (“Michael Lugo”) has each of the five vowels (a, e, i, o, u) exactly once. Such a word is called supervocalic.
What are the chances of that?

A quick calculation: assume that letters have the frequencies given in the Wikipedia article for English. In particular the frequencies of A, E, I, O, and U are 8.167%, 12.702%, 6.966%, 7.507%, 2.758%. The frequency of all other letters combined is 61.900%; call this q. Call the product of these c; the value of c is about $1.50 \times 10^{-6}$.

Now assume that names are created by picking letters independently at random. To construct a string in which each vowel appears exactly once, we must:

• decide where the vowels will appear. We can do this in $n(n-1)(n-2)(n-3)(n-4) = n!/(n-5)!$ ways; here order matters.
• put A, E, I, O, U in those five pre-chosen positions, and consonants in the others; the probability of this is $C q^{n-5}$.

So a string of length n has probability ${n! \over (n-5)!} C q^{n-5}$ of having each vowel occur exactly once. For $n = 6, 7, \ldots, 20$ I give those probabilities in the following table:

 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0.0007 0.0014 0.0024 0.0033 0.0041 0.0047 0.005 0.005 0.0048 0.0045 0.004 0.0035 0.003 0.0025 0.0021

For example, a name of length 11 (like mine) has probability about 0.0047 of containing each vowel exactly once. The string length which is most likely to be supervocalic is 13; that makes sense, as a typical string is thirty-eight percent vowels, and five is about thirty-eight percent of thirteen. It’s hard to go much further with this, though, because I don’t have the distribution of lengths of names. But whatever the distribution of name lengths, the proportion of supervocalic names is bounded above by one in two hundred. Special, but not that special. (My instinct is that supervocalic names are probably a bit more likely than this, because the distribution of the number of vowels in a name of length $n$ is probably more tightly concentrated than a binomial.)

Ken Jennings has a list of sets that contain exactly one such word, many of which contain less than a couple hundred elements, but it’s hard to say what that means in this context. For more words with this property, see the message boards; in particular there are some nine-letter examples. Getting much shorter than that seems to interfere with euphony, which my model doesn’t take into account. There have been 250 major league baseball players who have each vowel at least once; many have each vowel exactly once. Many of them are named Charlie; few, it seems, are named Michael, because your typical baseball player is more likely to go by Mike.

Happy Pi Day!

March 14 is Pi Day, in recognition of the fact that the first three digits of the decimal approximation of π are 3.14.

My alma mater, MIT, will make admissions decisions available at 6:28 pm (US Eastern time). Click the link, there are funny pictures.

They used to do it at 1:59 pm (so the date and time formed 3/14 1:59) but the move to 6:28 means that they can satisfy the tauists.

On the probability of coincidences (but not really)

I am teaching statistics at Berkeley, where we use the Freedman, Pisani, and Purves text for many of the introductory courses. Since the text is titled Statistics, like a lot of other books, it’s referred to by the names of its authors. But “Freedman, Pisani, and Purves” is too long, so generally we call it “FPP”.

I’ve heard some people who have been around the department for a while call it “Freedman”, and indeed it does have some stylistic similarities with Freedman’s other books, such as Statistical Models: Theory and Practice. And since we’re talking about coincidences, I believe Pisani is not the CNBC correspondent of the same name, or the financial trainer, or any of various others with the same name. (Pisani’s reminiscences upon the death of Blackwell tell us that he was a lecturer at Berkeley for a long time, which seems like something these people would mention in their bios; he also got his PhD in 1970, and these two Pisanis seem younger.) While I’m on the subject, this is a wonderful, well-written book for introductory statistics classes, although sometimes it suffers from using language too well… my sense is that Kids These Days1 aren’t used to reading, and some are more comfortable with cookbook-style textbooks that will just tell them what to do. I try to break this down in my classes, but as anyone who’s taught (or learned!) knows, that’s not easy.

I also participate on the “community weblog” metafilter. There FPP refers to a “front page post”, i. e. a post made to the “front page” of the site, usually consisting of links to one or more related web sites. It would be hopelessly meta to make a front page post about Freedman, Pisani, and Purves, but I don’t have it in me. An interesting question: how many three-letter acronyms should we expect exist in my life, given that there’s a collision between two of them? By analogy with the birthday problem, the number must be at least on the order of the square root of the number of possible such acronyms, i. e. a hundred or so — surprisingly small.

The text doesn’t abbreviate “simple random sample” to SRS, but I’m tempted to sometimes in my lecture notes. But of course that conflicts with the abbreviation for “stratified random sample”. Or for “sexual reassignment surgery”.

(On titles of books: there are at least three books in my library entitled Algebra, namely those by Artin, Hungerford, and Lang. This barely counts as a coincidence, because that is the most obvious title for an algebra book.)

1. I use “Kids These Days” ironically, being still in my twenties.

Taalman and Rosenhouse on Sudoku

Jason Rosenhouse and Laura Taalman have written an excellent book, Taking Sudoku Seriously. Despite the title, this is not primarily a puzzle book; rather it uses Sudoku, and the idea that mathematicians are essentially puzzle solvers, as a gateway into explaining to the general reader what it is that mathematicians do. The book actually contains very few standard Sudoku puzzles but a large number of variations on the standard theme. This is more interesting than standard Sudoku, I find; once you learn how to do standard Sudokus you essentially are just executing an algorithm mindlessly.

(Don’t borrow this book from a library, as I did, if you intend to do the puzzles, unless you’re okay with hogging a copy machine for a while; also, even then, some puzzles in this book involve color in a meaningful way.)

Some Sudoku-related facts from this book that I found interesting:

How many filled-in Sudoku squares are there? The authors begin by carefully working through counting “Shidoku” puzzles; this is like Sudoku, but 4-by-4 instead of 9-by-9. The method is essentially to fill in the upper left 2-by-2 square; then finish the first row and first column. If we start with

 1 2 3 4 3 4 2 4

then there are three ways to complete this board. Each of these represents 96 possible Shidokus, obtained by switching the third and fourth columns, or not; switching the third and fourth rows, or not; and permuting the numbers 1, 2, 3, 4. So there are 288 possible Shidokus. But many of these are equivalent; it turns out that there are only two essentially different Shidoku puzzles:

 1 2 3 4 3 4 1 2 2 1 4 3 4 3 2 1

and

 1 2 3 4 3 4 1 2 2 3 4 1 4 1 2 3

and all others can be reached from these by various symmetries, including relabeling the digits, permutation of certain rows, columns, or blocks, and rotations or reflections. These symmetries form the Shidoku group; unfortunately the orbits of its action on the set of Shidokus are of different sizes! (There are 96 Shidoku puzzles equivalent to the first one above, and 192 equivalent to the second, for a total of 288.

Determining the number of Sudoku puzzles is harder. There are 948,109,639,680 ways to fill in the first three rows of a Sudoku, satisfying the Sudoku constraints. (See the Wikipedia article on the mathematics of Sudoku.) This actually gives a nice heuristic argument for the total number of ways to fill in a Sudoku. There are $(9!)^3 \approx 4.78 \times 10^{16}$ ways to fill in the first three rows of a Sudoku if we just force each row to have nine different numbers and ignore the constraint on the blocks. So if we fill in the first three rows by filling each row with a permutation chosen uniformly at random, then the probability of satisfying the block constraint is $948109639680/(9!)^3 \approx 1.98 \times 10^{-5}$; call this number $p$. Now imagine filling all nine rows of a Sudoku with permutations chosen uniformly at random; there are $(9!)^9$ ways to do this. But now the probability that the top three blocks satisfy the block constraint is $p$; the same is true for each of the three rows of blocks and each of the three columns. If we assume these constraints are independent, which they’re not, then we estimate that the total number of 9-by-9 squares with each row containing nine different numbers, and each set of three blocks forming a row or column being valid in Sudoku, is $(9!)^9 p^6$. But these are just filled Sudokus, and that number is about $6.6 \times 10^{21}$. Perhaps coincidentally, but perhaps not, the actual number of Sudokus is about $6.7 \times 10^{21}$, as shown by Felgenhauer and Jarvis; the heuristic is due to Kevin Kilfoil.

How are sudoku puzzles constructed? One way to do it is to set a “mask” — a set of squares within the puzzle which will be filled in — and then populate randomly and count the number of solutions. Then make random changes to the numbers filling in this mask, generally but not always reducing the number of solutions, (The authors state that something like this was used to form the puzzles in the book by Riley and Taalman, No-Frills Sudoku.)

Sudoku puzzles can be encoded in terms of graph colorings. Each square in Sudoku becomes a node, and we draw an edge between two vertices that can’t be filled with the same number; then the question is to extend a partial coloring of the Sudoku graph to a full coloring.

But they can also be encoded in terms of polynomials For these purposes we’ll play Sudoku with the numbers -2, -1, 1, 2, 3, 4, 5, 6, 7. Let each cell of the Sudoku be represented by a variable. Then for each cell we have an equation $(w+2)(w+1)(w-1)(w-2)(w-3)(w-4)(w-5)(w-6)(w-7) = 0encoding the fact that it contains one of these nine numbers, and for each region of nine cells (row, column, or block) we have two equations$latex x_1 + x_2 + \cdots + x_9 = 25, x_1 x_2 \cdots x_9 = 10080\$

encoding the fact that each of the nine numbers is contained in the region exactly once. (Why not use the usual numbers, 1 through 9? Because there is another set of nine integers that has sum 45 and product 362880; can you find it?)

I’ll close with an extended quote that I think bears repeating (pp. 115-116):

Your authors have been teaching mathematics for quite some time now, and it has been our persistent experience that this lesson [that hard puzzles are more interesting to solve than easy puzzles], obvious when pondering Sudoku puzzles, seems to elude students struggling for the first time with calculus or linear algebra. When presented with a problem requiring only a mechanical, algorithmic solution, the average student will dutifully carry out the necessary steps with grim determination. Present instead a problem requiring an element of imagination or one where it is unclear how to proceed, and you must brace yourself for the inevitable wailing and rending of garments.
This reaction is not hard to understand. In a classroom there are unpleasant things like grades and examinations to consider, not to mention the annoying realities of courses taken only to fulfill a requirement. Students have more on their minds than the sheer joy of problem solving. They welcome the mechanical problems precisely because it is clear what is expected of them. A period of frustrated confusion can be amusing when working on a puzzle, because there is no price to be paid for failing to solve it. The same experience in a math class carries with it fears of poor grades.

Finally, if you don’t have time to spare to read the whole book, look at Taalman’s article Taking Sudoku Seriously. If you like your math in podcast form, listen to Sol Lederman’s interview with Rosenhouse and Taalman. If you could care less about math but want books of Sudoku: No Frills Sudoku (standard Sudoku, but starting with an astonishingly low 18 clues each), Naked Sudoku (Sudoku variants with no starting numbers), Color Sudoku (more graphically interesting).