Calvin Poker

Probability problem

2010-12-18T15:52:00.000-08:00

There's a famous problem in probability: find a probability distribution such that two such independent random variables have a sum that is uniformly distributed from 0 to 1.

That turns out to be impossible. One way to prove it is by considering the expected value of exp(2*pi*i*x). Because the distribution of the sum has to have this quantity be 0, each part also has to have the same property. The only distribution with support between 0 and .5 with this property is 0 w.p .5, and 0.5 w.p. 0.5. That distribution doesn't work.

A related problem is: find a probability distribution such that two such independent random variables x1, and x2 satisfy x1 + 2*x2 is uniformly distributed from 0 to 1.

Can you do it?

2010-12-02T19:27:00.001-08:00

package main

func main(){
stat := make([][][]int, 9)
for i := 0; i < 9; i++ {
stat[i] = make([][]int, 9)
for j := 0; j < 9; j++ {
stat[i][j] = make([]int, 9)
}
}
rule := make([][]*int, 324)
for i := 0; i < 324; i++ {
rule[i] = make([]*int, 9)
}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
for k := 0; k < 9; k++ {
rule[i*9+j][k] = &stat[i][j][k]
rule[81+i*9+j][k] = &stat[i][k][j]
rule[162+i*9+j][k] = &stat[k][j][i]
rule[243+i*9+j][k] = &stat[3*(i/3)+(k/3)][3*(i%3)+(k%3)][j]
}
}
}
input := "96..1.7.4..1....2....2.59....3......59.....76......1....98.3....7....2..1.8.7..69"
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
for k := 0; k < 9; k++ {
if input[9*i+j] == '1'+byte(k){
stat[i][j][k] = 1
}
}
}
}
for iter := 0; iter < 100; iter++ {
for i := 0; i < 324; i++ {
sum := 0
for j := 0; j < 9; j++ {
sum += *rule[i][j]
}
if sum&1 == 1 {
for j := 0; j < 9; j++ {
if *rule[i][j] == 0 {
*rule[i][j] = 2
}
}
}
if sum == 16 {
for j := 0; j < 9; j++ {
if *rule[i][j] == 0 {
*rule[i][j] = 1
}
}
}
}
}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
for k := 0; k < 9; k++ {
if stat[i][j][k] == 1 {
print(k+1)
}
}
}
println()
}
}

Graded New Year's Resolutions 2008

2008-12-31T12:50:00.000-08:00

1. Read two books a month. ("Who do you think you are, Einstein?!")

Nope. But I've read some very good ones this year, including "American Fascists" (Chris Hedges) and "Facts and Mysteries in Elementary Particle Physics" (Martinus Veltman).

