# How is it that you can guess if one of a pair of random numbers is larger with probability > 1/2?

My apologies if this is too elementary, but it's been years since I heard of this paradox and I've never heard a satisfactory explanation. I've already tried it on my fair share of math Ph.D.'s, and some of them postulate that something deep is going on.

The Problem:

You are on a game show. The host has chosen two (integral and distinct) numbers and has hidden them behind doors A and B. He allows you to open one of the doors, thus revealing one of the numbers. Then, he asks you: is the number behind the other door bigger or smaller than the number you have revealed? Your task is to answer this question correctly with probability strictly greater than one half.

The Solution:

Before opening any doors, you choose a number $r$ at random using any continuous probability distribution of your choice. To simplify the analysis, you repeat until $r$ is non-integral. Then you open either door (choosing uniformly at random) to reveal a number $x$. If $r < x$, then you guess that the hidden number $y$ is also smaller than $x$; otherwise you guess that $y$ is greater than $x$.

Why is this a winning strategy? There are three cases:

1) $r$ is less than $x$ and $y$. In this case, you guess "smaller" and win the game if $x > y$. Because variables $x$ and $y$ were assigned to the hidden numbers uniformly at random, $P(x > y) = 1/2$. Thus, in this case you win with probability one half.

2) $r$ is greater than $x$ and $y$. By a symmetric argument to (1), you guess "larger" and win with probability one half.

3) $r$ is between $x$ and $y$. In this case, you guess "larger" if $x < y$ and "smaller" if $x > y$ -- that is, you always win the game.

Case 3 occurs with a finite non-zero probability $\epsilon$, equivalent to the integral of your probability distribution between $x$ and $y$. Averaging over all the cases, your chance of winning is $(1+\epsilon)/2$, which is strictly greater than half.

Given that the original numbers were chosen "arbitrarily" (i.e., without using any given distribution), it seems impossible to know anything about the relation between one number and the other. Yet, the proof seems sound. I have some thoughts as to the culprit, but nothing completely satisfying.

• Meta-answer: there's no such thing as a paradox, just a failure of your intuition. Dec 15 '09 at 21:45
• Disagreement by definition: a paradox is a failure of your intuition ;) Dec 15 '09 at 21:48

After Bill's latest clarifications in the commentary on Critch's answer, I think the question is interesting again. My take:

One thing that always seemed to fall through the cracks when I learned about probability theory is that probability is intricately tied to information, and probabilities are only defined in the context of information. Probabilities aren't absolute; two people who have different information about an event may well disagree on its probability, even if both are perfectly rational. Similarly, if you get new information relevant to a certain event, then you should probably reevaluate what you think is the probability that it will occur. Your particular problem is interesting because the new information you get isn't enough for you to revise that probability by purely mathematical considerations, but I'll get to that in good time.

With the previous paragraph in mind, let's compare two games:

G1. You are given two closed doors, A and B, with two numbers behind them, and your goal is to choose the door with the higher number. You are given no information about the doors or numbers.

G2. You are given two closed doors, A and B, with two numbers behind them, and your goal is to choose the door with the higher number. You are allowed to look behind one of the doors and then make your choice.

For the first game, by symmetry, you clearly can't do better than choosing a door randomly, which gives you a success probability of exactly 1/2. However, the second game has a chance of being better. You are playing for the same goal with strictly more information, so you might expect to be able to do somewhat better. [I had originally said that it was obviously better, but now I'm not so sure that it's obvious.] The tricky thing is quantifying how much better, since it's not clear how to reason about the relationship between two numbers if you know one of the numbers and have no information about the other one. Indeed, it isn't even possible to quantify it mathematically.

