\problemdata                                                             
        {Guessing biggest from 2 numbers} % latex-friendly label for the prob.
        {Randomized stragegies, probability} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 11, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Remember the game demonstrated in lecture: David shows you two
envelopes, each lying face down on a table.  He tells you there are
natural numbers between zero and $n$ in each envelope, and the numbers are
not equal.  You choose an envelope, and David shows you the number
written in it.  He now tells you that you can either choose to stay with
that envelope, or switch to the other envelope.  You {\em win} if the
number in the envelope you finally choose is the larger of the two.

\begin{problemparts}

\problempart A \emph{randomized strategy} for you in this game is a function
that, for each number $i$, assigns a probability $p_i$ of switching {\em
given} that the number in the envelope you picked first was $i$.  Prove
that the strategy described in class for winning with probability at least
$1/2 + 1/2n$ is \emph{optimal} for you.  In particular, if David picks $i
\in [0,n-1]$ with uniform probability, and then places $i$ and $i+1$ in
each envelope with equal probability, then your probability of winning is
\emph{at most} $1/2 + 1/2n$.

\solution{Let $p_i$ denote the probability that you switch if you see the
number $i$.  Then, the probability that you win if David picks the pair
$(i,i+1)$ is the probability that you will see the smaller number and
switch, or that you will see the bigger number and stay.  Since the
probability of picking either number is $1/2$, the probability that you
win is
\[(1/2)p_i + (1/2)(1-p_{i+1}).
\]

Then, the probability that you win is:
\[
\sum_{i=0}^{n-1} \frac{1}{n} \left(\frac{1}{2}p_i + \frac{1}{2}(1-p_{i+1})\right)
= \frac{1}{2} + \frac{1}{2n}\sum_{i=0}^{n-1} (p_i-p_{i+1})
= \frac{1}{2} + \frac{1}{2n} (p_0 - p_n) \leq \frac{1}{2} + \frac{1}{2n}
\]
}

\problempart Now suppose the numbers from the problem above are drawn from the
set of all natural numbers, $\naturals$.  Design a randomized strategy for
playing this game such that, no matter what two numbers, $i \neq j$, that
David might pick, you will still have \emph{more} than an even chance of
winning.

\solution{Choose \emph{any} distribution on $\naturals$ with a positive
probability, $p_i$, assigned to each $i \in \naturals$, so that larger
numbers have smaller probability.  For example, let $p_i = 2^{-i-1}$.  Now
suppose that David chooses the pair $\set{i,j}$ with $i<j$.  Then as
above with this randomized strategy, the probability that you win is the
probability that you see $i$ and switch, or that you see $j$ and don't
switch, namely,
\[
\prob{\mbox{win}} = \frac{1}{2}p_i +\frac{1}{2}(1-p_{j}) =  
\frac{1}{2} + \frac{1}{2}(p_i - p_j)  > \frac{1}{2}.
\]


Of course in this case, in contrast to the case when the choice of numbers
is bounded, David can force the probability that you win as close
to---but not equal to---1/2 as he chooses, by choosing sufficiently large
$i,j$,


}

\end{problemparts}
\end{problem}
                                 