2. Smell better. ("No way, really?", spark of hope lingering in Dina's eye)

"Yeah, on average--you're definitely cleaner."

3. Beat my time up Old La Honda (21:50) and olympic triathlon (2:30:31)

I got somewhat close to my OLH record (under 24:00), but didn't break it.

4. Grade this years resolutions w/ Dina ("um... Is there any resolution about me? um...")

Check! Dina, don't you have anything to do now? "Every year you're getting meaner; you take me for granted :'("

Overall: 2/4, plus maybe some partial credit, but not really.

Selected 2007 Resolutions

2. Get more done at work, and spend less time there.

Yes! This year has been a very good one at work. I definitely spent less time at work in 2008 than in 2006, but probably about the same as 2007 (can't keep going down forever)

5. Keep in touch with friends and colleagues better

I call my parents and brother more, so let's count this as a success.

Liars dice poker

2008-03-07T22:25:00.000-08:00

Okay, here's a game I made up. You use dice, and bet with chips, like poker.

Two players: player 1 and player 2.

Player 1 puts in 1 chip, player 2 puts in 2 chips.

Player 1 rolls 10 dice and then declares a number of pips, from 1 to 6, say "4".

Player 2 rolls 10 dice and then declares either "higher" or "lower", say"lower".

At this point, we have a betting round, as in no-limit poker. Both players have an opportunity to raise, starting with player 1 (who has only put in 1 chip). If there is a showdown, the player with, in the example, the lower number of 4's wins and takes the pot. If they have the same number of 4's, they chop the pot.

What does everyone think?

New Years Resolutions, 2008

2008-01-01T20:58:00.000-08:00

In keeping with tradition, I'm writing new year's resolutions on Jan 1, 2008.

1. Read two books a month. ("Who do you think you are, Einstein?!")

2. Smell better. ("No way, really?", spark of hope lingering in Dina's eye)

3. Beat my time up Old La Honda (21:50) and olympic triathlon (2:30:31)

4. Grade this years resolutions w/ Dina ("um... Is there any resolution about me? um...")

In addition to this year's resolutions, I'm also trying to keep my 2007 resolutions.

Well, this year's resolutions are a bit silly, but I think I'm sticking with them. I'm serious about them all. Okay... it's 10:24 p.m., and time to hit the sack.

To be updated :-)

Last year's resolutions graded!

2007-12-28T08:55:00.000-08:00

1. Blog more. I used to have a ton of fun with this blog.

Well, admittedly 362/365 of the days this year have passed without a peep, but there are still 3 days left, so I won't jump the gun in grading this one yet. Besides, I'm writing now, aren't I?

2. Get more done at work, and spend less time there.

Yeah! This is a big success for this year. After changing groups, I'm infinitely more productive, and I've been keeping reasonable hours much of the time.

3. Start dating a girl I can see as my equal in the ways that matter, and is a good match for me.

Can't complain! However, I'm not going to write it all up here.

4. Revise my thesis.

See #1. Actually, after studiously ignoring this for most of this year, I've started working on this again. I'm taking my officemate Bob's approach, which is this: learn the minimum set of tools necessary to get the job done, and get the job done.

5. Keep in touch with friends and colleagues better.

Bad. Actually, a huge failure this year was missing the retirement party of my graduate advisor. The timing couldn't have been worse, with a major external product demo and several of us (including me) working 12+ hour days then.

-------------------

So, I guess that makes it 2/5 resolutions kept, which is at least par for the course. Probably more like an eagle.

Anyway, I'm really happy with the resolutions that I did keep this year. In a few days, I'll write a new set of resolutions for the coming year (that's 2008!). I'll renew the resolutions I didn't keep, and write a few new ones, which I've already been thinking about.

New Year's Resolutions

2007-01-01T22:05:00.000-08:00

This year, I have some big resolutions to keep. I'm writing 'em down while it's still Jan. 1 and still counts.

1. Blog more. I used to have a ton of fun with this blog.

2. Get more done at work, and spend less time there.

3. Start dating a girl I can see as my equal in the ways that matter, and is a good match for me.

4. Revise my thesis.

5. Keep in touch with friends and colleagues better.

So, the most interesting one is #3, so why not talk about that for a while. What are the ways that matter?

I dated a girl for a long time who had everything any guy wants in terms of attractiveness and attentiveness. The thing that ultimately made the relationship end was that I could never talk with her about things I care about a lot about. Things I blog about. Partly, that's because we grew up speaking different languages (and neither of us became fluent enough in the other's language). Partly, that's because the things we care about are so different.

Anyway, what I want to find is someone who's discriminating, caring, physically attractive, likes the person that I am, is liberal in the sense of "people should be free to make their own choices".

Who knows what the new year will bring. 2006 was interesting--not the best year on record for me. The best year on record for me might have been 1998, when I started working on what became my graduate work. I hope 2007 can find itself looking more like 1998 than 2006.

Brain started to work

2006-02-09T12:18:00.000-08:00

me: it's like my brain just started working for the first time in months

Andy: what do you mean?

me: well, i was trying to figure something out last night
then, on the way home, i figured something out

Andy: yeah

me: then i came into work this morning, made like 10 changes to some code i was working on
then ran it, and it just worked

Andy: nice man
glad to hear it

me: that hasn't happened in such a long time

Andy: totally cool
good work [smile]

me: thanks man

Fundamental observation of science

2005-10-05T00:02:00.000-07:00

I had a post a way back about fundamental theorems of certain branches of mathematics. This post is about what I think is the fundamental observation of science. Ready? The fundamental observation of science is:

Repeated observations are more reliable than unrepeated ones.

Why is that? Basically, that is because people are unreliable. I have memories of things I can prove to myself never happened, or happened quite differently from what I remember. How do I know? Well, the time I am thinking of involves me doing something rather unthinkable that could have potentially killed my brother. I firmly remember it as being on accident, but I also know that this memory has been reconstructed at least once in my head. I actually have two different memories of the event. I know that a particular one of them is wrong, because nobody could run as fast as I remember my brother running in that one.

Other times, I've made stuff up out of thin air. Why? Because it seemed advantageous at the time. Like that I only had "one" piece of candy for desert. That I had done my homework, but forgot it at home (might have said that more than once, and I'll bet it was a lie at least 99% of the time).

It stands to reason that this kind of thing happens to other people too sometimes. Maybe some people are more reliable than me. Maybe some people never lie. Maybe some people are never deceived by their senses or their memories. Maybe some people have perfect intuition or never make a logical mistake. Unfortunately, it's hard to reliably tell who those people are.

So, if we can't trust any single person, can we ever gain a reliable picture of the world? The laws of nature? The gross history of the universe? I think our best bet is to get rid of single points of failure in the system.

A certain codification of this philosophy is called science. An experiment is a procedure you can repeat any number of times to give an observation that either rejects or is consistent with a hypothesis. You can be as sure as you like which is the case by repeating the experiment enough times. A hypothesis is scientific if you can show that if it's false then there is some experiment that rejects it.

That isn't, by far, enough to define science. In fact, it's just one aspect. Science is fundamentally a creative endeveor. When does a hypothesis become accepted as being a probable fact? At least it needs to go through a reasonable period of scrutiny in which people try to show that it's false based on some experiment, or that it's somehow infeasible to do the experiments.

But serious scientists insist on not allowing single mistakes from forever corrupting the conclusions. This is related to the value of skepticism, which says that it's better to be unsure than to be sure and wrong.

Sideways

2005-08-28T14:23:00.000-07:00

So, it's actually been a year or something since I've seen the movie Sideways, but for some reason it always manages to come up in interesting conversations, as it did a few nights ago. I ended up loving the movie, even though I almost walked out of the theater (I had gone by myself) half an hour in.

So, what was great about the movie? I really don't care at all about the wine aspect. I'm not a big fan of wine. For me, wine was a metaphor for anything "otaku". Otaku is a good Japanese word that means somewhere between "fanatic" and "geek". Good examples of otaku are computer hackers and the guys who climb Mount Everest just for the hell of it.

If you've seen the movie, the otaku is Miles, played by Paul Giamatti. The non-otaku is Jack, played by Thomas Hayden Church (I just looked this crap up right now--I didn't know any of that off the top of my head). The movie is about a trip that Miles and Jack take from L.A. to Napa Valley, ostensibly to tour the wineries, though Jack's actual purpose is to have as much sex as he can before he gets married the following week.

