One thing that I’ve been getting a lot of requests about as a Manchester mortgage advice consultant is the ongoing mortgage mess in the US. I wrote a bit about it a while ago, explaining what was going on. But since then, I’ve gotten a lot of people asking me to explain various things about how mortgages work, and what kinds
of trouble people have gotten into.
During my Haskell tutorial, I used balanced binary search trees as an example. I’ve had people write to me asking me to write about that in a non-functional programming post, because the Haskell one got too tied up in how to do things without assignments, and with tail recursion.
Binary search trees (BST) are another one of the really fundamental simple data structures. They’re conceptually similar to heaps – they’re also a kind of size-ordered binary tree with O(lg n) performance – but they’ve got a different set of basic invariants to represent the different performance goals.
The goal of a structure like a BST is to have a variable-size stucture where
you can cheaply and easily increase or decrease the size of the structure, and where insert, delete, and searching for values are all inexpensive. BSTs are a good choice for implementing things like dictionaries, where you have a key associated with a value, or where you want to be able to search for an arbitrary member quickly.
BSTs are very widely used – for example, the default ordered collections, sets, and maps in the C++ standard libraries are all implemented as a kind of BST (in fact, the very kind that I’m going to describe below.)
If you have a meaningful ordering operation, then a BST is a good choice: expanding and contracting the structure happen automatically every time you do an insert or remove; and insert, delete, and search are all bounded by lg(n), where N is the number of values in the tree.
As you’ve hopefully all heard by now, the Mars Phoenix lander made a perfect
landing over the weekend, and is already returning images. NASA managed to not
only achieve a perfect landing, but to use Mars reconnaissance orbiter to catch a
picture of the Phoenix descending with parachutes deployed!
Alas, NASA’s Phoenix press people aren’t nearly as good as its technical people. As an alert reader pointed out, in their press release about capturing
the photo of the probe with parachute deployed, that they said the following:
Phoenix released its parachute at an altitude of about 12.6 kilometers (7.8 miles) and a velocity of 1.7 times the speed of sound.
That looks relative innocuous, right?
Wrong.
The statement about velocity is meaningless.
The speed of sound isn’t a constant. It varies, enormously, depending
on the medium. In air, its speed is dependent on the chemical makeup of
the air, and on its density, temperature, and pressure – among other factors. So what speed of sound are they talking about?
The speed of sound where the probe was entering the Martian atmosphere? That would make sense as a measurement, but be totally uninformative to us back on
earth, since we don’t know the speed of sound in the upper atmosphere of Mars.
The speed of sound on earth? That would be informative to us – since we
have an idea of the speed of sound here, but it wouldn’t make much sense as a measurement there – the point of using the speed of sound would seem to
be related to giving us a sense of the kind of forces acting on the Phoenix
as it decelerates. But the speed of sound on earth doesn’t tell us that – because the kind of shock waves we would expect is dependent on the speed of sound in the atmosphere it’s passing through.
You can talk about speeds compared to the speed of light – because there’s a meaningful upper bound – the speed of light in a vacuum. And that’s what we usually mean when we talk about the speed of light. But with sound, that’s not
true. The speed of sound can vary quite dramatically in different mediums. It’s a big enough difference that it’s part of a common experiment done by
elementary school students! (I can remember doing an experiment in fourth grade science with a wall, where we were measuring when you could hear a rock hit a wall; one person had their ear against the wall; the other was standing a couple of feet away from the wall, and the person with the rock was about 10 feet away. The time difference was noticeable. It was very small – but distinctly noticeable. The speed of sound in air is 1260 feet per second; so a sound takes roughly 1/10th of a second to move 100 feet. The speed of sound in stone is in the range of 21,000 feet per second – which is virtually instantaneous to a human being at a range of 100 feet. So you’re looking at a roughly 1/10th second difference.)
So how fast was the Phoenix moving when it deployed its parachute? I haven’t
a clue. My best guess would be around 580 meters per second – assuming that
they were using the speed of sound in earth atmosphere at standard temperature and pressure. The speed of sound in the Martian atmosphere – which is quite a lot thinner than earth’s – would be slower, so 580 m/s is a decent upper-bound estimate.
A bunch of people have been mailing me links to an article from USA today
about schools and grading systems. I think that most of the people who’ve
been sending it to me want me to flame it as a silly idea; but I’m not going to do that. Instead, I’m going to focus on an issue of presentation. What they’re talking about could be a good idea, or it could be a bad idea – but because the
way that they present it leaves out crucial information, it’s not possible to meaningfully judge the soundness of the concept.
This has been mentioned elsewhere – like on the Machinist blog on Salon (where I first saw it) – but I can’t resist saying something about it myself. And I’ll also chip in a little bit of originality, by also criticizing some of the people that I’ve seen criticizing it.
The story is, there’s a scammy company that sells a rather expensive device that allegedly increases your gas mileage. The way that it (supposedly) works
is that it uses electricity from the alternator to get hydrogen by splitting
water, and then adding that hydrogen to the air that gets mixed in the engine. The argument is that the hydrogen causes the gasoline to burn more completely and more cleanly, thus increasing the efficiently of the engine, which allows it to go further on a gallon of gasoline.
A local TV station in Florida claims to have tested the device. They tested the mileage of their news van using a dynamometer; then they mounted the device on the engine of their news van, and after giving it time to break in, put the
van back on the dynamometer, and tested its mileage again.
Here’s where the pathetic part comes in. They reported that before mounting the hydrogen generator on their van, they got an average mileage of 9.4 miles per gallon. After mounting it, they claim that they got 23.2 miles per gallon. Ok so far? Now, they go on to say that increasing their mileage from 9.4 to 23.2 mpg is a 61% improvement in mileage.
In my last post on game theory, I said that you could find an optimal
probabilistic grand strategy for any two-player, simultaneous move, zero-sum game.
It’s done through something called linear programming. But linear programming
is useful for a whole lot more than just game theory.
Linear programming is a general technique for solving a huge family of
optimization problems. It’s incredibly useful for scheduling, resource
allocation, economic planning, financial portfolio management,
and a ton of of other, similar things.
The basic idea of it is that you have a linear function,
called an objective function, which describes what you’d like
to maximize. Then you have a collection of inequalities, describing
the constraints of the values in the objective function. The solution to
the problem is a set of assignments to the variables in the objective function
that provide a maximum.
One of the most common sleazy tricks used by various sorts of denialists
comes back to statistics – invalid and deceptive sampling methods. In fact,
the very first real post on the original version of this blog was a shredding of
a paper by Mark and David Geier that did this.
Proper statistical analysis relies on a kind of blindness. Many of the things
that you look for, you need to look for in a way that doesn’t rely on any a priori
knowledge of the data. If you look at the data, and find what appears to be an
interesting property of it, you have to be very careful to show that it’s
a real phenomena – and you do that by performing blind analyses that demonstrate
its reality.
The reason that I bring this up is because one of my fellow SBers,
Tim Lambert, posted something about a particularly sleazy example of this
by Michael Duffy, a global warming denialist over at his blog, Deltoid.
The situation is that there’s a Duffy claims
that global warming stopped in 2002. It didn’t. But he makes it look like it did by using a deliberately dishonest way of sampling the data.
The games that we’ve looked at so far are the simplest case of
basic games. In these games, we’ve got a payoff matrix, and both players
can see the whole matrix – the players have equal information,
and nothing is secret. The players move simultaneously – so neither player can wait to see what his opponent does before making his own decision. Finally, the game is played exactly once – there are no repetitions.
The first complication we can add is to make it an iterative game – that is, instead of each player going once, they’ll repeat the game 10 times in sequence. Everything else stays the same: perfect, equal information, simultaneous moves, etc.
This creates an interesting added dimension. Now, we’ve got two layers
of strategy: each iteration, each player selects a strategy; and then there’s an over-arching strategy that they use to select their strategy each iteration. That over-arching strategy is called a grand strategy
In an iterated game, the optimal solution for players can be different than in the single iteration. The goal is to maximize your total utility at the end of a series of iterations. It’s OK if some iterations result in a loss of utility, so long as by the end of the series of iterations, the final
sum of the utility of the series is maximal.
Pardon me, while I go off on a rant.
Since I came to work for Google, I have a pretty long commute. Most of the time, I don’t really mind it. It’s all by train – first commuter rail from home into the city, and then subway from the terminal to my office. Commuting by train is not bad at all – you get some quiet time before and after work, to sit and read, or just relax.
But in a year of doing this, I’ve learned a couple of things. And today’s commute gave me a perfect example of one of them. People who wear suits to work in Manhattan are the biggest god-damned dicks you’ll find anywhere.
I see just about every kind of people you can imagine on the subway on my commute: black, white, and every shade of brown that there is. I hear
just about every language you can think of: today, I’m sure that I heard
english, spanish, hindi, cantonese, and japanese being spoken by different people. But the only group of people that I’ve had any unpleasant experiences with are white guys in suits.
I cringe when one gets onto the train behind me. Because they’re invariably the people who feel like they’ve got a right to more personal space than anyone else, and will freely use their elbows to enforce that. They’re the people who’ll park their ass right in front of the subway door, and refuse to step aside to let people off of the train. They’re the rudest, most obnoxious, entitled, shits you’ll ever have the misfortune to meet.
And they’re also the ones who complain more bitterly about everyone else on the train. The asshole who won’t get out of the doorway of the train
is always the guy who opens up about how rude black men are after one of then pushes his way through to get off the train at his stop. They’re the ones who, after elbowing other people aside, bitch about the dominican guy who they had to shove. They’re the ones who can’t talk to each other without shouting – and then shout about how annoying it is to them to have to listen to people on the train speaking spanish.
The stereotypes of New York City invariably portray New Yorkers as rude, obnoxious people. But usually, the ones that they’re portraying as rude aren’t the guys in suits; it’s always the minorities or the working class. But in a year of this commute, I’ve never seen one of those stereotypical New Yorkers being the least bit rude. In fact, in general, I think New Yorkers are some of the nicest people you’ll ever meet. (The best description I’ve ever heard of New Yorkers was “If you’re walking out of the subway with a stack of papers, and drop them, New Yorkers are the people who’ll help you catch all of your papers, and then tell you what an idiot you are for dropping them.” That’s NY; we’re very direct, but for the most part, we’re good people.)
The assholes are always the rich guys in suits on their way to work, who feel like they’re entitled to more than anyone else.
What brought this little rant on is that I got stuck on the subway this morning. Four guys in pinstripe suits got on behind me; spend the ride sneering like a bunch of overprivileged frat-boys about every non-white person on the train, and then as a group, blocked the doors at my stop, so that no one could get off. They weren’t trying to block the doors; they just happened to be standing there, and the idea of taking a step to one side to let anyone off the train – well, they weren’t about to move for
a bunch of lower-class slime. It wasn’t their stop. Of course, if anyone got in their way when they wanted to get off, they would have gone off into a giant flaming rant about how awful it was that the Insert Ethnic Group of Perpetrator got in their way, and weren’t all Members Of Said Ethnic Group a bunch of jerks.
It’s pretty much exactly the Bill O’Reilly syndrome. I’m sure everyone
remembers how he was shocked that at a black restaurant in Harlem, no one was
shouting out “Hey motherfucker, more ice tea over here” – because he really
deep down believes that minorities are a bunch of crude, stupid, obnoxious
assholes. But his regular daily behavior is even worse than his stereotypes
of his hated minorities.