indessed roscivs

The Prisoner’s Dilemma is sort of a thought experiment in the field of game theory (where mathematics are used in an attempt to model human choices). Although there are very many different variations on the game, the central feature is that the rational decision is not the decision that would provide the best outcome.

Here’s one of my favorite variations on the game. Imagine Bill Gates comes to you and a dozen of your friends and offers you this deal: each of you, without consulting or showing the others, must write down a single letter, either “C” or “D”.

After everyone has written down their letter, they are all revealed simultaneously, and everyone is given a payout based on what they wrote and what the others wrote. If you wrote a “C”, you collect $100 dollars for every other “C” in the group (not counting your own). If you wrote a “D”, however, you collect $5 plus $10,000 for every “C” in the group.

If there are twelve other people playing, then your maximum theoretical payoff is $120,005—you are the only “D”, and everyone else is a “C”. If everyone chooses “C”, on the other hand, then everyone walks away with $1,200. Your minimum theoretical payoff, unfortunately, is $0—if you’re the only “C” and everyone else is a “D”.

The “Prisoner’s Dilemma”-esque part of this game is that, no matter what everybody else picks, you are always better off by writing “D” rather than “C”. No matter what. So, rationally, everyone writes “D”—and goes home with five bucks in their pocket instead of over a thousand bucks apiece.

Game theorists call the $10,000 lure “the temptation to defect”. Ever since learning about the Prisoner’s Dilemma, I see examples of it everywhere. For example, at sports games where everyone is standing the whole time instead of comfortably sitting down. If everyone sits down, everyone can see just as well as if everyone is standing up. But the temptation to defect—the idea that if I’m the only “D” in a world full of “C”s—is very strong. I can see a whole lot better if I’m the only one standing up and everyone else is sitting down.

Similarly when I’m picking up my luggage at the airport carousel—if everyone stands back a few feet from the carousel and waits until they see their bags, then it’s moderately easy for everyone. But there’s that temptation to defect—the idea that I could be the only one standing right next to the carousel, and everyone else stands back, making it slightly easier for me—that pushes everyone towards the conveyor belt. In the end, it’s more difficult for everyone to get their bags off than it would be if everyone stood back a few feet. But the rational choice—the one that leaves you better off no matter what everyone else does—is to get as close to the carousel as possible.

Recently I’ve realized that the public funding of sports stadiums (as well as government subsidies to local businesses) is a perfect example of a prisoner’s dilemma. Seattle taxpayers give millions of dollars to the Seahawks (the local football team), and in exchange, they graciously agree to stay in our city. If the taxpayers threaten to withdraw the funding, the Seahawks threaten to leave the city for another city who’s willing to give them the money they want.

If every city cooperated and refused to build stadiums and fund teams with taxpayer money, then the stadiums would still get built and the teams would still play wherever there were large numbers of people interested in sports. But the temptation to defect—the idea that your smaller city can bring in more tax revenue and rejuvenate local industries if you simply offer some cash to a team who wouldn’t normally set up shop there—wins out again. In the end, of course, the larger cities also defect and offer more cash to the teams who would have built stadiums in the larger cities to begin with, leaving everyone exactly where they started—except the taxpayers a little poorer, and the NFL a little richer.

There is a curious dilemma in universities today with regard to the field of computer science. Historically, computer science was part of the mathematics department. Many of the foundational concepts of computers—boolean logic, algorithms, formal systems, functions, lambda calculus—these were all purely theoretical concepts residing squarely inside the math department before computers came along. Furthermore, the earliest computers were primarily used for mathemetical calculations (that’s why they’re called computers, after all—a term which previously was reserved for humans who crunched numbers for a living), either by mathematicians or physicists. So it was only natural that, as computers became part of the modern university, classes on computer theory would be part of the math department.

Since those early years, computers have become so popular and such a force of their own that most universities have a separate “computer science” department (although typically still conjoined with the mathematics department in some way). As computers have matured, non-mathematical uses of them have grown increasingly common. The art of programming, with its roots in pure mathematics, looks much less like mere formulas and equations than it once did. And, finally, those who are majoring in computer science these days typically go on to be software developers—not theoretical mathematicians. As a result of all these factors, the face of computer science departments has changed radically.

Many people lament the passing of the traditional “computer science” discipline, full of mathematicians (not programmers) and rich with theory and symbols (not software development models). Where is the computer science of Knuth, or Dijkstra, who allegedly said, “Computer science is no more about computers than astronomy is about telescopes”? Has it died, pushed out of our universities in the increasing trend towards university-as-trade-school?

