Reading List Again

Owen decided to get up at 3:30 this morning, so I thought I might as well write a post while I watch him play. It's a little early to try to write anything complicated, so I'll just do a reading list again.

Currently Reading:

The Drunkard's Walk, Leonard Mlodinow
This is a nice non-mathematical discussion of randomness and probability. It has a good description of a few of the common counterintuitive probability questions, like the Monty Hall Problem and the Two Child Problem.

Anton, Dale Eisler
See the previous entry.

The Princeton Companion to Mathematics
Ditto.

Recently Read:

American Gods, Neil Gaiman
Great. I really enjoyed this one.

Gödel's Proof, Ernest Nagel and James Newman
Kurt Gödel's Incompleteness Theorem is a great landmark in mathematical thought. While Gödel's actual paper is quite technical, the ideas are not too difficult to understand without getting too deep into the technical details. This book is a nice explanation of Gödel's proof and its implications.

In the "To Read" Pile:

A Spark at the End of Summer, David Glen Kerr
This is the first book in the Creation Myth series. I went to school with the author, and I'm looking forward to getting into this one.

Neverwhere, Neil Gaiman
Room, Emma Donoghue
Full Dark No Stars, Stephen King
Lisey's Story, Stephen King
Shalimar the Clown, Salman Rushdie
A Mathematical Nature Walk, John Adam

Also, recently I've been reading a lot of Curious George for some reason :).

Reading List Update

I posted a reading list a few months ago, and I thought I'd post an update.

Currently Reading:

Anton, Dale Eisler
This is my uncle's third book and first novel. It's a fictionalized account of the events surrounding my grandmother's family during the Bolshevik Revolution after the first world war - Anton, the main character, is based on my great-uncle Tony. The full synopsis and other information is given on the book's website.

I'm a couple chapters in, and enjoying the writing so far. It's a bit tough for me to read, since it's very personal for me, and there are some really tragic events that happen in the story. It's going to be an interesting experience to read this.

The Princeton Companion to Mathematics
I've read a few sections here and there, which have been uniformly excellent. It's quite slow going, though, as the topics require full attention and can't really be read casually.

The Dark Tower: The Gunslinger Born
I've only read the first chapter of this, but I'm enjoying it so far.

Recently Read:

Logicomix, Apostolos Doxiadis & Christos Papadimitriou
This is a book that I almost can't believe exists - it's a graphic novel about the life of Bertrand Russell and his involvement in the development of the modern philosophy of logic and mathematics. It's difficult to describe, so I'll just link to the Amazon page.

Under the Dome, Stephen King
I thought this was one of the better recent King books, and was a quick read for a thousand-page book. It was nothing earth-shattering, but I quite enjoyed it. 4/5.

The Book of Basketball, Bill Simmons
I generally like Bill's writing style and share his sense of humour, and this book was no exception. On the other hand, I'm only a casual basketball fan, so the topic itself wasn't great for me. I'd say 5/5 for writing and 3/5 for subject matter, so I guess 4/5 overall.

In the "To Read" Pile:

Shalimar the Clown, Salman Rushdie
Godel's Proof, Ernest Nagel & James Newman
A Mathematical Nature Walk, John Adam

Reading List

I received a few new books over the Christmas holidays. They total somewhere in the neighbourhood of 3,500 pages, so I should be finished reading them all roughly around the end of time. Here they are briefly, and hopefully I'll post some comments as I finish each of them. Don't hold your breath, though.

The Princeton Companion to Mathematics
This is a wonderful thousand-page book that would seem to have an incredibly narrow appeal. It's essentially a survey of current thinking across all mathematical disciplines, written to be as accessible as possible. The original goal for the book was that it could be handled by anyone with high school-level math, but the authors weren't able to meet this for all sections. I find this incredibly interesting, and pretty much everyone else I know would not find it interesting at all :).

Under the Dome, Stephen King
I'm a reasonably big fan of King, although I haven't read some of his more recent stuff. This one has been getting reviews in the range of good to great, and drawing comparisons to The Stand, which is a favourite of mine.

The Book of Basketball, Bill Simmons
Bill Simmons writes for ESPN; he's also known as The Sports Guy. This book is essentially just all of his opinions about basketball, including a few hundred pages ranking the best players of all time.

The Dark Tower: The Gunslinger Born
Stephen King wrote a seven-novel series called The Dark Tower over a period of about 30 years. Recently, Marvel has been publishing comics in the Dark Tower universe. This book is a collection of the first few issues.

