Who discovered this number-guessing paradox?

In this math.se post I described in some detail a certain paradox, which I will summarize:

$A$ writes two distinct numbers on slips of paper. $B$ selects one of the slips at random (equiprobably), examines its number, and then, without having seen the other number, predicts whether the number on her slip is the larger or smaller of the two. $B$ can obviously achieve success with probability $\frac12$ by flipping a coin, and it seems impossible that she could do better. However, there is a strategy $B$ can follow that is guaranteed to produce a correct prediction with probability strictly greater than $\frac12$.

The strategy, in short, is:

• Prior to selecting the slip, $B$ should select some probability distribution $D$ on $\Bbb R$ that is everywhere positive. A normal distribution will suffice.
• $B$ should generate a random number $y\in \Bbb R$ distributed according to $D$.
• Let $x$ be the number on the slip selected by $B$. If $x>y$, then $B$ predicts that $x$ is the larger of the two numbers; if $x<y$ she predicts that $x$ is the smaller of the two numbers. ($y=x$ occurs with probability $0$ and can be disregarded.)

I omit the analysis that shows that this method predicts correctly with probability strictly greater than $\frac12$; the details are in the other post.

I ended the other post with “I have heard this paradox attributed to Feller, but I'm afraid I don't have a reference.”

I would like a reference.

Solution 1:

Thanks to a helpful comment, since deleted, by user Stefanos, I was led to this (one-page) paper of Thomas M. Cover “Pick the largest number”Open Problems in Communication and Computation Springer-Verlag, 1987, p152.

Stefanos pointed out that there is an extensive discussion of related paradoxes in the Wikipedia article on the ‘Two envelope problem’. Note that the paradox I described above does not appear until late in the article, in the section "randomized solutions".

Note also that the main subject of that article involves a paradox that arises from incorrect reasoning, whereas the variation I described above is astonishing but sound.

I would still be interested to learn if this paradox predates 1987; I will award the "accepted answer" check and its 15 points to whoever posts the earliest appearance.

Solution 2:

In his blog post, mathematical physicist John Baez considered this problem described by Thomas M. Cover as the special case $n = 2$ of what was called "the game of googol" by Martin Gardner in his column in the Feb. 1960 issue of Scientific American.

That is, John Baez accepted (the suggestion by one of his blog readers) that this is a variant of the famous secretary problem, which wiki entry actually includes this "game of googol".

If you are willing to take this point of view (Thomas M. Cover sort of did, in his closing remark), then the quest becomes the history of (this variant of) the secretary problem.

John Baez's blog post is a good expository piece with some good discussion in the comments there. However, he didn't really do the literature search that pertains to Thomas M. Cover's approach going backwards in time.

Similarly, there's no citation in that Quanta magazine article that got John Baez's notice. FWIW, the analysis there is thorough enough while being easily accessible to the general public.

My personal stance at this point is that, nobody before Thomas M. Cover looked at the secretary problem in this particular way. He passed away in 2012 so one can only learn how he encountered this problem by studying his notes or asking his collaborators, friends, etc.

I have to admit that I didn't go through all the publications (27 so far) that cited that short paper by Thomas M. Cover to see if they found anything preceding that.

For the record, if one wants to see Martin Gardner's original text, I cannot find an open access of the Feb.1960 Scientific American nor the earliest reprint of the column in his 1966 book.${}^2$ The best thing I've got is the 1994 google book. See the 2nd paragraph on p.18 for the case $n=2$. Martin Gardner certainly didn't know what he was missing.

Footnote 1:$\quad$ "New Mathematical Diversions from Scientific American". Simon and Schuster, 1966, Chapter 3, Problem 3. This is a relatively long chapter in the book, as it essentially deals with the secretary problem.

Solution 3:

For the history of the paradox see "Guess the Larger Number" by Alexander Gnedin, MATHEMATICA APPLICANDA Vol. 44(1) 2016, p. 183–207.

Gnedin traces the idea back to “work on theoretical statistics by David Blackwell and Bruce Hill" of 1951 (!) and 1968, respectively. He says "Much of the interest was sparked by Tom Cover’s half-page abstract, where the game framework was explicitly introduced."