I don’t think so. In many ways, the discipline of the early computer science pioneers has been sucked wholly back into the math department. Many of the same mathematical concepts present in those early computers are still heavily studied and examined in the math department, with computers as a useful resource, not the focus—just like computer science once was. It’s just not called “computer science” any more.

Unfortunately, I think a result of this paradigm shift is that the brilliant mathematicians are ceasing to have as strong an effect on the software development world as they once did. There’s not as much cross-culture as there was when the two disciplines were more closely interrelated.

Another problem is that, after traditional computer science was reabsorbed by the math department, nobody has been able to agree on what the “new” computer science discipline should be. The mixed nature of a typical computer science department faculty—made up of both “old-school” theory-heavy, math-heavy powerhouses as well as people with years of real-world software development experience from industry—just exacerbates the problem.

Some believe that the department should prepare its students for jobs in software development, since that’s where a significant percentage of them end up. Others think that the department should focus on theory, and that development-centric classes belong in trade schools, or at least a different department. As Joel Spolsky (author of several books on software development) puts it in characteristically tongue-in-cheek fashion:

[E]lite schools think that teaching practical skills is better left to the technical-vocational institutes and the prison rehabilitation programs. You can learn mere programming anywhere. We are Yale University, and we Mold Future World Leaders. You think your $160,000 tuition entititles you to learn about while loops? What do you think this is, some fly-by-night Java seminar at the Airport Marriott? Pshaw.

So universities are typically stuck in this middle-world of half mathematics, half software development. Students who want the former struggle through the programming-heavy classes of computer architecture and compilers, while those who are interested in the latter have to wade through theory-heavy classes like automata theory and “database” classes that have very little real-world utility.

So what do I think should happen? I think there should be a theory-centric track fully inside the math department, and a development-centric track (perhaps called “software engineering”, as many universities are leaning towards) full of programming-heavy courses on software design, development methodologies, and code maintenance. The development-centric track shouldn’t be simply “learn how to program” nor “learn what development tools are popular today”—I do agree that such tasks should be left to trade schools and the like. But there’s a lot of university-appropriate knowledge that has been applicable for decades and will be applicable for decades to come that is specific to software development.

I believe this is the world we’re heading towards, but as always, the transition period will be one messy, bumpy ride.

Yesterday I talked about the importance of the number twelve, its prevalence in measurement systems, and how the metric system was created in order to align our weights and measures with our ten-based counting system.

But why is our counting system ten-based? Many people assume it has to be that way, or that it’s more logical that way, but it turns out that it’s just an accident based on our number of phalanges. Ten-based systems aren’t inherently any more convenient than any other base—only when you’re dealing with tens. Let me illustrate.

Hundreds of years ago, positional notation was invented in India. Previously, all counting had been done in systems like Roman Numerals, where a particular symbol always stood for a particular number, like X or V. Multiplication and division was a real chore in systems like these (try it for yourself!), so positional notation was a welcome change. The novel idea was that a particular symbol could stand for many different numbers depending on where it stood in the number—its position. For example, the symbol “1″ in 123 represents a hundred, whereas the same symbol in 312 stands for ten. (The invention of the zero was vital in this scheme, so that you could represent the position of “1″ in 100 and 10 without the presence of any other numbers.)

Although using “100″ to represent a hundred seems obvious to us, having grown up with the decimal system, it’s not the only way of doing things. When learning simple arithmetic as a child, we were told that the one is in the “hundreds-place” or the “tens-place”—each column represents some value. A 3 in the “hundreds-place” column represents three of that value, or three “hundreds”. But the value of each column is arbitrary. What if to the left of the “ones-place” you had a “threes-place” and then a “nines-place”? Then “100″ would mean nine, “10″ would mean three, “200″ would mean eighteen, and “20″ would mean six! Note that in this system, we only need three digits—0, 1, and 2—to represent any value; counting looks like this: 1, 2, 10 (three), 11 (one in the threes-place, one in the ones-place = 4), 12, 20, and so on.

This is called “base three”, because we only need three digits, and each column is a power of three (threes-place, nines-place, and next would be the twenty-sevens-place). And an interesting property of any base is that, when you multiply any number written in that base times the base itself, you can simply shift digits to the left. For example, if we multiply base-three “20″ (meaning six) times three, we get eighteen—which in base three is written “200″. This happens in every base, which is why in our decimal counting system, multiplying “20″ (meaning twenty) times ten you get “200″.

You could even have “base twelve”, where you have a twelves-place and a gross-place, so multiplying “20″ (meaning twenty-four) by twelve would equal “200″ (two gross). Then you could have all the benefits of the number twelve (including its divisibility by two, three, four, and six) as well as all the benefits of the metric system (easy multiplication and division when dealing with a standard factor, which in this case would be twelve).

