\documentclass[11pt]{article}
%\usepackage{eepic}
\usepackage{psfig}
\usepackage{amsmath}
%\usepackage{graphics}
%\usepackage{eepic}
\input{macros-course}

\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersect}{\bigcap}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}
\newcommand{\underdash}{\_}

\newcommand{\solution}[1]{}
%%  \newcommand{\solution}[1]{\textbf{Solution}: \quad #1}


\begin{document}

\tutprobn{12}{4/30/99}{April 29, 1999}

\section{Team Problems}

\begin{problems}

\problem You repeatedly roll two fair six-sided dice until either a six or
nine appears (that is, until the sum of the values of the dice on a given
roll is 6 or 9).  You \emph{win} if a nine is rolled before any six, you
\emph{lose} if a six is rolled before any nine, and you \emph{tie} if a
six or nine never comes up (it takes a long time to tie \texttt{:-)} ).

\bparts We model this dice game with a sample space $S$ consisting of the
outcomes of a finite number of dice rolls of other than six or nine,
followed by a six or nine, along with a single sample point ``tie.''
That is,
\begin{eqnarray*}
S & = & \{6;\ \ 9;\\
&   & \ 2,6;\ \ 3,6;\ \ 4,6;\ \ 5,6;\ \ 7,6;\ \ 8,6;\ \ 10,6;\ \ 11,6;\ \ 12,6;\\
&   & \ 2,9;\ \ 3,9;\ \ 4,9;\ \ 5,9;\ \ 7,9;\ \ 8,9;\ \ 10,9;\ \ 11,9;\ \ 12,9;\\
&   & \ 2,2,6;\ \ 2,3,6;\ \ 2,4,6;\ \ 2,5,6;\ \ 2,7,6;\ \ 2,8,6;\ \ 2,10,6;\ \ 2,11,6;\ \ 2,12,6;\\
&   & \ 2,2,9;\ \ 2,3,9;\ \ 2,4,9;\ \ 2,5,9;\ \ 2,7,9;\ \ 2,8,9;\ \ 2,10,9;\ \ 2,11,9;\ \ 2,12,9;\\
&   & \ 3,2,6;\ \ 3,3,6;\ \ 3,4,6;\ \ 3,5,6;\ \ 3,7,6;\ \ 3,8,6;\ \ 3,10,6;\ \ 3,11,6;\ \ 3,12,6;\\
&   & \ 3,2,9;\ \ 3,3,9;\ \ 3,4,9;\ \ 3,5,9;\ \ 3,7,9;\ \ 3,8,9;\ \ 3,10,9;\ \ 3,11,9;\ \ 3,12,9;\\
&   & \dots \} \union \set{\mbox{tie}}
\end{eqnarray*}

\ppart Why can't we model ties by adding a sample point for each tieing
sequence, that is a point for each infinite sequence of the numbers
2,3,4,5,7,8,10,11,12?

\solution{There are uncountably many such sequences, and in 6.042, sample
spaces must be countable.}

\ppart What is the most reasonable probability to assign to each sample
point?  Prove that this assignment of probabilities does make $S$ into a
probability space.

