\documentstyle[12pt,twoside,amssymb]{article}
\input{macros-course}

%       \addtolength{\topmargin}{-.35in}
\addtolength{\textheight}{.25in}
%       \setlength{\textheight}{9in}

\newcommand\Ex[1]{\mbox{\bf E}[\, #1 \, ]}
\newcommand\vari[1]{\mbox{\bf Var}[\, #1 \, ]}
\newcommand\Prob[1]{\mbox{\bf Pr}[\, #1 \, ]}

\begin{document}

\pset{13}{May 17, 1997}{never}

{\bf Reading:} Lecture Notes on {\em Probability}

This set of problems can be used to improve your facility with
expectations and deviations.  Solutions are available in the next
handout.


\bigskip
\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf [12 points]}

At the carnival, there is a betting game played with
three fair and (mutually) independent dice.
You may bet \$1 on any of the six values $\set{1,2,3,4,5,6}$.
If any of the dice matches your value,
you get your original bet back plus you win
\$1 if one of the dice matches your value,
\$2 if two of the dice match your value, and
\$3 if three of the dice match your value.

Bobo thinks the game is fair since if he simultaneously
bets \$1 on each of the 6 choices, and the dice come up $a,b,c$,
he wins 3 bets plus \$3, for a total of \$6, which is what he wagered.
Bobo figures that he does the same if some value comes up more than
once.
\begin{problemparts}
\problempart
What is the probability that
        \begin{enumerate}
        \item   All three dice have different values?
        \item   Two dice have the same value and the third die has a
                different value?
        \item   All three dice have the same value?
        \end{enumerate}

\problempart
What is the expected return (net winnings) if you wager \$6, placing
\$1 on each of the six values?  Justify your answer.
\problempart
What is the expected return if you wager \$1
on only one of the six values?
Justify your reasoning.
\problempart
Set up this game so that it is fair by fixing the three prizes
$i_1, i_2, i_3$ so that if you match $d$ of the dice, you win~$\$i_d$
(plus
you get your your original \$1 bet back).
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf [8 points]}

% (Negative binomial distribution)

Consider a system consisting of $2$ components, each of which can
fail at each step with probability $p$.  Failures at different steps
and/or components are mutually independent (in particular, this means
that failure need not be permanent).  The steps are numbered $1,2,\ldots$.

\bparts
\ppart
Let $X$ be the random variable whose value is the step number of the
first step at which there is a failure (in either component).  Find $\Ex{X}$. 
\ppart
Let $Y$ be the random variable whose value is the step number of the
first step at which both components fail simultaneously.  Find $\Ex{Y}$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf [10 points]}
% (Linearity of expectations)

The same $n$ college students apply to two graduate schools, $A$ and
$B$.
In order to same money and time, each grad school ranks the students
randomly, with all permutations chosen with equal likelihood.  The
rankings of the two graduate schools are independent of each other.

\bparts
\ppart
What is the expected number of students that have a higher rank on
the list for grad school B than they do for grad school A?

\ppart
 What is the expected number of students that have a rank on the
list for grad school B that is at least $k$ higher than their rank on the
list for grad school A?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf [20 points]}

Suppose $n$ balls are thrown randomly and mutually independently 
into $n$ boxes, so each ball lands in each box with uniform probability.
\bparts
\ppart  What is the expected number of empty boxes?
\hint Use linearity of expectation.
\ppart  Show that
$\Prob{\geq k \mbox{ balls fall in the first box}}
        \leq {n\choose k} \left(\frac{1}{n}\right)^k$.\\
Argue that this probability is at most $1/k!$, and therefore \\
$\Prob{\geq k \mbox{ balls fall into {\em some\/} box}}
        \leq n/k!$.
\ppart  Let random variable $R$ be the maximum number of balls that land
in any box.  Use Stirling's formula and the result from the last part
to give an upper bound for $\Prob{R\geq k}$.
\ppart  How does your answer to the last part behave asymptotically
with $n$ when $k=n^\alpha$ for some constant~$\alpha$?
Is $\Prob{\mbox{$\geq k$ balls land in some box}}$ large or small?\\
What about when $k=\lg\lg n$?
\ppart
We'd like to know when this upper bound goes from being close to 1
to being close to 0  as we increase $k$.
Show that this happens around $\displaystyle k\approx \frac{\lg n}{\lg\lg n}$.
\\
(You only need to find when $n/k^k$ goes from being close to $0$ to
close to~$1$.)
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf [8 points]}
% (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.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf [20 points]}

Let $X$ and $Y$ be random variables whose values are independent
observations drawn uniformly at random from the set
$\set{1,\ldots,n}$.  Compute the following quantities:
\bparts
%\ppart $\Ex{X}$ 
%\ppart $\vari{X}$.
%\ppart $\vari{2X}$
%\ppart $\vari{X+Y}$.
%\ppart $\Ex{X-Y}$
%\ppart $\Ex{(X+Y)/2}$ 
%\ppart $\vari{(X+Y)/2}$.
\ppart $\Ex{\max(X,Y)}$.
\ppart $\Ex{\min(X,Y)}$.  ({\em Hint:}  There is a way to get the answer to this reasonably quickly using the previous part.)
%\ppart $\Ex{|X-Y|}$.
\ppart $\vari{X-Y}$.
\ppart $\vari{|X-Y|}$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf [10 points]}
\bparts
\ppart Let $X$ be a random variable whose value is an observation
drawn uniformly at random from the set
$\{-n,-n+1,\ldots,-2,-1,0,1,2,\ldots,n-1,n\}$.
Let $Y = X^2$. Show that $X$ and $Y$ are {\em not} independent, but
that
$\Ex{XY} = \Ex{X} \Ex{Y}$.
\ppart Show in general for any two random variables $X$ and $Y$
that if $\Ex{XY} = \Ex{X} \Ex{Y}$ then $\vari{X+Y} =
\vari{X} + \vari{Y}$.  In particular, this shows that it is possible
for non independent variables to have variances that exhibit
linearity.
%\ppart Let $X_1, X_2, \ldots, X_n$ be $n$ {\em pairwise} independent
%random variables.  Show that $\vari{X_1 + X_2 + \cdots + X_n} =
%\vari{X_1} + \vari{X_2} + \cdots + \vari{X_n}$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem
%Suppose you have $n$ letters to be stuffed in $n$ addressed envelopes.
%However, you decide, for fun, to stuff the $n$ letters randomly into
%the $n$ envelopes, making sure that there is exactly one letter in
%each envelope.  Let $X_n$ be a random variable whose value is the
%number of letters in the correct envelopes.  
%
%\bparts
%\ppart What is $\Ex{X_n}$?
%\ppart Show that $\lim_{n \to \infty} \Prob{X_n = 0} = 1/e$.  That is,
%show that as
%$n$ grows large, the probability that none of the letters are in the
%correct envelope approaches $1/e$.  
%{\em Hint}:  The Inclusion-Exclusion principle and
%the Taylor expansion $e^x = \sum_{i=0}^{\infty} x^i/i!$ will be useful
%here.
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem 
%Let $R_1,\ldots,R_n$ be mutually independent identically distributed 
%random variables, and let each have the same distribution as random 
%variable $R$.  
%Let $V$ be a random variable (mutually independent of the $R_i$)
%with range $\{1,\ldots, n\}$.   Let $Z=R_1+\cdots+R_V$.  
%
%This setup corresponds to an experiment where we first select an integer $k$ 
%according to the distribution of $V$ and then conduct $k$ independent trials 
%of selecting a value for $R$ and summing the $k$ values.