A Mathematical Nature Walk, John Adam
I hadn't heard of this one prior to receiving it for Christmas, but it looks to be the kind of thing I like.

Exposition Problems

Recently, there was a blog post on my feed reader, referencing a recent paper on the topic of Open Exposition Problems in mathematics. To introduce this term, I'll use the same quote from the paper as was given in that blog post:

All mathematicians are familiar with the concept of an open research problem. I propose the less familiar concept of an open exposition problem. Solving an open exposition problem means explaining a mathematical subject in a way that renders it totally perspicuous. Every step should be motivated and clear; ideally, students should feel that they could have arrived at the results themselves.

This is an interesting idea, and I think it has applications in software development as well. The normal approach when explaining an algorithm is to just explain its steps. For any reasonably complex algorithm, it's also required to give some justification for why these steps achieve the desired result. Generally, the idea is that the student obtains enough of an understanding of the logic to produce a working version of the algorithm, and to extend it if need be.

That's fine, but the quoted text above goes further. It talks not only about the problem itself, but also about the motivation behind the steps of the solution, and about the student's feeling they could have constructed the solution themselves. This is something else entirely. We're now talking not just about explaining an algorithm, but explaining the process through which the algorithm was devised.

When writing code, we are always encouraged to add comments explaining how the code works. When the code needs to be maintained later, it's helpful to have these comments rather than having to work out what the code is doing. But, if someone's maintaining the code, it seems likely that they may be needing to write some similar code of their own. Maybe they need to extend this piece of code, or write a similar method in another language. In such a case, "exposition" comments might be useful as well, talking about how the code came about, other options that were rejected, and so on.

In any case, it's interesting to think about, both in terms of mathematics and software development. If nothing else, I learned the word perspicuous, and got a bit of a laugh that it was the word chosen to explain about making ideas completely clear.

Interesting Numbers

There's a well-known (to mathematicians) story about a famous mathematician, Srinivasa Ramanujan. The story goes that Ramanujan was taking a taxi ride with another mathematician, Godfrey Hardy. Their taxi was number 1729, and Hardy commented that this was rather an uninteresting number. Ramanujan replied that it was in fact quite interesting, as it is the smallest whole number expressible as the sum of two cubes in two different ways.

Sure enough, it's true: 1729 = 10³ + 9³ = 12³ + 1³. This is the kind of thing mathematicians love, and Ramanujan is very well-respected, so this story is popular, and 1729 has even come to be known as the Hardy-Ramanujan number. Mathematicians also enjoy generalizing, so there's now a whole set of taxicab numbers, having to do with summing up powers like the cubes in this example.

There's another thing about this story that I like to think about - the notion of an interesting number. It seems an obvious and expected thing that some numbers are interesting and others aren't; there's even a Book of Curious and Interesting Numbers. This fact about 1729 makes it interesting (at least to me), and I can imagine some other number that has no similar interesting properties.

However, something odd happens if you try to actually find an uninteresting number. Let's just look at whole numbers, starting with zero. 0 is interesting because it is the additive identity, among other reasons. 1 is interesting because it's the multiplicative identity. 2 is the first prime number. 3 is the first odd prime number. 4 is 2². We can continue this way until we find our first uninteresting number. But wait! The first uninteresting number seems like an interesting property for our number to have, so it turns out to be interesting after all.

This seems like a bit of a trick, and maybe it is. There's some kind of paradox or weird self-reference at work here; our decision that a number is uninteresting is what makes it interesting. You can come up with more tricks like this without too much trouble. Here's another quick one, just to make the point: what is the smallest whole number that is not describable in twenty or fewer words?

With 20 words, you can describe a lot of numbers. One hundred; fifty million and three; three googol squared; Steve Wozniak's bank balance. However, there aren't an infinite number of english words, so there aren't an infinite number of 20-english-word combinations. That means there are more whole numbers than 20-word combinations, so some numbers are not describable in 20 words, and there must be a smallest one of these. But wait! The smallest whole number that is not describable in twenty or fewer words is only 13 words long, so this number is describable in less than 20 words after all.

Ok, it's another nice little trick. These are fun little diversions, and they've been known for a long time. They just seem like curiosities, though, without much real meaning or importance in more concrete matters. You wouldn't think that this idea of self-reference could undermine the foundation of all mathematical thought. It did, but that's a topic for a future post.

