\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{11F}

%% old problem, Expectations, infinite expectations
\begin{problem}
The St.\ Petersburg Casino offers the following game: the gambler bets a
fixed wager, and then the dealer flips a fair coin (dealers do not flip
coins in US casinos, but they do in St.\ Petersburg) until it comes up
heads. The gambler receives \$1 if the coin shows heads the first time,
\$2 if it shows the first head at second toss, and in general $\$2^{k-1}$
if the dealer tosses the coin $k$ times to get the first head.

\begin{problemparts}
\problempart Suppose the fixed wager is \$10.  What is the expected amount of
money that the gambler will win in this game?  Suppose the fixed wager
is \$10,000?

\solution{
Let $V$ be the random variable corresponding to the amount of money
that the gambler is paid by the dealer. The distribution of
$V$ is as follows: for any $n\geq 1$,
\[
\prob{V= 2^{n-1}} = 2^{-n},
\]
where the probability refers to the event that the dealer
tosses $n-1$ tails followed by a head.
The average of $V$ is
\[
\expect{V} = \sum_{n=1}^{\infty} [2^{-n} 2^{n-1}]
= \sum_{n=1}^{\infty} 1/2 = \infty.
\]
So whatever the fixed wager, the gambler expects to win an infinite
amount.}

\problempart What is the probability that the gambler does not lose money in a
game when the fixed wager is \$10,000?

\solution{
The probability of recovering the
money of the wager is only
\begin {eqnarray*}
\prob{V \geq 10,000} & = & \prob{V \geq 2^{14}}\\
& = & \prob{\mbox{dealer flips at least 14 consecutive tails}}\\
& = & 2^{-14} = \frac{1}{16,384}
\end {eqnarray*}
}

\problempart In reality, it would not be reasonable for the gambler to play the
game with the fixed wager at \$10,000.  Why? (\hint Suppose the casino
goes bankrupt.)

\solution{

Above, we concluded that a \$$10,000$ wager still ``makes sense''
because the expected amount of money (payoff) that the gambler will get
from the casino is infinite. However, in reality, the casino can only
pay back a certain amount of money before it goes bankrupt. This
restriction has a dramatic impact on the expected value of the payoff. Consider,
for example, the following, more realistic setting: 
\begin{quote}
The gambler still receives \$$2^{k-1}$ if he flips $k-1$ tails before
flipping a head, but this only holds for profits up to \$$2^{30}$ (i.e. about a
billion dollars). If the gambler flips 31 tails or more before he gets a
head, he still only gets \$$2^{30}$.
\end{quote}

Notice that the probability of flipping 31 or more tails in a row is $2^{-31}$.

Under this scenario, the expected amount of money that the gambler will
receive from the casino is 
\begin{eqnarray*}
\expect{V} &=& \sum_{n=1}^{31} \frac{1}{2} + 2^{-31}\cdot 2^{30} \\
&=& 31\cdot\frac12 + \frac12 \\
&=& 16
\end{eqnarray*}

So, in our ``realistic'' scenario, the expected payoff is just \$$16$,
which is considerably less than infinity. The \$$10$ wager makes sense,
but not the \$$10,000$ one.

You should note that the infinite expectation we got in part (a) was due
to the (infinite) contribution of ridiculously high payoffs which, even
though they happen with inversely ridiculously low probability, still
contribute $\frac12$ \emph{each} to the sum. Since there is an infinite number
of (different) ridiculously high payoffs, we have an infinte number of
$\frac12$ terms in the sequence, which makes the sum infinite. 

\paragraph{Optional exercise:} Above, by setting the maximum payoff at
\$$2^{30}$, we brought the expected payoff down to just \$$16$. What
should the maximum payoff be for the expected payoff to be greater than
\$$10,000$, so that the \$$10,000$ wager makes sense?

\paragraph{Answer:} Around \$$2^{20,000}$. For comparison, note that there are
$2^{300}$ particles in the universe.
}
\end{problemparts}
\end{problem}