In fact, some argue that the French made the wrong decision when deciding to switch our useful-twelve-based measurement systems to align with our arbitrarily-ten-based counting system, and that they should have gone the other way instead. You can find their writings at the Dozenal Society. I tend to agree with them in theory, but the fact of the matter is that it was difficult enough getting everyone (well, almost everyone) to switch something as easily changed as units of measurement. Attempting to change the base of our entire counting system would be madness.

But it certainly is interesting to think about.

A dozen donuts, twelve inches in a foot, twelve pence to a a shilling, a dozen dozens in a gross. Twelve months in a year, twelve apostles for Our Lord, twelve hours on the clock, and twelve signs of the zodiac. Why is twelve such a ubiquitous number?

It turns out that twelve is a very useful number for all sorts of mathematical reasons. For instance, it has a lot of divisors: 2, 3, 4, and 6 all go into twelve evenly. There are only six numbers under 50 that have more divisors than twelve, and nearly all of those are multiples of twelve.

Why is this property of twelve beneficial? It’s because a half, a third, and a fourth are very useful and common divisions. Dividing a dozen donuts fairly among three people is trivial. Taking half a foot or a quarter of a foot results in a nice whole number of inches. Twelve apostles can be divided equally into two groups, three groups, four groups, or six groups very easily, depending on the need.

The US has been rather recalcitrant to give up its dozen-based measurement systems in favor of the ten-based metric system. But why did the rest of the world switch to begin with, if twelves are so useful? What does the metric system have to offer us? Quite simply, it aligns the counting system—which is ten-based—to the measurement system, making dividing or multiplying measurements by ten a trivial operation.

But why is our counting system ten-based? Many people assume it has to be that way, or that it’s more logical that way, but it turns out that it’s just an accident based on our number of phalanges. Ten-based systems aren’t inherently any more convenient than any other base—only when you’re dealing with tens. In tomorrow’s post, I’ll give a few examples to illustrate this idea.

I’ve always been fascinated with combinatorics. For those of you not familiar with the field, it’s part of the study of discrete mathematics, which is in essence the part of math that’s particularly interesting to computer scientists. (My apologies to any mathematicians who just cringed.) Combinatorics in particular concerns itself with trying to figure out how various combinations and permutations of items work.

For example, let’s say we have three musical notes: G, C, and F^#. Given only those three notes, how many unique series of notes can you have? It depends on how long the series of notes can be, first of all. Let’s start out looking at two-note series: GG, GC, GF^#, CG, CC, CF^#, F^#G, F^#C, and F^#F^#. That’s a total of 9 possible combinations.

How many possible three-note series are there? Or ten-note series? Or thousand-note series? It would take a while to list all of them, but combinatorics gives us a really simple formula for figuring out the answer:

where n is the number of notes to choose from, and r is the length of the series. So there can be 3² two-note series of three notes—a total of 9 possible combinations, just as we showed before. There are 27 (3³) possible three-note series, 59,049 (3¹⁰) possible ten-note series, and a whole lot of possible thousand-note series (3¹⁰⁰⁰). And the formula is just as easy if you use all seven notes in a scale (7³ possible three-note series) or all twelve semitones (12³ possible three-note series).

But what if you want to exclude repeats? In other words, how many permutations of a given set of notes can you create? To use our previous example of two-note series of three notes, we could have: GC, GF^#, CG, CF^#, F^#G, and F^#C. Six possible permutations. The formula for this situation is a little tricker, because it involves the “factorial” mathematical operator, represented as an exclamation point. 2-factorial, or 2!, is equal to 2×1. 3! is equal to 3×2×1, 4! is equal to 4×3×2×1, and so on. The mathematical formula for permutations excluding repeats is:

or, for our above scenario of two-note series of three notes (without repeats), 3!/(3-2)!, which becomes 6/1, equalling six possible permutations. Again, you can plug in whatever numbers you like into this formula to get the answer without having to enumerate all the possible permutations yourself. If you have a choice of seven notes in a scale, and want to create a four-note series with no repetitions, you have 7!/3!, or 840 different options to choose from.

One more before I end—what if order doesn’t matter? For example, what if you’re choosing Jelly Bellies to mix. There are fifty official flavors, and let’s say we want to mix three different jelly beans together to get some unique combination. It doesn’t matter whether we pick licorice+lemon+cinnamon or cinnamon+licorice+lemon, it ends up being the same thing. The formula for this is:

So the answer to our Jelly Belly question is 50!/3!x47!, or 19,600 possible combinations. The majority of them, most likely, quite disgusting.