In game theory, perhaps the most important category of simple games is
something called zero sum games. It’s also one of those mathematical
things that are widely abused by the clueless – you constantly hear
references to the term “zero-sum game” in all sorts of contexts, and they’re
almost always wrong.
A zero-sum game is a game in which the players are competing for resources, and the set of resources is fixed. The fixed resources means that any gain by one player is necessarily offset by a loss by another player. The reason that this is called
zero-sum is because you can take any result of the game, and “add it up” – the losses will always equal the wins, and so the sum of the wins and losses in the result of the game will always be 0.
Suppose you’ve got a bunch of data. You believe that there’s a linear
relationship between two of the values in that data, and you want to
find out whether that relationship really exists, and if so, what the properties
of that relationship are.
I’m going to jump into the framing wars again. As I mentioned last time,
I think that most folks who are “opposed” to framing really don’t understand what they’re talking about – and I’ll once again explain why. But on the other hand,
I think that our most prominent framing advocates here at SB are absolutely
terrible at it – and by their ineptitude, are largely responsible for
the opposition to the whole thing.
Several people have asked me to write a few basic posts on statistics. I’ve
written a few basic posts on the subject – like, for example, this post on mean, median and mode. But I’ve never really started from the beginnings, for people
who really don’t understand statistics at all.
To begin with: statistics is the mathematical analysis of aggregates. That is, it’s a set of tool for looking at a large quantity of data about a population, and finding ways to measure, analyze, describe, and understand the information about the population.
There are two main kinds of statistics: sampled statistics, and
full-population statistics. Full-population statistics are
generated from information about all members of a population; sampled statistics
are generated by drawing a representative sample – a subset of the population that should have the same pattern of properties as the full population.
My first exposure to statistics was full-population statistics, and that’s
what I’m going to talk about in the first couple of posts. After that, we’ll move on to sampled statistics.
As an introduction to a mathematical game, and how you
can use a little bit of math to form a description of the game that
allows you to determine the optimal strategy, I’m going to talk a bit about Nim.
Lots of people wanted game theory, so game theory it is. The logical first question: what is game theory?
Game theory is typical of math. What mathematicians like to do is reduce
things to fundamental abstract structures or systems, and understand them in
terms of the abstraction. So game theory studies an abstraction of games – and
because of the level of abstraction, it turns out be be applicable to a wide
variety of things besides what you might typically think of as games.
Game theory starts with the fundamental idea of a game. What is
As you’ve probably noticed, things have been rather slow around here lately. I’ve got more posts in the works on group theory and abstract algebra – but they take a lot of time to research and write, so they’ll be coming out slowly – one a week or so.
In the meantime, I’m looking for other topics to write about, and I’d like to know what you, my faithful readers, are interested in hearing about.
Some things I’ve considered:
- Cellular automata: CA are very cool. I’ve been wanting an excuse to read my copy of Wolfram’s text.
- Data structures: my programming-related posts have always been very popular; and there’s a collection of unusual data structures that have interesting mathematical properties.
- Game theory: a pretty cool area of math.
- Conway’s games: basically the second half of Conway’s ONAG.
Or any other mathematical subject that you’re interested in learning about. Suggest away in the comments.
And keep those bad-math links coming!
This is a complicated recipe. It takes a couple of days to do properly,
and works best done with a slow-cooker. But it’s worth it. It’s a Taiwanese dish – a spicy beef noodle soup. It’s pretty much the national
dish of Taiwan – Taiwanese love this dish. There are annual competitions
in Taipei for who can make the best Niu Rou Mien. I learned about it from
my wife, who grew up in Taiwan. I’ve made this a few times, and this is the
recipe the way I’ve worked it out.
After yesterday’s post about the great women of computer science, I noticed my SciBling MarkH over at the Denialism blog had discovered Vox Day and his latest burst of stupidity, in which he alleges that the greatest threat to science is…. women. Because, you see, women are all stupid.
The bizarre propositions of equalitarianism always sound harmless and amusing at first because they are so absurd. What the rational observer often fails to understand, however, is that these propositions don’t sound the least bit absurd to the equalitarian proponent because the average equalitarian is fundamentally an intellectual cave-dweller with no more interest in reason or capacity for logical thought than a hungry kitten. The idea of biology classes being taught by lesbian professors who believe that heterosexual procreation is a myth or calculus courses being taught by women who can’t do long division may sound impossible today, but tell that to any software developer, and he’ll be able to provide you with plenty of current examples of computer science engineers, some with advanced CS degrees, who have no idea how to even begin writing a computer program.
Women love education; it’s the actual application they don’t particularly like. Whereas the first thought of a woman who enjoys the idea of painting is to take an art appreciation class, a similarly interested man is more likely to just pick up a paintbrush and paint something – usually a naked woman.
This is… I don’t know a word that sufficiently expresses the stupidity of this. Vox has a long history of being a moron with delusions of intelligence, but this one really takes the cake.
At Science, Education, and Society, the Urban Scientist
posts a meme to name five women scientists from each of a list of fields. Sadly, my fields are left off the list. So I’ll respond in my own way
by adding computer science. This is a very idiosyncratic list – it’s women
who are particularly important to my own experience as a student and later
practitioner of computer science.
It’s worth noting that I’ve got a very atypical experience as a computer
scientist, in that many of the most influential people in my
career have been women. That’s very unusual, given the incredibly skewed
ratio of men to women in computer science. But as an undergraduate student,
a graduate student, and a professional researcher, the majority of people who had a great influence on my education and career have been women.
- Fran Allen. In a list of women in computer science, Fran has to
be at the top. (I’ve met Fran Allen personally, and she told me
to call her Fran.) Fran was the first woman to earn the Turing award – and
the only real question concerning her getting it is why the hell it took
so long. I used to work at IBM Research, where Fran also works, but I knew
about her long before I went there. Fran is one of the people who
created the field of compilers. I had the amazing good
fortune to meet Fran on several occasions, and she’s one of the
most pleasant, interesting people that I’ve ever spoken to. She’s also
an incredibly active advocate for women in math and science, and her
tireless effort has probably brought more women into the field than
anyone else. (Yes, when it comes to Fran, I am pretty much a drooling
fanboy. Fran is my idol :-). If in my career, I can accomplish 1/50th
of what Fran did, I’ll be a very proud and happy person.)
- Grace Murray Hopper. Admiral Grace Murray Hopper was one of the designers of the
Cobol programming language. You could make an argument about whether
Adm. Hopper or Fran Allen really deserved to be the first woman to earn
the Turing award. Personally, having heard her talk a few times, I don’t
think she held a candle to Fran. But it’s undeniable that she played
a crucial, formative role in the creation of what become computer
science and software engineering.
- Ada Lovelace. You can’t fairly talk about women in computer science
without mentioning Lady Ada Lovelace. She was, arguably, the first
- Jeanne Ferrante. Professor Ferrante once worked at IBM, but left before I
got there. I’ve never gotten to meet her. But she wrote one of the first
static analysis papers that I ever read, which had a whole lot to do with what
I’ve ended up doing with my life.
- Barbara Ryder. Barbara is a professor at my undergraduate alma mater.
I never had the good fortune to take a class taught by her, but I got
to know her anyway. She’s one of the leading researchers in static analysis,
and her students are some of the leading lights in compilers, programming
languages, static analysis, and compiler optimization. She’s also one
hell of a tough person, who’s done an amazing amount to fight to get
women involved in computer science.
This list leaves off some women who’ve played major roles in my life and career. Like, for instance, my wife, who is a brilliant computational linguist (smarter and a better researcher than I am); my PhD advisor, Lori Pollock, who is an amazing researcher and
the best advisor a student could ask for; my academic grandmother,
Mary Lou Soffa; and one of my favorite current researchers in
software engineering, Gail Murphy.