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

\begin{document}

\handout{ps9}{Problem Set 9}{April 26, 1994}

\pset{9}

{\bf Reading:\ }Maurer \& Ralston: Sections 6.4--6.7. Tom's lecture notes.

\medskip

The oral problems are
due in tutorial on Monday, May 2.
The written problems are due in class on May 3.

\bigskip

\begin{problems}

\oproblem
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 (as was done in
recitation) or to sum over the cases when fewer than 400 heads come up
(as was done in class).  You may use any formulas that were derived in
class or in recitation.

\oproblem
Let $R:S\mapsto  \cal{N}$ be a random variable on sample space $S$.  Let
$G(z)$ be the probability generating function for $R$.  Show that
$Ex(R)= G'(1)$ where $G'$ is the derivative of $G$ with
respect to $z$.

\oproblem
Let $R$ and $G(z)$ be as in the previous problem.  Show that
$G(z)/(1-z)$ is the OGF for the cummulative distribution function for
$R$, i.e., show that $G(z)/(1-z)= \Sigma_{n=0}^{\infty} Pr(R\leq n)z^n.$

\oproblem
 A couple keeps having babies until they get a child of each sex
(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?

\oproblem
Problem 13 on page 490 from Maurer Ralston.

\oproblem
Problem 17 on page 491 from Maurer Ralston.

\oproblem
Problem 19 on page 490 from Maurer Ralston.

\oproblem
Problem 33 on page 492 from Maurer Ralston.

\newpage

\wproblem
Let $f(k) = {n\choose k}2^{-n}.$ Use Stirling's approximation to show 
that $f(n/2-b\sqrt{n}) \sim (\sqrt{2/\pi n})e^{-2b^2}.$

\wproblem
 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}).  Assume
that there is a total ranking of the players and that the better
player always wins.  If all $n!$ permutations of players are equally
likely, what is the expected number of times that a challenger will
win a round.  (There is no challenger in round $1$). \\ Hint: notice
that the challenger wins in round $i~(i>1)$ if and only if he/she is
the best among the first $i+1$ players.  Use indicator variables and
linearity of expectation.

\wproblem
Consider the following game: in each round you flip a coin, if it
comes up heads you gain a dollar, else you lose one. You have one
dollar to begin with and the game stops when you go broke. If the coin
has probability $p$ of coming up heads show that your probability of
going broke is $ f(p) = \Sigma_{n=0}^{\infty}1/(n+1){2n\choose
n}p^n(1-p)^{n+1}.$ Draw a graph of $f(p)$ versus $p$ and show that
when $p = 2/3$ your chance of going broke is even.

\end{problems}


\end{document}