100% of all numbers contain a 3

Or: Infinity Weirdness, Part 1.

What percentage of all whole numbers contain at least one digit 3? It seems like a simple enough question. The simplest way to start trying to answer it is to have a look at some numbers, and do some counting.

Let's look at 1-digit numbers first. There are 10 of them: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Only one of these 10 contains a 3, so that's 10%.

Now, let's extend our list to the first 100 whole numbers: 0 through 99. We know that 10% of the numbers from 0 to 9 contain a 3. It's the same 10% with numbers from 10 to 19, because they are just the numbers from 0 to 9 with a 1 attached. Adding a 1 doesn't affect our count of numbers with 3s. Similarly, our count is 10% for 20-29, 40-49, 50-59, and so on. The interesting case is 30-39; obviously, all 100% of these numbers contain a 3. Taken together, our count looks like this:

0 - 9: 10%
10 - 19: 10%
20 - 29: 10%
30 - 39: 100%
40 - 49: 10%
...
90 - 99: 10%

We have 9 sets at 10%, and 1 set at 100%. Average this out, and we find that 19% of the numbers from 0 to 99 contain at least one 3.

The way this step from 1-digit numbers to 2-digit numbers worked gives us an insight into how this works generally. When we add a digit, we're adding each of the digits 0 - 9 to all of our existing numbers. 9 of these 10 digits (0-2, 4-9) have no effect on the count of 3s, and the last digit (3) creates a 100% count.

This means that if X is the fraction of n-digit numbers containing a 3, then the fraction of n+1-digit numbers containing a 3 is given by: 0.9X + 0.1. In more formal notation, this is a recursion where:

F_n+1 = 0.9F_n + 0.1
F₁ = 0.1

This can be expressed as a closed form in the following way (this can be shown with a small induction proof):

F_n = 1 - 0.9ⁿ

That's fine; the first few values of this are 10%, 19%, 27.1%. But we're interested in all the whole numbers, and the limit as n goes to infinity here is 100%. So we end up with an odd conclusion: 100% of all whole numbers contain a 3, even though not all whole numbers contain a 3. It's an important difference when dealing with infinite sets - 100% and all don't mean the same thing.

American Idol Algebra

I ran into a little coincidence last week. There was a news story about an American Idol staffer claiming that the fix was in, and that the final four contestants had already been chosen. At the time, there were 11 contestants remaining on the show. Maybe the staffer just made this up - what are the odds that they could just guess the correct final four? The number we want is the number of ways to choose 4 people from a group of 11, and this is just the same calculation as was done in my Arby's Algebra post a few weeks ago. There are 330 possible final fours from a pool of 11 contestants, so the odds of guessing correctly are 1 in 330, or about 0.3%.

Of course, this quick calculation ignores the fact that not all contestants are equal, as some are known to be popular and so on.

Formula Testing

Just testing a way to display formulas. If this works, it might make things clearer for posts like the Arby's one from a little while ago.

Happy Pi Day!

Today is March 14 - 3.14. Celebrate by having some pastry, or by measuring some circumferences.

Arby's Algebra

Arby's has recently had a commercial announcing their current deal, where you can choose 4 items from a list of 8 choices. They mention that this gives you 330 different options. Counting up this total is a nice example of combinatorics, so let's see how to figure out the total value.

Before getting into the math, it's helpful to assign a number to each of the eight menu choices. Rather than talking about an order as sandwich, fries, drink, apple turnover, it's simpler to call this 1,2,3,4. In the items below, when something like item 1 is mentioned, that just means I'd rather type "1" than "roast beef sandwich".

There are some approaches that are reasonable, but that don't give the right answer. First, you might consider that you have 8 choices for each of your 4 items, and simply count up 8*8*8*8, which gives 4096. This gives the total number of four-digit numbers where all the digits are from 1 to 8. The problem is that this double-counts some orders: the orders 1,1,2,3, 1,2,3,1, 3,2,1,1 are all counted as separate orders, when really they are the same.

Another approach is the 8 choose 4 method. The logic of this is that we have 8 items and we will choose 4 of them. There are 8 choices for the first item; once that's selected, there are 7 remaining choices for the next item, 6 for the third item, and 5 for the last. The total is 8*7*6*5 =1680. There are two problems with this. The first is that we're again double-counting some orders; this method will include both 1,2,3,4 and 4,3,2,1 as separate orders. We could solve that by dividing out these repetitions, but the second problem is worse: we're missing some orders. This method doesn't include repeating one item more than once. An order like 1,1,2,3 or 4,4,4,4 (for someone who loves apple turnovers) is never counted.

