Someone has prepared two envelopes containing money.

Additional material

My analysis agrees with the one posted but without any additional
information such a pdf, my strategy would be to SWITCH IF THE AMOUNT OF
MONEY IS ODD.  BTW, the analysis correctly states that you cannot
average ratios and that's why the 1.25X answer is incorrect.  More
correctly stated, you cannot use an arithmetic average of ratios.  But
you CAN use a geometric mean to correctly average ratios and the result
would be:

Geometric Mean = [(X/2)*(2X)]^(1/n) = X
   where n is the number of terms (in this case, 2).

Thus the expected value is exactly X, not 1.25X, and there is no
mathematical advantage to switching.

-- bkolb@arinc.com

[ Editor: an expected value is the probability-weighted arithmetic
mean of the payoffs; the geometric mean X computed here is exp of the
expected log of the payoff, which is a different quantity. ]

In article <70nhrc$vsa$1@nnrp1.dejanews.com>, hochster@rocketmail.com
writes:

>The usual resolution (as in the archive) is to point out you have
>implicitly assumed a uniform distribution on an unbounded set of
>numbers, a no-no.

I never liked that resolution.  It solves the standard problem, but it
doesn't solve it for other distributions which make the same
problematic assumption, as the version below.

>The following variant shows the issue is a little more subtle: Suppose
>the numbers are assigned to the envelopes like this: Let X be 2^k with
>probability (1/3)*(2/3)^k For k = 0,1,2, ...  $X is now randomly placed
>one envelope and $2*X in the other. In this setup, if you open envelope A
>and find $N, then envelope $B contains $N/2 with probability 3/5 and $2N
>with probability 2/5, so that you expect to gain $N/10 by
>switching, and the paradox persists.

>ObPuzzle: What is going on?

The problem lies in that the expected value of $N is unbounded.
[Calculation: expected value = 2^k * (1/3) * (2/3)^k summed over all k]
In intuitive terms, there's an infinite reserve of money, so everybody
wins and nobody loses.

A thought experiment to convince you:  suppose we have two players
playing this game.  Person A always switches.  Person B never switches.
We let them all play a large number of games and see how they do on
the average.

Result:  On the average, person A gets more money than person B.
Result:  On the average, both players get "infinity" dollars.

Therefore, person B gets "infinity," and person A gets some fraction
more than "infinity" -- which is the same as "infinity"!

Conclusion:  Both players get the same result!

If this doesn't convince you, here's a simpler scenario: I give you 1
cent, then another cent after 1/2 second, then another cent after 1/4
second, etc.  But every time I give YOU a cent, I also give your worst
enemy an entire dollar.  In other words, I'm giving your worst enemy
100 times as much as you're getting.  Question:  Who has more money
after 1 second, you or your worst enemy?  Answer: You both have the
same amount of money -- infinity!  For every amount that your worst
enemy spends, you can match it, and vice versa.

Note that if the distribution is such that the expected value of an
envelope is bounded (e.g., a distribution of (2/3)*(1/3)^k probability
of getting 2^k), then it becomes unadvantageous to switch, and there is
no paradox.

In short, if the expected value of an envelope is infinity, then every
time you open an envelope and see a finite amount of money, you've
been shortchanged and you should switch.  :-)

-- Wei-Hwa Huang <whuang@ugcs.caltech.edu>

[ Editor: in a thread "Is this a paradox", comparing the Tie paradox
with the Wallet paradox.  In the necktie paradox two men wager that
whoever wears the more expensive tie must give it to the other; each
reasons that he stands to win more than he can lose. ]

I agree that the Tie paradox is more interesting than the Wallet
paradox.

The Tie paradox is essentially the Two Envelopes paradox covered in the
archives. This particular group collectively understands the Two
Envelopes paradox better than most professionals do.

To get the Tie paradox into line with the Envelopes paradox, find a
distribution of probability that can be shared by the tie owners, such
that each will still prefer to swap given the proprietary information
about how much his own tie costs.

Hm, that wasn't very clear.

Ok, try this.  We need a *prior* probability distribution over prices
of ties, which will be shared by the tie-owners. Each tie-owner then
conditionalizes on the price of his own tie; the resulting
distributions are different (though symmetric). Each tie owner now
prefers to swap.

The problem with the Wallet paradox is that there isn't any probability
distribution that yields a paradoxical result.

-- Jamie Dreier <pl436000@brownvm.brown.edu>

