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


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

\begin{document}

\pset{11}{November 25, 1997}{December 5 , 1997 in tutorial}

{\bf Reading: Lecture notes}

\bigskip

\begin{Large}

\end{Large}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem{\bf [10 points]}

The couple who is having children until they get a boy and a girl knows 
that the expected number of children is 3.  What is the variance?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
\problem {\bf [10 points]}

Now suppose that the couple wants to get two girls in a row.
Find the expected number of children.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem {\bf [15 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 $\vari{(aX+bY)}$.
\ppart $\E[\max(X,Y)]$.
\ppart $\E[\min(X,Y)]$.  ({\em Hint:}  There is a way to get the answer 
to this using the previous part.)
\ppart $\E[|X-Y|]$.
\ppart $\vari(|X-Y|)$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\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
$\E[XY] = \E[X] \E[Y]$.

\ppart 
Show in general for any two random variables $X$ and $Y$
that if $\E[XY] = \E[X] \E[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.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem {\bf [10 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 toss a fair coin.  This stage is repeated
once for each spot I got in the first stage.  The total number of heads 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 head 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?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem {\bf [15 points]}


Suppose that someone is infected with an unknown incurable contagious disease.
Everyday he encounters $n$ healthy people and infects each of them with
probability $p$. Encounters are mutually independent.
These people in turn meet $n$ people and infect them with 
probability $p$ and so on.

\bparts

\ppart 
Write a recurrence for the expected number of people on the $k+1$st day
in terms of the expected number of people on the $k$th day.
Assume that each day every sick person meets $n$ {\em different} persons.

\ppart Solve the recurrence of part (a).

\ppart
Now suppose that any sick person recovers from the disease each day with 
probability $r$. Find the expected number of sick people on the $k$th day.

\eparts
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem{\bf [10 points]}

A miner, lost in some abandoned mine, finds himself in a room 
containing three doors.  Door 1 leads him to freedom after two 
hours travel; door 2 returns him to the same room after four hours travel, and 
door 3 returns him to the room after eight hours travel.
Each time he finds himself in the room, 
the miner picks a door with equal probability.  
Let $T$ denote the time until he finds the exit. \\

\bparts

\ppart Define a sequence of iid random variables $X_i$ and a stopping rule 
$N$ such that

\begin{displaymath}
T = \sum_{i=1}^{N}{X_i}
\end{displaymath}

\ppart Use Wald's Identity to find $\E[T]$

\eparts   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
\problem{\bf [10 points]}

Recall than in the Chinese Appetizer Problem $R$ is number of people that
get the same appetizer after a spin of the Lazy Susan.

\bparts

\ppart
Compute the variance of $R$.

\ppart
Show that the upper bound that you get on $\Pr(R \geq N)$ from the strong form
of Chebyshev's inequality is tight.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem {\bf [10 points]} 

In this problem, we analyze probabilistically the 1st stage of bubble sort
performed on a list of $n$ integers $\{ i_1, \ldots i_n \}$.  
We assume that all the integers are 
distinct.
%Consider the following sequential $n$-player tournament.
On the first step we compare integers $i_1$ and  $i_2$. If $i_1 > i_2$ we
swap them otherwise we leave them as they are.
%In round $1$, players $1$ and $2$ play each other.  
On step $k~(2\leq k\leq n-1)$, we compare the new  $i_k$ with
$i_{k+1}$. If $i_k > i_{k+1}$ we swap else we leave them as they are.
%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.
We assume that the order of the integers is chosen uniformly from all 
possible orderings.  
%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 on the $k$th step ($2\leq k\leq n-1)$,
$i_{k+1}$ is the biggest integer to appear in the list so far?

%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_k$ be a random variable that is equal to $1$ if $i_{k+1} > i_{k}$. 
What is $\E[C_k]$?

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

\ppart  
Let random variable $C=\sum_{k=1}^n C_k$. 
Give an asymptotic bound for $\E[C]$ as well as an interpretation
of what $\E[C]$ is.
\eparts


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

\end{problems}
\end{document}
