# Help: rules of a game whose details I don't remember!

In a probability course, a game was introduced which a logical approach won't yield a strategy for winning, but a probabilistic one will. My problem is that I don't remember the details (the rules of the game)! I would be thankful if anyone can complete the description of the game. I give the outline of the game, below.

Some person (A) hides a 100 or 200 dollar bill, and asks another one (B) to guess which one is hidden. If B's guess is correct, something happens and if not, something else (this is what I don't remember). The strange point is, B can think of a strategy so that always ends to a positive amount, but now A can deduce that B will use this strategy, and finds a strategy to overcome B. Now B knows A's strategy, and will uses another strategy, and so on. So, before even playing the game for once, there is an infinite chain of strategies which A and B choose successively!

Can you complete the story? I mean, what happens when B's guess correct and incorrect?

Thanks.

-
You might want to take an introductory course in game theory. The result is very typical in games where player's play against each other (non-cooperative), that is, the ordering of the outcomes of both players are not aligned. You will then see that quite often, a strategy mix with probabilities dominates a strategy mix where you play one with certainty. If your Mathematics department doesn't offer one, check the Economics department. –  FooBar Jun 7 at 15:48

In the Envelope Paradox player 1 writes any two different numbers $a< b$ on two slips of paper. Then player 2 draws one of the two slips each with probability $\frac 12$, looks at its number $x$, and predicts whether $x$ is the larger or the smaller of the two numbers.

It appears at first that no strategy by player 2 can achieve a success rate grater than $\frac 12$. But there is in fact a strategy that will do this.

The strategy is as follows: Player 2 should first select some probability distribution $D$ which is positive everywhere on the real line. (A normal distribution will suffice.) She should then select a number $y$ at random according to distribution $D$. That is, her selection $y$ should lie in the interval $I$ with probability exactly $$\int_I D(x)\; dx.$$ General methods for doing this are straightforward; methods for doing this when $D$ is a normal distribution are well-studied.

Player 2 now draws a slip at random; let the number on it be $x$. If $x>y$, player 2 should predict that $x$ is the larger number $b$; if $x<y$ she should predict that $x$ is the smaller number $a$. ($y=x$ occurs with probability 0 and can be disregarded, but if you insist, then player 2 can flip a coin in this case without affecting the expectation of the strategy.)

There are six possible situations, depending on whether the selected slip $x$ is actually the smaller number $a$ or the larger number $b$, and whether the random number $y$ selected by player 2 is less than both $a$ and $b$, greater than both $a$ and $b$, or in between $a$ and $b$.

The table below shows the prediction made by player 2 in each of the six cases; this prediction does not depend on whether $x=a$ or $x=b$, only on the result of her comparison of $x$ and $y$:

$$\begin{array}{r|cc} & x=a & x=b \\ \hline y < a & x=b & \color{blue}{x=b} \\ a<y<b & \color{blue}{x=a} & \color{blue}{x=b} \\ b<y & \color{blue}{x=a} & x=a \end{array}$$

For example, the upper-left entry says that when player 2 draws the smaller of the two numbers, so that $x=a$, and selects a random number $y<a$, she compares $y$ with $x$, sees that $y$ is smaller than $x$, and so predicts that $x$ is the larger of the two numbers, that $x=b$. In this case she is mistaken. Items in blue text are correct predictions.

In the first and third rows, player 2 achieves a success with probability $\frac 12$. In the middle row, player 2's prediction is always correct. Player 2's total probability of a successful prediction is therefore $$\frac12 \Pr(y < a) + \Pr(a < y < b) + \frac12\Pr(b<y) = \\ \frac12(\color{maroon}{\Pr(y<a) + \Pr(a < y < b) + \Pr(b<y)}) + \frac12\Pr(a<y<b) = \\ \frac12\cdot \color{maroon}{1}+ \frac12\Pr(a<y<b)$$

Since $D$ was chosen to be everywhere positive, player 2's probability $$\Pr(a < y< b) = \int_a^b D(x)\;dx$$ of selecting $y$ between $a$ and $b$ is strictly greater than $0$ and her probability of making a correct prediction is strictly greater than $\frac12$ by half this strictly positive amount.

