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

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

\begin{document}
\inclassproblems{12, Fri}

%% Rad 2002, first time used
%% Wald's Theorem.

\begin{problem} Consider the excerpt from Herbert Simon's paper ``The
Architecture of Complexity'' attached at the end.

\begin{problemparts}
\problempart What is wrong with the analysis?

\problempart What is the correct expected time for Hora and Tempus to
complete a watch?

\solution{

%{\em NOTES for the TAs (remove before publishing solution):
%This is the first time this problem is being used. There is no
%official solution written up anywhere. I will ask each table for a
%volunteer to write up the solution, and the best one will be selected
%as the ``official'' solution, perhaps for many years to come...}

%REMOVE OR EDIT SOLUTION BEFORE RELEASING

%The error is where he claims that the mean time to failure is 5
%(irrespective of the probability of failure $p$). The expected time
%till interruption should still be related to $p$.

% $t = 1/p$.  At that point Hora will have
% $t mod 10$ parts to reassemble. He will have made floor of t/10
% complete assemblies, and will be interrupted on the ceiling of t/10 th
% assembly.  So for $p=.01$, we expect interruption on the 100th part,
% so Hora will have finished 9 assemblies and will be interrupted on the
% last piece of the 10th assembly.  (This also makes from the $.99^10
% =.9$ chances of completing an assembly, right?)  So he will have 10
% parts to reassemble for every 10 assemblies, so that's one part per
% assembly on average.  I dunno......????

%CORRECT ARGUMENT: Actually explained in the notes quite well. 

The expected time for Tempus to complete an assembly is (expected
length of a try) x (expected number of tries). Success is if he
assembles all $n$ parts correctly, which is probability $(1-p)^n$. By
mean time to failure, the expected number of rounds is $1 / (1-p)^n$.
The expected length of a try (how far he expected to get before a
piece breaks, is again a mean time to failure type argument but over a
finite range. Turns out that E[length of a try] = $1-(1-p)^n / p$.

So the expected number of steps E[T] is $1/p ((1/(1-p)^n ) - 1)$.

If p = .01 and $n = 1000$ this is roughly 2 million steps.

Hora on the other hand uses a heirarchy of subassemblies, where each
subassembly has 10 elements. The expected time E[T] for $n=10$ is
about 10.57, same formula as above. But now if you draw out the tree
with 1000 leaves, then there are 111 subassemblies (nodes) that need to
get created. So total time = 111 x 10.57 = 1173.

}
\end{problemparts}
\end{problem}

%% 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
has a limit of a billion dollars.)

\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 infinite 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}
Just like event probabilities, expectations can be conditioned on some
event. We define \emph{conditional expectation, $\expcond{R}{A}$, of a
random variable, $R$, given event, $A$}:
\begin{equation}\label{defcondexp}
\expcond{R}{A} \eqdef \sum_r r \cdot\prcond{R=r}{A}.
\end{equation}

In other words, it is the expected value of the variable $R$ once we
skew the distribution of $R$ to be conditioned on event $A$.  A real
benefit of conditional expectation is the way it lets us divide
complicated expectation calculations into simpler cases. 

\begin{theorem}\label{thm:condexp}[Law of Total Expectation]
If the sample space is the disjoint union of events $A_1,A_2,\cdots$,
then
\[
\expect{R} = \sum_i \expcond{R}{A_i} \pr{A_i}.
\]
\end{theorem}

Prove the above theorem.

\solution{
\begin{proof}
  \begin{align*}
    \expect{R} &\eqdef \sum_r r \cdot \pr{R=r}\\
    &= \sum_r r \cdot \sum_i \prcond{R=r}{A_i} \pr{A_i}
            & \text{(Total Probability)}\\
    &= \sum_r \sum_i r \cdot \prcond{R=r}{A_i} \pr{A_i}
              & \text{(distribute constant $r$)}\\
    &= \sum_i \sum_r r \cdot \prcond{R=r}{A_i} \pr{A_i}
              & \text{(exchange order of summation)}\\
    &= \sum_i \pr{A_i} \sum_r r \cdot \prcond{R=r}{A_i}
             & \text{(factor constant $\pr{A_i}$)}\\
    &= \sum_i \pr{A_i} \expcond{R}{A_i}
             & \text{(Def.~\ref{defcondexp})}.
  \end{align*}
\end{proof}
}
\end{problem}


