Archive for July 2010

## Milk

I am a milk person. I can easily drink half a gallon of milk a day. The problem with half a gallon of milk a day is that it is about half of my target calorie intake. That is why I switched to the reduced-fat milk. It didn’t taste good, but I was very proud of myself. That is, I was proud for about a year until I finally decided to read the labels. One serving of whole milk is 150 calories, while one serving of reduced-fat milk is 130 calories. All this year-long suffering saved me an insignificant 13%. Not to mention that the amount of sugar is the same.

I decided to look into this more closely. I went to my nearest super-market and checked the milk. The low-fat milk is 110 calories per serving, while non-fat milk is 90 calories.

If I had just reduced my milk intake by half, I would have consumed fewer calories than by replacing whole milk with non-fat milk, but I would have enjoyed it so much more. The lesson? Read the labels and do the math!

## The Sexual Side of Life

### by John H. Conway as told to Tanya Khovanova

Forty years ago, it took about 18 months for us to find the rules that eventually became the Game of Life. We thought in terms of birth rules and death rules. Maybe one day’s death rule would be a bit too strong compared to its birth rule. So the next day at coffee time we’d either try to weaken the death rule or strengthen the birth rule, but either way, only by a tiny bit. They had to be extremely well-balanced; if the death rule was even slightly too strong then almost every configuration would die off. And conversely, if the birth rule was even a little bit stronger than the death rule, almost every configuration would grow explosively.

What’s wrong with that, you might ask. Well, if the “radius” grows by 1 unit per generation, then after 9 or 10 moves, it’s off the (19 by 19) Go board. We can probably find more Go boards, of course, but after another 20 or so moves it will outflow the coffee table and then it is awfully hard to keep track. We wanted to be able to study configurations for much longer than that, which meant that we had to disallow rules that might lead to linear growth. Of course, we weren’t interested in rules that usually led to collapse.

Who were “we”? Well, I was the chief culprit and had an aim in mind — to find a simple set of rules that would lead to a system able to simulate a universal computer. Von Neumann had already shown that this was possible, but his system had 29 states and a very complicated set of rules. The rest of “us” were mostly graduate students who had no higher aim than amusing themselves. Every now and then some rather older colleagues or visitors took an interest.

So my plan was, first, to find a set of rules that almost always prevented explosive growth and catastrophic collapse. Second, I wanted to study it long enough to learn how it could be “programmed”. I hoped to find a system whose rules were much simpler than Von Neumann’s, preferably with only two states (on and off) per cell, rather than his 29.

I’ll just describe the last few rule fiddles. We had in fact given up on finding a two-state system, in favor of one with three states: 0, A, B. State 0 represented an empty cell, and it was natural to think of A and B as two sexes, but we only found their proper names when Martin Huxley walked by and said, “Actresses and bishops!”

Perhaps I should explain this. There is a British anecdote that starts like this:

“The actress sat on the left side of the bed, and removed her stockings. The bishop, on the right side of the bed, removed his gaiters. Then she unbuttoned her blouse and he took off his shirt…”

You are supposed to be getting excited, but it all ends quite tamely, because it turns out that the bishop was in his palace, while the actress was in her bedsit near the theater. There are lots of stories in England about the actress and the bishop, and if a person says something that has a salacious double meaning, it’s standard to respond “as the actress said to the bishop,” or “as the bishop said to the actress”.

Okay, back to Life! To inhibit explosive growth, we decided to imitate biology by letting death be a consequence of either overcrowding or isolation. The population would only grow if the number of neighbors was neither too large nor too small. Rather surprisingly, this turned out to mean that children had to have three or more parents. Let’s see why. If two parents could give birth, then in the figure below, the parents A and B, who are on the border of the population, would produce children A’ and B’ at the next time step, followed by grandchildren A” and B” and so on, thus giving us linear growth!

So we moved to threesomes. Children were born to three parents, made up of both sexes. Moreover, the sex of the child was determined by the sex of its parents — two bishops and one actress would give birth to a little actress, while two actresses and one bishop would produce a tiny bishop. This was “the weaker-sex birth rule,” and it was accompanied by “the sexual frustration death rule,” which made death the punishment for not touching somebody of the opposite sex!