The correct way to look at this is as a "balls in buckets" problem (technically, combinations with repetition). The 8 menu items are the buckets, and we have 4 balls (choices in our order) to place in these buckets. If we place 2 balls in bucket 1, a ball in bucket 2, and a ball in bucket 3, that's an order of 1,1,2,3. All balls in bucket 4 is an order of 4,4,4,4. Now, here's the trick:

We can picture this as 7 dividers separating our 4 items into the 8 buckets. Visually, this means we translate our orders this way:

Order 1,2,3,4: o/o/o/o////
Order 4,4,4,4: ///oooo////
Order 2,4,5,8: /o//o/o///o

With the orders written this way, using the o and / characters, what we want to know is: how many different ways can we arrange 7 /s and 4 os? For this, we want an 11 choose 4 calculation. We have 11 total characters, and we need to choose 4 of them to be o's.

To start this calculation, we use 11*10*9*8, just like in the 8 choose 4 example above. As mentioned there, this has the problem of double-counting; it counts placing os in spots 1,2,3,4 as well as placing them in spots 4,3,2,1. This means that to get our final answer, we need to divide out these double-counts.

Luckily, that's pretty straightforward. The number of double-counts is just the number of ways to rearrange four numbers, and by the same logic we know this is 4*3*2*1. The final calculation is:

11*10*9*8 / 4*3*2*1
= 7920 / 24
= 330

Wikipedia link: Combinations

3/3/09

Happy Square Root Day! Make sure you enjoy it; the next one's seven years away.

30% of all numbers start with 1

Well, not exactly. However, it is true that in certain common types of data, numbers beginning with 1 appear the most frequently, making up about 30% of the values. Numbers beginning with 2 appear slightly less frequently, about 18% of the time. Each successive digit appears with a lower frequency, until 9 shows up as the leading digit in less than 5% of the values. This property is called Benford's Law, after physicist Frank Benford.

This is quite a counter-intuitive thing. Why should there be more bank balances starting with a 1 than with a 9? Six times more of them, in fact. Why should this be true for the lengths of all the rivers in the world? The technical explanation for this is that these types of real world values are distributed logarithmically. For a more intuitive explanation, an example is probably more helpful.

Let's say you invest $100 in an account that pays 10% annually. This means that your investment will double every 7.3 years. The investment will reach $200 after 7.3 years, so for that entire first 7.3 years the investment's value began with a 1. Now, it will take another 7.3 years to double again. However, this time it's doubling to $400, not $300. The investment was valued in the $100s for the same amount of time it was valued in the $200s and $300s. The point is that the investment is growing at a rate proportional to its own size. It's compounding. The investment only spends 4 years or so in the $200s, 3 years in the $300s, and so on, finally breezing through the $900s in just over a year. Then this repeats for all the 4-digit values: 7.3 years in the $1000s, 4 in the $2000s, etc.

The reason I've been thinking about this topic recently is that it's been mentioned in relation to Bernie Madoff's ponzi scheme. Benford's Law is a good tool for detecting fraudulent data, because people faking such data often don't take it into account. Apparently, Madoff was sophisticated enough to generate numbers that met Benford's Law reasonably well.

As a quick real-world test of this, I thought I'd check the sizes of all the files on my computer's hard drive. The results seem to fit the Law's prediction quite well:

Digit	# Files	% Files	Benford
1	48,295	28.6%	30.1%
2	32,893	19.5%	17.6%
3	23,297	13.8%	12.5%
4	15,925	9.4%	9.7%
5	12,612	7.5%	7.9%
6	10,665	6.3%	6.7%
7	8,438	5.0%	5.8%
8	9,972	5.9%	5.1%
9	6,498	3.9%	4.6%

Wikipedia Link: Benford's Law

NFL Win Probability Calculator

Two things I've been interested in for a long time are NFL football and mathematics. This makes a site like Advanced NFL Stats right up my alley. In particular I like the Win Probability Calculator that was recently posted there. You enter a game state, including the score, field position, and time remaining, and the system produces the probability of each team winning the game. I think this could be a great tool for arguments about going for it on 4th down, or for attempting 2-point conversions.