326 lines
16 KiB
Markdown
326 lines
16 KiB
Markdown
---
|
||
created_at: '2015-11-29T11:28:33.000Z'
|
||
title: The envelope paradox (2006)
|
||
url: http://blog.plover.com/math/envelope.html
|
||
author: olalonde
|
||
points: 43
|
||
story_text:
|
||
comment_text:
|
||
num_comments: 74
|
||
story_id:
|
||
story_title:
|
||
story_url:
|
||
parent_id:
|
||
created_at_i: 1448796513
|
||
_tags:
|
||
- story
|
||
- author_olalonde
|
||
- story_10644381
|
||
objectID: '10644381'
|
||
year: 2006
|
||
|
||
---
|
||
[Source](https://blog.plover.com/math/envelope.html "Permalink to The Universe of Discourse : The envelope paradox")
|
||
|
||
# The Universe of Discourse : The envelope paradox
|
||
|
||
# [The Universe of Discourse][1]
|
||
|
||
| ----- |
|
||
|
|
||
|
||
|
||
Mark Dominus (陶敏修)
|
||
[mjd@plover.com][2]
|
||
|
||
![][3]
|
||
|
||
[RSS][4] [Atom][5]
|
||
|
||
[12 recent entries][1]
|
||
|
||
| [The many faces of the Petersen graph][6]
|
||
| [Shitpost roundup, 2018-01][7]
|
||
| [Sapporo has closed][8]
|
||
| [The rubber duck explains coherence spaces][9]
|
||
| [Samuel Johnson and Ossian][10]
|
||
| [The gods of Stackexchange karma are fickle][11]
|
||
| [I forgot there are party conventions][12]
|
||
| [Presidential tax return disclosure][13]
|
||
| [England in a pother in 1533][14]
|
||
| [Plutonium collection][15]
|
||
| [How do plutonium-powered pacemakers work?][16]
|
||
| [The horn of mead][17]
|
||
|
||
Archive:
|
||
|
||
| ----- |
|
||
| [2018][18]: [J][19][F][20]
|
||
| [2017][18]: [J][21][F][22][M][23][A][24][M][25][J][26]
|
||
| [J][27][A][28][S][29][O][30][N][31][D][32]
|
||
| [2016][33]: J[F][34][M][35][A][36][M][37][J][38]
|
||
| [J][39]ASO[N][40][D][41]
|
||
| [2015][42]: JF[M][43][A][44][M][45][J][46]
|
||
| [J][47][A][48][S][49][O][50][N][51][D][52]
|
||
| [2014][53]: [J][54][F][55][M][56][A][57]MJ
|
||
| [J][58]ASO[N][59][D][60]
|
||
| [2013][61]: JFMAMJ
|
||
| [J][62]A[S][63][O][64]N[D][65]
|
||
| [2012][66]: [J][67][F][68][M][69]AMJ
|
||
| J[A][70]SON[D][71]
|
||
| [2011][72]: JFMA[M][73][J][74]
|
||
| JASO[N][75]D
|
||
| [2010][76]: [J][77]FMAMJ
|
||
| J[A][70][S][78][O][79][N][80]D
|
||
| [2009][81]: [J][82][F][83][M][84]A[M][85][J][86]
|
||
| [J][87]A[S][88]ON[D][89]
|
||
| [2008][90]: [J][91][F][92][M][93][A][94][M][95][J][96]
|
||
| [J][97]A[S][98][O][99][N][100]D
|
||
| [2007][101]: [J][102][F][103][M][104][A][105][M][106][J][107]
|
||
| [J][108][A][109][S][110][O][111][N][112][D][113]
|
||
| [2006][114]: [J][115][F][116][M][117][A][118][M][119][J][120]
|
||
| [J][121]A[S][122][O][123][N][124][D][125]
|
||
| [2005][126]: [O][127][N][128][D][129]
|
||
|
||
|
||
|
||
* * *
|
||
|
||
Subtopics:
|
||
|
||
| ----- |
|
||
| [Mathematics][130]139
|
||
| [Programming][131]60
|
||
| [Language][132]34
|
||
| [Cosmic Call][133]25
|
||
| [Misc][134]24
|
||
| [Book][135]23
|
||
| [Physics][136]20
|
||
| [Oops][137]20
|
||
| [Unix][138]20
|
||
| [Tech][139]19
|
||
| [Linogram][140]14
|
||
| [Perl][141]14
|
||
| [Biology][142]10
|
||
| [CS][143]10
|
||
| [Calendar][144]10
|
||
| [Meta][145]9
|
||
|
||
![][146] ![Higher-Order Perl][147] ![Blosxom][148]
|
||
|
||
Comments disabled
|
||
|
||
|
|
||
Fri, 16 Jun 2006
|
||
|
||
[The envelope paradox][149]
|
||
[Addendum 20151130: I have since written this up in greater and more formal detail. If you find the details here lacking, please consult [my math.se post about it][150].]
|
||
|
||
This is on my mind because someone asked about it in IRC yesterday and I was surprised at how coherently I was able to explain it on the spur of the moment. There are several versions of this paradox. My favorite version goes like this: you're going to play a game with an adversary. The adversary writes two different numbers on slips of paper and puts them in an envelope. The numbers are completely arbitrary; they could be absolutely any numbers whatsoever: zero, or π, or -1428573901823.00013, or anything else.
|
||
|
||
You pick one slip at random from the envelope and examine the number written on it. You then make a prediction about whether the _other_ number is larger or smaller. If your prediction is correct, you win a dollar; if it is incorrect, you lose a dollar.
|
||
|
||
Clearly, you can break even in the long run simply by making your prediction at random. And it seems just just as clear that there is no strategy you can use that does better than breaking even. But this is the paradox: there _is_ a strategy you can use that does better than breaking even. (This is what W.V.O. Quine calls a "veridical paradox": it's something that seems impossible, but is nevertheless true.)
|
||
|
||
Spoilers follow, so you might want to stop reading here for twenty-four hours and try to figure out a winning strategy yourself.
|
||
|
||
* * *
|
||
|
||
Let's call the number you get from the envelope _A_ and the number still in the envelope _B_. You can see _A_, and you are trying to predict whether _B_ is larger or smaller than _A_.
|
||
|
||
Here's your winning strategy. Before you see _A_, choose a random number _R_. If _A_ < _R_, then conclude that _A_ is "small", and predict that _B_ is larger. If _A_ > _R_, make the opposite prediction.
|
||
|
||
There are three possibilities. Either (1) _A_ and _B_ are both less than _R_, or (2) they are both greater than _R_, or else (3) one is less than _R_ and one is greater.
|
||
|
||
In case 1, you predict that _B_ > _A_, and you have a 50% probability of being correct. In case 2, you predict that _B_ < _A_, and you have a 50% probability of being correct.
|
||
|
||
But in case 3, you win _every time_! If _A_ < _R_ < _B_ then you see _A_, conclude that _A_ is "small", and predict that _B_ > _A_, which is correct; if _B_ < _R_ < _A_ then you see _A_, conclude that _A_ is "large", and predict that _B_ < _A_, which is correct.
|
||
|
||
Since you're breaking even in cases 1 and 2, and you have a guaranteed win in case 3, you have a better-than-even chance of winning overall. There's some positive probability _p_ (which depends on the method you use to choose _R_) that you have case 3, and if so, then your expected positive return on the game is _p_ dollars per game.
|
||
|
||
The paradoxical part is that it initially seems as though you can't get any idea, just from looking at _A_, of whether it's larger or smaller than the unknown number _B_. But you can get such an idea, because you can tell from looking at _A_ how big it is, and big numbers are more likely to be larger than _B_ than small numbers are.
|
||
|
||
What you've done with _R_ is to invent a definition of "large" and "small" numbers: numbers larger than _R_ are "large" and those smaller than _R_ are "small". It's an arbitrary definition, and it doesn't always succeed in distinguishing large from small numbers—it thinks that _R_+1 and 1000000_R_+1000000 are both "large"—but it can distinguish _some_ large numbers from _some_ small numbers, and it never gets confused and concludes that _x_ is large and _y_ is small when _x_ is actually smaller than _y_. So it may be arbitrary, and extremely coarse, but it is never actually wrong.
|
||
|
||
In the cases where this very coarse method of deciding "large" from "small" fails to distinguish _A_ from _B_, you get no new information, but that's okay, because you can still break even. But if you get lucky and the adversary has chosen numbers that you can distinguish, then you win.
|
||
|
||
Another way to look at the paradox is like this: suppose the adversary is required to choose his two numbers at random. Then you have a simple winning strategy: if _A_ is positive, predict that _B_ is smaller, and if _A_ is negative, predict that _B_ is larger. Even when both numbers are positive or both are negative, you win half the time; if one is positive and one is negative, you are guaranteed a win.
|
||
|
||
If the adversary knows that this is what you are doing, he can cut you back to merely breaking even, by limiting himself to always choosing positive numbers. But you can foil this strategy of his by choosing your "positive" and "negative" classes to be divided somewhere other than at 0: instead of "positive" being "> 0" and "negative" being "< 0", you make them mean "> _R_" and "< _R_". The adversary still wants to choose two numbers that are always positive, but since he doesn't know how big _R_ is, hw doesn't know how large he has to make his own numbers to get them both to be "positive".
|
||
|
||
Still, this suggests the best strategy for the adversary: choose two very very large numbers that are close together. By doing this, he can make your expected win close to zero.
|
||
|
||
The envelope paradox is often presented in a different form: you are given two envelopes. One contains a bunch of money, say _x_ dollars. The other contains twice as much. You open one envelope at random and examine its contents. Then you choose one envelope to keep.
|
||
|
||
A naïve analysis goes like this: I open the first envelope and see _x_. I can keep this envelope and collect amount _x_. If I switch, I have a 50% chance of ending up with 2_x_ and a 50% chance of ending up with _x_/2, for an expected outcome of 5_x_/4. Since 5_x_/4 > _x_, I should _always_ switch.
|
||
|
||
This is what Quine calls a "falsidical paradox": the reasoning seems good, but leads to an impossible conclusion. The strategy of always switching can't possibly be correct, because you could apply it with without even seeing what is in the envelope. You could keep switching back and forth all day, never opening either envelope, and increasing your expected winnings to infinity.
|
||
|
||
The tricky part, again, is that having seen _x_ in the envelope, you cannot conclude that there is exactly a 50% chance of _x_ being the larger of the two amounts. You get some information from the size of _x_, and if _x_ is a large amount of money, then the probability that _x_ is the larger of the two amounts is thereby greater than 0.5.
|
||
|
||
To do a full analysis, one has to ask the question of how the original amounts were selected. Say that the two amounts are _b_ and 2_b_; let's call _b_ the "base amount". How did the adversary select _b_? Let's say that the probability of the base amount being any particular amount _x_ is _P_(_x_). It is impossible that _b_ has an equal probability of being every number, because $$int_{-infty}^infty P(x) dx$$ is required to be 1, and if _P_(_b_) is the same for every possible base amount _b_, then it is a constant function, and constant functions do not have the required property.
|
||
|
||
When you see _x_ in the envelope, you know that one of two situations occurred. Either _x_ is the base amount, and so is smaller, which occurs with probability _P_(_x_), or _x_/2 is the base amount, and _x_ itself is the larger, which occurs with probability _P_(_x_/2).
|
||
|
||
Since these are the only possibilities, the a posteriori likelihood that _x_ is the smaller number is _P_(_x_)/(_P_(_x_/2) + _P_(_x_)). This is equal to 1/2 only if _P_(_x_) = _P_(_x_/2). Although this can occur for particular values of _x_, it can't be true for every _x_. As _x_ increases, _P_(_x_) approaches zero, so for sufficiently large _x_, we must have _P_(_x_/2) > _P_(_x_), so _P_(_x_/2) + _P_(_x_) > 2_P_(_x_), and _P_(_x_)/(_P_(_x_/2) + _P_(_x_)) < _P_(_x_)/2_P_(_x_) = 1/2.
|
||
|
||
|
||
|
||
[_[Other articles in category /math][151]] [permanent link][149]_
|
||
|
||
|
||
|
|
||
|
||
[1]: https://blog.plover.com/
|
||
[2]: mailto:mjd%40plover.com
|
||
[3]: https://pic.blog.plover.com/TOP.jpg
|
||
[4]: https://blog.plover.com/index.rss
|
||
[5]: https://blog.plover.com/index.atom
|
||
[6]: https://blog.plover.com/math/petersen-graph.html
|
||
[7]: https://blog.plover.com/meta/shitpost/roundup-2018-01.html
|
||
[8]: https://blog.plover.com/food/sapporo.html
|
||
[9]: https://blog.plover.com/math/logic/coherence-spaces.html
|
||
[10]: https://blog.plover.com/book/ossian.html
|
||
[11]: https://blog.plover.com/math/math-se-gods.html
|
||
[12]: https://blog.plover.com/oops/tax-return-dislosure.html
|
||
[13]: https://blog.plover.com/politics/tax-return-disclosure.html
|
||
[14]: https://blog.plover.com/history/1533.html
|
||
[15]: https://blog.plover.com/tech/plutonium-collection.html
|
||
[16]: https://blog.plover.com/tech/seebeck-effect.html
|
||
[17]: https://blog.plover.com/oops/horn-of-saltwater.html
|
||
[18]: https://blog.plover.com/2017/
|
||
[19]: https://blog.plover.com/2018/01/
|
||
[20]: https://blog.plover.com/2018/02/
|
||
[21]: https://blog.plover.com/2017/01/
|
||
[22]: https://blog.plover.com/2017/02/
|
||
[23]: https://blog.plover.com/2017/03/
|
||
[24]: https://blog.plover.com/2017/04/
|
||
[25]: https://blog.plover.com/2017/05/
|
||
[26]: https://blog.plover.com/2017/06/
|
||
[27]: https://blog.plover.com/2017/07/
|
||
[28]: https://blog.plover.com/2017/08/
|
||
[29]: https://blog.plover.com/2017/09/
|
||
[30]: https://blog.plover.com/2017/10/
|
||
[31]: https://blog.plover.com/2017/11/
|
||
[32]: https://blog.plover.com/2017/12/
|
||
[33]: https://blog.plover.com/2016/
|
||
[34]: https://blog.plover.com/2016/02/
|
||
[35]: https://blog.plover.com/2016/03/
|
||
[36]: https://blog.plover.com/2016/04/
|
||
[37]: https://blog.plover.com/2016/05/
|
||
[38]: https://blog.plover.com/2016/06/
|
||
[39]: https://blog.plover.com/2016/07/
|
||
[40]: https://blog.plover.com/2016/11/
|
||
[41]: https://blog.plover.com/2016/12/
|
||
[42]: https://blog.plover.com/2015/
|
||
[43]: https://blog.plover.com/2015/03/
|
||
[44]: https://blog.plover.com/2015/04/
|
||
[45]: https://blog.plover.com/2015/05/
|
||
[46]: https://blog.plover.com/2015/06/
|
||
[47]: https://blog.plover.com/2015/07/
|
||
[48]: https://blog.plover.com/2015/08/
|
||
[49]: https://blog.plover.com/2015/09/
|
||
[50]: https://blog.plover.com/2015/10/
|
||
[51]: https://blog.plover.com/2015/11/
|
||
[52]: https://blog.plover.com/2015/12/
|
||
[53]: https://blog.plover.com/2014/
|
||
[54]: https://blog.plover.com/2014/01/
|
||
[55]: https://blog.plover.com/2014/02/
|
||
[56]: https://blog.plover.com/2014/03/
|
||
[57]: https://blog.plover.com/2014/04/
|
||
[58]: https://blog.plover.com/2014/07/
|
||
[59]: https://blog.plover.com/2014/11/
|
||
[60]: https://blog.plover.com/2014/12/
|
||
[61]: https://blog.plover.com/2013/
|
||
[62]: https://blog.plover.com/2013/07/
|
||
[63]: https://blog.plover.com/2013/09/
|
||
[64]: https://blog.plover.com/2013/10/
|
||
[65]: https://blog.plover.com/2013/12/
|
||
[66]: https://blog.plover.com/2012/
|
||
[67]: https://blog.plover.com/2012/01/
|
||
[68]: https://blog.plover.com/2012/02/
|
||
[69]: https://blog.plover.com/2012/03/
|
||
[70]: https://blog.plover.com/2010/08/
|
||
[71]: https://blog.plover.com/2012/12/
|
||
[72]: https://blog.plover.com/2011/
|
||
[73]: https://blog.plover.com/2011/05/
|
||
[74]: https://blog.plover.com/2011/06/
|
||
[75]: https://blog.plover.com/2011/11/
|
||
[76]: https://blog.plover.com/2010/
|
||
[77]: https://blog.plover.com/2010/01/
|
||
[78]: https://blog.plover.com/2010/09/
|
||
[79]: https://blog.plover.com/2010/10/
|
||
[80]: https://blog.plover.com/2010/11/
|
||
[81]: https://blog.plover.com/2009/
|
||
[82]: https://blog.plover.com/2009/01/
|
||
[83]: https://blog.plover.com/2009/02/
|
||
[84]: https://blog.plover.com/2009/03/
|
||
[85]: https://blog.plover.com/2009/05/
|
||
[86]: https://blog.plover.com/2009/06/
|
||
[87]: https://blog.plover.com/2009/07/
|
||
[88]: https://blog.plover.com/2009/09/
|
||
[89]: https://blog.plover.com/2009/12/
|
||
[90]: https://blog.plover.com/2008/
|
||
[91]: https://blog.plover.com/2008/01/
|
||
[92]: https://blog.plover.com/2008/02/
|
||
[93]: https://blog.plover.com/2008/03/
|
||
[94]: https://blog.plover.com/2008/04/
|
||
[95]: https://blog.plover.com/2008/05/
|
||
[96]: https://blog.plover.com/2008/06/
|
||
[97]: https://blog.plover.com/2008/07/
|
||
[98]: https://blog.plover.com/2008/09/
|
||
[99]: https://blog.plover.com/2008/10/
|
||
[100]: https://blog.plover.com/2008/11/
|
||
[101]: https://blog.plover.com/2007/
|
||
[102]: https://blog.plover.com/2007/01/
|
||
[103]: https://blog.plover.com/2007/02/
|
||
[104]: https://blog.plover.com/2007/03/
|
||
[105]: https://blog.plover.com/2007/04/
|
||
[106]: https://blog.plover.com/2007/05/
|
||
[107]: https://blog.plover.com/2007/06/
|
||
[108]: https://blog.plover.com/2007/07/
|
||
[109]: https://blog.plover.com/2007/08/
|
||
[110]: https://blog.plover.com/2007/09/
|
||
[111]: https://blog.plover.com/2007/10/
|
||
[112]: https://blog.plover.com/2007/11/
|
||
[113]: https://blog.plover.com/2007/12/
|
||
[114]: https://blog.plover.com/2006/
|
||
[115]: https://blog.plover.com/2006/01/
|
||
[116]: https://blog.plover.com/2006/02/
|
||
[117]: https://blog.plover.com/2006/03/
|
||
[118]: https://blog.plover.com/2006/04/
|
||
[119]: https://blog.plover.com/2006/05/
|
||
[120]: https://blog.plover.com/2006/06/
|
||
[121]: https://blog.plover.com/2006/07/
|
||
[122]: https://blog.plover.com/2006/09/
|
||
[123]: https://blog.plover.com/2006/10/
|
||
[124]: https://blog.plover.com/2006/11/
|
||
[125]: https://blog.plover.com/2006/12/
|
||
[126]: https://blog.plover.com/2005/
|
||
[127]: https://blog.plover.com/2005/10/
|
||
[128]: https://blog.plover.com/2005/11/
|
||
[129]: https://blog.plover.com/2005/12/
|
||
[130]: https://blog.plover.com/math/
|
||
[131]: https://blog.plover.com/prog/
|
||
[132]: https://blog.plover.com/lang/
|
||
[133]: https://blog.plover.com/aliens/dd/
|
||
[134]: https://blog.plover.com/misc/
|
||
[135]: https://blog.plover.com/book/
|
||
[136]: https://blog.plover.com/physics/
|
||
[137]: https://blog.plover.com/oops/
|
||
[138]: https://blog.plover.com/Unix/
|
||
[139]: https://blog.plover.com/tech/
|
||
[140]: https://blog.plover.com/linogram/
|
||
[141]: https://blog.plover.com/prog/perl/
|
||
[142]: https://blog.plover.com/bio/
|
||
[143]: https://blog.plover.com/CS/
|
||
[144]: https://blog.plover.com/calendar/
|
||
[145]: https://blog.plover.com/meta/
|
||
[146]: https://pic.blog.plover.com/buttons/mjd-universe.png
|
||
[147]: https://pic.blog.plover.com/buttons/HOP-BUTTON.png
|
||
[148]: https://pic.blog.plover.com/buttons/blosxom-sux.png
|
||
[149]: https://blog.plover.com/math/envelope.html
|
||
[150]: http://math.stackexchange.com/a/656426/25554
|
||
[151]: https://blog.plover.com/math
|
||
|