\problemdata
{expected value}
{theory pig}
{infinite expectation}
{Eric Ho S02}
\begin{problem}6.042 TA Eric has offered to play a
``fun game'' with Theory Pig, who rarely comes out of his drawer
anymore after all the abuse that he has suffered this term.

\begin{problemparts}
\problempart The game is as follows: Suppose that Eric rolls a fair,
6-sided die.  He offers to pat Theory Pig for the number of days
indicated on the die. If Theory Pig rejects the offer, then Eric rolls
again and pats Theory Pig for the number of days shown on the second
roll. Theory Pig decides to use the following strategy - he accepts
the initial offer with probability $p_k$, given that $k$ is rolled.
What is expected number of patting-days, if Theory Pig uses an optimal
strategy? (Hint: find a formula that yields the expected payoff of any
strategy. Then find out what values for $p_k$ maximize the equation.)

\solution{If Theory Pig always declines the initial offer, then his
expected payoff is $\frac{7}{2}$, the expected roll on a fair, 6-sided
die.  Let $p_k$ be the probability that Theory Pig accepts the initial
offer, given that $k$ is rolled.  Then Theory Pig's expected payoff is

\begin{eqnarray*}
\Ex(\text{patting days})
        & = & \sum_{i=1}^6 \frac{1}{6}\left(p_i \cdot i +
                (1 - p_i) \cdot \frac{7}{2}\right)
\end{eqnarray*}

This sum is maximized by maximizing each term.  Consequently, we
should choose $p_1 = p_2 = p3 = 0$ and $p_4 = p_5 = p_6 = 1$.  That
is, Theory Pig should decline an offer of 3 or less and accept an
offer of 4 or more.  In this case, his expected payoff is
$\frac{17}{4}$.

We can also deduce Theory Pig's strategy directly.  Since his expected
payoff from the second offer is $\frac{7}{2}$, he should accept any
initial offer higher than this and reject any initial offer that is
lower.  
}

\problempart Eric now proposes a different game. Eric flips a coin
until he gets a heads.  Let $n$ be the number of tails preceding the
first heads.  For example, if he flips $TTTH$, then $n = 3$, and if he
flips just $H$, then $n = 0$.  Now Eric offers to pat Theory Pig on
each of the next $3^n$ days.  If Theory Pig declines the offer, then
Eric repeats the coin-tossing experiment and instead pats Theory Pig
on each of next $3^m$ days where $m$ is the number of tails before the
first heads in the second trial. What is the expected number of
patting days if Theory pig decides to (i) always accept the initial
offer (ii) always decline the initial offer?

% As usual, this game sounds great, but Theory Pig is understandably
% nervous.  He wants to determine his best strategy.

\solution{If Theory Pig declines the initial offer, then his expected
payoff is

\begin{eqnarray*}
\Ex(\text{patting days if decline})
        & = & \sum_{i=0}^\infty \frac{1}{2^{i+1}} \cdot 3^i.
\end{eqnarray*}

This summation is infinite.  Therefore, if there is a positive
probability that Theory Pig decines the initial offer, his expected
payoff is infinite.  On the other hand, suppose that there is zero
probability that Theory Pig declines the initial offer; that is, he
always accepts.  Then his expected payoff is

\begin{eqnarray*}
\Ex(\text{patting days if accept})
        & = & \sum_{i=0}^\infty \frac{1}{2^{i+1}} \cdot 3^i.
\end{eqnarray*}

This is the same infinite sum.  Therefore, every strategy is optimal
and gives an infinite expected number of patting days.
%We are still tallying up the precentage of students that solved this
%problem correctly.
}
\end{problemparts}
\end{problem}