%Show that $\Ex{Z}=\Ex{R}\cdot \Ex{V}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem 
%Consider the following sequential $n$-player tournament.  
%In round $1$, players $1$ and $2$ play each other.  
%In round $i~(2\leq i\leq n-1)$, the winner of round $i-1$ plays player 
%$i+1$, who is called the {\it challenger}.
%(There is no challenger in round~$1$.)
%There is a total ranking of the players and the more highly ranked
%player always wins.  
%The order in which the players enter the tournament is a permutation
%of the $n$ players chosen uniformly at random.
%\bparts
%\ppart  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? \\
%What is the probability that the challenger in round $i$ 
%($2\leq i\leq n-1)$ is the highest-ranked player to appear in the 
%tournament so far?
%\ppart  Let $C_i$ be a random variable that is equal to $1$ if the
%challenger wins in round~$i$ and 0 if the challenger loses.
%What is $\Ex{C_i }$?
%\ppart  Let random variable $C=\sum_i C_i$. 
%Give an asymptotic bound for $\Ex{C}$ as well as a physical interpretation
%of $\Ex{C}$.
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf [12 points]}

Suppose you flip a fair coin 100 times.  The coin flips are all mutually independent.  
What is an upper bound on the probability
that the number of heads is at least 70\ldots
\begin{problemparts}
\problempart
\ldots according to Markov's Inequality?
\problempart
\ldots according to Chebyshev's Inequality?
\problempart
\ldots according to Chernoff's Bound?
\problempart
\ldots according to the upper bound for binomial distributions
        derived in lecture?\\
        (Get a strict upper bound by using the multiplicative factors
of
        $\frac{1-\alpha}{1-2\alpha}$ to account for the case that
        there are strictly more than 70 heads,
        and $(\frac{n}{e})^{\frac{1}{12n}}$ to adjust Stirling's
        approximation.)
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem
%Give upper bounds for the following probabilities using the Markov,
%Chebyshev, or Chernoff inequality, where appropriate.  If more than
%one inequality applies, use the inequality that gives you the best
%bounds. 

