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

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

\begin{document}

\pset{11}{November 28, 1995}{December 04, 1995}

%{\bf Reading:} Pages 261-275 of {\it
%Discrete Mathematics and its Applications} by Kenneth H. Rosen.

\bigskip
\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem 
Let $S$ be a sample space.  Say random variable $X: S \rightarrow \naturals$ has 
distribution
\[
X = \left\{ \begin{array}{cl} 2 & \mbox{with probability $1/4$,} \\
                             3 & \mbox{with probability $1/4$,} \\
                             5 & \mbox{with probability $1/2$;} \end{array}
\right.
\]
and random variable $Y:S\rightarrow \naturals$ has distribution
\[
Y = \left\{ \begin{array}{cl} 1 & \mbox{with probability $2/3$,} \\
                             4 & \mbox{with probability $1/3$;} \end{array}
\right.
\]
where $X$ and $Y$ are independent.

\bparts
\ppart What is the expected value of $X+Y$?
\ppart What is the expected value of $\max(X,Y)$?
\ppart What is the expected value of $\min(X,Y)$ (there's a
quick answer from the other two parts)?
\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  

You are given a wheel (like a roulette wheel) which contains the numbers
from $1$ to $2n$ arranged in some way. The wheel has a spinner and on each
spin you get the two numbers at the opposite ends of the spinner.  How would
you arrange the numbers on the wheel to maximize the expected value of:

\bparts
\ppart The sum of the numbers chosen?
\ppart The product of the numbers chosen?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
We are given a random vector of $n$ distinct numbers.  We then
determine the maximum of these numbers by the following procedure:

Pick the first number.  Call it the ``current maximum''.  Go through
the rest of the vector (in order) and each time we find a number $x$
that exceeds our ``current maximum'', we update the ``current maximum''
with $x$.

What is the expected number of times we update the ``current maximum''?


\problem Deviations from the mean:
\bparts
\ppart Prove that if $X$ is a random variable with mean $m$,
then $X-m$ is a random variable with mean 0
\ppart
Suppose I flip $n$ unbiased independent coins.  We know that
the mean number of heads is $n/2$.  What is the {\em expected 
  deviation from the mean}?  That is, if the number of heads is a
random variable $X$, what is
\[
E[|X-n/2|]?
\]
\eparts

%Feller, exercises on expectation
\problem (A true story from world war two).  Suppose the army needs to
test its $n$ soldiers for a disease that occurs independently at
random with probability $p$ for each soldier. The test is by means of
a blood test.  One approach (i) is to test each soldier individually:
this requires $n$ tests.  An alternative approach (ii) is the
following.  Group the soldiers into groups of $k$.  Blend the blood
samples of each group and apply the test once to each blended sample.
If the group-blend is free of the disease, we are done after one test.
If the group-blend fails the test, then someone has the disease and we
have to test all $k$ people for a total of $k+1$ tests. 

\bparts
\ppart What is the expected number of tests in method (ii) as a
function of the number of soldiers $n$, the disease probability $p$,
and the group size $k$?

\ppart How should $k$ be chosen to minimize the expected number of
test performed, and what is the resulting expectation?

\ppart What fraction of the work does method (ii) expect to save over
method (i) in a million-strong army with disease incidence $1\%$?

\ppart Can you come up with a better scheme by using multiple levels
of grouping (ie, groups of groups)?
\eparts

\problem  Consider a tournament among $10$ teams, each playing the
other.  Recall that a {\em chain} is a ranking of the teams such that
each team beats the one just behind it in the ranking.  Prove that
there is a tournament outcome such that there are over $3000$
distinct chains.  {\em Hint:} If each game outcome is random (50-50),
what is the expected number of chains?  Can all tournaments end up
with fewer chains than the expected number?

This problem is an instance of the {\em probabilistic method.} It uses
probability to prove the existence of an object without constructing
it.

\end{problems}

\end{document}