However, the weaker-sex birth rule lived up to its name, by being weaker than the death rule. Remember we weren’t interested in rules that led to disappointingly swift collapses, as the actress said to the bishop. Therefore, we strengthened the birth rule by allowing same-sex conception, but again by applying the weaker-sex rule — so that three actresses would produce a bishop or three bishops an actress. However this strengthened the birth rule too much, causing us to apply the death penalty more often.

We decided to apply the death penalty to those who weren’t touching at least two other people, whatever their sex. At first sight it was not obvious that this was stronger than the sexual frustration rule, but in fact it was, because the weaker-sex rule ensured that the sexes were fairly evenly mixed, so if you were touching at least two other people, there was a good chance that one of them would be of the opposite sex.

According to our new set of rules, the sex of parents played no role except to determine the sex of the children, so we abolished sex. After all, according to the bishop, Life without sex is much cleaner.

This is now called the Game of Life and these rules, at last, turned out to be clean and well-balanced.

## Women, Science and The Right Tail of a Bell Curve

### by Rebecca Frankel

The article Daring to Discuss Women in Science by John Tierney in the New York Times on June 7, 2010 purports to present a dispassionate scientific defense of Larry Summers’s claims, in particular by reviewing and expanding his argument that observed differences in the length of the extreme right tail of the bell curves of men’s and women’s test scores indicate real differences in their innate ability. But in fact any argument like this has to acknowledge a serious difficulty: it is problematic to assume without comment that the abilities of a group can be inferred from the tail of a bell curve. We are so used to invoking bell curves to talk about group abilities, we don’t notice that such arguments usually use only the mean of the curve. Using the tail is a totally different story.

Think about it: it is reasonable to question whether a single data point — the test score of an individual person — is a true indication of his/her ability. It might not be. Maybe a single test score represents a dunce with hyper-overachieving parents who push him to study all the time. So does that single false reading destroy the validity of the curve? No of course not: because some other kid might have been a super-genius who was drunk last night and can barely keep his eyes open during the test. One is testing above his “true ability” and the other is testing below his “true ability,” and the effect cancels out. Thus the means of curves are a good way to measure the ability of large groups, because all the random false readings average out.

But tails are not. On the tail this “canceling out” effect doesn’t work. Look at the extreme right tail. The relatively slow but hyper-motivated kids are not canceled out by the hoard of far-above-the-mean super geniuses who had drunken revels the night before. There just aren’t that many super-geniuses and they just don’t party that much.

Or let’s look at it another way: imagine that you had a large group which you divided in half totally at random. At this point their bell curve of test scores looks exactly the same. Lets call one of the group “boys” and the other group “girls”. But they are two utterly randomly selected groups. Now lets inject the “boys” with a chemical that gives the ones who are very good already a burning desire to dominate any contest they enter into. And let us inject the “girls” with a chemical that makes the ones who are already good nonetheless unwilling to make anyone feel bad by making themselves look too good. What will happen to the two bell curves? Of course the upper tail of the “boys’” curve will stretch out, while the “girls’” tail will shrink in. It will look like the “boys” whipped the “girls” on the right tail of ability hands down, no contest. But the tail has nothing to do with ability. Remember they started out with the same distribution of abilities, before they got their injections. It is only the effect of the chemicals on motivation that makes it look like the “boys” beat the “girls” at the tail.

So, when you see different tails, you can’t automatically conclude that this is caused by difference in underlying innate ability. It is possible that other factors are at play — especially since if we were looking to identify these hypothetical chemicals we might find obvious candidates like “testosterone” and “estrogen”.

The possibility of alternative explanations for these findings calls into question Tierney and Summers’ claims to superior dispassionate scientific objectivity. Moving from the mean to the tail of a bell curve makes systematic effects on averages irrelevant, true, but it is instead susceptible to systematic effects on deviations, which are irrelevant at the mean. An argument that uses this trick to dodge gender differences in averages cannot claim the mantle of scientific responsibility without accounting for gender differences in deviations. I am deeply disappointed that Tierney and Summers did not accompany their assertions with a suitable reminder of this fact.

## Hats and Rooms. Take II

I recently published a puzzle about wizards, hats of different colors and rooms. Unfortunately, I was too succinct in my description and didn’t explicitly mention several assumptions. Although such assumptions are usual in this type of puzzle, I realize now, from your responses, that I should have listed them and I apologize.