\solution{
\begin{eqnarray*}
\prob{6 \mbox{ on any given roll}} & = & 5/36\\
\prob{9 \mbox{ on any given roll}} & = & 4/36 = 1/9\\
\prob{\mbox{neither 6 nor 9 on any given roll}} & = & 1 - 5/36 - 4/36 = 3/4
\end{eqnarray*}
Let $x$ be a finite sequence of natural numbers between 2 and 12 not
containing any 6's or 9's, let $x_i$ be the number of occurrences of $i$
in $x$.  Then
\begin{eqnarray*}
\prob{x6} & ::= & p_2^{x_2} \dots p_{12}^{x_{12}} \frac{5}{36},\\
\prob{x9} & ::= & p_2^{x_2} \dots p_{12}^{x_{12}} \frac{1}{9},\\
\prob{\mbox{tie}} & ::= & 0.
\end{eqnarray*}
We must prove that the probabilities sum to 1.  In the following,
sequences indicated $2,\dots,12$ do \emph{not} include 6 or 9:
\begin{eqnarray*}
\prob{S} & = & \prob{\mbox{win}} + \prob{\mbox{lose}} + \prob{\mbox{tie}}\\
& = & \sum_{x6}p_2^{x_2} \dots p_{12}^{x_{12}} \frac{5}{36}
 + \sum_{x9}p_2^{x_2} \dots p_{12}^{x_{12}} \frac{1}{9}\\
& = & \frac{9}{36} \sum_x p_2^{x_2} \dots p_{12}^{x_{12}}\\
& = & \frac{1}{4}
        \sum_{n = 0}^\infty
        \sum_{\scriptsize{\begin{array}{l}
               n_2,\dots, n_{12} \in \naturals \\
               n_2+\dots + n_{12} = n
             \end{array}}}
          \binom{n}{n_2,\dots, n_{12}} p_2^{n_2} \dots p_{12}^{n_{12}}\\
& = & \frac{1}{4} \sum_{n = 0}^\infty (p_2 + \dots + p_{12})^n\\
& = & \frac{1}{4} \sum_{n = 0}^\infty (\frac{3}{4})^n\\
& = & \frac{1}{4}\frac{1}{1 - 3/4} = 1
\end{eqnarray*}
}

\ppart What is the probability you win?

\solution{
\begin{eqnarray*}
\prob{\mbox{win}} & = &  \prob{\mbox{first roll is 9}} + \prob{\mbox{first roll
neither 6 nor 9}} \cdot \prob{\mbox{win}}\\
& = & \frac{1}{9} + \frac{3}{4}\prob{\mbox{win}},
\end{eqnarray*}
so $\prob{\mbox{win}} = \frac{1/9}{1 - (3/4)} = \frac{4}{9}$.
}

\eparts

\problem Remember the game demonstrated in lecture: Albert 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 Albert 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.

\bparts

\ppart 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 Albert 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 Albert 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}
\]
}

\ppart Now suppose the numbers from the problem above are drawn from the
set of all natural numbers, $\naturals$.  Design a strategy for playing
this game such that whatever numbers Albert picks, 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 Albert 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}.
\]

\iffalse

Of course in this case, in contrast to the case when the choice of numbers
is bounded, Albert 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$,

\fi

}

\eparts

\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.

\bparts

\ppart 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.}

\ppart 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 13 consecutive tails}}\\
& = & 2^{-13} = \frac{1}{8,192}
\end {eqnarray*}
}

\ppart 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 or
the player goes bankrupt.

\solution{\hint In reality, the casino goes bankrupt after a relatively
small number of consecutive tails, so the gambler's win in bounded by the
casino's net worth. This makes the expectation finite.  Optional exercise:
what should the casino's net worth be in order for the gambler's
expectation to be positive?}

\eparts

\iffalse

\textbf{6042-STAFF: WE'LL USE AT MOST ONE OF THE FOLLOWING TWO PROBLEMS.
LET ME KNOW WHICH YOU PREFER -- ARM.}

\problem Let $R$ and $T$ be independent random variables, and $f$ and $g$
be any functions on the real numbers, i.e. $f,g : \reals \to \reals$.
Prove that $f(R)$ and $g(T)$ are independent random variables.