% other expectation formulas and wald's theorem
% also independence.

\begin{problem} 
Compute the expected value for each of the following random variables.
(Assume that all dice are fair and six-sided and that dice rolls are
mutually independent.)

\begin{problemparts}
\problempart The sum of the rolls of three dice.

\solution{
The expected value of one die roll is
\begin{eqnarray*}
1 \cdot \frac{1}{6} +
2 \cdot \frac{1}{6} +
3 \cdot \frac{1}{6} +
4 \cdot \frac{1}{6} +
5 \cdot \frac{1}{6} +
6 \cdot \frac{1}{6}
        & = & \frac{7}{2}.
\end{eqnarray*}

By linearity of expectation, the sum three rolls is
\begin{eqnarray*}
\frac{7}{2} + \frac{7}{2} + \frac{7}{2} & = & \frac{21}{2}.
\end{eqnarray*}
}
\problempart The product of the rolls of three dice.

\solution{For independent random variables, the expectation of the
product is the product of the expectations.  Therefore, the expected
product is
\begin{eqnarray*}
\frac{7}{2} \cdot \frac{7}{2} \cdot \frac{7}{2} & = & \frac{343}{8}.
\end{eqnarray*}
}

\problempart The sum of the rolls of a number of dice that is given by
the roll of a single die.  (For example, if you roll a 3 on the single
die, then you take the sum of 3 dice rolls; if you roll a 5 on the
single die, then you take the sum of 5 dice rolls.)

\solution{By Wald's Theorem, the answer is the expected number of dice
rolled multiplied by the expected roll of one die, which is
\begin{eqnarray*}
\frac{7}{2} \cdot \frac{7}{2} & = & \frac{49}{4}.
\end{eqnarray*}
}

\problempart Suppose now that the dice rolls are not guaranteed to be
mutually independent.  Which of your answers above must still be
correct?

\solution{The first and third answers remain valid because linearity of
expectation and Wald's Theorem do not require independence.  The remaining
answer about the product of the dice is does make use of independence.}
\end{problemparts}
\end{problem}

\appendix
\section{Appendix}

%% expectation formulas
The \emph{expectation} of random variable, $R$, is:
\begin{equation*}%\label{expsum2}
\expect{R} \eqdef \sum_{r \in \range{R}} r \cdot \pr{R = r}.
\end{equation*}

If $R$ has codomain $\naturals$, then this definition can also be written
as
\begin{equation*}
\expect{R}= \sum_{r \in \naturals} \pr{R > r}
\end{equation*}

\begin{theorem*}% \label{wald} [Wald]
Let $C_1, C_2, \dots,$ be a sequence of nonnegative random variables, and
let $Q$ be a positive integer-valued random variable, all with finite
expectations.  Suppose that
\[
\expcond{C_i}{Q \geq i} = \mu
\]
for some $\mu \in \reals$ and for all~$i \geq 1$.  Then
\[
\expect{C_1 + C_2 + \cdots + C_Q} = \mu \expect{Q}.
\]
\end{theorem*}

\newpage
{\bf Architecture of Complexity \newline
Herbert A. Simon \newline
Professor of Administration, Carnegie Institute of Technology}

{\em Proceedings of the American Philosophical Society, vol 106, no 6,
dec 1962. Excerpt, page 470.} 

%% Also reprinted as Chapter 4 of "Sciences of the Artificial",
%% H.A. Simon, MIT Press, Cambridge, MA.}

\vspace{.2in}