"But how can that be?" you may ask. "This is a mathematical problem, so how can the solution not be mathematically definable?" There's the rub: part of the issue is that the problem isn't formulated in a mathematically rigorous way. That can be fixed in multiple ways, and any way we choose will make the paradox evaporate. The problem is that we're asked to reason about "the probability of answering the question correctly," but it's not clear what context that probability should be computed in. (Remember: probabilities aren't absolute.) In common probability theory problems and puzzles, this isn't an issue because there is usually an unambiguous "most general applicable context": we should obviously assume exactly what's given in the problem and nothing else. We can't do that here because the most general context, in which we assume nothing about how the numbers $$x$$ and $$y$$ are chosen, does not define a probability space at all and thus the "probability of answering the question correctly" is not a meaningful concept.

Here's a simpler ostensible probability question that exhibits the same fallacy: "what's the probability that a positive integer is greater than 1,000,000?" In order to answer that, we have to pick a probability distribution on the positive integers; the question is meaningless without specifying that.

As I said, there are multiple ways to fix this. Here are a couple:

I1. (Tyler's interpretation.) We really want the probability of answering the question correctly given a particular $$x$$ and $$y$$ to be greater than 1/2. (The exact probability will of course depend on the two numbers.)

I2. (Critch's interpretation.) More generally, we want the probability of answering correctly given a particular probability distribution for $$(x,y)$$ to be greater than 1/2. (The exact probability will of course depend on the distribution.)

(Those two are actually equivalent mathematically.) Clearly, if we knew what that distribution was, we could cook up strategies to get a success probability strictly above 1/2. That's pretty much obvious. It is not nearly as obvious that a single strategy (such as the one in the statement of the question) can work for all distributions of $$(x,y)$$, but it's true, as Bill's proof shows. It's an interesting fact, but hardly paradoxical now.

Let me summarize by giving proper mathematical interpretations of the informal statement "there is a strategy that answers the question correctly with probability strictly greater than 1/2," with quantifiers in place:

(1a) $$\exists \text{ strategy } S: \forall x, y: \exists \delta > 0$$: $$S$$ answers correctly on $$x$$, $$y$$ with probability at least $$1/2 + \delta$$.

(1b) $$\exists \text{ strategy } S: \forall \text{ probability distributions } P \text{ on } \mathbb{N}^2: \exists \delta > 0$$: $$S$$ answers correctly, when $$x$$, $$y$$ are chosen according to $$P$$, with probability at least $$1/2 + \delta$$.

I think with the proper quantifiers and the dependence on $$x$$ and $$y$$ explicit, it becomes a cool mathematical result rather than a paradox. Actually, based on my arguments at the beginning, it's not even that surprising: we should expect to do better than random guessing, since we are given information. However, simply knowing one number doesn't seem very useful in determining whether the other number is bigger, and that's reflected in the fact that we can't improve our probability by any fixed positive amount without more context.

Edit: It occurred to me that the last part of my discussion above has a nonstandard-analytical flavor. In fact, using the first version of the formula for simplicity (the two being equivalent), and the principle of idealisation, I think we immediately obtain:

(2) $$\exists \text{ strategy } S: \exists \delta > 0: \forall \text{ standard }x, y:$$ $$S$$ answers correctly on $$x$$, $$y$$ with probability at least $$1/2 + \delta$$.

(Please correct me if I'm wrong.) The number $$\delta$$ is not necessarily standard, and a basic argument shows that it must actually be smaller than all standard positive reals, i. e., infinitesimal. Thus, we can say that being able to look behind one door gives us an unquantifiably small, infinitesimal edge over random guessing. That actually meshes pretty well with my intuition! (It might still a nontrivial observation that the strategy $$S$$ can be taken standard; I'm not sure about that...)

• Thank you for your thoughtful answer, and for clarifying the questions under debate! Your first formula (call it (1)) is the one that I intended to inquire about, and to me remains the strongest statement (in any instance of the game, there is a quantifiable advantage to looking under a door). I agree that this implies your second statement (2), though because delta is standard in (1) but non-standard in (2), I'm not sure that (2) implies (1). Dec 17 '09 at 18:37
• I wasn't sure which you were referring to, so I numbered my formulas. Delta in (1a) and (1b) is of course standard (because you don't need nonstandard analysis to prove them), while delta in (2) is nonstandard. I think the three formulas are all equivalent (I'm not very good at nonstandard analysis), but in any case, (1a) and (1b) are equivalent, and they imply (2). Dec 17 '09 at 20:05
• @Bill, I agree with Darsh's assessments here, which are of game G2, and that the conflation of games G1 and G2 could be a significant source of confusion, depending on the confusee of course (as all paradoxes do). @Darsh, I edited our game/interpretation labels to make them easier to refer back to... hope you don't mind. Dec 18 '09 at 2:21
• Great, so we're all in agremeent about the formulation of the problem! Perhaps the fact that there is information revealed in opening a door will be the best intuition we can have for the result. I'll leave this thread open for a few days, but I expect Darsh has had the final word! Dec 18 '09 at 3:49
• Great response. I would vote it up more if I could, and Bill should accept it and be done. (Bill: MO is not a great place for a debate, methinks, so I hope "questions under debate" is meant rhetorically.) I'm never much impressed with "paradoxes" except when they are used to illustrate a failure of well-formedness or of intuition; I think your answer exactly describes how a "paradox" can best be used to extend mathematical understanding. Dec 18 '09 at 4:54

It might be useful to the intuition to consider the following simpler strategy: If the revealed number is positive, guess that it is the larger of the two. If the revealed number is negative, guess that it is the smaller of the two.

This simple strategy already guarantees you a chance of winning that is always at least 50% and sometimes greater. In particular, your chance of winning is 50% if the numbers are either both positive or both negative, and 100% if they have opposite signs.

That's not quite a solution to the original problem, but it works --- or comes close to working --- for exactly the same reason that the actual solution works, and it's easy to understand in an instant.

• What's interesting here is that no matter where you put the threshold, your odds don't change - you could choose to threshold at 0, -100, or a million, and the odds stay the same. Even though you're changing the decision you'd make for many numbers, there's an infinite number of values for which the decision stays the same, making any strategies of this nature with different thresholds effectively indistinguishable. Nov 4 at 16:30

Thanks for writing out the proof in detail, so that answers can easily refer back to it! The math is fairly straightforward, but as a paradox I find this very interesting.

EDIT (Dec. 17, after change in question statement): This answer interprets the question with the values { $x,y$ } varying over possible games. Mathematically speaking this is only an integral more general than the case where { $x,y$ } is fixed (which is the special case where the hosts's choice distribution $Q$ is supported uniformly on two fixed integers), but a new level of potentially paradoxical issues arise. The answer below is intended presuming the fixed case is understood, and addresses issues that arise in passing to the variable case. For a discussion of the fixed case, I recommend Darsh's excellent answer.

Logical/mathematical remarks:

(0) An easier method than "repeating until non-integral" is to directly fix a probability distribution $P$ on numbers of the form $n+0.5$ and choose one randomly via $P$.

(1) The proof for this strategy is valid provided that you know the host is choosing his number according to SOME fixed, well-defined probability distribution $Q$ on the integers (but you don't have to know what $Q$ is). In this sense, you know that his choice is actually not completely arbitrary... you know he's following some system, even if you don't know which one.

For example

(1.1) Specifically, consider the step "Averaging over all the cases" (after Case 3 in the question). The number $\epsilon$ in Case 3 depends on $x$, $y$, and your distribution $P$. "Average over all the cases" means that you integrate the function $(1+\epsilon)/2$ over the space of all possible pairs $(x,y)$. This requires a probability distribution on the pairs $(x,y)$, which is where $Q$ comes in. Since any $Q$ will give a result greater than $1/2$, it is tempting to think $Q$ is irrelevant to the conclusion. This is a fallacy! I cannot stress enough that treating an unknown as a random variable is a non-vacuous assumption that has real consequences, this scenario itself being an example. Without this assumption, the step "Averaging over all the cases" is meaningless and invalid.

(2) Although the result of your strategy is that you "know something" about the relation between the two numbers, your confidence in this knowledge is arbitrary. That is, you have no estimate, not even a probabilistic one, on how much bigger than $0.5$ your chances of winning are.

Resolving the paradox: (isolating what causes the "weird feeling" here)

In short, I'd say mixing "random" and "arbitrary" in the same scenario makes for a patchy idealization of reality.

Here, one unknown, the choice of ordered pair $(x,y)$, is being treated via a probability distribution $Q$, whereas a related unkown, the choice of probability distribution $Q$, is being treated as "arbitrary". This is a weird metaphysical mix of assumptions to make.

Why?

For example, in science and in everyday life, an estimate of "what's likely" can be accompanied, consciously or unconsciously, with an estimate of how accurate the first estimate is, and in principal one could have estimates of those accuracies as well, and so on. This capacity for self reflection is a big part of being sentient (or at least the "illusion of sentience", whatever that means).

In this scenario, such self-reflective estimates are in principle impossible (because we don't assume that the host's distribution $Q$ was chosen according to any distribution on distributions), which makes it a very unfamiliar situation.

This is just one reason why mixing "random" and "arbitrary" can make for a weird-seeming model of reality, and I blame this mixture for allowing the scenario to appear paradoxical.

• Thank you for considering! In response to your points: (1) I'm not sure why the host has to follow any fixed distribution, unless we define his behavior over (unbounded) time to be that distribution. But I agree that the notion of "arbitrary" is what makes this weird! (2) This might be fixable. Say that you reveal your probability distribution to the host ahead of time, and he promises to choose two numbers that lead to an epsilon of at least a given size. I don't think this changes the proof, or the paradox. Yet it does provide a level of confidence regarding your knowledge in the game. Dec 15 '09 at 21:26
• I would add that I agree the assumptions are unusual, and perhaps that is to blame. But is there a better way to model this situation? If you played the game for unbounded time, could you beat the house? If yes, then that seems like a paradox to me. Dec 15 '09 at 21:32
• (1) If you don't assume a probability distribution on the hosts outputs, then talking about probabilities of his outputs doesn't make sense! This is just a mathematical prerequisite for probabilistic reasoning. (2) How is the scenario paradoxical at all of the host is cooperating with you? Dec 15 '09 at 21:39
• (1) Let's say that we define the host's probability distribution as his behavior over time. I think that suffices? In other words, ANY host would draw from some distribution, as defined in this way. It is not that we are imposing an additional assumption on the scenario. (2) Even though the host is cooperating in this way, this does not reveal any information about which number is bigger, which is the source of the paradox. Dec 15 '09 at 21:51
• (2) I don't see what you could be wondering about here. If the host conspires with the guest to ensure that the guest is right more than half the time, there is no surprise if the guest succeeds. If you mean to assume the guest also knows the host is conspiring, then this extra information will allow the guest to unsurprisingly predict for himself that he will succeed. If you mean something else, I don't know what it could be. Dec 16 '09 at 0:41

I don't think there is any need to reason about your opponent's probability distribution (and therefore the above explanations of the paradox seem spurious). For concreteness, say that you draw your guess from the Laplace distribution. You can now claim: "For every pair of integers (a,b), the probability of success is strictly greater than 1/2".

There's no distribution here -- we can just make this claim about the set of all integer pairs, and so we no longer have to reason about how the opponent comes up with them.

I'm finding most of the above either wrong or unnecessarily obtuse. My take is that the paradox arises in two parts. The first is a simple trick. The game looks like it reduces to:

(Incorrect:) The game show host puts the prize behind one of two doors. He tells you an arbitrary unrelated integer m. You pick a door.

But the integer m is actually related. The game really reduces to:

The host puts the prize behind one of two doors, and picks an integer n. You pick a door. He tells you m, computed as follows: if you picked the right door, m=n, if not, m=n+1 (or greater). You then get an option to switch doors before he opens them.

Now, for the sake of brevity, let's just take it for granted that you should pick a random door initially, and privately choose an integer r. On hearing m, you should switch doors if r<m. Let's also take the worst case that m=n+1 when you initially guess the wrong door. The whole thing reduces to the following:

The host picks an integer n. You guess what the integer is. If you guess right, he gives you the prize. If not, he flips a coin to decide if you win.

Let me emphasise that up to this point, the reduction involves only integers and makes no assumptions on probability distributions for guessing arbitrary integers. The second part of the paradox is just this:

Proposition: You have a strictly positive probability of correctly guessing an arbitrary integer.

Here comes in all the talk of distributions, interpretations, random versus arbitrary, etc.

The problem is that there's no way to define a random sample over all the real numbers, where every real number has equal probability of being chosen.

See this related problem and solution by Randall Munroe, the creator of XKCD.

• Yes, I agree with this. It is the most simple answer, but the correct one. You say 'Given that the original numbers were chosen "arbitrarily" (i.e., without using any given distribution)'. This is an inconsistent assumption, which leads to the paradox. You have to choose a distribution. In case of a die, you can choose the same probability for each side. In case of infinite set, you get troubles and you should take care that you don't assume something impossible. This is also the cause of the envelope problem paradox. Jul 4 '10 at 21:00
• I don't think this is the only issue. As Darsh puts it, the surprise, mathematically speaking, is that the same strategy works regardless of the probability distribution on x and y. This is a nontrivial fact which is not accounted for by the observation that we should specify such a distribution. Jul 5 '10 at 5:41
• I don't agree with this either, and moreover I think the xkcd (continuous) version adds nothing and just muddies things more. Among other things the xkcd answer isn't a "strategy" since there is no finite way to compare two arbitrary real numbers (not even two computable ones). If they are compared to only finite precision, I think there is a way to defeat the strategy. Jul 5 '10 at 17:20
• If the distribution isn't uniforn, then P(x>y) isn't 1/2 after revelation of x. You get a conditional probability then. One of the pitfalls of probability is to ignore a fact. Jul 5 '10 at 19:46
• Let the two numbers be $a$ and $b$ and denote your strategy by $S$. Your probability of winning is some function $P$ of $a$, $b$ and $S$. The claim is that there exists an $S$ such that for all $a$ and $b$, $P(a,b,S)>1/2$. This is a perfectly meaningful claim and does not rely on any probability distribution for $a$ and $b$. Jan 19 '16 at 6:11

There is a related "paradox" known as the two envelopes problem which has a nice article on wikipedia.

• Actually, I find it to be one of the worst written Wikipedia articles on mathematics I've seen and it badly needs some attention from a probabilist. For example, it starts trying to resolve the problem by saying "You cannot denote an unknown amount chosen by chance by a variable" which rules out any argument that makes use of random variables. And having claimed that you can't write a random variable in this way, it proceeds to use it anyway. Dec 15 '09 at 22:48

As previously explained above, the success of the proposed contestant strategy is entirely dependent upon the assumption made by the contestant about the host's method of choosing x and y.

An example where a fixed contestant strategy almost always fails. Suppose the host always chooses an "unexpectedly" large negative number for x, say x = -n, where n has >1000 digits, and r is more "ordinary", say having <100 digits. The method depends on the contestant betting that x < r < y. If the host's uniform strategy has always chosen y = x-1, then the contestant will almost certainly lose round after round of play. (If, after numerous rounds of this, the contestant then realizes this strategy of the host and tries to change his/her betting strategy, the host can adapt as well, choosing y = -x = n for later rounds)

This is a problem that becomes much simpler if one makes the effort to make the problem precise. The following is somewhat inspired by [Alexander Gnedin. "Guess the larger number." arXiv:1608.01899 (2016).] that contains a lot of discussion, variations, and history regarding the problem.

A pure strategy specifies for each observed number whether one accepts it as the larger or at least as large one ($$1$$) or passes to the other number ($$0$$). So we can take the space of pure strategies to be $$\{0,1\}^\mathbb{Z}$$. For each let $$t_n\in\{0,1\}^\mathbb{Z}$$ be the $$n^\text{th}$$ threshold strategy for which $$t_n(l)=1$$ iff $$l\geq n$$.

Now let $$\nu$$ be any probability distribution over $$\mathbb{Z}$$ and let $$\pi(\nu,t)$$ be the winning probability of picking the larger or equally larger number of someone using the pure strategy $$t$$ when both numbers are chosen independently from $$\nu$$. (Note that this does not fully agree with the original statement in which both numbers must be distinct, but if we have enough freedom to pick both distributions separately, one cannot ensure a winning probability of more than $$1/2$$ for each $$\nu$$.)

It is easy to see that for each $$\nu$$, the winning probability $$\pi$$ is maximized at some threshold strategy and that any other maximizing strategy must equal a threshold strategy $$\nu$$-almost surely.

Observe that a threshold strategy guarantees a winning probability of at least $$1/2$$ against any distribution $$\nu$$ on the integers. Also, for any distribution $$\nu$$ on the integers, some threshold strategy has a winning probability strictly larger than $$1/2$$.

So far, nothing should have been truly surprising. Now let $$\mu$$ be any full support probability distribution on $$\mathbb{Z}$$. There is an induced randomized threshold strategy $$t_\mu$$ that chooses the threshold strategy $$t_n$$ with probability $$\mu(n)$$. If we extend $$\pi$$ in the obvious way to a function $$\pi:\Delta(\mathbb{Z})\times\Delta(\{0,1\}^\mathbb{Z})\to\mathbb{R}$$ where $$\Delta(X)$$ is the set of Borel probability measures on $$X$$, we see that $$\pi(\nu,t_\mu)>1/2$$ for all $$\nu\in\Delta(\mathbb{Z})$$. Indeed, for each $$\nu$$, and each $$n$$, $$\pi(\nu,t_n)\geq 1/2$$, and with positive probability, we pick some $$n$$ such that $$\pi(\nu,t_n)>1/2$$.

Finally, note that the originally proposed strategy based on a continuously distributed random variable $$r$$ corresponds to $$t_\mu$$ with $$\mu(n)$$ being the probability that $$n>r$$.

The numbers are supposedly chosen from an infinite distribution...

There is no valid way to "sample" an infinite distribution of integers to get x and y, nor is there a way to get r from an infinite real distribution.

Sticking to the integers - the chance of "sampling" any given integer is zero. The chance of "sampling this distribution" with an integer between and two arbitrary integers, no matter how ridiculously large, is also zero.

Put another way, there is no way to define the probability of an integer "thus chosen" within any arbitrary range to be anything other than zero.

All values p(i) are zero.

Now, if we could put some constraints on the values the game show host can choose from, and the probabilities thereof, we could effectively integrate over ranges and talk about probabilities and formulate a winning strategy...

Consider the following simplified problem: I will pick two numbers from the non-zero integers with probability proportional to $\frac{1}{|k|}$. So:

$$p(|k|) \propto \frac{1}{|k|}$$

And we play the same game as above, I reveal one and ask you whether the other is smaller or not. Now, what is p(5)? This is just $\frac{1}{R} \frac{1}{|5|}$, where $R$ is the renormalization constant. So:

$$R = 2 \sum_{k=1}^{\infty} \frac{1}{k}$$

whoops!

So, now, what does this mean? is $p(5) = 0$? is $p(k) = 0$ for all k? Does this problem make any more sense if I took the probability proportional to $\frac{1}{|k|}^\alpha$ as $\alpha \to 0$? What does it mean to pick a number whose probability is 0?

How would I even write down these numbers to compare them? They're obviously much larger than the number of atoms in the universe...Do I have an algorithm to spit out the bits and try to compare them that way?

This problem is a syntax error. The premise that you can 'pick a random number' from all integers is invalid. You can't do this. The reason why your (faulty) logic appears to work is because you're implicitly capping the distribution from $[-M,M]$ and then waving your hands by taking $M \to \infty$, which can't be done.

• Sorry, but that's just wrong. That's not what this paradox is about at all. There is no problem choosing a probability distribution on the integers so that each integer gets positive probability, or in taking a continuous distribution on the reals so that each nonempty interval has positive probability. Feb 19 '10 at 6:23