[ Editor: comments on the worked example above that begins "Assume the
smaller envelope is uniform on [$0,$M]". ]

>Assume the smaller envelope is uniform on [$0,$M], for some value
>of $M.  What is the expectation value of always switching?  A quarter of
>the time $100 >= $M (i.e. 50% chance $X is in [$M/2,$M] and 50% chance
>the larger envelope is chosen).  In this case the expected switching
>gain is -$50 (a loss).  Thus overall the always switch policy has an
>expected (relative to $100) gain of (3/4)*$50 + (1/4)*(-$50) = $25.

There appears to be an error in this paragraph.  What does "a quarter of
the time" mean?  A quarter of *what* times?  A quarter of the times that
the game is played?  But if we're playing the same game over and over,
then M is fixed, and either $100 >= $M or it isn't---for *all* games.  Or
(following the "i.e." in parentheses) is the idea that in a quarter of
the games, the amount we find in the envelope we pick first will exceed
$M?  In that case, what is the computation (3/4)*$50 + (1/4)*(-$50)
supposed to show?

-- Tim Chow <tycchow@math.mit.edu>, September 1993

My analysis agrees with the one posted but without any additional
information such a pdf, my strategy would be to SWITCH IF THE AMOUNT OF
MONEY IS ODD.  BTW, the analysis correctly states that you cannot average
ratios and that's why the 1.25X answer is incorrect.  More correctly
stated, you cannot use an arithmetic average of ratios.  But you CAN use a
geometric mean to correctly average ratios and the result would be:

Geometric Mean = [(X/2)*(2X)]^(1/n) = X
   where n is the number of terms (in this case, 2).

Thus the expected value is exactly X, not 1.25X, and there is no
mathematical advantage to switching.

-- <bkolb@arinc.com>, March 1994

[ Editor: on the "test value" technique described at the end of the
entry above. ]

Sadly, this discussion obscures the extremely counterintuitive result
that makes this problem interesting.  The question of whether the pdf
is uniform is irrelevant.  The "test value" technique works for _any_
pdf, and even when the ratio between the higher amount H and the lower
amount L is not restricted to 2.  In general (assuming you pick the
initial envelope at random) the technique wins when T is in (L,H] and
otherwise breaks even.  The payoff matrix is:

                  : Initial envelope  :  Probability of  : Payoff
    Choice of T   :    L       H      : correct decision :
   ---------------+-------------------+------------------+----------
    T <= L <  H   :    L       H      :      1/2         : (L+H)/2
    L <  T <= H   :    H       H      :       1          :   H
    L <  H <  T   :    H       L      :      1/2         : (L+H)/2

All that is needed is a positive a priori probability that the second
case occurs, i.e. that T is in (L,H].  For this to work in the case
that the pdf is a single accumulation point, all possible intervals
(L,H] must be covered; in particular, T must be picked from an
open-ended distribution.  One way is to pick T=N with probability
6/(Pi^2 N^2), for N=1,2,3,....

Using this technique, you are guaranteed to make the correct decision
more than half the time (and to win more than half the money) whenever
there is a positive probability that the envelopes contain different
amounts.  It is indeed the case that the improvement may not be very
much (whether or not the pdf is uniform).  What is amazing is that an
improvement over even odds can be realized at all.

-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>, October 1994

I'm not sure if this is the same article that was recently cited for
the P(smaller=2^n) = (1/3)*(2/3)^n example, but I just came across the
following:

Steven J. Brams and D. Marc Kilgour, "The Box Problem: to Switch or
Not to Switch," _Mathematics_Magazine_, Vol. 68 no. 1, February 1995.

This article discusses the two-envelope problem under the assumption
that you know or have guessed at the prior probability distribution of
the amounts in the envelopes.  It gives various distributions for
which the conditional expectation always calls for switching, and
presents a number of general results, including the fact that given a
known prior probability distribution, there is always some amount you
could find in the first envelope that calls for switching.  Both
discrete and continuous probability distributions are covered.

-- David A. Karr <karr@cs.cornell.edu>, February 1995

The article with the (1/3)*(2/3)^n distribution is:

E. Linzer, The Two Envelope Paradox
Amer Math Monthly, 101 (May, 1994) 417-419

-- Jay Rothman <jrothman@carbon.cudenver.edu>

[ Editor: a derivation of the conditional expectation, reposted with
two typos (pointed out by Heinz Herbeck) corrected and marked, January
1997. ]

Here is the derivation of the expected value formula,

E(y|x) = x [2f(x) + (1/4)f(x/2)] / [f(x) + (1/2)f(x/2)]

{This derivation is from Broome, "The two-envelope paradox", _Analysis_
55 (January 1995).}

Call the amount in the smaller envelope, s.  Remember that f(s) is the
density function representing prior probabilities for amounts in the
*smaller* envelope (the envelope with the lower value).  And the
expectation in question is the conditional one: given that we have
found x, what is the expectation of the value of the other envelope?

We first find the probability that y = 2x given a value of x.  (That
is, the probability that we have picked the smaller envelope.)

Take a small interval, between z and z+e.  Supposing that x falls in
that interval, what do we take to be the probability that y = 2x?

If x is between z and z+e, then either s is between z and z+e, or it is
between z/2 and (z+e)/2.  (We take e small enough so that these are
disjoint intervals.)  We have y=2x just when s is between z and z+e.

pr(y=2x) =  pr([z < s < (z+e)]  |  [z < s < (z+e)] v [z/2 < s < (z/2+e/2)]

(Assuming that the value we found lies in the z to z+e interval, the
probability that we have the smaller value is the probability that the
smaller value is in that interval given that it is either in that
interval or the z/2 to (z/2 + e/2) interval.)

This probability is equal to:

               pr(z < s < z+e)
      -------------------------------
   pr(z < s < z+e)  +  pr(z/2 < s < (z/2+e/2))


Now, as e gets smaller, this approximates

         f(z) * e
    ------------------
f(z) * e   +  (1/2) f(z/2) * e

(Probability under the curve in the given interval is approximately the
length of the interval times the density at a point in the interval;
this approximation converges to the exact value as the interval
contracts to a point.)

The e now cancels out.

f(z) / [f(z) + (1/2) f(z/2)]

We were conditioning on x=z.  So we reach

pr(y=2x | x) =  f(x) / [f(x) + (1/2) f(x/2)]

And similarly,

pr(y=x/2 | x) =  (1/2) f(x/2) / [f(x) + (1/2) f(x/2)]
   ~~~~~
{I'd erroneously typed "y=2x/2" here}

Then the expectation of y given x is

E(y | x) = (2x) pr(y=2x | x) + (x/2) pr(y=x/2 | x)
                                        ~~~~~~~~~
                                 {and here I'd mistyped as "y=2/x | x"}

=  x [2f(x) + (1/4)f(x/2)] / [f(x) + (1/2)f(x/2)]

QED.

-- Jamie Dreier <pl436000@brownvm.brown.edu>

[ Editor: from a discussion of the two-envelope paradox and the related
wallet paradox of Kraitchik on a mailing list of the Prometheus Society,
May 2000.  Chris Langan had stated the wallet paradox: ]

>>> First, we consider the related paradox of Kraitchik.  Two people are
>>> offered a chance to bet on whose wallet contains the lesser amount of
>>> money; the one with less gets all of the money in both wallets.  Both
>>> players reason as follows:
>>>
>>> "If I lose, I lose just what I have, but if I win, I win more than I have.
>>> Therefore, given that the win and loss probabilities are indifferent, my
>>> expectation is positive and I should bet."

[ Editor: Bridgester@aol.com ("Mike") replied: ]

>> Chris: Your analysis here is mathematically compelling, yet it seems
>> to me that there is additional *information* that could explicitly be
>> factored into the two-wallet game. I'm thinking of the actual amount
>> contained in my wallet at the time that the game is offerred to me.

> Of course. The given resolution would be worthless if it were unable to
> accommodate whatever additional information might be available to the
> player. The resolution can easily be reformulated in light of such
> additional information, again by distinguishing two subjective frames in
> which the possible contents each wallet are characterized in terms of a
> known distribution.

The "inclusion" approach.

>> If I've just come back from the bank or ATM with several hundred
>> dollars in my wallet then I will reason that the probability of my
>> *winning* the game by having the *lowest* amount is far lower than
>> 50/50 because in my experience only a few people ever carry more than
>> $100 in their wallet at any one time, especially in this *cashless*
>> economy. In this case the game is far from zero-sum to me, who is the
>> *subjective* calculator of the possible outcomes. Specifically, if I
>> should be carrying $300 at the time the game is offerred, I would
>> decline inasmuch as I would reason that the likelihood of my winning
>> is less than 5%.

> Yes. Your quantitative judgment is based on what you believe to be a
> more or less well-defined distribution characterizing the cash contents
> of all wallets. That distribution can be accommodated within the
> resolution.

>> I don't need to spend a lot of time on the converse. Let's say in the
>> normal course of events I'm carrying $30 and I take the family to a
>> fast food place. Those are quite expensive these days so I leave with
>> a few Big Macs and some fries and drinks for everyone and now I'm
>> down to just $16.44. With this amount in my wallet, I'd play the
>> wallet game because I'd impute an *average* amount of $30- $50 to
>> the other guy's wallet (unless he was in front of me in line and had
>> just bought a bag of Quarter-Pounders.)

> If you have more than one person in your family, you must have made
> a floating point error. I figure that if you enter Mickey D's with $300,
> $164.40 is about what you'd leave with these days

No, Chris.  You missed the $30 that Mike mentioned after the $300.

> (a single Big Mac runs around a fin or so, doesn't it?).

Is that a Big Mackerel? :-)

>> Perhaps I'm influenced  by yesterday's Preakness, but I see the two-
>> wallet example as more akin to betting on a horse in a pari-mutual
>> race. If I reason that the horse I like is *really* about a 4-1 shot
>> while the pari-mutual wagering puts a price of 6-1 on the horse, then
>> I'll bet. If it looks like the crowd likes the pony more than he's worth
>> and makes him just  3-1, then I won't bet. This is the essence of good
>> handicapping: compute a realistic probability for your horse to win,
>> and then look for inequities between this probability and the actual
>> price the horse will pay if it wins.

> Precisely. These paradoxes were deliberately formulated with
> indifferent probabilities to expose the logical essence of the basic
> problems with mathematical expectation, forcing logical resolutions
> free of quantitative hairsplitting. Because the logical resolutions are
> fully general, the inevitable hairsplitting presents no problem.

It would be interesting to see the details of how problems are avoided.

>> The wallet problem is similar, although not exactly the same. Compute
>> a likely percentile on the (imputed) probability function of *all wallet
>> holdings* for your own wallet's contents and, if it's lower than the 50th
>> percentile ( and there is no *irrational* disutility for losing the, say
>> $16.44 you have there), then go ahead and bet. If its contents are above
>> the 50th-tile, then avoid the bet. (Of course, this too could be refined to
>> allow for the fact that when you *win* you always get more than your
>> own wallet's amount. Thus, a playable cutoff of perhaps the top third-
>> 67th percentile- is probably a more practical heuristic. The demographic
>> milieu is also critical. The 50th-tile for  Kenwood Country Club  wallets
>> would likely differ from the 50-tile for Norwood Bowling Lanes.)

I suspect that the break-even point may be a little lower than the 67th
percentile.  Also, following Mike in moving into the inclusion of
realistic conditions, one must include in one's calculations how much
the two players know about one another's finances and the question of
how the idea of playing the game comes up.

> Mike, I like the way you always go for specific examples, filling in the
> dollar amounts to the penny!

>> The amount contained in one's wallet at the start of the game is as
>> important in its information content as the knowledge that Monty
>> has just opened a goat-door in the Monty Hall game. In both cases,
>> use of this knowledge allows one to make a better decision about
>> what choice to make.

> You're quite correct. The Monty Hall problem is actually quite
> transparent once you realize that the sought-after probabilities are
> merely subjective and need not be mistaken for the objective reality
> of the situation, which is that probability theory has nothing to do
> with the factual, deterministic yes-or-no locations of prizes behind
> doors.

> Chris Langan

I understand and agree with what Chris is getting at here, but, of
course, probability theory does have something to do with reasoning
about the problem.  One just needs to steer it around the paradox.

-- Kevin Langdon <kevin.langdon@polymath-systems.com>, May 2000

[ Editor: the Web paper "The Two-Envelope Paradox: A Complete
Analysis?" by David J. Chalmers, Department of Philosophy, University
of California, Santa Cruz <chalmers@paradox.ucsc.edu>, converted from
HTML; its mathematics is in LaTeX notation, kept as in the original.
It is followed by a reply from Jamie Dreier on rec.puzzles, January
1997. ]

The Two-Envelope Paradox: A Complete Analysis?

A wealthy eccentric places two envelopes in front of you.  She tells
you that both envelopes contain money, and that one contains twice as
much as the other, but she does not tell you which is which.  You are
allowed to choose one envelope, and to keep all the money you find
inside.

This may seem innocuous, but it generates an apparent paradox.  Say
that you choose envelope 1, and it contains $100.  In evaluating your
decision, you reason that there is a 50% chance that envelope 2
contains $200, and a 50% chance that it contains $50.  In retrospect,
you reason, you should have taken envelope 2, as its expected value is
$125.  If your sponsor offered you the chance to change your decision
now, it seems that you should do so.  Now, this reasoning is
independent of the actual amount in envelope 1, and in fact can be
carried out in advance of opening the envelope; it follows that
whatever envelope 1 contains, it would be better to choose envelope 2.
But the situation with respect to the two envelopes is symmetrical, so
the same reasoning tells you that whatever envelope 2 contains, you
would do better to choose envelope 1.  This seems contradictory.  What
has gone wrong?

The paradox can be expressed numerically.  Let A and B be the amounts
in envelope 1 and 2 respectively; their expected values are E(A) and
E(B).  For all n, it seems that p(B>A|A=n) = 0.5, so that E(B|A=n) =
1.25n.  It follows that E(B)=1.25E(A), and therefore that E(B) > E(A)
if either expected value is greater than zero.  The same reasoning
shows that E(A) > E(B), but the conjunction is impossible, and in any
case E(A) = E(B) by symmetry.  Again, what has gone wrong?

This problem has been discussed in the pages of _Analysis_ by Jackson,
Menzies and Oppy [2], and by Castell and Batens [1], but for reasons
that will become clear I think that their analyses are incomplete and
mistaken respectively, although both contain insights that are
important to the resolution of the problem.  I will therefore present
my own analysis of the "paradox" below.

Some distractions inessential to the problem arise from the facts that
in the real world, money comes in discrete amounts (dollars and cents,
pounds and pence) and that there are known limits on the world's money
supply.  We can remove these distractions by stipulating that for the
purposes of the problem, the amounts in the envelopes can be any
positive real number.

There are a number of steps in the resolution of the paradox.  The
first step is to note (as do the authors mentioned above) that the
amounts in the envelopes do not fall out of the sky, but must be drawn
from some probability distribution.  Let the relevant probability
density function be g, where the probability that the smaller amount
falls between a and b is \int_a^b g(x) dx.  We can think of this
distribution as either representing the chooser's prior expectations,
or as the distribution from which the actual values are drawn.  I will
generally write as if it is the second, but nothing much rests on this.
To fix ideas, we can imagine that our sponsor chooses a random variable
Z with probability density g, and then flips a coin.  If the coin comes
up heads, she sets A=Z and B=2Z; if it comes up tails, she sets A=2Z
and B=Z.

Recognizing the existence of a distribution immediately shows us that
the reasoning that leads to the paradox is not always valid, as Jackson
et al note.  For example, if the distribution is a uniform distribution
over values between 0 and 1000, with amounts over 1000 being
impossible, then if A > 500, it is always a bad idea to switch.  It is
therefore not true that for all distributions and all values of n,
p(B>A|A=n) = 0.5.  In general, E(B|A=n) will not depend only on n; it
will also depend on the underlying distribution.

In their analysis, Jackson et al are satisfied with this observation,
combined with the observation that limitations on the worlds' money
supply ensure that in practice the relevant distributions will always
be bounded above and below.  The paradox does not arise for bounded
distributions, as we saw above.  When A is a medium value, there may be
equal chances that B is larger or smaller, but when A is large B is
likely to be smaller, and when A is small B is likely to be larger, so
the paradox does not get off the ground.

This practical observation is an insufficient response to the
mathematical paradox, however, as Castell and Batens note.  Unbounded
distributions can exist in principle if not in practice, and
in-principle existence is all that is needed for the paradox to have
its bite.  For example, it might seem that if the distribution were a
uniform distribution over the real numbers, then p(B>A|A=n) = 0.5 for
all n.  This would seem to have paradoxical consequences for
mathematics, if not for the world's money supply.

This leads to the second step in the resolution of the paradox, which
is that taken by Castell and Batens.  (We will see that this step is
ultimately inessential to the paradox's resolution, but it is an
important intermediate point of enlightenment.)  There is in fact no
such thing as a uniform probability distribution over the real numbers.
To see this, let g be a uniform function over the real numbers.  Then
\int_k^{k+1} g(x)dx is equal to some constant c for all k.  If c=0,
then the area under the entire curve will be zero, and if c>0, then the
area under the entire curve will be infinite, both of which contradict
the requirement that the integral of a probability distribution be 1.
At one point Jackson et al raise the possibility of infinitesimal
probabilities, but if this is interpreted as allowing c to be
infinitesimal, the suggestion does not work any better.  To see this,
note that if the distribution is uniform:

  \int_0^\infty g(x) dx
      = \int_0^1 g(x)dx + \int_1^2 g(x)dx + \int_2^3 g(x)dx + \cdots
      = \int_0^1 g(x)dx + \int_2^3 g(x)dx + \int_4^5 g(x)dx + \cdots
      = 1/2\int_0^\infty g(x)dx,

so that the overall integral must be zero or infinite.  A uniform
distribution over the real numbers can only be an "improper"
distribution, whose overall integral is not 1.

The impossibility of a uniform probability distribution over the real
numbers is reflected in the fact that every proper distribution must
eventually "taper off": for all \epsilon > 0, there must exist k such
that \int_k^\infty g(x) dx < \epsilon.  It is very tempting to suppose
that this "tapering off" supplies the resolution to the paradox, as it
seems to imply that if A is near the high end of the (proper)
distribution, it will be more likely that B is smaller; perhaps
sufficiently more likely to offset the paradoxical reasoning?  This is
the conclusion that Castell and Batens draw.  They offer a "proof" that
the distribution must be improper for the paradoxical reasoning to be
possible.

Unfortunately Castell and Batens' proof is mistaken, and in fact there
exist proper distributions for which the paradoxical reasoning is
possible.  The error lies in their assumption, early in the paper, that
p(B>A|A=n) = \frac{g(n)}{g(n) + g(n/2)}.  This seems intuitively
reasonable, but in fact p(B>A|A=n) = \frac{2g(n)}{2g(n) + g(n/2)},
which is significantly larger in general.

To see this, note that if A is in the range n \pm dx, then B is either
in the range 2n \pm 2dx or in the range n/2 \pm dx/2.  The probability
of the first, relative to the initial distribution, is g(n)dx; the
probability of the second is g(n/2)dx/2.  The probabilities that B is
greater or less than A therefore stand in the ratio 2g(n):g(n/2), not
g(n):g(n/2), as Castell and Batens suppose.

For example, given a uniform distribution between 0 and 1000, if A is
around 100, it is in fact twice as likely that B is around 200 than
that B is around 50.  To dispel any lingering counterintuitiveness,
note that something like this _has_ to be the case to make up for the
fact that when A > 500, B is always less than A.  To find a
distribution where the chances of a gain and a loss are truly equal for
many n, we should turn not to a uniform distribution but to a
decreasing distribution, where g(n/2) = 2g(n) for many n.  An example
is the distribution g(x) = 1/x, where we cut off the distribution
between arbitrary bounds L and U, and normalize so that it has an
integral of 1.  This distribution will have the property that for all n
such that 2L < n < U/2, p(B>A|A=n) = 0.5.  To illustrate this
intuitively, note that for such a decreasing distribution, the prior
probability that the smaller value is between 4 and 8 is the same as
the probability that it is between 8 and 16, and so on, if L and U are
appropriate.  Given the information that 8 < A < 16, it is equally
likely that B is in the range above or below.

This flaw in Castell and Batens' reasoning nullifies their proof that a
distribution must be improper for the paradoxical reasoning to arise,
but it does not yet show that the conclusion is false.  It remains open
whether there is a proper distribution for which the paradoxical
reasoning is possible.  The bounded distribution above will not work,
as its bound will block the paradoxical reasoning in the usual fashion;
and the _unbounded_ distribution g(x) = 1/x is improper, having an
infinite integral.  But this can easily be fixed, by allowing the
distribution to taper off slightly faster.  In particular, the
distribution g(x) = x^{-1.5}, cut off below a lower bound L and
normalized, allows the paradox to arise.  The distribution has a finite
integral, and even though for most n, p(B>A|A=n) < 0.5, it is still
the case that for all relevant n, E(B|A=n) > n.  To see this, note that
if n < 2L, then E(B|A=n) = 2n; and if n >= 2L, then

  p(B>A|A=n) : p(B<A|A=n) = 2g(n):g(n/2)
                          = 2n^{-1.5}:(n/2)^{-1.5}
                          = 1:\sqrt{2}.

The expected value E(B|A=n) is (2n+\sqrt{2}n/2)/(1+\sqrt{2}), which is
about 1.12n.  The paradox therefore still arises.

The distribution here may be unintuitive, but it is easy to illustrate
a similar distribution intuitively.  Take a distribution in which the
probability of a value between 1 and 2 is c, the probability of a value
between 2 and 4 is just slightly less, say 0.9c, the probability of a
value between 4 and 8 is 0.81c, and so on.  This distribution has a
finite integral, as the integral is the sum of a decreasing geometric
series; and it is sufficiently close to the case in which the
probability of a value between 2^k and 2^{k+1} is constant that the
paradoxical reasoning still arises.  Even though p(B < A|A=n) is now
slightly less than 0.5, due to the incorporated factor of 0.9, it has
decreased by a sufficiently small amount that E(B|A=n) remains greater
than n.  The case g(x) = x^{-1.5} is just like this, except that the
factor of 0.9 is replaced by a factor of 1/\sqrt{2}, which is around
0.7.

The paradox has therefore not yet been vanquished; there are perfectly
proper distributions for which the paradoxical reasoning still applies.
This leads us to the third and final step in the resolution of the
paradox.  Note that although the distributions above have finite
integrals, as a probability distribution should, they have infinite
_expected value_.  The expected value of a distribution is
\int_0^\infty xg(x)dx.  When g(x) = x^{-1.5} (cut off below L), the
expected value is \int_L^\infty x^{-0.5} dx, which is infinite.  But if
the expected value of the distribution is infinite, there is no
paradox!  There is no contradiction between the facts that E(B) = 1.12
E(A) and E(A) = 1.12 E(B) if both E(A) and E(B) are infinite.  Rather,
we have just another example of a familiar phenomenon, the strange
behavior of infinity.[*]

  [*] Castell and Batens note some similar consequences of infinite
  expected values in another context, in which the distribution is over
  a countable set.  They say that infinite expected values are
  "absurd", but I do not see any mathematical absurdity.

To fully resolve the paradox, we need only demonstrate that for
distributions with finite expected value, the paradoxical situation
does not arise.  To do this, we need to precisely state the conditions
expressing the paradoxical situation.  In its strongest form, the
paradoxical situation arises when E(B|A=n) > n for all n.  However, it
arises more generally whenever reasoning from B's dependence on A leads
us to the conclusion that there is expected gain _on average_ (rather
than all the time) by switching A for B.  This will hold whenever
E(K-A) > 0, where K is the random variable derived from A by the
transformation x \mapsto E(B|A=x).  We therefore need to show that when
E(A) is finite, E(K-A) = 0.

Let h be the density function of A.  Then h(x) = 1/2.(g(x) + g(x/2)/2)
= 1/4.(2g(x)+g(x/2)).  (Note that h \neq g, as g is the density
function of the _smaller_ value.)  Then

  E(K-A) = \int_0^\infty h(x) (E(B|A=x) - x) dx
         = \int_0^\infty \frac{2g(x) + g(x/2)}{4}.
             (\frac{2x.2g(x) + x/2.g(x/2)}{2g(x)+g(x/2)} - x) dx
         = \int_0^\infty \frac{2xg(x) - x/2.g(x/2)}{4} dx
         = 1/4.(\int_0^\infty 2xg(x)dx - \int_0^\infty 2yg(y)dy)
         = 0.

Note that the fourth and fifth steps above are valid only if
\int_0^\infty xg(x)dx is finite, which holds iff E(A) is finite.  (If
\int_0^\infty xg(x)dx is infinite, it is possible that \int_0^\infty
2xg(x)-x/2.g(x/2)dx \neq 0, even though \int_0^\infty 2xg(x)dx =
\int_0^\infty x/2.g(x/2) dx.)

It follows that when E(A) is finite, consideration of the dependence of
B on A will not lead one to the conclusion that one should switch A for
B.  A corollary of the result is that when E(A) is finite, it is
impossible that E(B|A=n) > n for all n, so that the strong form of the
paradox certainly cannot arise.

If E(A) is infinite, this result does not hold.  In such a case, it is
possible that E(A) = E(K) (both are infinite) but that E(K-A) > 0.
Here, the "paradoxical" reasoning will indeed arise.  But now the
result is no longer paradoxical; it is merely counterintuitive.  It is
a consequence of the fact that given infinite expectations, _any_ given
finite value will be disappointing.  The situation here is somewhat
reminiscent of the classical St. Petersburg paradox: both "paradoxes"
exploit random variables whose values are always finite, but whose
expected values are infinite.  The combination of finite values with
infinite expected values leads to counterintuitive consequences, but we
cannot expect intuitive results where infinity is concerned.[*]

  [*] I first learned of this paradox from Doug Hofstadter in 1988.  I
  reached the conclusions contained in this paper in discussion with
  Hofstadter and a number of others in 1988 and 1989.  The appearance
  of the problem in a philosophical journal prompts me to write up the
  analysis.

References

[1] P. Castell and D. Batens, `The Two-Envelope Paradox: The Infinite
    Case'.  _Analysis_ 54:46-49.

[2] F. Jackson, P. Menzies, and G. Oppy, `The Two Envelope
    "Paradox"', _Analysis_ 54:43-45.

-- David J. Chalmers <chalmers@paradox.ucsc.edu>

Hm.

I think I was too hasty in endorsing Chalmers' analysis.

I do not agree with the last few paragraphs.  And in particular, I do
not agree with the conclusion that there is no paradox but only a
counterintuitive result.

I think I'd better post the discrete distribution I mentioned earlier,
since it's easy enough and will save some people looking it up in
_Analysis_.  I'll use the convention n**m for "n raised to the mth
power."

Suppose the envelopes are filled like this.  First, a *smaller* amount,
s, is chosen from the distribution pr(s=2**n) = 2**n / 3**(n+1).

[We let n range over the non-negative integers.  That is, a number of
dollars is chosen, assigning to each power of two a finite probability
of being chosen.  For example, the chance that $8 is chosen, since
8=2**3, is 8/81.]

Note that this probability distribution is well-behaved in that the sum
of the probabilities of all the disjoint possibilities is one.

The second envelope is stuffed with twice as much money as the first.

Now, if you pick an envelope at random from the pair and look inside
and find a certain amount, say $8, the chance that the other envelope
contains twice as much is only 2/5.  The expectation of switching,
then, if you've found $x, is

2/5($2x) + 3/5($x/2) = $ 11x/10.

This is greater than the expectation of keeping your envelope, no
matter what you find.

Chalmers says that there is no paradox here, because the *prior*
expected value of switching is infinite, and so is the prior expected
value of keeping.  (That is to say, before you look in your envelope,
your expected value is infinite for playing the game no matter whether
you plan to keep or switch.)  Well, the expectations *are* infinite,
but I don't see how this is supposed to resolve the paradox.

The question is what you are supposed to do.  And we have found that
conditional on any given amount you find in your envelope, the
expectation of switching is finite and greater than the expectation of
keeping.  This looks like an awfully compelling reason to switch.  Yet
the advice always to switch is absurd.  It could not possibly be better
to pick an envelope at random and then switch, than it would be to pick
an envelope at random and keep it.

I would be wary of any argument which depended on the player's
comparing two infinite expected values.  (I am not even exactly sure
what an infinite expected value is supposed to be.  I would put things
a bit differently: the prior expected value *does not exist*, it is
undefined.)  But the present argument does not need to mention those
aberrant values.  It can rest on the *conditional* expectations,

E(switch | find x).

And all of those are finite and well-defined.

-- Jamie Dreier <pl436000@brownvm.brown.edu>, January 1997

[ Editor: a proposed solution of Martin Gardner's necktie paradox, May
1996. ]

The problem.

Red and Green wear a tie eachone. Red neither knows the value of its
tie, nor the value of Green's tie. The same for Green. The following
bet is done. After checking the value of both ties in a store, the man
wearing the cheaper tie will win the other (more expensive) tie. Red
thinks this bet is favorable to him: "I have the same probability to
win and to lose.  If I lose, I lose my tie, but if I win, I win a more
expensive tie". But also Green thinks the same. The question is: how
can the same bet be favorable to both (opposite) men?

-----------------------------
First of all a few hypotheses in order to formalize it.

1) Red knows that values of his tie are distributed between a minimum
and a maximum positive finite values, MIN and MAX (in dollars). He
don't know what is the probability distribution (or probability
function, if we consider a finite probability space, e.g. the space of
integers between MIN and MAX), but knows that the same probability
distribution also applies to values of Green's tie. Green knows exactly
the same.

2) After checking the value of both ties in a store, the man wearing
the cheaper tie will win the other (more expensive) tie.