Miles, meanwhile, has not recovered from a doomed marriage and does his best to avoid the intimacy of his past acquaintance and obvious soulmate, Maya. Halfway through the movie comes a very memorable scene. Jack has hooked up with a bartender and friend of Maya's named Stephanie, and the four, Jack, Stephanie, Miles and Maya find themselves at her house. Maya opens her soul to Miles, and they share a conversation about the perfect wine experience. Practically the only thing left to do is have sex, but Miles momentarily can't bring himself to it, and instead spoils the mood by hanging on to the topic of wine.

But it is a kind of turning point in the movie, after which Miles begins to fall for Maya. As they are driving away, separately, he gives her two boxfulls of pages that are the manuscript of his book and providing the thread that will keep them together.

The way I've set it up, there should be a moral to the story that's expressable in terms of otaku. Probably there's not. If there was, it would go something like this: it's not worth pretending your something that you're not. If you're an otaku, you might as well be an otaku. Miles is much better off with Maya than with his ex-wife. However, Jack might also be better off with his bride-to-be than with any of the people he just cheated on her with. He shuns the otaku world, and good for him. He was never one of them.

How does this relate to me?

I'm not sure whether I'm comfortable writing about all the ways it relates to me, but here's one basic way: I definitely think I'm an otaku. Not about wine, obviously, but about other things. I'm an otaku about languages, for one. Mostly though, I just want to think my way through things. I like understanding the technical arguments that people make. I like thinking about the theory of science, like how you can never really prove that a hypothesis is right, only that certain alternatives are wrong.

Message?

2005-07-26T17:03:00.000-07:00

I was at an airport recently, and after finishing a quick breakfast, I realized that I didn't have much time to get to my flight. However, I couldn't remember what number my gate was. Mentally, I narrowed it down to either 82 or 84, which I could see were in opposite directions. For some reason it occured to me that my gate number would be written on the under side of my snapple cap. When I turned it over, the message read "There are over 82 miles of shoreline in Nantucket."

Amazed, I began to wonder how it was that my question had been so aptly answered. After all, it's not every day that the idea comes to one that his flight number should be located on a bottle cap. Most bottle caps don't have anything written on them at all, much less the flight number of a soon-to-depart airline.