%\bparts
%\ppart Suppose you play the following game:  Flip $5$ independent and
%fair coins.  Score one point if the difference between the number of
%heads and tails is at least $3$.  What is the probability that your
%average score is greater than $0.9$ if you play the game $100$ times?

%\ppart Let $a$ and $b$ be two numbers picked independently and
%uniformly at random from the set $\{0,1,2,3,4\}$.
%For $i = 0,1,2,3,4$, define the random
%variable $X_i$ to be equal to $ai + b \bmod p$.  
%Let $Y = \frac{1}{5}(X_1 + X_2 + X_3 + X_4 + X_5)$.  
%What is the probability that $Y$ is greater than $3.5$?
%{\em Hint}: Observe that $X_i$ is distributed uniformly on the set
%$\{0,1,2,3,4\}$.  

%\ppart You are told that the average (mean) annual income is \$10,000
%in a particular population.  Five people are picked independently and
% uniformly and at random from the population.  
%What is the probability that their avearge (mean) annual income is
%greater than or equal to \$1,000,000?
%\eparts

%\problem
% (Conditional expectation)
%
%A medical insurance company insures subscribers from three separate
%pools, A, B and C, all containing the same number $n$ of subscribers.
%Individuals in pool A have a 1\% chance of developing a major illness in a
%given year, those in pool B a 5\% chance and those in pool C a 25\% chance.
%Each major illness costs the insurance company \$10,000.
%The law requires that the company charge everyone equal rates for
%insurance.
%
%If a subscriber is chosen at random from the union of all three
%pools, what is the expected amount of payout from the insurance
%company to that subscriber in a given year?
%
%(You may assume that no one develops more than one major illness.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
A couple keeps having babies until they get a child of each gender,
whereupon they stop.
Each child is equally likely to be a boy or a girl.
\bparts
\ppart
What is the expected number of children that they will have?
\ppart
What is the variance?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let $R:S\rightarrow \nats$ be a random variable.
\begin{problemparts}
\problempart
Let $R'=cR$ for some positive constant~$c$.
If $\sigma_R = s$, what is $\sigma_{R'}$?
\problempart
If $\Ex{R}=1$, how large can $\vari{R}$ be?
\problempart
If $R$ is always positive (nonzero), how large can $\Ex{1/R}$ be?
\problempart
Describe a possible distribution for $R$ with 
$\Ex{R}=10$; $\sigma^2_R=9$; and \\$\Prob{|R-\Ex{R}| \geq 6} = 1/4$.
\end{problemparts}


\end{problems}

\end{document}