The Sultan decided to test the wisdom of his wizards. He collected them together and gave them a task. Tomorrow at noon he will put hats of different colors on each of the wizard’s heads.
The wizards have a list of the available colors. There are enough hats of each color for every wizard. The wizards also have a list of rooms. There are enough rooms to assign a different room for every color.
Tomorrow as the Sultan puts hats on the wizards, they will be able to see the colors of the hats of the other wizards, but not the color of their own. Without communicating with each other, each wizard has to choose a room. The challenge comes when two wizards have the same hat color, for they must choose the same room. On the other hand, if they have different hat colors, they must choose different rooms. Wizards have one day to decide on their strategy. If they do not all complete their task, then all of their heads will be chopped off. What strategy would you suggest for the wizards?

In his comment on the first blog about this problem, JBL beautifully described the intended solution for the finite number of wizards, and any potentially-infinite number of colors. I do not want to repeat his full solution here. I would rather describe his solution for two wizards and two colors.

Suppose the colors are red and blue. The wizards will designate one of the rooms as red and another as blue. As soon as each wizard sees the other wizard’s hat color, he chooses the room of the color he sees. The beauty of this solution is that if the colors of hats are different, the color of the rooms will not match the color of the corresponding hats: the blue-hatted wizard will go to the red room and vice versa. But the Sultan’s condition would still be fulfilled.

JBL’s solution doesn’t work if the number of wizards is infinite. I know the solution in that case, but I do not like it because it gives more power to the axiom of choice than I am comfortable with. If you are interested, you can extrapolate the solution from my essay on Countable Wise Men with Hats which offers a similar solution to a slightly different problem.

## The First Western IMO

The International Math Olympiad started in Eastern Europe in 1959. Romania was the first host country. The Olympiad grew and only in 1976 did it move outside the Eastern bloc. The competition was held in Austria.

I was on the Soviet team in 1975 and 1976, so I was able to compare competitions held in Eastern vs. Western countries. Of course, the Austrian Olympiad was much better supported financially, but today I want to write about the differences in how our team was prepped.

Before our travel to Austria the Soviet team members were gathered in a room with strangers in suits for a chat. I assumed that we were talking to the KGB. They gave us a series of instructions. For example, they told us not to leave the campus during the competition, to always walk in groups, and to avoid talking to kids from countries that are enemies of the USSR. They warned us that they would be watching, and I was scared to death.

Now that I am older and wiser, I understand that their goal was to frighten us. Our team traveled with adult supervisors, who were trusted by the KGB. But for several days during the grading period of the competition, our supervisors were not allowed to see us. So the KGB wanted us to be too afraid to be very adventurous when we were left on our own.

In addition, the KGB had a Jewish problem. In general, Jews were not allowed to go abroad. I had many Jewish friends who qualified for the pre-IMO math camp where the team was chosen, but who were not able to get on the IMO because of delays with their travel documents. Some local bureaucrats were eager to impress the KGB and therefore held up visas for Jewish students, preventing them from being on the team. But the team selection process itself wasn’t yet corrupt in 1976. So every year despite the efforts of the system, some young Jewish mathematicians would end up on the team.

Before 1976, the Olympiad was in the Eastern bloc, so the KGB wasn’t quite so concerned about having Jewish members on the team. But Austria was not only a Western country, it was also the transition point for Jewish refugees from the Soviet Union. The speed with which the IMO moved their competition to a Western country was much faster than the Soviet bureaucratic machine could build a mechanism for completely preventing Jews from joining the team.

One very strong candidate, Yura Pass, didn’t get his documents, but two other Jewish boys made it on to the team that was going to Austria. They were joking that they would be the only Soviet Jews who would go to Austria and actually come back. They did come back, only to go forward later: both are now math professors working in the US.

Because we had Jewish members on our team, it gave the KGB a special extra reason to scare us. But the biggest pressure was to win. We were told that 1976 was the most important year for the Soviet team to be the best. We were told that capitalist countries spread rumors that the judges in Eastern bloc countries favored the Soviet team and that the relative success of the Soviet team throughout the years had not been fully deserved. Now that the competition was in Austria, the suits told us, the enemies of the USSR were hoping for the downfall of the Soviet team. Our task was to prove once and for all that the Soviet students were the best at math, and that the rumors were unfounded. We had to win the team competition not only to prove ourselves, but also to clear the name of the Soviet team for all the previous years.