What could be the reason for that kind of a revelation at such a time? Certainly it was an important flight for me not to miss. Could some supernatural force be projecting itself into my mind at just the right moment, so that I wouldn't miss my flight?

I took a look at my boarding pass just to make sure. "Gate 84", it said. I turned around and walked to my gate.

Cousins

2005-07-14T17:37:00.000-07:00

I was walking out of my lab yesterday and saw something that really struck me. There was a chipmunk underneath an oak tree standing up and eating an acorn. A large black dog on pulling at his leash regarded the chipmunk as the chipmunk stared back at the dog. The dog's owner, talking on her cell phone took stock of the situation and allowed her dog to continue staring at the chipmunk. I continued walking past the three, stopping only long enough to begin thinking about what all four of us have in common.

I had the sudden feeling of satisfaction in knowing that we are all cousins, separated of course by generations, but tied together by a genuine family relation. My great-great-great... grandfather and the chipmunk's could have been the same creature. It wasn't a realization of the fact of evolution. I've understood that theory for quite a long time. Rather, it was almost a feeling of community with the animals. After all, we are just one big family.

What could be more fantastic? And yet, I remember how doubters of evolution in my high-school would ask me "so you're related to monkeys?", spitting out the words in disgust.

So now I want to know: why is that disgusting? What's wrong with acknowledging that you're cousins with the animals? I know it goes against all of the myths of creation, which many educated people still believe. Is that actually a reason to find the idea distasteful?

One upshot of this is that I no longer feel like I want to eat the meat of mammals. After all, I've known enough dogs to be sure of their intelligence and emotions. Pigs are supposed to be even smarter. I do not doubt that I could become friends with a pig if given the opportunity. How can I justify killing a creature I might otherwise have been friends with to satisfy an appetite I could easily satisfy otherwise?

I'll probably draw the line at mammals. I don't feel as close to fish or fowl, and there is a much bigger difference between my mind and theirs, so I think that eating them is not so bad.

What do you think?

Internationalization of "Intellectual Property"

2005-07-11T22:15:00.000-07:00

The Chinese Communist Party has acquiesced to enforce charges of piracy against Chinese people brought by United States companies. Despite the potentially lucrative implications for those companies, this is an unfortunate development for several reasons.

The first reason is straightforward. It increases the perceived legitimacy of so-called intellectual property. Although intellectual property was originally founded upon the public good, it is now increasingly being seen as a right that exists for the benefit of the IP owner.

Another body of law which was founded upon the public good is anti-trust law. In this realm, litigation has been decided in a way that confirms that the laws are for the public good. Companies like AMD, alledging harm by Intel, must present their claims and arguments in terms of harm to the public good.

By contrast, when companies (or individuals) try to use one of the Electronic Frontier Foundation's 10 Most Wanted Patents to extort money from small businesses, they do not have to show that such extortion is in the public interest. In essence, that debate is presumed to have already happened. The U.S. patent office implicitly takes it that the research done by the inventors, for the sake of the patents, has (in the preponderance of cases) benefited the public more to an extent that justifies the heavy burden on the courts of enforcement, and on would-be competitors and the market they would serve.

In a sense, it would be nice to have a renewed debate on whether the whole system is worth it in these terms. Unfortunately, it may be too late. Patents are no longer even supposed to be for the public good, but rather are considered as a right of inventors, akin to the freedom of speech or freedom to own physical objects.