\begin{problem} 
Suppose that I choose a listing of the numbers $1, 2, \ldots, n$
uniformly at random.  What is the expected number of entries that are
greater than all preceding entries?  For example, in the listing 4, 2,
1, 5, 3, the numbers 4 and 5 are greater than all preceding
entries\footnote{This problem can be equivalently phrased as follows:
There are n people whose heights are $1, 2, \ldots, n$. I choose a
random permutation, and line them up accordingly. What is the expected
number of people who can see what's going on in front of the line? We
are assuming that a person can see if and only if all the people in
front of him/her are shorter.} (Hint: What's the probability that the
first entry is greater than all the preceding entries? What about the
second one?)

\solution{Let $i_k$ be an indicator for the event that the $k$-th
entry is greater than the preceding $k-1$ entries.  By linearity of
expectation

\begin{eqnarray*}
\expect{\text{\# new maxima}}
    & = &   \sum_{k=1}^n \Ex(i_k) \\
    & = &   \sum_{k=1}^n 1 \cdot \Pr(i_k = 1) + 0 \cdot \Pr(i_k = 0) \\
    & = &   \sum_{k=1}^n \Pr(i_k = 1)
\end{eqnarray*}

All that remains is to compute $\Pr(i_k = 1)$, which is the
probability that the $k$-th entry is greater than all preceding
entries.  Note that each of the first $k$ entries is equally likely to
be the largest.  Therefore, $\Pr(i_k = 1) = \frac{1}{k}$.
Substituting into the equation above gives:

\begin{eqnarray*}
\expect{\text{\# new maxima}}
    & = &   \sum_{k=1}^n \Pr(i_k = 1) \\
    & = &   \sum_{k=1}^n \frac{1}{k} \\
    & = &   H_n
\end{eqnarray*}
}

\end{problem}

\begin{problem}
Ben Bitdiddle is asked to analyze a game in which a fair coin is
tossed until the first time a head turns up.  If this head occurs on
the $n$th toss, and $n$ is odd, then he wins $\$2^n/n$, but if $n$ is
even, he loses $\$2^n/n$.  Ben observes that the expected dollar win
from this game is the value of the series:
\begin{eqnarray*}
& (1/2) \cdot 2 - (1/4) \cdot 2 + (1/8) \cdot 8/3 + \cdots \pm (1/2^n)
\cdot 2^n/n \cdots\\
& = 1 - 1/2 + 1/3 - 1/4 + \cdots \pm 1/n \cdots
\end{eqnarray*}

This is the \emph{alternating harmonic series}---a series which is
known to converge to a definite real number $r>0$.  Ben concludes that
since $r >0$, it's to his advantage to play this game.  As usual,
Ben's shoot-from-the-hip analysis is off the mark.  Explain. (Hint:
show that by reordering the series you can make it converge to
different values)

\solution{
The definition of expectation of $R$ is a summation, where we sum
$r\cdot\prob{R=r}$ for all values that R can take. However the definition
itself does not specify an ordering on how we do that sum the terms,
therefore it is \emph{not} valid for series where reordering the terms may
change the value (also see
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln11.pdf}
{Course Notes 11}).

In this case $\expect{\textrm{win}} = 1 -1/2 + 1/3 -1/4...$

This series converges, which means that if you add up the terms in the
\emph{given order} you will get some positive value $r$ that is not
infinite.  However it is not absolutely convergent as described below.
If I rearrange the terms then I can make it sum to a different value,
in fact \emph{any} value, even negative, This problem arises because
the positive terms sum to inifinity and the negative terms also sum to
infinity, so one can easily remove a little from infinity here or
there and make this sum acquire any value, depending on how the
expectation is evaluated.

As a result $\expect{\textrm{win}}$ is not well-defined.  The
definition of expectation requires absolute convergence.

%This series is convergent, but not \emph{absolutely}
%convergent. The definition of expectation requires absolute
%convergence, so the expectation in this case is not defined.  The fact
%that the expectation is undefined is no mere formality.  The number
%$r$ is not relevant to the behavior of the game. In fact by reordering
%its terms, the series can be made to converge to any real value or
%diverge to $\pm\infty$.

\paragraph{Parenthesis on convergence vs.~absolute convergence:}
Consider the series
 \[
 S \eqdef \sum_{i=0}^{\infty} (-1)^i = 1 + (-1) + 1 + (-1) + \cdots
 \]
 By regrouping the terms we can deduce:
 \begin{eqnarray*}
 S & = & [ 1 + (-1) ] + [ 1 + (-1) ] + \cdots = 0 + 0 + \cdots = 0,\\
 S & = & 1 + [(-1) + 1] + [(-1) + 1] + \cdots = 1 + 0 + 0 + \cdots = 1.
 \end{eqnarray*}

To see the problem here, let $S_n \eqdef \sum_{i=0}^{n}(-1)^i$.  Then
$S_n = 1$ for odd $n$ and $S_n = 0$ for even $n$.  Hence $S_n$ does
not have a well-defined limit as $n$ tends to infinity, implying that
$S$ is not a convergent series.

Even for convergent, but not absolutely convergent, series, rearranging
terms can cause big changes.  For example, the series above
 \[
 1 - 1/2 + 1/3 - 1/4 \dots
 \]
 converges, but is not absolutely convergent.  We can reorder terms in
 the series so that the resulting series converges to 3.  \dots so it
 converges to 4.  \dots so it doesn't converge.

Note that the sum of the negative terms goes to negative infinity, because
 the sum
 \[
 -1/2 - 1/4 - 1/6 -  \dots - 1/2n = -H_n/2 \sim (-\ln n)/ 2
 \]
 and $\ln n$ goes to infinity with $n$.  Similarly, the sum of the positive
 terms goes to positive infinity.

 To reorder the terms to converge to 3, begin by taking the positive terms
 in decreasing order until their sum first exceeds 3.  Next, take the
 negative terms in order of decreasing magnitude until the sum of all the
 terms taken---positive and negative---first goes below 3.  Now take the
 remaining positive terms in decreasing order until the sum again exceeds 3,
 then the negative terms till the sum goes below 3, and so on.  It is always
 possible to move the sum above or below 3 by taking enough of the remaining
 positive or negative terms, because the remaining positive terms sum to
 positive infinity and the remaining negative terms sum to negative
 infinity.  Also, the running sum of the positive and negative terms taken
 in this way goes above and below 3 at most by the magnitude of the last
 term taken.  Since the magnitude of the terms goes to zero, this implies
 that the sum goes above and below 3 by an amount that decreases to zero.
 But this is exactly what it means to say the sum converges to 3.

 Replacing ``3'' by ``4'' above yields an ordering in which the sum
 converges to 4.

 Finally, alternately taking enough positive terms to increase the sum by 1
 and then taking one negative term, yields an ordering in which the sum
 diverges to positive infinity.

 This argument applies to any convergent series that is not
 absolutely convergent to show that it can be reordered to converge to
 \emph{any} desired number, or to diverge.  The moral: when reordering terms
 in a series, be sure to check for absolute convergence.

 }
\end{problem}

%% proposed by ashish, modified by albert,eric,rad
\begin{problem}
Theorem: If X and Y are two random variables, such that
$$
\forall x\neq 0, y\neq 0,~~\prob{X=x\wedge Y=y}=\prob{X=x}\prob{Y=y}
$$
then
$$
\expect{XY}=\expect{X}\expect{Y}
$$

\begin{proof}
$$
\forall x\neq 0, y\neq 0,~~\prob{X=x\wedge Y=y}=\prob{X=x}\prob{Y=y}
$$
implies that
\begin{eqnarray}
\expect{XY}&=&\sum_{x, y} xy\prob{X=x \wedge Y=y}\\
&=&\sum_{x, y\neq 0} xy\prob{X=x \wedge Y=y}\\
&=&\sum_{x, y\neq 0} xy\prob{X=x}\prob{Y=y}\\
&=&\sum_{x, y\neq 0} x\prob{X=x}y\prob{Y=y}\label{frombug}\\
&=&\sum_{x\neq 0}\sum_{y\neq 0}x\prob{X=x}y\prob{Y=y}\\
&=&\sum_{x\neq 0} x\prob{X=x} \sum_{y\neq 0} y\prob{Y=y}\label{tobug} \\
&=&\sum_{x\neq 0} x\prob{X=x} \expect{Y} \\
&=&\expect{Y}\sum_{x\neq 0} x\prob{X=x}  \\
&=&\expect{Y}\expect{X}
\end{eqnarray}
\end{proof}

\begin{problemparts}
\problempart For each line in the proof, briefy justify its correctness. 

\solution{
(1) - definition of expectation.
(2) - term is zero when $x$ or $y$ is zero.
(3) - by hypothesis.
(4) - multiplication is commutative.
(5) - reordering sums.
(6) - factorization.
(7) - definition of expectation.
(8) - factorization.
(9) - definition of expectation.
}

\problempart 
One of the TAs thought that the theorem was incorrect and proposed the
following counter-example (see below). What is wrong with this
counter-example?

\begin{eqnarray*}
X&=&\left\{
\begin{array}{ll}
0&\textrm{  with probability }1/2\\
1&\textrm{  with probability }1/2
\end{array}\right.\\
Y&=&1-X
\end{eqnarray*}
Then $\expect{X}=\expect{Y}=1/2$, but $\expect{XY}=\expect{0}=0$.

\solution{At $x=1$ and $y=1$, $\prob{X=x\wedge Y=y} = 0$ while
$\prob{X=x}\prob{Y=y} = \frac{1}{2}\cdot\frac{1}{2} = \frac{1}{4}$.  The
TA's example therefore does not fit the requirements for the random
variables $X,Y$.}
\end{problemparts} 
\end{problem}

%% pset 10, fall 97
\begin{problem} 
In a physics experiment, every second a $\pi$-meson passes through a
detector with probability $p$.  $\pi$-meson arrivals are mutually
independent from second to second.

\begin{problemparts}
\problempart
What is the probability of getting exactly $k$ $\pi$-mesons passing through
the detector in one minute?

\solution{At each second the appearance of a $\pi$-meson is the outcome of a
Bernoulli trial with probability of success $p$.  Therefore the number
of $\pi$-mesons observed in $60$ seconds is Binomially distributed.

$$
\Pr(k) = {60 \choose k} p^k (1-p)^{60-k}
$$
}

\problempart Suppose the detector is on for one minute.
For what values of $k$ is the probability of getting exactly $k$
$\pi$-mesons greater than the probability of getting exactly $k-1$
$\pi$-mesons?  For what values of $k$ is it less?  What value of $k$
is the most likely number of $\pi$-mesons?

\solution{Consider the ratio of the probability of $k$ $\pi$-mesons  over the
probability of $k-1$ $\pi$-mesons.

\begin{eqnarray*}
\frac{{60 \choose k}p^k(1-p)^{60-k}}{{60 \choose {k-1}}p^{k-1}(1-p)^{60-k+1}}
& = &\frac{\frac{60!}{k!(60-k)!}p}{\frac{60!}{(k-1)!(60-k+1)!}(1-p)} \\
& = & \frac{(60-k+1)p}{k(1-p)}
\end{eqnarray*}

This quantity is greater or equal to $1$ if and only if $(60-k+1)p \geq k(1-p)
\Longleftrightarrow 61p \geq k$. 
So, for $k \leq 61p$ the probability increases from $k-1$ to $k$, and
for $k \geq 61p$, the probability decreases.  The value of $k$ that
maximizes the probability is thus $\lfloor 61p \rfloor$. 
%(Note: at the maximum value, the probability might change).

}

\problempart
Suppose that we keep observing until $m$ $\pi$-mesons are observed. Find the
probability distribution for the time $T$ to see $m$
$\pi$-mesons. What is the expected value of $T$?

\solution{
Consider the event $\{T = l\}$.  This means that there was one $\pi$-meson
observed in the $l$th second, and there were $m-1$ $\pi$-meson
arrivals on the previous $l-1$ seconds.

Since the arrivals at each second are independent, we have:

\begin{eqnarray*}
\Pr(T = l) & = & \Pr(\text{$m-1$ arrivals in $l-1$ seconds})P(\text{1 arrival 
on the $l$th second})\\
& = & {l-1 \choose m-1} p^{m-1}(1-p)^{l-m} p\\
& = & {l-1 \choose m-1} p^{m}(1-p)^{l-m}\\
\end{eqnarray*}

Let $X$ be the time to observe one $\pi$-meson.  Since future arrivals are 
independent of past arrivals, the time to see two $\pi$-mesons is $X+X = 2X$,
and more generally the time to see $m$ $\pi$-mesons is $mX$.
Therefore $E[T] = mE[X] = {m \over p}$.
}
\end{problemparts}
\end{problem}

%% pset11 problem8 spring98; from fall 97 pset11 problem9
\begin{problem}
In this problem, we analyze probabilistically the 1st stage of bubble
sort performed on a list of $n$ integers $\{ i_1, \ldots i_n \}$.  We
assume that all the integers are distinct and that the order of the
integers is chosen uniformly from all possible orderings.

On the first step we compare integers $i_1$ and $i_2$. If $i_1 > i_2$
we swap them otherwise we leave them as they are. On step $k~(2\leq
k\leq n-1)$, we compare the new $i_k$ with $i_{k+1}$. If $i_k >
i_{k+1}$ we swap else we leave them as they are.

\begin{problemparts}
\problempart If a number $x$ is randomly (uniformly) chosen from a set of $n$
distinct numbers, what is the probability that $x$ is the largest
number in the set?

\solution{$1/n$}

\problempart What is the probability that on the $k$th step ($2\leq k\leq n-1)$,
$i_{k+1}$ is the biggest integer to appear in the list so far?

\solution{
%$\Pr({\mbox{choosing largest of $n$ numbers}}) = 1/n$.  
$\Pr({\mbox{$i_{k+1}$ in $k$ step is highest so far}})=1/(k+1)$.
}

\problempart Let $C_k$ be a random variable that is equal to $1$ if 
$i_{k+1} > i_{k}$. What is $\expect{C_k}$?

\solution{
\[\expect{C_k} = \Pr({C_k = 1}) 
        = \Pr({\mbox{ $i_k$ is highest so far}}) 
        = \frac{1}{k+1}\]
}

\problempart Let random variable $C=\sum_{k=1}^n C_k$. 
Give an asymptotic bound for $\expect{C}$ as well as an interpretation
of what $\expect{C}$ is.

\solution{
\[\expect{C} = \sum_k \expect{C_k} = \sum_{k=2}^{n}\frac{1}{k} \sim \ln n.\]

$C$ is the total number of swaps, 
so $\expect{C}$ is the expected number of swaps.
}

\end{problemparts}
\end{problem}

\end{document}

%%%% OTHER %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
{\large OTHER}


\begin{problem} In the board game Monopoly, the number of
squares that a player advances in a single turn is determined by up to
three rolls of dice as follows.

\begin{itemize}
\item Initially, the player rolls two dice, sums the results, and
advances that many squares.

\item If the same number comes up on both dice---this is called
\emph{rolling a double}---then the player rolls the dice a second time,
sums the results, and advances that many additional squares.

\item If the player rolled on double on the second roll, then the player
rolls the dice a third time, sums the results, and advances that many
additional squares.

\item However, if third roll was a double, then the player ``goes to
jail''.  We will treat this as though he had to reset his position to
where he was just before the first roll, so the total number of squares
advanced by the player in this case is zero.
\end{itemize}

What is the expected number of squares that a player advances in a single
turn?  Assume that the dice are fair and six-sided and that rolls are
mutually independent.

\solution{
Here is one approach to the problem.

It's convenient to assume the dice are \emph{always} rolled three times,
with the player simply ignoring results of any roll which was preceded by
a non-double roll.

Let the random variable $R_i$ be the sum of the two dice on the $i$th
roll, and let $I_i$ be an indicator for the event that the $i$th roll was
a double.

We can express the random variable $R$, the number of squares advanced
by the player, as $R = R_1 + I_1 R_2 + I_1 I_2 R_3 - I_1 I_2 I_3 (R_1
+ R_2 + R_3)$. Since the dice rolls are independent, we know that
$R_i$'s and $I_j$'s at different rolls are independent.  We can take
expectations of both sides and reason as follows:
\begin{eqnarray*}
\expect{R}      & = &   \expect{R_1}
                 + \expect{I_1 R_2}
                 + \expect{I_1 I_2 R_3} \\
        & & \mbox{}
                 - \expect{I_1 I_2 I_3 R_1}
                 - \expect{I_1 I_2 I_3 R_2}
                 - \expect{I_1 I_2 I_3 R_3} \\
        & = &   \expect{R_1}
                 + \expect{I_1} \cdot \expect{R_2}
                 + \expect{I_1} \cdot \expect{I_2} \cdot \expect{R_3} \\
&&\mbox{}        - \expect{I_2} \cdot \expect{I_3} \cdot \expect{I_1 R_1} \\
&&\mbox{}        - \expect{I_1} \cdot \expect{I_3} \cdot \expect{I_2 R_2} \\
&&\mbox{}        - \expect{I_1} \cdot \expect{I_2} \cdot \expect{I_3 R_3}
\end{eqnarray*}
Note that the expectation of $R_i$ is $7$, and the expectation of $I_i$ is
$1/6$.  Finally, note that $\expect{I_i R_i} = 7/6$ by direct calculation.
Substituting into the formula above gives $\expect{R} = 595 / 72$.

Here is another approach: Let $D_i$~be the event that the $i$th roll
is a double. Then, by the law of total probability
\begin{multline*}
  \expect{R} = 
  \expect{R \mid \overline{D_1}} \Pr(D_i) + 
  \expect{R \mid D_1 \cap \overline{D_2}} \Pr(D_1 \cap \overline{D_2}) + \\
  \expect{R \mid D_1 \cap D_2 \cap \overline{D_3}}
     \Pr(D_1 \cap D_2 \cap \overline{D_3}) + 
  \expect{R \mid D_1 \cap D_2 \cap D_3} \Pr(D_1 \cap D_2 \cap D_3).
\end{multline*}
Computing the relevant expectations and probabilities gives
\begin{gather*}
  \expect{R \mid \overline{D_1}} = 7, \\
  \expect{R \mid D_1 \cap \overline{D_2}} = 7 + 7 = 14, \\
  \expect{R \mid D_1 \cap D_2 \cap \overline{D_3}} = 7 + 7 + 7 = 21, \\
  \expect{R \mid D_1 \cap D_2 \cap D_3} = 0, \\
  \Pr(\overline{D_1}) = 5 / 6, \\
  \Pr(D_1 \cap \overline{D_2}) = 5 / 36, \\
  \Pr(D_1 \cap D_2 \cap \overline{D_3}) = 5 / 216, \\
  \Pr(D_1 \cap D_2 \cap D_3) = 1 / 216.
\end{gather*}
}
\end{problem}

\begin{problem} %Peter Winkler Seminar 2001

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 
\[
\expect[\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 
\[
\expect[X_{Q+1}] - X = \expect \left [\sum_{i=1}^Q p_i \right ] = \sum_{q=1}^\infty \left(\expect \left[
\sum_{i=1}^q p_i \biggm| \{Q=q\} \right ] \Pr[Q=q] \right)
\]
But we just proved above that
\[ \expect \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
\[\expect[\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}

\begin{problem} 
\begin{problemparts}

\problempart Suppose we flip a fair coin until two heads in a row come up.  What
is the expected number, $F$, of flips we perform?

\hint Let
$F_{\text{T}}$ be the expected number of further flips until two heads
comes up, given that the previous flip was T, and likewise let
$F_{\text{H}}$ be the expected number of further flips until two heads
comes up given that the previous flip was H.  Argue that $F_{\text{T}}$
will equal 1 plus the average of $F_{\text{T}}$ and $F_{\text{H}}$.

\solution{
$F=F_{\text{T}}$, since the initial condition has no chance
of achieving two heads on the first flip and is thus the same as if the
previous flip had been tails. 

To calculate the expected number of flips, we take $1$ for the first 
flip and then consider the two equally-likely outcomes: the first flip
is tails, or the first flip is heads. The remaining flips we can expect
are simply $F_{\text{T}}$ and $F_{\text{H}}$, respectively.
This gives us a total expectation of:
\[
F_{\text{T}} = 1 + \frac{1}{2}F_{\text{T}} + \frac{1}{2}F_{\text{H}}
\]
If the previous flip was heads, we get a similar calculation. The biggest
difference is that if the first flip is heads, we have no more flips
beyond the current one (we are done).
\[
F_{\text{H}} = 1 + \frac{1}{2}F_{\text{T}}+ \frac{1}{2}(0)
\]
Solving for $F_{\text{T}}$ (by substitution) yields $F=6$.

This can also be solved using a single equation formed by examining
that cases for the first and second flips, but it is not as clean.

%Clearly $F=F_{\text{T}}$.  Assuming the hint
%\[
%F_{\text{T}} = 1 + \frac{F_{\text{T}}+ F_{\text{H}}}{2}.
%\]
%Similarly,
%\[
%F_{\text{H}} = 1 + \frac{F_{\text{T}}+ 0}{2}.
%\]
%Solving for $F_{\text{T}}$ yields $F=6$.

}

\problempart Suppose we flip a fair coin until a head followed by a tail come
up.  What is the expected number, $G$, of flips we perform?

\solution{
Clearly $G=G_{\text{T}}$.  As above
\begin{eqnarray*}
G_{\text{T}} &=& 1 + \frac{G_{\text{T}}+ G_{\text{H}}}{2},\\
G_{\text{H}} &=& 1 + \frac{0+G_{\text{H}}}{2}.
\end{eqnarray*}
So $G=G_{\text{T}}=4$.
}

\problempart Suppose we now play a game: flip a fair coin until either HH or HT
first occurs.  You win if HT comes up first, lose if HH comes up first.
What odds should you offer an opponent to make this a fair game?

\solution{
Even money odds.  Although the expected time for HH is larger
than for HT, the game of waiting for one or the other to come up first is
fair!

To prove this, let W be the probability of winning.  Clearly,
\[
W = (1/2)\prob{W \mid \text{first roll is }T} + (1/2)\prob{W \mid \text{first
roll is }
H} = (1/2)W + (1/2)(1/2)
\]
so $W = 1/2$.
}
\end{problemparts}
\end{problem}


\begin{problem} \textbf{Wald's Theorem.}
% Spring 99 Final. 

Suppose successive digits from zero to nine are generated independently
until the four digit sequence \textbf{9999} appears.

What is the expected number of digits generated? 

\hint Parse the sequence into consecutive ``tries to get 9999'', where a
``try'' is either a single digit other than 9, or a 9 followed by a single
digit other than 9, etc.  For example, the sequence 92349982999769999
parses into eight tries:
\[
/92/3/4/998/2/9997/6/9999/.
\]

\solution{
\textbf{Solution:}
11110.

By Wald's Theorem, the expected number is the mean time to a successful
try, namely $10^4$, times the expected length of a try.  Notice that a try
is of length four iff it begins with three nines, so the probability of a
length four try is $1/10^3$.  That means the expected length of a try is
\[
1 \cdot \frac{9}{10} + 2 \cdot \frac{1}{10}\frac{9}{10} + 3 \cdot
(\frac{1}{10})^2\frac{9}{10} + 4 \cdot (\frac{1}{10})^3
 =  (900 + 180 + 27 + 4)/1000 = 1111/1000
\]
Thus on average, we will have to read 11110 digits in order to see
``9999''.}
\end{problem}


\begin{problem}
% (Wald's theorem)

Consider the following $3$-stage experiment:

In the first stage, I throw a $6$-sided die.  The number of spots that I
get determines how many instances of the second stage to perform.

In the second stage, I throw a $6$-sided die.  This stage is repeated
once for each spot I got in the first stage.  The total number of spots that I
get in this stage determines how many instances of the third stage to perform.

In the third stage, I throw a $6$-sided die.  This stage is repeated
once for each spot I got in all instances of the second stage.

For example, if the outcome of the first stage is $3$, then stage 2
gets played $3$ times.  Suppose the outcomes of the $3$ instances of
stage 2 are $1,3,4$.  Then stage $3$ is played $1+3+4 = 8$ times, and
the score is the sum of $8$ instances of stage $3$.

Assume that all throws are mutually independent.

My score is the total number of spots on all the instances of the
third stage.

What is my expected score?

(Analyze this as carefully as you can, using Wald's theorem.  Try to
be careful about uses of independence.)

\solution {Let $X$ be the random variable whose value is the roll in
the first stage.  Let $Y_1, Y_2, \ldots, Y_X$ be the random variable
whose values are the rolls in the second stage.  Define $Y = Y_1 +
\cdots + Y_X$.  Let $Z_1, Z_2, \ldots, Z_Y$ be the random variable
whose values are the rolls in the third stage.  Define $Z = Z_1 +
\cdots + Z_Y$.  We want to find $\expect[Z]$.  Now all the rolls are
mutually independent, so we can use Wald's theorem to get $\expect[Y]
= \expect[X]\expect[Y_i] = (7/2)^2$.  Since $Y$ is determined by rolls
that are independent of the rolls in the third stage, $Y$ and $Z_i$
are independent.  So we apply Wald`s theorem again to get $\expect[Z]
= \expect[Y]\expect[Z_i] = (7/2)^3.$

The answer is $(7/2)^3$.
}
\end{problem}

\begin{problem} Calculate the expected number
of ``triples'' of people having the same birthdate\footnote{By
birthdate we mean born on the same day of the same month. Assume that
all birthdates are equally likely and independently chosen (by a
higher force).} in a classroom with $m$ people on a planet with $N$
days in a year. How many such triples would you expect to see in this
class ($m=100,N=365$)?

\solution{
The probability that a triple of students has the same birthday is
$1/N^2$. The number of possible triples is $\binom{m}{3}$ which is
$\frac{m(m-1)(m-2)}{6}$. Problem is that these triples are not
independent of each other, so computing the probability of $i$ triples
is very hard. However if we use the linearity of expectations, then we
get to ignore this thorny issue. As in the part(b), each triple gets
assigned an indicator random variable and the expected value of that
variable is $1/N^2$ (feel free to verify rigorously). Let $T$ be the
random variable representing the number of triples with the same
birthdate. Then,

$$\expect{T} = \frac{m(m-1)(m-2)}{6N^2}$$

For this class that is $100.99.98/6.365.365 = 1.2 (approx)$
}
\end{problem}


%% old problem, unsure where it came from
\begin{problem} %source: spring00 ps8
A biased coin has probability $p$ of heads and probability $1-p$ of tails.
Suppose we flip this coin $n$ times.
\begin{problemparts}
\problempart
What is the probability of getting exactly $k$ heads?
\problempart
For what values of $k$ is the probability of getting exactly $k$ heads
greater than the probability of getting exactly $k-1$ heads?
For what values of $k$ is it less?
What value of $k$ is the most likely number of heads?
\problempart
Show that if $p=1/n$ then the probability of getting no heads is 
$\sim 1/e$ (for large $n$).
What is the ratio of the probability of no heads to the probability
of exactly one head?
\end{problemparts}

\solution{
\begin{enumerate}
\item
Out of the $n$ tosses, $k$ of them are heads and $n-k$ of them are
tails.  The probability of any particular sequence is $p^k(1-p)^{n-k}$.
For a sequence of $n$ coins, there are ${n \choose k}$ ways 
to pick a sequence with $k$ heads.  Thus, the probability
of exactly $k$ heads is 
\[
{n \choose k} p^k (1-p)^{n-k}
\]

\item
Consider the ratio of the probability of $k$ heads over the
probability of $k-1$ heads.
\begin{eqnarray*}
\frac{{n \choose k}p^k(1-p)^{n-k}}{{n \choose {k-1}}p^{k-1}(1-p)^{n-k+1}}
& = &\frac{\frac{n!}{k!(n-k)!}p}{\frac{n!}{(k-1)!(n-k+1)!(1-p)}} \\
& = & \frac{(n-k+1)p}{k(1-p)}
\end{eqnarray*}

This quantity is greater than 1 if and only if $(n-k+1)p>k(1-p)
\Longleftrightarrow np+p>k$.
So, for $k<np+p$ the probability increase from $k-1$ to $k$,
and for $k>np+p$, the probability decreases.
The value of $k$ the maximizes the probability is thus
$\lfloor np+p \rfloor$.

\item
The probability of no heads is $(1-p)^n= (1-\frac{1}{n})^n$.  For
large $n$, this expression approaches $1/e$.  

The probability of exactly one head is ${n \choose 1}p(1-p)^{n-1} =
(1-\frac{1}{n})^{n-1}$.  Forming the ratio, we find the probability of
no heads over the probability of exactly one head is
$\frac{1}{1-1/n}$, which is one over the probability of a tail.
\end{enumerate}
}
\end{problem}

