Simpson's Paradox is a wonderful little statistical phenomenon which is counterintuitive to most people. Here is a simple, concrete example.
Consider two cancer drugs A and B. We do a study, Study #1, where we give some cancer patients drug A and some people drug B. Let's say we give 11 people drug A and 7 people drug B. Of the 11 people given drug A, 5 die and 6 survive. Of the 7 people given drug, B 3 die and 4 survive. So it seems that drug B is better than drug A since 4/7 is greater than 6/11.
Just to be sure we do another study, Study #2. Again we give some patients drug A and some patients drug B. Of those given drug A, 6 die and 3 survive. Of those given drug B, 9 die and 5 survive. Again it seems like drug B is better than drug A since 5/14 is larger than 3/9.
But wait! What happens if we look at all the data together? Now, of those given drug A, 11 died in total and 9 survived. For drug B, 12 died in total and 9 survived. So when we look at the combined data drug, A is better than drug B.
This paradox is known as Simpson's paradox. While one might think that this is the sort of thing that only comes up with cleverly picked numbers in the real world, there are actually many examples of actual data that exhibits this behavior.
Aside from being extremely counterintuitive, this result also plays havoc with our naive notions of what constitutes confirmation of a hypothesis. In particular, the fact that we can have two separate pieces of evidence which alone constitute confirming evidence but together constitute disconfirming evidence is jarring. Results like this one undermine naive Bayesian views of how science should function.
Showing posts with label Math. Show all posts
Showing posts with label Math. Show all posts
Thursday, September 11, 2008
Tuesday, August 5, 2008
Aleph-not is a large cardinal
The math level in this post may be a bit higher than the usual level in my math entries so feel free to skip it. I just have to share this because I found it absolutely amazing.
ℵ0 is a large cardinal. We just declare it to exist with an axiom that we all agree on. For all the common definitions of large cardinals ℵ0 satisfies the requirements. To a lot of people who have studied model theory and set theory this will likely seem trivial, but this was pretty mind-blowing to me.
This information is courtesy of Harry Altman.
ℵ0 is a large cardinal. We just declare it to exist with an axiom that we all agree on. For all the common definitions of large cardinals ℵ0 satisfies the requirements. To a lot of people who have studied model theory and set theory this will likely seem trivial, but this was pretty mind-blowing to me.
This information is courtesy of Harry Altman.
Thursday, July 24, 2008
Mathematics education
In the United States there are long-running "math wars" over how to educate children in mathematics. CNN had a recent article about the latest skirmishes in these math wars. Now, I could spend an entire entry ranting about how people abuse the word "war" and I intend to do that sometime in the future. I could also write an entry about how the CNN article has no real news content and is hard to see as newsworthy. Instead I'm going to focus on the issues that the article raises.
The article focuses on how in certain schools teachers are deliberately not teaching the children how to do long-division and multiplication. However, frustrated parents are teaching their children how to do it, rather than focus on the "conceptual" understanding.
As someone who has tutored kids in math and has worked as a counselor at a summer program which teaches number theory to high school students, I have to side with the parents.
First, long-division is conceptual. It isn't that hard to understand what is going in the algorithm. And if a teacher cannot explain conceptually why long-division works they are not a very good teacher.
Second, conceptual in this sort of context often is a disguise for ad hoc methods that sometimes are shorter but in general will not be efficient. For example, to quote from the article "When a parent is asked to multiply 88 by 5, we'll do it with pen and paper, multiplying 8 by 5 and carrying over the 4, etc. But a child today might reason that 5 is half of 10, and 88 times 10 is 880, so 88 times 5 is half of that, 440 -- poof, no pen, no paper." This works fine, but what if I asked you to multiply two 3 digit numbers? Or 4 digit numbers? Can you easily use such methods then? If you cannot do that, then you do not have a true conceptual understanding of the content in question.
Third, there's an issue of causation v. correlation. People who are good at math use such short-cuts all the time when they are available. But they do that because they are good at math. That does not mean knowing how to use those tricks will make you good at math.
Fourth, many more advanced ideas depend on long-division and multiplication. For example, what if you want to understand how to multiple or divide in another base? Or what if you want to divide polynomials, or to do arithmetic in more abstract rings like Z7[x]? The "conceptual" understanding will not help much there. But having a good understanding of how to do division and multiplication the "old-fashioned way" and understanding why they work will help a lot.
There's also one problem that bothers me which has little to do directly with the math at hand: Some parents in the article report that they feel like they are being "rebels" for teaching their children. There is something seriously wrong when parents providing additional education to children are made to feel unwanted or to feel like they are doing something wrong. We have serious problems with parents not being involved in their kids' education. We don't want to discourage the good parents who are willing to help out simply over pedagogical disagreements.
The article focuses on how in certain schools teachers are deliberately not teaching the children how to do long-division and multiplication. However, frustrated parents are teaching their children how to do it, rather than focus on the "conceptual" understanding.
As someone who has tutored kids in math and has worked as a counselor at a summer program which teaches number theory to high school students, I have to side with the parents.
First, long-division is conceptual. It isn't that hard to understand what is going in the algorithm. And if a teacher cannot explain conceptually why long-division works they are not a very good teacher.
Second, conceptual in this sort of context often is a disguise for ad hoc methods that sometimes are shorter but in general will not be efficient. For example, to quote from the article "When a parent is asked to multiply 88 by 5, we'll do it with pen and paper, multiplying 8 by 5 and carrying over the 4, etc. But a child today might reason that 5 is half of 10, and 88 times 10 is 880, so 88 times 5 is half of that, 440 -- poof, no pen, no paper." This works fine, but what if I asked you to multiply two 3 digit numbers? Or 4 digit numbers? Can you easily use such methods then? If you cannot do that, then you do not have a true conceptual understanding of the content in question.
Third, there's an issue of causation v. correlation. People who are good at math use such short-cuts all the time when they are available. But they do that because they are good at math. That does not mean knowing how to use those tricks will make you good at math.
Fourth, many more advanced ideas depend on long-division and multiplication. For example, what if you want to understand how to multiple or divide in another base? Or what if you want to divide polynomials, or to do arithmetic in more abstract rings like Z7[x]? The "conceptual" understanding will not help much there. But having a good understanding of how to do division and multiplication the "old-fashioned way" and understanding why they work will help a lot.
There's also one problem that bothers me which has little to do directly with the math at hand: Some parents in the article report that they feel like they are being "rebels" for teaching their children. There is something seriously wrong when parents providing additional education to children are made to feel unwanted or to feel like they are doing something wrong. We have serious problems with parents not being involved in their kids' education. We don't want to discourage the good parents who are willing to help out simply over pedagogical disagreements.
Tuesday, July 8, 2008
Prisoners, Information Transfer, and the Axiom of Choice
The following entry is courtesy a variety of people. I believe that I heard the initial version of this riddle from my twin. The follow-up to infinitely many people is due to Erick Knight. Note that since I’ve noticed that I’m not very good at remembering to post follow-ups to puzzles I post I am just going to include the solutions in this post.
Initial riddle: Suppose there are a hundred prisoners. They are in a room and told that they will be all lined up so that the first one can see the next ninety-nine, the second one can see the next ninety-eight but not the first person, the third one can see the next ninety-seven but not the first or second, and so on. Each one will have placed on his head a black or white hat. The first one gets to shout out “black” or “white” so that everyone in the line hears. Then the second one shouts out “black” or “white”. If everyone shouts out the same color as the hat that that person is wearing then they will all get to go free. What is the best strategy for the prisoners? Remember, they are able to communicate before hand but once in can only say “black” or “white”. And no using stupid tricks like delaying when they say it to communicate more information.
Answer:
The first person counts the parity of all hats they see, with black hats as 1 and white hats as 0. If the result is odd they black and if the result is even they say white. Each person after that one will then know what their hat is, since it must preserve parody with all the hats before and after them. Thus, they will get 99 hats correct and will have a ½ chance getting the first hat correct.
Exercise: generalize this to n different hat colors.
Now the part due to Erick Knight:
Suppose we have the exact same problem as before, but there are countably infinite prisoners each wearing a black or white hat (so there’s a first prisoner, a second prisoner, a third prisoner and so on). How can they assure that they at most finitely many people will not say the correct hat color. You may assume that the prisoners are able to see everyone in front of them.
Ok, the solution to this is unbelievably cool. Again, denote a black hat by 1 and a white hat by 0. So every possible string consists of some strings of 1s and 0s. Now, define an equivalence class on strings as follows: two strings are equivalent if they agree for all sufficiently far off digits. So for example, 010010000000000000... Is equivalent to 000000000… Now, from each such class pick a representative string, and remember it. When the prisoners are lined up each prisoner can see the string in front of him, and can recognize that as being in some equivalence class. So all the prisoner does is consults which representative string from that class they choose, and picks whichever 0 or 1 corresponds to his current position. Using this method, at most finitely many prisoners will get it wrong, because otherwise the string in question would not be equivalent and would thus not be a representative of that equivalence class.
Ok, isn’t that bizarre? It doesn’t even require any actual communication among the prisoners except at the start.
There are a number of objections to this solution: I will note three of them and discuss one of the more interesting ones in more detail:
Objection 1: People cannot look at infinite strings of data in finite time.
Objection 2: People cannot store all the representative strings (exercise so that the set of representative strings is uncountable).
These two objections are uninteresting, because even if one accepts them it isn’t at all clear why beings able to do these things should be able to get away with this. At best it is non-intuitive.
Objection 3: This is the interesting one: Who said I can pick representatives? In fact, in order to do so I need to use the axiom of choice, which says essentially that if I have a collection of disjoint non-empty sets I can pick one representative from each. This seems intuitive but the axiom can lead to strange results and some mathematicians do not accept the axiom. This puzzle gives a starting groundwork for appreciating that the axiom of choice although intuitive is strange. I hope to discuss the axiom of choice in more detail in a later blog entry.
Initial riddle: Suppose there are a hundred prisoners. They are in a room and told that they will be all lined up so that the first one can see the next ninety-nine, the second one can see the next ninety-eight but not the first person, the third one can see the next ninety-seven but not the first or second, and so on. Each one will have placed on his head a black or white hat. The first one gets to shout out “black” or “white” so that everyone in the line hears. Then the second one shouts out “black” or “white”. If everyone shouts out the same color as the hat that that person is wearing then they will all get to go free. What is the best strategy for the prisoners? Remember, they are able to communicate before hand but once in can only say “black” or “white”. And no using stupid tricks like delaying when they say it to communicate more information.
Answer:
The first person counts the parity of all hats they see, with black hats as 1 and white hats as 0. If the result is odd they black and if the result is even they say white. Each person after that one will then know what their hat is, since it must preserve parody with all the hats before and after them. Thus, they will get 99 hats correct and will have a ½ chance getting the first hat correct.
Exercise: generalize this to n different hat colors.
Now the part due to Erick Knight:
Suppose we have the exact same problem as before, but there are countably infinite prisoners each wearing a black or white hat (so there’s a first prisoner, a second prisoner, a third prisoner and so on). How can they assure that they at most finitely many people will not say the correct hat color. You may assume that the prisoners are able to see everyone in front of them.
Ok, the solution to this is unbelievably cool. Again, denote a black hat by 1 and a white hat by 0. So every possible string consists of some strings of 1s and 0s. Now, define an equivalence class on strings as follows: two strings are equivalent if they agree for all sufficiently far off digits. So for example, 010010000000000000... Is equivalent to 000000000… Now, from each such class pick a representative string, and remember it. When the prisoners are lined up each prisoner can see the string in front of him, and can recognize that as being in some equivalence class. So all the prisoner does is consults which representative string from that class they choose, and picks whichever 0 or 1 corresponds to his current position. Using this method, at most finitely many prisoners will get it wrong, because otherwise the string in question would not be equivalent and would thus not be a representative of that equivalence class.
Ok, isn’t that bizarre? It doesn’t even require any actual communication among the prisoners except at the start.
There are a number of objections to this solution: I will note three of them and discuss one of the more interesting ones in more detail:
Objection 1: People cannot look at infinite strings of data in finite time.
Objection 2: People cannot store all the representative strings (exercise so that the set of representative strings is uncountable).
These two objections are uninteresting, because even if one accepts them it isn’t at all clear why beings able to do these things should be able to get away with this. At best it is non-intuitive.
Objection 3: This is the interesting one: Who said I can pick representatives? In fact, in order to do so I need to use the axiom of choice, which says essentially that if I have a collection of disjoint non-empty sets I can pick one representative from each. This seems intuitive but the axiom can lead to strange results and some mathematicians do not accept the axiom. This puzzle gives a starting groundwork for appreciating that the axiom of choice although intuitive is strange. I hope to discuss the axiom of choice in more detail in a later blog entry.
Friday, June 6, 2008
A few weighing puzzles
Here are three related puzzles. I'll post answers next week and discuss how it is related to certain notions in computer science.
1) Suppose I have ten stacks of ten gold coins each. Each coin weighs 1 ounce, but there is one set of counterfeit coins. The coins in that stack weigh only .5 ounces. You have a scale. What is the minimum number of weighings to determine which stack is counterfeit?
2) Suppose instead of a scale, you only have a balance and you don't know how light the counterfeit coins are but they are too light. Then how many weighings can you do it in? What if we instead have n stacks with one counterfeit? How many weighings does it take? Can you prove that you can't do it in fewer?
3) This last generalization is due to Elissa. Suppose we again have n stacks with one set counterfeit but instead of a balance we have a k-balance which compares k different objects simultaneously and returns their mass order. So for example, if on a 4-balance I had two two ounce objects (object a and object b respectively), one ounce object (c) and one three ounce object (d), I'd be told that
c < a = b < d. The normal balance is thus a 2-balance. In general for a k-balance with n stacks what is the minimum number of weighings?
Important PointAfter I put up this issue Etienne pointed a issue I had not anticipated. In the original phrasing of 2 and 3 there was only a single counterfeit coin and one no longer had stacks. In my phrasing above I assumed that this wouldn't make a difference for the general solution. It turns out that in fact it does. So instead for 2 and 3 assume that one just has n coins with 1 counterfeit rather than n stacks. Etienne has not yet worked out the general solution with stacks nor have I, so bonus points if you can do that.
Feel free to either post or email me solutions.
1) Suppose I have ten stacks of ten gold coins each. Each coin weighs 1 ounce, but there is one set of counterfeit coins. The coins in that stack weigh only .5 ounces. You have a scale. What is the minimum number of weighings to determine which stack is counterfeit?
2) Suppose instead of a scale, you only have a balance and you don't know how light the counterfeit coins are but they are too light. Then how many weighings can you do it in? What if we instead have n stacks with one counterfeit? How many weighings does it take? Can you prove that you can't do it in fewer?
3) This last generalization is due to Elissa. Suppose we again have n stacks with one set counterfeit but instead of a balance we have a k-balance which compares k different objects simultaneously and returns their mass order. So for example, if on a 4-balance I had two two ounce objects (object a and object b respectively), one ounce object (c) and one three ounce object (d), I'd be told that
c < a = b < d. The normal balance is thus a 2-balance. In general for a k-balance with n stacks what is the minimum number of weighings?
Important PointAfter I put up this issue Etienne pointed a issue I had not anticipated. In the original phrasing of 2 and 3 there was only a single counterfeit coin and one no longer had stacks. In my phrasing above I assumed that this wouldn't make a difference for the general solution. It turns out that in fact it does. So instead for 2 and 3 assume that one just has n coins with 1 counterfeit rather than n stacks. Etienne has not yet worked out the general solution with stacks nor have I, so bonus points if you can do that.
Feel free to either post or email me solutions.
Saturday, April 12, 2008
This is unsolved. No really,
I recently encountered an amazingly simple unsolved problem known as the Frankl
Conjecture. Suppose I have a non-empty finite family of finite sets closed under union, is there necessarily an element that is an element in at least half the sets in the family?
For the people who haven't studied set theory in a while here's a quick refresher (everyone else can skip the next three paragraphs). A set is a collection of objects where we do not care about order and things are either in the set or not. So for example {1,2,3} is a set. If something is in a
set we say it is an element of that set. So for example 2 is an element of {1,2,3} but 5 is not an element. Sets are defined just by what elements they have, so for example the set {2,3,5} is the same as the set defined by containing any prime less than 6. Sets also don't just need to contain
integers. You could think about the set of US Presidents or the set of years in which the Yankee's won the pennant. (Some people may note that this actually leads to problems, but I may post on that later).
Now, the union of two sets is the set formed by making the set that contains everything and is generally denoted with a big U. So for example {1,2} U {2,7} = {1,2,7}.
Now the problem is again suppose I have a non-empty finite family of finite sets closed under union, is there necessarily an element that is an element in at least half the sets in the family? First let's think about what families might work. Well, how about {1},{2},{3},{1,2},{2,3},{1,3},{1,2,3} . This is closed under unions (if you are fuzzy on sets this would be good to check). And in fact the conjecture is true, in fact every element appears in exactly half the sets.
Now for everyone: It isn't hard to see that if there are any singletons in the family, that is sets of of the form {a} then one can take your element to be a. And a similar results holds if one has a pair. If there is a set of the form {a,b} then one can show that either a or b appears in at least half the sets. However, this actually breaks down for triplets. There are families closed under union that contain a triplet {a,b,c} and not one of a b or c appears in half the sets.
This problem is fantastically simple to state. It is hard to explain to a non-math person how simple this problem sounds. The fact that it is unsolved is striking. This is one of the things that appeals to me about math. We have problems that can be simply explained to laypeople and yet those problems are unsolved.
Subscribe to:
Posts (Atom)
