A commercial for "Degree Clinical Protection" deodorant said: "Do you know one in four people think they sweat more than normal?"
So another one in four people are in denial, since the number of people who sweat more than normal is probably about half. (I'm assuming that "sweating more than normal" is the sort of thing one would deny, which seems reasonable, at least in the perspective of a deodorant commercial.)
I'm reminded of the often-quoted fact that three-quarters of all incoming students at [insert prestigious university here] think they're going to be in the top quarter of their incoming fact.
(The amazon.com page has a description beginning "Did you know one in four Americans worry about excessive sweating?", which I don't have a problem with, because the word "excessive" doesn't have the same statistical connotations.)
30 November 2007
Pattern avoidance redux: explaining part of Alon's conjecture
Not long ago I wrote a post about pattern avoidance, in which I mentioned the following conjecture of Noga Alon:
Conjecture (Alon): The threshold length t(k), for a random permutation to contain all k-permutations with substantial probability, has t(k) ~ k^2/4.
The paper by Richard Arratia from which I learned this conjecture doesn't really give any idea where it comes from; some rationale for the conjecture may be in one of Alon's papers (most of his post-1990 papers are available online) but I'm not particularly interested in tracking down the source.
Anyway, there are two things to understand about that conjecture -- the "2" and the "4". I have no idea where the 4 comes from, but I think I can heuristically explain the 2. The problem can be looked at as an instance of the classical "coupon collecting" problem. In order to see all k! of the k-permutations, we need there to be about (k! log k!) different places in which we could see a k-permutation. That is, we need
but by Stirling's approximation, the right-hand side is
Now, note that if n is much larger than k, then we have
since we can represent
as a quotient of products; the numerator contains k factors which are each approximately n, and the denominator is k!. So we have
Solving for t(k), we get
and applying Stirling's approximation, we get
But for large k, (k \log k)1/k is very close to 1. However, we get the wrong constant: e-2, not 1/4. This is because the dependence problem is quite serious -- if we pick two subsets of length k from a set of size (k/e)2, the probability that they intersect doesn't go to zero as $k$ goes to infinity is nonneglibible, and is something we can compute. Consider the probability that two randomly chosen k-subsets of a set of size ak2 do not intersect. This will be given by the quotient
which is just the number of ways we can choose the second subset not to intersect the first, divide by the total number of ways to choose the second. But recalling our approximation
, we see that this is approximately
and as k gets large, this approaches e-1/a. In our case, a = e-2, so this probability is e-e2, or about 0.0006. So the probability that two randomly chosen subsets of size k do intersect is about 0.9994. So the independence assumption is so wrong it's not even funny; the dependence makes it more likely that we see the same patterns over and over again, explaining why we need to go further than (k/e)2 to expect to see all the patterns.
Conjecture (Alon): The threshold length t(k), for a random permutation to contain all k-permutations with substantial probability, has t(k) ~ k^2/4.
The paper by Richard Arratia from which I learned this conjecture doesn't really give any idea where it comes from; some rationale for the conjecture may be in one of Alon's papers (most of his post-1990 papers are available online) but I'm not particularly interested in tracking down the source.
Anyway, there are two things to understand about that conjecture -- the "2" and the "4". I have no idea where the 4 comes from, but I think I can heuristically explain the 2. The problem can be looked at as an instance of the classical "coupon collecting" problem. In order to see all k! of the k-permutations, we need there to be about (k! log k!) different places in which we could see a k-permutation. That is, we need
but by Stirling's approximation, the right-hand side is
Now, note that if n is much larger than k, then we have
since we can represent
Solving for t(k), we get
and applying Stirling's approximation, we get
But for large k, (k \log k)1/k is very close to 1. However, we get the wrong constant: e-2, not 1/4. This is because the dependence problem is quite serious -- if we pick two subsets of length k from a set of size (k/e)2, the probability that they intersect doesn't go to zero as $k$ goes to infinity is nonneglibible, and is something we can compute. Consider the probability that two randomly chosen k-subsets of a set of size ak2 do not intersect. This will be given by the quotient
which is just the number of ways we can choose the second subset not to intersect the first, divide by the total number of ways to choose the second. But recalling our approximation
and as k gets large, this approaches e-1/a. In our case, a = e-2, so this probability is e-e2, or about 0.0006. So the probability that two randomly chosen subsets of size k do intersect is about 0.9994. So the independence assumption is so wrong it's not even funny; the dependence makes it more likely that we see the same patterns over and over again, explaining why we need to go further than (k/e)2 to expect to see all the patterns.
29 November 2007
Punitive damages
From Overcoming Bias: Unbounded Scales, Huge Jury Awards, & Futurism.
Apparently jurors are able to consistently rank-order the amount of money that they think should be given as damages in various cases -- they can say "I think person A deserves more money than person B", and other people will agree with them. And it seems implied in the post (although it's never actually stated) that they're fairly consistent in things like "I think person A deserves twice as much money as person B". But their assignments of dollar amounts to people are all over the map.
(If you're thinking "jurors always give ridiculous amounts in punitive damages!", that might be because the media seems to like the really out-there cases, like the guy who sued his dry cleaners for $54 million because they ruined his pants. He didn't get the money. I am not a lawyer, but I suspect that the amounts given in damages in most cases are more reasonable-sounding, if only because the people on juries are people like you and me.)
Similar things might hold for predictions of the future -- people are better at guessing the order in which the future will unfold than the speed at which it will unfold.
Apparently jurors are able to consistently rank-order the amount of money that they think should be given as damages in various cases -- they can say "I think person A deserves more money than person B", and other people will agree with them. And it seems implied in the post (although it's never actually stated) that they're fairly consistent in things like "I think person A deserves twice as much money as person B". But their assignments of dollar amounts to people are all over the map.
(If you're thinking "jurors always give ridiculous amounts in punitive damages!", that might be because the media seems to like the really out-there cases, like the guy who sued his dry cleaners for $54 million because they ruined his pants. He didn't get the money. I am not a lawyer, but I suspect that the amounts given in damages in most cases are more reasonable-sounding, if only because the people on juries are people like you and me.)
Similar things might hold for predictions of the future -- people are better at guessing the order in which the future will unfold than the speed at which it will unfold.
A puzzle, and some brief thoughts on education
A puzzle, from arpatubes.net.
There's no trick here. Still, only twenty percent of the people answering it have gotten it right, because it's the sort of thing you have to read very carefully.
The comments at fark.com (where I found this puzzle) are interesting. One common theme seems to be "this isn't really a math problem, this is a reading comprehension problem" or "this is a logic problem". But reading comprehension and logic are, of course, large parts of mathematics. I have a sense I'm preaching to the choir here.
On a similar but less frivolous note: from Pencils Down, A Letter to a Young Mathematician is a (fictional?) answer to what seems to be a student asking "what good are proofs?" (From vlorbik.) I'm reminded of the recent book Letters to a Young Mathematician, by Ian Stewart (who also wrote Does God Play Dice?; the resemblance of titles is almost certainly intentional. I suspect that students would, for the most part, feel differently about proofs and other things that aren't just rote calculation if they were introduced from the very beginning of their mathematical training, before they get the idea that all mathematics is arithmetic. But this might not be possible, because abstract reasoning is something that young children just aren't capable of, yet we need to start getting arithmetic into them at a young age. Their brains haven't matured enough yet for abstract reasoning.
As it is, students seem to resent being asked to prove something. A large part of this seems to be that proofs often require writing words, and mathematics, they feel, does not properly involve words. I actually spend a fair bit of time trying to counteract this in my teaching, but I can only do so much insisting that calculus students should know how to write complete sentences and be able to clearly explain their logic before they start to rebel.
And there is of course the problem that many students probably learn their first mathematics from an elementary school teacher that never much liked math when ey was in school.
There's no trick here. Still, only twenty percent of the people answering it have gotten it right, because it's the sort of thing you have to read very carefully.
The comments at fark.com (where I found this puzzle) are interesting. One common theme seems to be "this isn't really a math problem, this is a reading comprehension problem" or "this is a logic problem". But reading comprehension and logic are, of course, large parts of mathematics. I have a sense I'm preaching to the choir here.
On a similar but less frivolous note: from Pencils Down, A Letter to a Young Mathematician is a (fictional?) answer to what seems to be a student asking "what good are proofs?" (From vlorbik.) I'm reminded of the recent book Letters to a Young Mathematician, by Ian Stewart (who also wrote Does God Play Dice?; the resemblance of titles is almost certainly intentional. I suspect that students would, for the most part, feel differently about proofs and other things that aren't just rote calculation if they were introduced from the very beginning of their mathematical training, before they get the idea that all mathematics is arithmetic. But this might not be possible, because abstract reasoning is something that young children just aren't capable of, yet we need to start getting arithmetic into them at a young age. Their brains haven't matured enough yet for abstract reasoning.
As it is, students seem to resent being asked to prove something. A large part of this seems to be that proofs often require writing words, and mathematics, they feel, does not properly involve words. I actually spend a fair bit of time trying to counteract this in my teaching, but I can only do so much insisting that calculus students should know how to write complete sentences and be able to clearly explain their logic before they start to rebel.
And there is of course the problem that many students probably learn their first mathematics from an elementary school teacher that never much liked math when ey was in school.
28 November 2007
The binomial pinball machine
The Binomial Pinball Machine, from Kim Moser's repository of videos of Commodore 64 programs, via the Statistics Consulting Blog.
It's too bad the video stops before you actually start seeing a decent approximation to the normal distribution.
By the way, I almost named this blog quincunx, which is a name for this machine, but I decided that people might have trouble spelling it.
It's too bad the video stops before you actually start seeing a decent approximation to the normal distribution.
By the way, I almost named this blog quincunx, which is a name for this machine, but I decided that people might have trouble spelling it.
27 November 2007
Collections of images of mathematicians
The Sarong Theorem Archive, which claims to be "the only public repository of sarong-wearing mathematics images". If I had a sarong, and a digital camera with batteries in it, I'd be here. The people at the Secret Blogging Seminar have lamented the fact that this collection is not growing quickly. Incidentally, it seems to me that the best theorems for picture-taking are ones that have nice pictures associated with them, so I nominate Eric Paniagua proving the Pythagorean Theorem as the best of the lot.
Female mathematicians with teal hair. I'm not here because, well, my hair isn't teal. I don't know any of these people, although I went to college with a female mathematician named Teal.
On a more serious note, there are various pages which list a large number of mathematicians and have links to pictures of them; this is useful for putting a face to a name, although it would be more useful in the reverse direction of putting a name to a face. This is true in general; wouldn't it be nice to have something like identifont for faces? (Identifont asks a series of questions to help you identify an unknown font. After nineteen questions, it identified the font of this blog as Trebuchet, which is correct. I'm curious how exactly identifont works -- in particular, if I answer some questions wrong, can I still get the correct font? This is a question about error-correcting codes in disguise.) This isn't just for mathematicians, but for any population. There's a significant difference, though; usually when you're trying to identify a font, you have a sample of it in front of you, whereas if you have a picture of someone in front of you that would be good enough for such a method to be fruitful, you probably also know someone who knows their name. So a tree-like facial identifier patterned on Identifont would be more of a curiosity.
Female mathematicians with teal hair. I'm not here because, well, my hair isn't teal. I don't know any of these people, although I went to college with a female mathematician named Teal.
On a more serious note, there are various pages which list a large number of mathematicians and have links to pictures of them; this is useful for putting a face to a name, although it would be more useful in the reverse direction of putting a name to a face. This is true in general; wouldn't it be nice to have something like identifont for faces? (Identifont asks a series of questions to help you identify an unknown font. After nineteen questions, it identified the font of this blog as Trebuchet, which is correct. I'm curious how exactly identifont works -- in particular, if I answer some questions wrong, can I still get the correct font? This is a question about error-correcting codes in disguise.) This isn't just for mathematicians, but for any population. There's a significant difference, though; usually when you're trying to identify a font, you have a sample of it in front of you, whereas if you have a picture of someone in front of you that would be good enough for such a method to be fruitful, you probably also know someone who knows their name. So a tree-like facial identifier patterned on Identifont would be more of a curiosity.
Counting LEGO towers
A Lego counting problem, from Soren Eilers, via Vlorbik on Math Ed.
The question: what is the number of ways to make a tower of height six out of two-by-four LEGO® blocks? There are 102,981,504 ways; this is pretty straightforward, once you take the relevant symmetries into account. But apparently this has been confused with the problem of how many ways there are to make any sort of configuration out of six blocks; Eilers and his collaborator Mikkel Abrahamsen claim this number is 915,103,765, by what sounds like a brute-force program. The most common height for such a tower is 4; almost half the towers have this height.
How are the heights of towers containing n blocks distributed? I don't have much faith that this problem could be answered; it reminds me of the problem of counting self-avoiding walks. Let's say you live on the integer lattice, and you go for a walk, going north, south, east, or west at each step. There are clearly 4n walks of length n. But in how many of these walks do you never come back to a point you've previously visited? Nobody knows. There are various classes of self-avoiding walks that are restricted in certain ways, which can be counted; for example, it's not hard to count walks that only go to the north or east, or even walks that only go to the north, east, or west. (Such a walk has the following structure: go north. Then go east or west a bunch of times. Then go north. Then go east or west a bunch of times. And so on.) It wouldn't even be that hard to determine the average number of times that a NEW-walk chosen uniformly at random from all those of length n takes a northbound step; if I remember correctly it's on the order of n1/2. But counting all self-avoiding walks? Nobody knows. It's known that if f(n) is the number of self-avoiding walks of length n, then f(n)1/n has a limit as n goes to infinity; this limit is the self-avoiding walk connective constant in two dimensions, which is somewhere between 2.62 and 2.68.
It's not hard to show it must be between 2.41 and 3, if it exists:
But the walks counted by g(n) are all self-avoiding, and self-avoiding walks are a subset of those counted by h(n). So g(n) ≤ f(n) ≤ h(n), which is enough. I believe that at least some of the results which tighten up the connective constant were derived in the same way, by finding classes of walks which contain or are contained by the self-avoiding class.
(The thoughts on self-avoiding random walks are basically coming from a talk on prudent self-avoiding walks by Mireille Bousquet-Melou that I heard a couple weeks ago; I was hoping her slides would be online, since there were some nice pictures, but they aren't.)
The LEGO®-tower-counting problem is similar. In the case where the tower goes straight up, we don't have to worry about the different blocks colliding with each other, so it's something like the "easier" problems above. But if we allow more than one block on each level, we have to take into account the "physics" of the problem, namely that only one block can be in any given piece of space. The LEGO® problem is actually more closely related to counting polyominoes; if you look through the list of Bousquet-Melou's papers, you'll see she's done a lot of work on that sort of problem as well.
The question: what is the number of ways to make a tower of height six out of two-by-four LEGO® blocks? There are 102,981,504 ways; this is pretty straightforward, once you take the relevant symmetries into account. But apparently this has been confused with the problem of how many ways there are to make any sort of configuration out of six blocks; Eilers and his collaborator Mikkel Abrahamsen claim this number is 915,103,765, by what sounds like a brute-force program. The most common height for such a tower is 4; almost half the towers have this height.
How are the heights of towers containing n blocks distributed? I don't have much faith that this problem could be answered; it reminds me of the problem of counting self-avoiding walks. Let's say you live on the integer lattice, and you go for a walk, going north, south, east, or west at each step. There are clearly 4n walks of length n. But in how many of these walks do you never come back to a point you've previously visited? Nobody knows. There are various classes of self-avoiding walks that are restricted in certain ways, which can be counted; for example, it's not hard to count walks that only go to the north or east, or even walks that only go to the north, east, or west. (Such a walk has the following structure: go north. Then go east or west a bunch of times. Then go north. Then go east or west a bunch of times. And so on.) It wouldn't even be that hard to determine the average number of times that a NEW-walk chosen uniformly at random from all those of length n takes a northbound step; if I remember correctly it's on the order of n1/2. But counting all self-avoiding walks? Nobody knows. It's known that if f(n) is the number of self-avoiding walks of length n, then f(n)1/n has a limit as n goes to infinity; this limit is the self-avoiding walk connective constant in two dimensions, which is somewhere between 2.62 and 2.68.
It's not hard to show it must be between 2.41 and 3, if it exists:
- Let g(n) be the number of self-avoiding walks of length n which only make steps to the north, east, or west. Then g(n)1/n approaches 1+√2 as n goes to infinity. This can be shown by encoding the walks as words in the three-letter alphabet {N, E, W} and counting the number of words which don't include the subwords EW or WE;
- Let h(n) be the number of walks of length n which don't include the sequences NS, SN, EW, or WE. The number of these is 4 × 3n-1; the first step can be anything you like, and each following step can be anything except the opposite of the previous step. So h(n)1/n approaches 3.
But the walks counted by g(n) are all self-avoiding, and self-avoiding walks are a subset of those counted by h(n). So g(n) ≤ f(n) ≤ h(n), which is enough. I believe that at least some of the results which tighten up the connective constant were derived in the same way, by finding classes of walks which contain or are contained by the self-avoiding class.
(The thoughts on self-avoiding random walks are basically coming from a talk on prudent self-avoiding walks by Mireille Bousquet-Melou that I heard a couple weeks ago; I was hoping her slides would be online, since there were some nice pictures, but they aren't.)
The LEGO®-tower-counting problem is similar. In the case where the tower goes straight up, we don't have to worry about the different blocks colliding with each other, so it's something like the "easier" problems above. But if we allow more than one block on each level, we have to take into account the "physics" of the problem, namely that only one block can be in any given piece of space. The LEGO® problem is actually more closely related to counting polyominoes; if you look through the list of Bousquet-Melou's papers, you'll see she's done a lot of work on that sort of problem as well.
Subscribe to:
Posts (Atom)
