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

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

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

\begin{document}

\pset{10}{December 1, 1994}{In recitation, December 9, 1994}

{\bf Reading:} [MR], Sections~6.4--6.7, and 
{\it The Essentials of Probability}, Chapters~5~and~6.


\bigskip
\begin{problems}

\remove{
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
OJ's blood test reveals that his blood is (1) type O, (2) Rh negative, 
and (3) thick.  
Tests of blood from the scene of the crime reveal the same data.
It is known that one-tenth of the general population has blood type O,
one-third is Rh negative, and one-fifth has thick blood.
\bparts
\ppart
At the trial, a lab technician from Bobo's Blood Lab is called to testify.
He claims that the probability a random person matches this data is~$1/150$.\\
Is he correct?
What can you say about (a lower bound for)
the probability that a random person matches this data?
\ppart
On re-examination, it is found that Rh factor and blood thickness are
independent.  What can you say now 
about the probability that a random person matches this data?
\ppart
Still later, it is revealed that all pairs of blood data are independent.
What can you say now 
about the probability that a random person matches this data?
\eparts
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Suppose you flip a fair coin 100 times.
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 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}	

\remove{
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \problem
  Derive good upper and lower bounds on the probability that when 1000
  fair (and mutually independent) coins are tossed, 400 or fewer will
  come up heads.  Don't forget to include error terms 
  and to sum over the cases when fewer than 400 heads come up.
  You may use any formulas that were derived in class.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Suppose you flip $n$ coins where each coin comes up heads with 
probability~$p$ and the flips are mutually independent.
%	\bparts
%	\ppart   What is the expected number of heads?
Prove that \[ pn = \sum_{i=0}^{n} i{n\choose i}p^i(1-p)^{n-i}. \]
%	\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let $x$ and $y$ be drawn independently and uniformly from the set
$\set{1,\ldots,n}$.
\bparts
\ppart Show that $\Ex{(x+y)/2} \leq \Ex{\max(x,y)} \leq \Ex{x+y}$.
\ppart Compute $\Ex{\max(x,y)}$.
\ppart Compute $\Ex{\min(x,y)}$.
\ppart Compute $\Ex{x-y}$.
\ppart Compute $\Ex{|x-y|}$.
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.  
What is the expected number of children that they will have?


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


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

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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$.  What is $\Ex{C}$?
Give an asymptotic bound for $\Ex{C}$ as well as a physical interpretation
of~$\Ex{C}$.
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Suppose $n$ balls are thrown randomly 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=k(n)$.
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

\end{problems}

\end{document}