We did have a very strong team. The USSR came out first with 250 points, followed by the UK with 214 points and the USA with 188 points. Out of nine gold medals, we took four.

We could have gotten one more gold medal if Yura Pass had been allowed on the team. Yura was crushed by the machine’s treatment of Jews and soon afterwards quit mathematics.

## How to Live Longer

I just received a mass email on how to live longer and it made these points:

Tip 1. Delay your retirement. Studies show that people who retire at 65 live longer than people who retire at 60.

Tip 2. Sex makes you younger. Studies show that older people who have sex twice a week look ten years younger than their peers who do not have sex at all.

People who draw conclusions from such studies usually do not understand statistics. Correlation doesn’t mean causality. Let me use the above-mentioned studies to reach different conclusions by reversing the causality assumption of the unknown writer of the mass email. You can compare results and make your own decisions.

Case 1. Studies show that people who retire at 65 live longer than people who retire at 60. Reversed causality: People who live longer are healthier, so they are able to keep working and to retire later in life.

Case 2. Studies show that older people who have sex twice a week look ten years younger than their peers who do not have sex at all. Reversed causality: Older people who look ten years younger than their peers can get laid easier, so they have sex more often.

## Hats and Rooms

Sergei just came back from MOP — Mathematical Olympiad Summer Program, where he was a grader. The first question I asked him was, “What was your favorite math problem there?” Here it is:

There are wisemen, hats and rooms. Hats are of different color and there are enough hats of each color for every wisemen. There are enough rooms, so that you can assign a different room for every color. At some moment in time the sultan puts hats on the wisemen’s heads, so as usual they see all other hats, but do not see their own hat color. At the same time, each wiseman has to choose a room to go to. If two wisemen have the same hat color, they should go to the same room. If they have different hat colors, they should go to different rooms. What strategy should the wisemen decide upon before this event takes place?

Oh, I forgot to mention the most interesting part of this problem is that you shouldn’t assume that the number of wisemen or hats or rooms is finite. You should just assume that they have the power of choice.

## Shannon Entropy Rescues the Tuesday Child

My son Alexey Radul and I were discussing the Tuesday’s child puzzle:

You run into an old friend. He has two children, but you do not know their genders. He says, “I have a son born on a Tuesday.” What is the probability that his second child is also a son?

Here is a letter he wrote me on the subject. I liked it because unlike many other discussions, Alexey not only asserts that different interpretations of the conditions in the puzzle form different mathematical problems, but also measures how different they are.

If you assume that boys and girls are symmetric, and that days of the week are symmetric (and if you have no information to the contrary, assuming anything else would be sheer presumption on your part), then you can be in one of at least two states.

1) You say that “at least one son born on a Tuesday” is all the information you have, in which case your distribution including this information is uniform over consistent cases, in which case your answer is 13/27 boy and your information entropy is

− ∑27 (1/27) log(1/27) = − log(1/27) = 3.2958.

2) You say that the information you have is “The guy might have said any true thing of the form ‘I have at least one {boy/girl} born on a {day of the week}’, and he said ‘boy’, ‘Tuesday’.” This is a different mathematical problem with a different solution. The solution: By a symmetry argument (see below [*]) we must assign uniform probability of him making any true statement in any particular situation. Then we proceed by Bayes’ Rule: the statement we heard is d, and for each possible collection of children h, the posterior is given by p(h|d) = p(h)p(d|h)/p(d). Here, p(h) = 1/142 = 1/196; p(d) = 1/14; and p(d|h) is either 1 or 1/2 according as whether his other child is or is not another boy also born on a Tuesday (or p(d|h) = 0 if neither child is a boy born on a Tuesday). There are 1 and 26 of these situations, respectively. The answer they lead to is of course 1/2; but the entropy is

− ∑ p log p = − 1/14 log 1/14 − 26/28 log 1/28 = 3.2827