The second reason that the development in China is unfortunate is that it pits the U.S. government together with the CCP against certain freedoms of the Chinese people. This arrangement seems like it could undermine the pro-freedom stance that has been taken in the past by the US government (not that the US hasn't seriously undermined such positions in and around Iraq over the last 3 years). Perhaps the CCP will be able to find tacit support from the U.S. and international corporations for "playing ball" like so many friendly dictatorships.

Only a sith thinks in absolutes

2005-05-24T13:54:00.000-07:00

So, I went to see star wars last night with 900 other geeks from Caltech.

There's one line from the movie that nobody's going to understand in 20 years. The line has nothing at all to do with the movie, and everything to do with the politics of W. Bush. Yes, if you've seen the movie, you've already recognized the title of this post as being from the dialogue between Obi Wan Kenobi and Anakin Skywalker as they fight in the volcano world of Mustafar. The dialog goes like this:

Anakin: "Either you're with me, or you're my enemy"
Obi Wan: "Only a sith thinks in absolutes"

Now, let's all admit that this is a pretty good jab at W. But, if you take the second line seriously for a moment, as if it is really from the movie, it makes no sense. Not only does it make no sense, but it sells out the basic premise of the entire series of movies, which is Jedi versus the Dark Side Of The Force. Good versus Evil, damnit! The Jedi are the ones who see the world in terms of good and evil. In my opinion, Lucas pretty clumsily pushed his analogy past its breaking point with this line.

And I was on board with the analogy too. Yes, let the Galactic Empire be the United States! Let Darth Vader be George W. Fine with me, although I wouldn't give the US president credit for having any extra midichlorians. Damnit Lucas, why did you have to mess it up by also turning the Jedi knights into postmodernist liberals. Still, given your tack, there was an obvious continuation:

Anakin: "Either you're with me, or you're my enemy"
Obi Wan: "Only a sith thinks in absolutes"
Anakin: "Actually, that's a misunderstanding. We Sith aren't really about 'good' or 'evil', we mostly just use the force as a means to our own ends. If you think about it, the Jedi are more the ones thinking in terms of absolutes."
Obi Wan: "yes, well what I mean to say is, you're accepting the narrative of the oppressor; try listening to the narrative of the oppressed."
Anakin: "What?"
Obi Wan: "Just give up, I have the high ground."
Anakin: "You think confusing me gives you some kind of moral superiority?"
Obi Wan: "No, I mean that if you jump at me, I'll cut off your good arm."
Anakin: "Oh, so it's back to the movie then is it?"

Funny betting game

2005-05-19T13:22:00.000-07:00

So, I play poker sometimes, and one aspect that really interests me is the game-theoretic aspects to betting. Here's an interesting abstraction of a certain situation involving repeated bets (i.e. pre-flop, flop, turn, river).

There are just two players. Each player can put any amount between $1 and $100 into the pot, and each chooses his amount secretly and independently of the other. If the amounts are unequal, then whoever put more money into the pot wins.

Now, there are two superpowers in this game, a tie-breaking superpower and a pot-stealing superpower. the tie-breaking superpower is you get to win in the event of a tie, which means if you put in $100, the other player can't beat you by putting in a bigger amount. The pot-stealing superpower is invoked when an ace comes off of the top of a shuffled deck of cards, in which case the player with that superpower automatically wins all the money. The pot-stealing superpower takes precedence over the tie-breaking superpower.

The question is: which superpower would you pick? Also, how would you play the game?

Computer go v. computer chess

2005-05-10T22:12:00.000-07:00

What do you know about computer go?

There is a phenomenon that current computer programs for chess are on par with international chess grandmasters. Meanwhile, the best computer go can't even compete with average players who have played for a year.

What's the difference? Well, the common arguments are to the effect that go has a "bigger branching factor" because there are so many more possible moves in a typical position. This allows chess programs to look ahead up to twice as many moves ahead as a go program, given no pruning at all. Another reason is that chess programs can use sophisticated opening and endgame databases, and thus are really only able to lose a game in the mid-game.

This analysis is undermined if one notices that computer go is equally skillful (or unskillful) at playing 9x9 go as it is at playing 19x19 go. In 9x9 go, the branching factor is much closer to that in chess (around 40 moves on average). Again, opening databases can be used, and very few games are won or lost in the endgame anyway.

So, why do computers suck at go? The answer is that they don't suck at all. Rather, we humans are just much better at go than we are at chess. Spacial symmetry and spacial reasoning is much more meaningful in go than in chess, and we are good at spacial problems.

Go is a game where we win by proving to ourselves that a certain move is "good enough", not by finding the best move. Even pros play this way. In go, there are often many variations on a particular play that lead to essentially the same result. Though the stones might be in slightly different positions, we can see that the differences are either trivial or else don't matter at all. Our minds automatically fold these possibilities into each other and we forget about the unimportant differences. The effective branching factor is thus much smaller for go than it appears.

Logical separation of the action in different parts of the board is also possible in go to an extent that is not possible in chess. Long-range dependencies certainly exist in go, even on a relatively empty board, and good players take advantage of them. However, we can play reasonably well by forgetting about them, and it can save a lot of mental effort. That's a good trade-off, especially in the positions where we can prove to ourselves that the positions are truly independent.

These reasons make go a much more interesting game than chess in which to pit computers against humans. Sure, computers can beat us at chess using tree search and clever hacks. To beat us at go will take much more. Computers will have to think a lot more like we do.

Go is a game that offers big rewards for players that possess skills native to humans, to an extent that chess does not. The day that a computer became the world's chess champion was a milestone for artificial intelligence. The day that computers beat us in go will be a much bigger one.

Extreme Programming

2005-05-09T14:36:00.000-07:00

What the hell is Extreme Programming anyway?

I guess it's a loose collection of software programming practices, philosophies, or just a cult. It looks like a cult because there are a few big advocates and because it's so damn controversial. One reason it's controversial is that it strongly de-emphasizes up front design in favor of methods that make code much more flexible. What methods are those? Well, there's refactoring, which is a way of moving code around so that you create a different abstraction without actually changing the functionality. Another one is pair programming, which strongly encourages the programmer to write readily understandable code.

Back to the controversy, it's more than just the way of presentation that causes controversy. XP gives a lot more responsibility to the programmer, relative to his boss the software engineer, which he hates.

Perhaps the one argument against the hollistic view taken by XP advocates is that it couples the practices that lead to code flexibility with big changes in the way projects are managed. Software evolves, but teams that adopt XP are supposed, in one Great Leap Forward, to change the processes such as UML models and other documentation.

Anyway, the core technical processes of XP are probably here to stay, and they're going to have a positive impact on most teams that choose to use them.

China v. Taiwan

2005-05-08T01:07:00.000-07:00

Well, this is a sticky issue, isn't it. First, let's look at the question of whether Taiwan is functionally an independent nation, shall we? Here are some reasons to take each position. First, the reasons to think Taiwan is an independent nation:

1. Taiwan has it's own government that does not recognize the authority of the Chinese government.
2. As a U.S. citizen, I need a visa to enter mainland China, but not Taiwan.
3. Taiwan has it's own top-level domain name. (.tw), Olympic team.
4. The U.S. and other nations have agreed to defend Taiwan if China were to make military threat toward Taiwan.

Some reasons to believe that Taiwan is not an independent nation:

1. Taiwan is not a member of the UN
2. Almost all nations officially do not recognize Taiwan as a nation.
3. The government of China claims sovereignty over the island of Taiwan.

If Taiwan is not an independent nation, then it might be a part of China, or logically it might be a land mass that isn't part of any nation, like Antarctica, though nobody seriously espouses this position.

The legal status of Taiwan is not agreed to by everybody. The pro-independence position cites the San Francisco Treaty as renouncing Japan's Sovereignty over Taiwan, but does not officially state which nation, if any, is sovereign over Taiwan. China did not sign the San Francisco Treaty.

Historically, China has exercised some degree of sovereignty over Taiwan at various times in history. See the pro-independence position and the pro-unification position on this issue.

So, why should anybody besides the Chinese and Taiwanese people themselves care about the issue? One possible reason is that there is a substantial gap in the status of human rights in the two countries. For a rough, but accurate comparison, worldaudit.org is a good place to start.

Calvin Poker!

2005-05-06T21:20:00.000-07:00

Calvinpoker is a blog about poker. The name comes from my opinion about the house rules of a poker game that I play in sometimes. I won't explain how the rule came up right now, but one of the rules that we apparently officially play with is that if a board card is accidentally dealt before the round of betting is finished, we keep the card and finish the round of betting. After the round is over, any player can choose to have the card redealt, but this does not happen automatically. Somebody has to ask for it.

Sounds like CalvinBall, right? From Calvin and Hobbes. Exactly. CalvinPoker.

Fundamental Theorems

2005-04-29T16:24:00.000-07:00

It's kind of surprising how many branches of mathematics are structured around some kind of single fundamental theorem. Maybe in some cases, there are more than one theorem that compete for the title, but often there is a clear winner. Here are some fundamental theorems:

Arithmetic - Every positive integers is the product of a unique multiset of prime factors.

Algebra - Every complex polynomial of degree n is the product of n affine factors.

Calculus - Riemann Integration and differentiation are inverses.

Analysis - Lebesgue integration is the same as Riemann integration.

Game Theory - In a matrix game, both players have a mixed strategy which stochastically gurantees a common average outcome, at worst.

Statistics - The normalized limiting distribution of independent, bounded variance random variables is Gaussian.

Data Compression - A random variable can be decodably compressed into an average number of bits equal to its binary entropy, but no smaller.

Channel Coding - A channel can be used to reliably transmit a number of bits equal to its binary capacity, but no more.

Geometry - Any polygon that has n vertices also has n sides. Just kidding, there is no fundamental theorem of geometry, and don't tell me it's the Pythagorean theorem.

Galois Theory - For any n, if n is the power of a prime then there is a unique field of size n, otherwise no field of size n exists.