31 January 2008
What good are applications?
What We're Doing Wrong: Programming in Theory Classes, from Michael Mitzenmacher's blog My Biased Coin. Mitzenmacher claims that the standard introductory classes in algorithms don't include programming assignments; furthermore, he thinks this is bad for theoretical computer science, because non-theoretical computer scientists get the idea that theory isn't actually good for anything.
I think the theoretical computer scientists are doing it right! But I think this from a selfish point of view -- I'm taking an algorithms class that nominally requires that I have certain classes which involve programming as a prerequisite, and I don't feel lost for not having had those classes. From a less facetious point of view, I agree with Mitzenmacher, even though it would hurt me. If someone learning something new has no idea how it connects to anything they've ever learned, it's not going to stick in their brain. The human brain is not a computer -- and even if it were, that doesn't mean that throwing a bunch of random facts in it is the best way to do things.
The same statement holds, I would think, for any course in any field that covers the "theory" behind some other material. Within mathematics, for example, it's possible to teach people what a category is without giving examples of all the familiar structures they know that are in fact categories; it's possible to teach real analysis without pointing out the connections to the calculus students already know; it's possible to teach rigorous measure-theoretic probability without appealing to (often flawed, but still useful) intuition that people have about flipping coins and rolling dice and distributing objects among boxes. I'm sure my readers can provide other examples.
I think the theoretical computer scientists are doing it right! But I think this from a selfish point of view -- I'm taking an algorithms class that nominally requires that I have certain classes which involve programming as a prerequisite, and I don't feel lost for not having had those classes. From a less facetious point of view, I agree with Mitzenmacher, even though it would hurt me. If someone learning something new has no idea how it connects to anything they've ever learned, it's not going to stick in their brain. The human brain is not a computer -- and even if it were, that doesn't mean that throwing a bunch of random facts in it is the best way to do things.
The same statement holds, I would think, for any course in any field that covers the "theory" behind some other material. Within mathematics, for example, it's possible to teach people what a category is without giving examples of all the familiar structures they know that are in fact categories; it's possible to teach real analysis without pointing out the connections to the calculus students already know; it's possible to teach rigorous measure-theoretic probability without appealing to (often flawed, but still useful) intuition that people have about flipping coins and rolling dice and distributing objects among boxes. I'm sure my readers can provide other examples.
30 January 2008
Some probabilistic ramblings on evolution
The Repeater (Olivia Judson, in an NYT blog). The post begins:
This is the sort of question that's hard to answer a priori. Basically, evolution is made up of a ridiculously large numer of random decisions, each with a very small effect. There are a lot of classes of combinatorial structures for which we can generate members of the class uniformly at random (or according to some other probability distribution; the details don't matter here) and they'll all basically look the same. Why shouldn't evolution be like that? The details will be different every time; but in broad outline one can imagine that a "law of large numbers" and "central limit theorem" could apply to evolution -- if we consider some numerical measure of some evolutionary trait, then if we average that numerical measure over many independent "runs" of evolution we should approach some limit, and the deviations from that average might even be spread out according to a normal distribution.
Of course, this isn't something that has to be true -- the many events that make up a single evolutionary process aren't exactly independent, some of them can only happen if others happen, and so on. And whatever numerical measure I was talking about in the previous paragraph might only exist in some runs and not in others. That would seem to argue against my hypothesis. But on the other hand, evolution isn't just a random walk. There are selection pressures which are the more standard explanation for what's known as "convergent evolution", which is the indepedent evolution of similar traits in evolutionarily distinct populations.
By the way, on the topic of convergent evolution: the eye has evolved something like forty times. This suggests that eyes are very likely to arise via the evolutionary process; things that have only evolved once among all life, like language (although that's open for debate), are given the state of our current knowledge less likely to arise. One might be able to compute something like the "probability" that eyes, language, or some other complex trait evolves by looking at how many times it has arisen independently. But this is the sort of probability that is very hard to interpret -- what would it mean to let evolution happen more than once?
Here’s an evolutionist’s dream: 10,000 planet Earths, starting from the same point at the same time, and left to their own devices for four and a half billion years. What would happen? Could you go on safari from one planet to the next seeing an endless procession of wildly different organisms? Or would many of the planets be home to life forms that are broadly similar?
This is the sort of question that's hard to answer a priori. Basically, evolution is made up of a ridiculously large numer of random decisions, each with a very small effect. There are a lot of classes of combinatorial structures for which we can generate members of the class uniformly at random (or according to some other probability distribution; the details don't matter here) and they'll all basically look the same. Why shouldn't evolution be like that? The details will be different every time; but in broad outline one can imagine that a "law of large numbers" and "central limit theorem" could apply to evolution -- if we consider some numerical measure of some evolutionary trait, then if we average that numerical measure over many independent "runs" of evolution we should approach some limit, and the deviations from that average might even be spread out according to a normal distribution.
Of course, this isn't something that has to be true -- the many events that make up a single evolutionary process aren't exactly independent, some of them can only happen if others happen, and so on. And whatever numerical measure I was talking about in the previous paragraph might only exist in some runs and not in others. That would seem to argue against my hypothesis. But on the other hand, evolution isn't just a random walk. There are selection pressures which are the more standard explanation for what's known as "convergent evolution", which is the indepedent evolution of similar traits in evolutionarily distinct populations.
By the way, on the topic of convergent evolution: the eye has evolved something like forty times. This suggests that eyes are very likely to arise via the evolutionary process; things that have only evolved once among all life, like language (although that's open for debate), are given the state of our current knowledge less likely to arise. One might be able to compute something like the "probability" that eyes, language, or some other complex trait evolves by looking at how many times it has arisen independently. But this is the sort of probability that is very hard to interpret -- what would it mean to let evolution happen more than once?
29 January 2008
Prediction markets do measure something!
So I've talked on and off before about prediction markets. One of the questions one wants to ask is -- are they actually measuring something? I asked this last week.
In a comment to that post, John Armstrong has informed me of this post from the Volokh Conspiracy that shows that yes, they are. At least in the case of certain prediction markets dealing with Major League Baseball, that is. The standard contract here pays 10ドル if a team wins a particular game. A plot is provided which aggregates all the trades for contracts on MLB games in each ten-cent interval.
Now, let's say the Phillies and the Qankees are playing each other. (Longtime readers may recall that the reason for the Qankees' existence is because their name starts with Q, which is the letter after P. I haven't talked about them for a while, because it's not baseball season.) And let's say that I think the Phillies have a probability of 62.5% of beating the Qankees. Then I will be willing to pay up to 6ドル.25 for the aforementioned contract, since that's the expected payout.
Now, what does it mean that this probability is 62.5%? Well, it means that if lots and lots of games like that one were played, then the Phillies would win about 62.5% of them. (The meaning of "lots and lots" and "about" can be made precise via the law of large numbers.) But that particular game will never be played again, so we can't check if my intuition is right. But we can do the next best thing -- look at all the games where people paid 6ドル.25 for a contract for some team to win 10,ドル and ask if that team won 62.5% of the time.
It turns out that, basically, they do. That's the point of the chart over at Volokh, which is due to Michael Abramowicz, author of the book Predictocracy: Market Mechanisms for Public and Private Decision Making. It's nice to see some evidence that at least in the world of sports -- which seems to be a good test bed for a lot of statistical and economic work, because it's possible to collect basically all the relevant data -- these things appear to actually be measuring probabilities.
In a comment to that post, John Armstrong has informed me of this post from the Volokh Conspiracy that shows that yes, they are. At least in the case of certain prediction markets dealing with Major League Baseball, that is. The standard contract here pays 10ドル if a team wins a particular game. A plot is provided which aggregates all the trades for contracts on MLB games in each ten-cent interval.
Now, let's say the Phillies and the Qankees are playing each other. (Longtime readers may recall that the reason for the Qankees' existence is because their name starts with Q, which is the letter after P. I haven't talked about them for a while, because it's not baseball season.) And let's say that I think the Phillies have a probability of 62.5% of beating the Qankees. Then I will be willing to pay up to 6ドル.25 for the aforementioned contract, since that's the expected payout.
Now, what does it mean that this probability is 62.5%? Well, it means that if lots and lots of games like that one were played, then the Phillies would win about 62.5% of them. (The meaning of "lots and lots" and "about" can be made precise via the law of large numbers.) But that particular game will never be played again, so we can't check if my intuition is right. But we can do the next best thing -- look at all the games where people paid 6ドル.25 for a contract for some team to win 10,ドル and ask if that team won 62.5% of the time.
It turns out that, basically, they do. That's the point of the chart over at Volokh, which is due to Michael Abramowicz, author of the book Predictocracy: Market Mechanisms for Public and Private Decision Making. It's nice to see some evidence that at least in the world of sports -- which seems to be a good test bed for a lot of statistical and economic work, because it's possible to collect basically all the relevant data -- these things appear to actually be measuring probabilities.
Hoagies and permutations (yes, really!)
About once a week, I buy a hoagie from Wawa for lunch. (Apparently people not from the Philadelphia area think "Wawa" is a very funny word. Here's an explanation; basically Wawa the store is named after Wawa the town, which in turn is the name for the Canada Goose in the language of the people who lived there before Europeans did.) Today was such a day.
Now, when you go in and buy a hoagie, you order on a touch screen, and the touch screen prints out a receipt with a number on it. These numbers are assigned sequentially -- but for various reasons, people's orders don't get filled in the same order that people put in their orders. This is immensely frustrating, and gives one a visceral sense of why permutations with a lot of inversions are kind of annoying. (A permutation is just a reordering of some totally ordered set, say {1, 2, ..., n}; an inversion, informally, is what we have when a larger number comes before a smaller number. For example, 1 5 3 2 4 is a permutation of {1, 2, 3, 4, 5}; it has four inversions, namely the pairs (5, 3), (5, 2), (5, 4), and (3, 2). I know that some people define inversions a bit differently, looking at the position in which the offending numbers appear instead of the offending numbers themselves.) The reasons why orders don't come out in the same order they come in have to do with the fact that there are multiple people preparing orders in parallel (at least during the lunch rush; the dinner rush is much less intense, both because there are less people buying dinner than lunch on a university campus and because the times at which peopel eat dinner are more spread out than the times at which they eat lunch) and that some orders take longer to prepare than others. To a first approximation, there seem to be three classes of order: food which is already prepared, cold made-to-order things, and hot made-to-order things.)
The wait was long today, so I got to thinking -- basically this procedure is generating a permutation of the integers. But it's a permutation of the integers with only Θ(1) inversions per element; that is, for any given customer, the number of people who came in after them and yet get served before them is on average some constant number. (I have no idea what this number is.) If we consider, say, the permutation that's generated in this way over the course of an hour during the lunch rush, it might be a permutation of [100] with a few hundred inversions. A "typical" permutation of 100 has about 2,500 inversions -- as n gets large, the number of inversions of a permutation of n selected uniformly at random is approximately normally distributed with mean n(n-1)/4 and standard deviation on the order of n3/2/6. Efficiently generating a random permutation with, say, less than 10n inversions (for large n) is not just a matter of generating random permutations (which is easy) and throwing out the ones which you don't like; there are sampling algorithms which work this way, to sample uniformly at random from some subset of a set which it's easy to sample u. a. r. from -- but as far as I know they don't throw away all but a vanishingly small proportion of all the elements in the large set! I don't know if anybody's thought about this problem.
Now, when you go in and buy a hoagie, you order on a touch screen, and the touch screen prints out a receipt with a number on it. These numbers are assigned sequentially -- but for various reasons, people's orders don't get filled in the same order that people put in their orders. This is immensely frustrating, and gives one a visceral sense of why permutations with a lot of inversions are kind of annoying. (A permutation is just a reordering of some totally ordered set, say {1, 2, ..., n}; an inversion, informally, is what we have when a larger number comes before a smaller number. For example, 1 5 3 2 4 is a permutation of {1, 2, 3, 4, 5}; it has four inversions, namely the pairs (5, 3), (5, 2), (5, 4), and (3, 2). I know that some people define inversions a bit differently, looking at the position in which the offending numbers appear instead of the offending numbers themselves.) The reasons why orders don't come out in the same order they come in have to do with the fact that there are multiple people preparing orders in parallel (at least during the lunch rush; the dinner rush is much less intense, both because there are less people buying dinner than lunch on a university campus and because the times at which peopel eat dinner are more spread out than the times at which they eat lunch) and that some orders take longer to prepare than others. To a first approximation, there seem to be three classes of order: food which is already prepared, cold made-to-order things, and hot made-to-order things.)
The wait was long today, so I got to thinking -- basically this procedure is generating a permutation of the integers. But it's a permutation of the integers with only Θ(1) inversions per element; that is, for any given customer, the number of people who came in after them and yet get served before them is on average some constant number. (I have no idea what this number is.) If we consider, say, the permutation that's generated in this way over the course of an hour during the lunch rush, it might be a permutation of [100] with a few hundred inversions. A "typical" permutation of 100 has about 2,500 inversions -- as n gets large, the number of inversions of a permutation of n selected uniformly at random is approximately normally distributed with mean n(n-1)/4 and standard deviation on the order of n3/2/6. Efficiently generating a random permutation with, say, less than 10n inversions (for large n) is not just a matter of generating random permutations (which is easy) and throwing out the ones which you don't like; there are sampling algorithms which work this way, to sample uniformly at random from some subset of a set which it's easy to sample u. a. r. from -- but as far as I know they don't throw away all but a vanishingly small proportion of all the elements in the large set! I don't know if anybody's thought about this problem.
28 January 2008
Dummit and Foote for middle schoolers?
Somebody seems to have mistaken Dummit and Foote's Abstract Algebra -- a standard undergraduate abstract algebra text -- for a middle school algebra text, and wrote a bad review of it, saying things like:
I think it might be a parody. I hope it's a parody, of what someone who expected a middle school algebra text and got an abstract algebra text would say. And I think every mathematician has had that moment where they told someone they're taking "algebra" and people say "but didn't you learn that years ago?"
And the author makes a point, perhaps inadvertently - there is a time and a place for the precise language of higher-level mathematics, and middle school isn't it.
As we see from these excerpts from the text, Dummit and Foote are disciples of "new math," a doctrine discredited in the 70's. Too often, strange symbols and jargon take the place of clear English prose. Extraneous concepts like "sets"--much less "finite nilpotent groups" or "invariant factor decompositions" or "symmetric multilinear maps"--are merely obstacles to a student's understanding of algebra. Sadly, the authors, holed up in their ivory towers, have not yet learned these vital educational lessons.Well, of course! It's not good as a text for middle schoolers, because it was never supposed to be! (And it probably comes with a preface saying "this is a text for juniors and seniors in college majoring in math", or something like that; can anybody who has a copy of the book confirm this?)
I think it might be a parody. I hope it's a parody, of what someone who expected a middle school algebra text and got an abstract algebra text would say. And I think every mathematician has had that moment where they told someone they're taking "algebra" and people say "but didn't you learn that years ago?"
And the author makes a point, perhaps inadvertently - there is a time and a place for the precise language of higher-level mathematics, and middle school isn't it.
Primes is in P
It appears to not be widely known, at least among some people who would like to know it, that primality testing can be done in polynomial time. The "naive" methods for determining whether a number is prime -- trial division and the like -- take time which is polynomial in the size of the input (the polynomial may be n1/2, but it's still a polynomial) which is considered "large" because it's exponential in the number of digits or bits in the input.
The fact that primality testing can be done in polynomial time -- and without recourse to a randomized algorithm -- I've heard about here and there; not surprisingly, the exponent is large. Namely, to test n for primality takes time O~(log6 n), where O~(t(n)) = O(t(n) * P(log t(n))) and P is a polynomial. (If you don't like the O~ notation, you can say O(log6+ε n) for any positive real ε.) It's conjectured that "6" can be replaced by "3". The proof is based on a generalization of Fermat's Little Theorem; of course it's nothing like the "naive" method of trial division, but the paper is surprisingly accessible given the strength of the result.
The paper is Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160 (2004), 781-793. (http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf)
Edited, 7:21 pm: It's been pointed out to me that this result is widely known among people who work in the appropriate fields, and that's true. But a lot of people who are just looking for some sort of color when they're giving an example of a hard algorithmic problem, and whose specialty is not in that area, either don't know this or don't remember it. I'm claiming that the result deserves to be more well-known among mathematicians in general.
The fact that primality testing can be done in polynomial time -- and without recourse to a randomized algorithm -- I've heard about here and there; not surprisingly, the exponent is large. Namely, to test n for primality takes time O~(log6 n), where O~(t(n)) = O(t(n) * P(log t(n))) and P is a polynomial. (If you don't like the O~ notation, you can say O(log6+ε n) for any positive real ε.) It's conjectured that "6" can be replaced by "3". The proof is based on a generalization of Fermat's Little Theorem; of course it's nothing like the "naive" method of trial division, but the paper is surprisingly accessible given the strength of the result.
The paper is Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160 (2004), 781-793. (http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf)
Edited, 7:21 pm: It's been pointed out to me that this result is widely known among people who work in the appropriate fields, and that's true. But a lot of people who are just looking for some sort of color when they're giving an example of a hard algorithmic problem, and whose specialty is not in that area, either don't know this or don't remember it. I'm claiming that the result deserves to be more well-known among mathematicians in general.
27 January 2008
Street Fighting Mathematics
18.098/6.099. Street Fighting Mathematics, a course currently being offered during MIT's Independent Activities Period, by Sanjoy Mahajan. (I got a call from MIT asking me for money tonight; I donated some; that got me thinking about the Institute so I poked around the web site a bit.)
The course description is as follows:
From a quick poke around the web page, it looks like Mahajan also offered a similar, but more physics-oriented course in IAP 2006, as well as TAing a couple more substantial courses in the same vein at Caltech called "Order-of-Magnitude Physics". (The MIT IAP course meets three hours a week for four weeks and carries one-quarter the credit that a "normal" course at MIT would carry; the Caltech courses appear to have met three hours a week for ten weeks. As such, they have more problem sets. But they're also more physics-y, which may be good or bad depending on how you feel about physics.
The course description is as follows:
The art of guessing results and solving problems without doing a proof or an exact calculation. Techniques include extreme-cases reasoning, dimensional analysis, successive approximation, discretization, generalization, and pictorial analysis. Application to mental calculation, solid geometry, musical intervals, logarithms, integration, infinite series, solitaire, and differential equations. (No epsilons or deltas are harmed by taking this course.)Personally, I always thought the epsilons and deltas were harming me. The text (a draft version of which can be found on the course web page) stresses the idea that approximate answers, heuristics, etc. are more valuable than they are often claimed to be, which is a question that Mahajan also took on in his PhD thesis, which is a combination of a version of such a textbook and some extended examples on what one might call "research-level" problems, one of which is a probabilistic model of the primes which it is too late at night to seriously read.
From a quick poke around the web page, it looks like Mahajan also offered a similar, but more physics-oriented course in IAP 2006, as well as TAing a couple more substantial courses in the same vein at Caltech called "Order-of-Magnitude Physics". (The MIT IAP course meets three hours a week for four weeks and carries one-quarter the credit that a "normal" course at MIT would carry; the Caltech courses appear to have met three hours a week for ten weeks. As such, they have more problem sets. But they're also more physics-y, which may be good or bad depending on how you feel about physics.
Subscribe to:
Comments (Atom)