-----------------------------
And now my tentative solution. Can readers check and comment it?

I'll call R the values of Red's tie and G the values of Green's tie.
Now, since R and G are not constants, but values (samples) distributed
in a certain (unknown) way between MIN and MAX, it makes no sense to
use directly them in a formula in order to compute the expected gain.

If Red say, for example:

"Since i have the same probability, 1/2, to win and to lose, my
expected net gain is:

0.5 * G - 0.5 * R = 0.5 (G - R)"

this is not correct, since, in the above formula, it makes no sense to
multiply G or R by 0.5, nor to subtract G from R. You can find a
discussion about this topic in the response to the "two envelopes
paradox" (see the rec.puzzles archive in decision/envelope.s).

So, it is true that when Red wins, he wins a more expensive tie than
his own tie, but that do not necessarily mean that the bet is
favorable to him. We have to compute a correct expected net gain to
solve the problem.

(Note. As you can see in the following, the problem is completely
different from "two envelope paradox".)

We don't know the probability distributions of R values and G values,
but what we need to compute the expected net gain are not these
distributions, but:

1) when Red wins, the conditional distribution of G given G > R; I'll
indicate this distribution with f(G|G>R);
2) when Red loses, the conditional distribution of R given R > G; I'll
indicate this function with f(R|R>G).

Note that G and R in the above distributions are still "distributed"
between MIN and MAX.

Red can compute this expected net gain value:

  / MAX                    / MAX
  |      G f(G|G>R) dG  -  |       R f(R|R>G) dR
  / MIN                    / MIN

Obviously, since we don't know the distributions of R and G, we cannot
know the conditional distribution above.

But note that, since the distribution of R and the distribution of G
are equal, f(G|G>R) and f(R|R>G) are equal too, so the expected net
gain value is zero.

QED.

-- Gian Carlo Macchi <macchi@marina.scn.de>