# Dantzig's unsolved homework problems

From Wikipedia:

An event in George Dantzig's life became the origin of a famous story in 1939 while he was a graduate student at UC Berkeley. Near the beginning of a class for which Dantzig was late, professor Jerzy Neyman wrote two examples of famously unsolved statistics problems on the blackboard. When Dantzig arrived, he assumed that the two problems were a homework assignment and wrote them down. According to Dantzig, the problems "seemed to be a little harder than usual", but a few days later he handed in completed solutions for the two problems, still believing that they were an assignment that was overdue.

What were the two unsolved problems which Dantzig had solved?

• It seems that the two problems can be found in Dantzig's thesis. – Hagen von Eitzen Oct 20 '13 at 12:35

I think the two problems appear in these papers:

Dantzig, George B. "On the Non-Existence of Tests of 'Student's' Hypothesis Having Power Functions Independent of Sigma." Annals of Mathematical Statistics. No. 11; 1940 (pp. 186-192).

Dantzig, George B. and Abraham Wald. "On the Fundamental Lemma of Neyman and Pearson." Annals of Mathematical Statistics. No. 22; 1951 (pp. 87-93).

EDIT: In case snopes ever goes belly up, the story can be found in Albers, Reid, and Dantzig, An Interview with George B. Dantzig: The Father of Linear Programming, College Math J 17 (1986) 292-314. The interview has also been reprinted in Albers, Alexanderson, and Reid, More Mathematical People, page 67.

I'm a few years late to the party, but in fact the problem in the first, solo paper is easy to state with only elementary background, and the arguments in it are entirely reasonable for a talented young grad student to come up with. I have not taken the time to read the second paper. This topic comes up from time to time with interest from a very broad array of people, and nobody seems to have written a straightforward description of either problem, so I'll provide such a description for the first one.

For those with some background: Dantzig showed that in the situation of Student's t-test, the only way to get a hypothesis test whose power for any given alternative is independent of the standard deviation is to use a silly test which always has an equal probability of rejecting or failing to reject, which is obviously not useful.

In an unusual amount of detail, aimed at those with no statistical knowledge:

Lots of data is approximately normally distributed ("bell-shaped"), like IQ scores, birthweights, or people's height. The classical Central Limit Theorem gives one explanation for this phenomenon: complicated traits like birthweight can often be thought of as the result of adding up a large number of competing effects, like the presence or absence of specific genes. It is a statistical fact that under very general hypotheses, adding up many such effects tends to result in a normal distribution.

A century ago, William Gosset was Head Experimental Brewer at Guinness. He came up against something like the following problem. Certain strains of barley have approximately normally distributed yields. Using only a few data points, how could he tell which type of barley is better, and more importantly, how could he quantify his certainty that his conclusion wasn't simply due to random chance?

A little more formally, say our current strain of barley has a yield of 100 units, and we're only interested in switching to the new strain if its yield is at least 105 units. So, we have two specific hypotheses:

• ("Null hypothesis.") The new strain's yield is 100 units.
• ("Alternative hypothesis.") The new strain's yield is 105 units.

At the end of the day, we're going to need to pick one strain of barley or the other. There are hence four probabilities of interest:

1. In a world where the new strain's yield is actually 100 units...
• A. ...the probability that we correctly keep using the old strain.
• B. ...the probability that we mistakenly switch to the new strain.
2. In a world where the new strain's yield is actually 105 units...
• C. ...the probability that we mistakenly keep using the old strain.
• D. ...the probability that we correctly switch to the new strain.

We want to somehow minimize the probability of the two types of mistakes, B and C.

Gosset developed a clever test where you can specify in advance the probability of making mistake B, say it's 5%. You can then compute the probability of making mistake C, if you use his testing procedure. The power of the test is then probability D, which is thought of as the ability of the test to correctly tell us to switch to the new method.

Suppose you pick a testing procedure for which mistake B has a 5% probability. Imagine varying the alternative hypothesis--rather than just 105, you might test against 104, 103, .... It's harder to distinguish very close yields, so you'd expect the power of the test to go down as we test alternative yields closer and closer to 100.

In Gosset's barley situation, the new strain's yield is normally distributed. A given normal distribution is completely determined by its mean ("offset") and standard deviation ("dispersion", i.e. how spread out it is)--for instance, there is a 67% chance of being within 1 standard deviation of the mean in a normal distribution.

Here's where Dantzig came in. Suppose you pick a testing procedure for which mistake B has a 5% probability. We could ask how the power of the test depends on the standard deviation of the new strain's yield. In particular, we could ask if there is any test whatsoever which has the property that, for every fixed alternative, the power does not depend on the standard deviation. Dantzig showed that, while such tests exist, they are uninteresting in that probabilities A, B, C, and D are all 50%.

Closing remarks:

Finally, I wanted to comment on the tendency towards hyperbole. In Dantzig's 1986 College Mathematics Journal interview, Dantzig is quoted as calling the problems "two famous unsolved problems in statistics". In Dantzig's obituary (repeated on Wikipedia currently), this turned into "two of the most famous unsolved problems in statistics". While this is not my field and I am not old, I'm extremely dubious about the "most famous" claim. For instance, there seems to have been no rush to publish the second solution (it waited for Dantzig's thesis and an accident of someone else solving it). MathSciNet has only 5 citations for the first paper, three historical, and 7 citations for the second, again three historical. These are not the citation counts I would expect from solutions to a field's "most famous unsolved problems", even accounting for recent citation bias.

These exaggerations are frankly not necessary. Dantzig's reputation is enormous already, and the true story of a talented young grad student cleverly finding a few pages of brilliant argument that had eluded his teacher---something he never would have looked for if he knew that what he was working on was unsolved---is enough.