Therefore that assumed additional structure really is more information, which is only present at best implicitly in the original problem. How much more information? The difference in entropies is 3.2958 - 3.2827 = 0.0131 nats (a nat is to a bit what the natural log is to the binary log). How much information is that? Well, the best I can do is to reproduce an argument of E.T. Jaynes’, which may or may not really apply to this situation. Suppose you have some repeatable experiment with some discrete set of possible outcomes, and suppose you assign probabilities to those outcomes. Then the number of ways those probabilities can be realized as frequencies counted over N trials is proportional to eNH, where H is the entropy of the distribution in nats. Which means that the ratio by which one distribution is easier to realize is approximately eN(H1-H2). In the case of N = 1000 and H1 - H2 = 0.0131, that’s circa 5×105. For each way to get a 1000-trial experiment to agree with version 2, there are half a million ways to get a 1000-trial experiment to agree with version 1. So that’s a nontrivial assumption.

[*] The symmetry argument: We are faced with the following probability assignment problem

Suppose our subject’s first child is a boy born on a Tuesday, and his second child is a girl born on a Friday. What probability must we assign to him asserting that he has at least one boy born on a Tuesday?

Good question. Let’s transform our coordinates: Let Tuesday’ be Friday, Friday’ be Tuesday, boy’ be girl, girl’ be boy, first’ be second and second’ be first. Then our problem becomes

Suppose our subject’s second’ child is a girl’ born on a Friday’, and his first’ child is a boy’ born on a Tuesday’. What probability must we assign to him asserting that he has at least one girl’ born on a Friday’?

Our transformation necessitates p(boy Tuesday) = p(girl’ Friday’), and likewise p(girl Friday) = p(boy’ Tuesday’). But our state of complete ignorance about what’s going on with respect to the man’s attitudes about boys, girls, Tuesdays, Fridays, and first and second children has the symmetry that question and question’ are the same question, and must, by the desideratum of consistency, have the same answer. Therefore p(boy Tuesday) = p(boy’ Tuesday’) = p(girl Friday) = 1/2.

## Interns or Slaves?

My classmate Misha gave me a math problem. Although I liked the math part, I hated the setup. Here is the problem using the new setup:

You are hoping to get very rich one day and you base your hopes on your new invention: a diet pill. The pill works beautifully and doesn’t have side effects. Patients simply take a pill when they get hungry. Within one hour they will fall asleep and will be unable to awake for exactly two hours, at which time they will awake by themselves feeling completely sated.
You have just arrived at your lab, when you realize that one of your interns has misplaced your bottle of wonder pills. After some investigation, you come to the conclusion that your bottle is on the shelf with 239 other bottles that contain a placebo. Unfortunately, those placebo bottles were custom-designed for your statistical tests to exactly match your medicine bottle.
You need to bring the medicine bottle to your boss in two hours. While you panic, all your five interns volunteer for experiments, hoping to be mentioned in your paper. Can you find your bottle in two hours?

The problem Misha gave me had 240 barrels of wine, one of which contained deadly poison and five slaves who could be spared.

I do not like killing people even when they are imaginary. But while I was slow in inventing my own setup, the original version of the puzzle started making the rounds on the Internet. So I decided to kill the problem by writing the solution.

The strategy is to give out some pills immediately, wait for one hour and see who falls asleep. The next step is to give some other pills at the beginning of the next hour to some of the interns who are awake.

Let’s count the information you can get out of this. Each intern will experience one of three different situations: falling asleep in the first hour, in the second hour, or not falling asleep at all. Thus, you can have a total of 35 = 243 different outcomes.

If you had more bottles than 243, there would be no way to distinguish between them. The fact that you have 240 bottles might mean that 243 will work too, but apparently the designer of the puzzle didn’t want to hint into powers of three and picked the largest round number below 243. These considerations should increase your willingness to look into this problem base 3.

Let us label the bottles with different 5-character strings containing three characters 0, 1, and 2. Now we can use the label as instructions. The first character will be associated with the first intern and so on. Suppose the fourth character on the bottle’s label is 0, then the fourth intern doesn’t need to struggle with digesting a pill from this particular bottle. If the fourth character is 1, then the fourth intern gets the pill in the first hour. If the fourth character is 2, the fourth intern gets the pill in the second hour.

Note this minor detail: Suppose the fourth character on a bottle is 2, but the fourth intern is asleep by the second hour. That means, the bottle doesn’t contain the medicine, and we can put it aside.

At the end of two hours you know who fell asleep and when. This data will exactly match the label on the bottle with the medicine.