\problemdata                                                             
        {gambling game} % latex-friendly label for the prob.
        {expected values} % The topic(s) of the problem content.  
        {Peter Winkler Seminar 2001} % Source (if known)         
        {S01 Tutorial 13, 1} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Consider the following game.  I start with $X$ dollars, you start with $Y$
dollars.  In a round, we each wager any amount of dollars up to what we have.
Then we flip a biased coin.  If I wager $x$ and you wager $y$, then I win with
probability $\frac{x}{x+y}$, while you win with probability
$\frac{y}{x+y}$. Whoever wins a coin flip gets all the money wagered on that
flip.  The game ends when someone goes broke.  Calculate the probability that I
win.

(Hint: This question does not specify a particular wagering strategy.)

\solution{
In a particular round, I win $y$ dollars with probability $\frac{x}{x+y}$ and
lose  $x$ dollars with probability $\frac{y}{x+y}$.  Therefore, my expected 
return on a particular wager is 
\[
\Ex[\mathrm{Return\ on\ 1\ wager}] =\Pr[\mathrm{win}] \cdot \mathrm{profit} -
\Pr[\mathrm{loss}] \cdot \mathrm{loss} =
\frac{x}{x+y}\cdot y - \frac{y}{x+y}\cdot x = 0
\]
Therefore, after each wager, I expect to have the same number of
dollars as I had before it.  Intuitively, if our expected profit is
invariantly 0 for every wager, we can use linearity of expectations to
conclude that the expected profit for the whole game is 0.

However, a game will continue for a random number of rounds before concluding.
So formalizing this intuition becomes slightly more complicated.
Let $Q$ be a random variable for the length of the game in rounds.
($Q$ will depend on a number of things including the players'
strategies and the results of each wager until the game ends.)

Let $X_i$, be a random variable for the number of dollars I have before
round $i$.  Let $p_i$ be the profit for round $i$. So
$X_i = X + p_1 + p_2 + \ldots p_{i-1}$
and my profit at the end of the game is
\[
X_{Q+1} - X = \sum_{i=1}^Q p_i
\]
By the law of total probability, my expected profit is 
\[
\Ex[X_{Q+1}] - X = \Ex \left [\sum_{i=1}^Q p_i \right ] = \sum_{q=1}^\infty \left(\Ex \left[
\sum_{i=1}^q p_i \biggm| \{Q=q\} \right ] \Pr[Q=q] \right)
\]
But we just proved above that
\[ \Ex \left[ \sum_{i=1}^q p_i \biggm| \{Q=q\} \right ] = 0 \]
(this follows since we proved above that the expected return on any
wager is 0 given that the game is still running before the wager is
made).  So the whole sum and, thus, my total expected profit, is equal
to~0.

We can now use the expected return on the game to calculate the probability of
winning. If I win the game, I win $Y$ dollars.  If I lose the game, I lose $X$
dollars.  So, by the definition of expectation
\[\Ex[\mathrm{Return\ on\ game}] = \Pr[\mathrm{win}] \cdot
\mathrm{profit} - \Pr[\mathrm{loss}] \cdot \mathrm{loss} = 
 p \cdot Y - (1-p) \cdot X = 0.
\]
Solving for $p$ yields my probability of winning: $p = \frac{X}{X+Y}$.
}
\end{problem}
                                 