\solution{The event $f(R) = a$ is the disjoint union of all the events $\set{R
= r}$ for $r \in f^{-1}(a)$, so
\[
\prob{f(R) = a} = \sum_{r \in f^{-1}(a)} \prob{R = r}.
\]
Similarly for the event $\set{g(T) = b}$.  Also, the event $\set{f(R) = a
\mbox{ and } g(T) = b}$ is the disjoint unon of the events $\set{R =
r\mbox{ and }T = t}$ for $(r,t) \in f^{-1}(a) \times g^{-1}(b)$.  Hence,
\begin{eqnarray*}
\lefteqn{\prob{f(R) = a \mbox{ and } g(T) = b}}\\
& = & \sum_{(r,t) \in f^{-1}(a) \times g^{-1}(b)}
                \prob{R = r \mbox{ and } T = t}\\
& = & \sum_{(r,t) \in f^{-1}(a) \times g^{-1}(b)} \prob{R = r} \prob{T = t}
            \hspace{0.5in}\mbox{[because $R,T$ independent]}\\
& = & \sum_{t \in g^{-1}(b)} \sum_{r \in f^{-1}(a)} \prob{R = r} \prob{T =
               t}\\
& = & \sum_{t \in g^{-1}(b)} \prob{T = t} (\sum_{r \in f^{-1}(a)} \prob{R = r})\\
& = & \sum_{t \in g^{-1}(b)} \prob{T = t} (\prob{f(R) = a})\\
& = & \prob{f(R) = a} \sum_{t \in g^{-1}(b)} \prob{T = t}\\
& = & \prob{f(R) = a} \prob{g(T) = b}
\end{eqnarray*}
}

\problem Let $A,B,C$ be events over some probability space, and let
$I_A,I_B,I_C$ be the corresponding index variables, e.g., the event
$\set{I_A = 1}$ is the same as the event $A$ and $\set{I_A = 0}$ is the
same as $\bar{A}$.  Prove that $A,B,C$ are mutually independent iff the
random variables $I_A,I_B,I_C$ are mutually independent.

\solution{
($\Longrightarrow$):  
\begin{eqnarray*}
\prob{I_A = 1 \wedge I_B= 0 \wedge I_C = 1} & = & \prob{A \intersect \bar{B}
\intersect C}\\
& = & \prob{A \intersect C} - {A \intersect B \intersect C}\\
& = & \prob{A} \cdot \prob{C} - \prob{A} \cdot \prob{B} \cdot \prob{C}\\
& = & \prob{A} \cdot \prob{C} (1 -  \prob{B})\\
& = & \prob{A} \cdot \prob{C} \prob{\bar{B}}\\
& = & \prob{I_A = 1} \cdot \prob{I_C = 1} \prob{I_B = 0}\\
& = & \prob{I_A = 1} \cdot \prob{I_B = 0} \cdot \prob{I_C = 1}
\end{eqnarray*}
and similarly for any other three binary values in place of 101.

($\Longleftarrow$):  
\begin{eqnarray*}
\prob{A \intersect B \intersect C} & = & 
        \prob{I_A = 1 \wedge I_B = 1 \wedge I_C = 1}\\
& = & \prob{I_A = 1} \cdot \prob{I_B = 1 } \cdot \prob{I_C = 1}\\
& = & \prob{A} \cdot \prob{B} \cdot \prob{C}
\end{eqnarray*}
Also,
\begin{eqnarray*}
\prob{A \intersect B} & = & \prob{A \intersect B \intersect C}
                       + \prob{A \intersect B \intersect \bar{C}}\\
& = & \prob{I_A = 1 \wedge I_B = 1 \wedge I_C = 1} + \prob{I_A = 1 \wedge I_B = 1 \wedge I_C = 0}\\
& = & \prob{I_A = 1} \cdot \prob{I_B = 1} \cdot \prob{I_C = 1}
       + \prob{I_A = 1} \cdot \prob{I_B = 1} \cdot \prob{I_C = 0}\\
& = & \prob{A} \cdot \prob{B} \cdot \prob{C} + \prob{A} \cdot \prob{B}
                       \cdot \prob{\bar{C}}\\
& = & \prob{A} \cdot \prob{B} (\prob{C} + \prob{\bar{C}})\\
& = & \prob{A} \cdot \prob{B}
\end{eqnarray*}
and similarly for ${B \intersect C}$ and ${A \intersect C}$.
}

\fi

\end{problems}

\end{document}

