Good's "singing logarithms"

I've previously mentioned Sanjoy Mahajan's Street Fighting Mathematics. (Yes, that's right, almost the entire sentence is links, deal with it.)

One thing I didn't mention is approximating logarithms using musical intervals, from that course. We all know 2¹⁰ and 10³ are roughly equal; this is the approximation that leads people to use the metric prefixes kilo-, mega-, giga-, tera- for 2¹⁰, 2²⁰, 2³⁰, and 2⁴⁰ in computing contexts. Take 120th roots; you get 2^1/12 ≈ 10^1/40.

Now, 2^1/12 is the ratio corresponding to a semitone in twelve-tone equal temperament. So, for example, we know that 2^7/12 is approximately 3/2, because seven semitones make a perfect fifth. So log¹⁰ 3/2 ≈ 7/40 = 0.175; the correct value is 0.17609... Some more complicated examples are in Mahajan's handout.

You might think "yeah, but when do I ever need to know the logarithm of something?" And that may be true; they're no longer particularly useful as an aid for calculation, except when you don't have a computer around. But I often find myself doing approximate calculations while walking, and I can't pull out a calculator or a computer! (To be honest I don't use this trick, but that's only because I have an arsenal of others.)

Is this pointless? For the most part, yes. But amusingly so.

The method is supposedly due to I. J. Good, who is annoyingly difficult to Google.

Oh, and a few facts I find myself using quite often -- (2π)^1/2 ≈ 2.5, e³ ≈ 20.

Three beautiful quicksorts

Jon Bentley gives a lecture called Three Beautiful Quicksorts, as three possible answers to the question "what's the most beautiful code you've ever written?" (An hour long, but hey, I've got time to kill.)

Watch the middle third, in which some standard code for quicksort is gradually transformed into code for performing an analysis of the number of comparisons needed in quicksort, and vanishes in a puff of mathematical smoke.

Although I must admit, I'm kind of annoyed that he slips into the idea that an average-case analysis is the most important thing somewhere in there. The first moment of a distribution is not everything you need to know about it! Although I admit that at times I subscribe to the school of thought that says "the first two moments are everything", but that's only because most distributions of normal.

(Note to those who don't get sarcasm: I don't actually believe that most distributions are normal.)

Why medians are dangerous

Greg Mankiw provides a graph of the salaries of newly minted lawyers, originally from Empirical Legal Studies.

There are two peaks, one centered at about $45,000 and one centered at about $145,000. The higher peak corresponds to people working for Big Law Firms; the lower to people working for nonprofits, the government, etc.

The median is reported at $62,000, just to the right of the first peak, since the first peak contains slightly more people. But one gets the impression that if a few more people were to shift from the left peak to the right peak, the median would jump drastically upwards. We usually hear that it's better to look at the median than the mean when looking at distributions of incomes, house prices, etc. because these distributions are heavily skewed towards the right. But even that starts to break down when the distribution is bimodal.

Why devil plays dice?

Why devil plays dice?, by Andrzej Dragan, from the arXiv. I haven't read it; this post basically exists to forestall e-mails of the form "Have you seen the title of this paper?"

(Hat tip to The Quantum Pontiff.)

Lottery tickets with really bad odds

A CNN.com article talks about lottery tickets with zero probability of winning.

Why, you ask? Because some state lotteries continue selling the tickets for scratch-off games even after the top prize has been awarded. Therefore the odds stated on the ticket are, as of the time the ticket was purchased, incorrect.

But let's say that half the tickets for some game have already been sold, and the top prize not awarded -- then the tickets that are still out there have double the probability of winning that they did originally. You wouldn't see anybody complaining about that.

One way to fix this would be to have all the tickets be independent of each other, but drawn from the same distribution -- so instead of having one grand prize among the 100,000 tickets, each ticket independently has probability 0.00001 of being a grand prize ticket. But then there's a significant probability that there will be no grand prizes awarded, or that there would be two or more.

And some lottery websites actually state which prizes have already been awarded. So it might be possible for somebody to use this information to their advantage, by betting only in lotteries where a disproportionate number of prizes remain to be awarded. This is basically the same principle as card-counting in blackjack, where the player bets more when the cards in the deck are more favorable. I suspect, though, that this wouldn't work well because the house edge in lotteries is much higher than that in casinos.

On today's New York Times crossword

Today's New York Times crossword is by Tim Wescott. There is someone who's commented at Secret Blogging Seminar with that name.

Anyway, here are some of the answers:

4 down: EVEN TENOR
6 down: PERFECT GAME
11 down: ODD MEN OUT
25 down: SQUARE KNOTS
33 down: REAL MCCOY
37 down: PRIME TIME

There was one more clue saying that the first word of each of those answers (which had a star before the clue) described the number of its clue. So 4 is even, 6 is perfect, 11 is odd, 25 is square, 33 is real, and 37 is prime.

33 down seems like a bit of a cop-out to me. But I'm not saying I could do better at making a crossword. Crosswords (especially American-style ones) are hard to make; read the information-theoretic argument in MacKay's book for some justification why.

For the non-mathematicians who may have stumbled in (and the mathematicians who don't remember this particular bit of trivia), I feel like I should point out what a perfect number is. A number is perfect if it's equal to the sum of all the numbers it's divisible by. So 6 is divisible by 1, 2, and 3, and 1 + 2 + 3 = 6. 28 is the next perfect number; it's divisible by 1, 2, 4, 7, and 14, and 1 + 2 + 4 + 7 + 14 = 28. But 12 isn't perfect; it's divisible by 1, 2, 3, 4, and 6, and 1 + 2 + 3 + 4 + 6 = 16, which isn't 12. We call 12 "abundant" because 16 (the sum of its divisors) is more than 12. Just under one quarter of integers are abundant, which is entirely irrelevant.

A political minimum spanning tree

This morning, Nate Silver of fivethirtyeight.com posted State Similarity Scores. For each pair of states, Silver reports a score that gives the political "distance" between the two states. (He actually reports only the three states closest to each state.)

These are based on an analysis of certain variables that appear to be important in US politics, weighted by their importance in determining state-by-state polling in the 2004 and 2008 presidential elections. As it turns out, the pair of states that are closest to each other in this metric are the Carolinas, followed by the Dakotas; Kentucky-Tennessee; Michigan-Ohio and Oregon-Washington.

It occurred to me that the minimum-weight spanning tree for this data might look interesting. And indeed it does. I'm having some trouble articulating why it's interesting, but I just wanted to post the tree. There may be a slight issue because I don't have the full set of similarity scores, but the tree generated from the subset of the data that I do have is probably pretty close to the "true" tree and is quite interesting to look at. (The weight for the edge between any two states is 100 minus Silver's similarity score for that pair of states; Silver's similarity scores have a theoretical maximum of 100.)

Note that the positioning of the states in the drawing of the tree below is entirely irrelevant; I just attempted to draw the tree in such a way that people wouldn't be inclined to see edges that weren't actually there. In particular, Ohio is not somehow "unusual" even though the edges connecting it to adjacent states are long. (As a start, though, it does seem to be useful to think of Ohio as the center of the graph, in line with the conventional political wisdom that Ohio is at the political center of the US.) I thought about trying to make the distances in the drawing reflect the weights, but that was more trouble than I wanted to go to.

Also, some states that are close to each other in Silver's metric aren't close in the tree. There may be errors, since I did this by hand.

Here's the tree.