\framebox[7in]{
\parbox{6.5in}{

{\bf THE EVOLUTION OF COMPLEX SYSTEMS}

\indent Let me introduce the topic of evolution with a parable. There were
once two watch makers, named Hora and Tempus, who manufactured very
fine watches. Both of then were highly regarded, and the phones in
their workshops rang frequently --- new costumers were constantly
calling them. However, Hora prospered, while Tempus became poorer and
poorer and finally lost his shop. What was the reason?


The watches the men made consisted of about 1,000 parts each. Tempus
had so constructed his that if he had one partly assembled and had to
put it down --- to answer the phone say --- it immediately fell to
pieces and had to be reassembled from the elements. The better the
customers liked his watches, the more they phoned him, the more
difficult it became for him to find enough uninterrupted time to
finish a watch.


The watches that Hora made were no less complex than those of
Tempus. But he had designed them so that he could put together
subassemblies of about ten elements each. Ten of these subassemblies,
again, could be put together into a larger subassembly; and a system
of ten of the latter subassemblies constituted the whole watch. Hence,
when Hora had to put down a partly assembled watch in order to answer
the phone, he lost only a small part of his work, and he assembled his
watches in only a fraction of the man-hours it took Tempus.


It is rather easy to make a quantitative analysis of the relative
difficulty of the tasks of Tempus and Hora: Suppose the probability
that an interruption will occur while a part is being added to the
incomplete assembly is $p$. Then the probability that Tempus can
complete a watch he has started without interruption is $(1-p)^{1000}$
--- a very small number unless $p$ is .001 or less. Each interruption
will cost, on average, the time to assemble $1/p$ parts (the expected
number assembled before interruption). On the other hand, Hora has to
complete one hundred eleven sub-assemblies of ten parts each. The
probability that he will not be interrupted while completing any one
of these is $(1-p)^{10}$, and each interruption will cost only about
the time required to assemble five parts.

Now if $p$ is about .01 --- that is, there is one chance in a hundred
that either watchmaker will be interrupted while adding any one part
to an assembly --- then a straightforward calculation shows that it
will take Tempus, on the average, about four thousand times as long to
assemble a watch as Hora. We arrive at the estimate as follows:

\begin{enumerate}

\item Hora must make 111 times as many complete assemblies as Tempus;
   but,

\item Tempus will lose on average 20 times as much work for each
   interrupted assembly as Hora [100 parts, on the average, as
   against 5]; and,

\item Tempus will complete an assembly only 44 times per million attempts
   $(.99^{1000} = 44 \times 10^{-6})$, while Hora will complete nine out of
   ten $(.99^{10} = 9 \times 10^{-1})$. Hence Tempus will have to make 20,000
   as many attempts per completed assembly as Hora. 
$(9 \times 10^{-1})/(44 \times 10^{-6}) = 2 \times 10^4$. 
Multiplying these three ratios we get:
\vspace{-.1in}
\[
\frac{1}{111} \times \frac{100}{5} \times \frac{.99^{10}}{.99^{1000}} = 
\frac{1}{111} \times 20 \times 20,000 \sim 4,000.
\]
\end{enumerate}
}
}


\end{document}


%%%% OTHER  EXTRA PROBLEMS (a lot) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% 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}

\begin{problem} An urn contains red and blue colored balls. 
The fraction of red balls is $r$ where $0 \leq r \leq 1$. A gambler
repeatedly pulls a ball at random from the urn. That is, at any point
during successive pulls, each ball in the urn is equally likely to be
the next one pulled. The gambler puts the ball back into the urn
before making the next pull. He keeps pulling balls until he pulls
\emph{two red balls in a row}. We want to determine the expected
number of pulls the Gambler must make.

We can analyze this using Wald's Theorem. The sequence of pulls by the
Gambler can be regarded as a sequence of \emph{tries}, where the first
try begins with the first ball pulled.  Each try consists of a
sequence of pulled balls continuing until either a blue ball, or two
red balls in a row, are pulled.  For example, if the colors of pulled
balls are RBBBRBRR, then there are five tries which we indicate with
slashes: /RB/B/B/RB/RR/.  Note that each try consists of one or two
consecutive balls.
\begin{problemparts}

\problempart What is the expected length of the $i$th try, assuming
that there are at least $i$ tries?

\solution{Given that there is an $i$th try, it is of length 1 iff it
starts with a blue ball.  It is of length 2 iff it starts with a red
ball.  Hence,
\[\expect{\mbox{length of $i$th try} \mid \mbox{there is an
$i$th try}} = 1\cdot (1-r) + 2 \cdot r = 1 + r.
\]
}

\problempart What is the expected number of tries?

\solution{A series of tries ends iff only the last try consists of two
reds. We know from lecture that the ``mean time to failure'' is the
reciprocal of the probability of failure, so $\expect{\mbox{num
tries}}$ is the $1/\pr{\mbox{2 reds}}= 1/r^2$.}

\problempart What is the expected number of pulls the Gambler makes?

\solution{By Wald's Theorem we can just multiple the expected length
of the try by the the expected number of tries.}
\end{problemparts}
\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 infinity 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, briefly 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}

\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}
% (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}


%% 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
h$\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}