This analysis points toward player 1's strategy, if he wants to minimize player 2's chance of success. If player 2 uses a distribution $D$ which is identically zero on some interval $I$, and player 1 knows this, then player 1 can reduce player 2's success rate to exactly $\frac12$ by always choosing $a$ and $b$ in this interval. If player 2's distribution is everywhere positive, player 1 cannot do this, even if he knows $D$. But player 2's distribution $D(x)$ must necessarily approach zero as $x$ becomes very large. Since Player 2's edge over $\frac12$ is $\frac12\Pr(a<y<b)$ for $y$ chosen from distribution $D$, player 1 can bound player 2's chance of success to less than $\frac12 + \epsilon$ for any given positive $\epsilon$, by choosing $a$ and $b$ sufficiently large and close together. And even if player 1 doesn't know $D$, he should still choose $a$ and $b$ very large and close together.

I have heard this paradox attributed to Feller, but I'm afraid I don't have a reference.

[ Addendum 2014-06-04: I asked here for a reference, and was answered: the source is Thomas M. CoverPick the largest numberOpen Problems in Communication and Computation Springer-Verlag, 1987, p152. ]

-
Isn't it simpler to produce $y$ by selecting a $\xi \in (0,1)$ uniformly at random and then take $y$ to be the unique real number such that $\int_{-\infty}^y D(x)\,dx = \xi$? Or am I misunderstanding how $y$ is supposed to be chosen? –  kahen Jun 5 at 20:17
That is exactly how we're choosing $y$. I was unsure of the correct jargon for describing this briefly, and I would be grateful if you could tell me what it is. –  MJD Jun 5 at 20:20
@MJD as a programmer I know it as "inverse transform sampling" or as the "inverse transform method" of generating random values from a given distribution –  hobbs Jun 6 at 3:21
(because you make use of it by actually producing the inverse of the integrated distribution function ahead of time, and then plugging in values for ξ on demand) –  hobbs Jun 6 at 3:24
the jargon is perfect, we are sampling from D, no need to use the uniform which is mathematically equivalent –  Sergio Parreiras Jun 6 at 13:29

Are you perhaps thinking of the Two envelopes problem?

-
No. This is not what I'm looking for. –  Behzad Jan 29 at 14:23

A similar thing I rmember: $A$ picks arandom positive number $x$ and writes $x$ and $2x$ on two papers which are then hidden in envelopes. $B$ picks one of the envelopes, opens it, sees a number $y$. Now $B$ does not know whether $y=x$ or $y=2x$ and is asked whether he wants to keep his $y$ or switch to the other envelope, which may conatain either $2y$ or $\frac y2$. Since both variants are obviously equally likely, the expected value of switching is $\frac{2y+\frac y2}{2}>y$, so $B$ should always switch. But: This conclusion does not depend on $y$, so even without reading his number, he could have concluded that switching would be better! So why not switch immediately while picking the envelope in the first place? But with the other envelope, the same argument would apply! - Brain meltdown ...

-
Well, thanks, but It's not exactly what I'm looking for. –  Behzad Jan 29 at 14:27
@Behzad: My guess: the brain meltdown made that you forget that this was the problem. –  Marc van Leeuwen Jan 29 at 14:30
@MarcvanLeeuwen I disagree! Everything in the two envelope problem is probabilistic, not logical. As I said earlier, the game I'm looking for can be approached logically, despite the fact that the logical approach creates a chain of alternating strategies - given that A is smart enough. –  Behzad Jan 29 at 14:38

I think you are combining the two envelopes problem into your problem and that has caused the confusion. I think what you are looking for is something like one of the following:

1) you are talking about game theory of a sort akin to rock paper scissors in this link. http://www.ams.org/bookstore/pspdf/mbk-65-prev.pdf

2) alternatively you are talking about something about many games. As I understand it, if I pick envelope A you get 1 buck ; if I pick B, I win 2 bucks. I've no idea which is which and we play an infinite number of games. I program a computer to pick for me. You have a better computer.

If I tell mine to pick with any set pattern, your computer will figure it out in a finite number of games and then will win the infinite future games. You will win an infinite amount of money and I will only have won a finite number of games.

If I tell mine to pick randomly, your computer will never figure it out so we will both win 50% of games. You will win an infinite amount of money and I will only have won a finite number of games.

-

Probability theory is formalized in first order logic so anything you solve using probability theory is solved using logic. Thus such problem can not exist.

-