May 7, 2008
Category: Graph Theory
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.
Read on »
Posted by Mark C. Chu-Carroll at 2:28 PM • 20 Comments
View blog reactions
May 6, 2008
Category: Bad Statistics
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.
Read on »
Posted by Mark C. Chu-Carroll at 4:01 PM • 19 Comments
View blog reactions
May 5, 2008
Category: Game Theory
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.
Read on »
Posted by Mark C. Chu-Carroll at 10:09 AM • 4 Comments
View blog reactions
May 1, 2008
Category: Chatter
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.
Posted by Mark C. Chu-Carroll at 11:50 AM • 47 Comments
View blog reactions
April 30, 2008
Category: Chatter
I was recently fortunate enough to get a review copy of Cory Doctorow's new book, Little Brother
">"Little Brother". I've never read Doctorow before, but the book
was edited by Patrick Neilsen Hayden, who I think is the best editor in
the business, and Patrick says that this book is one of the best things
he's ever worked on. In his words, it's "one of the books that, should I happen to be run down by a beer truck next tuesday, I'd most like to be remembered for having helped into print". So when Patrick posted on his blog that he had review copies available, I jumped at the chance.
Read on »
Posted by Mark C. Chu-Carroll at 9:35 PM • 21 Comments
View blog reactions
April 29, 2008
Category: Data Structures
Last post, I described the basic idea of the binary heap data
structure. But I didn't talk about how to implement it - and there's
a very cool way of implementing it - optimally space efficient,
very fast, and with respectable cache locality for moderate sized
datasets.
Read on »
Posted by Mark C. Chu-Carroll at 10:49 AM • 23 Comments
View blog reactions
April 28, 2008
Category: Data Structures
One of the most neglected data structures in the CS repertoire is
the heap. Unfortunately, the jargon is overloaded, so "heap" can mean
two different things - but there is a connection, which I'll explain
in a little while.
In many programming languages, when you can dynamically create
objects in memory, the space from which you allocate the memory to
create them is called the heap. That is not what I'm talking about.
What I am talking about is an extremely simple but powerful structure
that is used for maintaining a collection of values from which you want
to be able to quickly remove the largest object quickly. This may sound
trivial, but this turns out to be an incredibly useful structure. You can use this basic structure to implement a very fast sorting algorithm; to maintain a prioritized set of values/tasks; to manage chunks of memory; etc. (The
prioritized set is the most common case in my experience, but that's probably because I've spent so much of my career working on distributed systems.)
Read on »
Posted by Mark C. Chu-Carroll at 11:37 AM • 32 Comments
View blog reactions
April 25, 2008
Category: Game Theory
Last time I wrote about Game Theory, I explained the basic idea of
zero sum games. In their simplest form, a game can be described by a payoff matrix,where each dimension of the matrix is the set of strategies which can be selected by one player, and each entry in the matrix describes the payoffs that result when all players select their strategy. Informally, a game is zero-sum when the total payoff is zero - that is, when any positive payout to one player is balanced by payouts from other players.
We can formalize some of the basic ideas more precisely. What we can say is that each move results in a state; and for each player y, there is a function, up, called a utility function, which maps from a state to a utility value. Taking the player utility functions as components, we can define the game's utility function in terms of tuples: for players 1..n,
the utility function maps from states to tuples of utility values: u(state)=(u1, ..., un).
Read on »
Posted by Mark C. Chu-Carroll at 12:17 PM • 1 Comments
View blog reactions
April 22, 2008
Category: Bad Probability
Remember when I talked about the problems with Bayesian probability? As you'll probably recall, one of the things that drives me crazy about Bayesianism is that you get a constant stream of crackpots abusing it. Since the basic assumption of Bayesian probability is that you can always use it, you'll constantly get people abusing it.
Christopher Mims, who was one of the people running ScienceBlogs when I first signed on, sent me a classic example. A professor has published a paper in a journal called "Astrobiology", arguing that there's an exceedingly low probability of intelligent life elsewhere in the Universe.
Read on »
Posted by Mark C. Chu-Carroll at 2:12 PM • 51 Comments
View blog reactions
April 16, 2008
