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

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

\newcommand{\problm}{\problem \rm}
\renewcommand{\ppart}{\problempart \rm}
\newcommand{\mystrut}{\rule{0pt}{14pt}}

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

\psol{11}{December 5, 1997}

\bigskip

\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?

\bigskip

After the first child, the waiting time until they get a success (a child of 
the opposite sex) is geometrically distributed.  That is the probability that the
first success occurs on the $n$th try is 
$(1-p)^{n-1} p$ ($n-1$ failures before 1 success).

The expectation of the geometric distribution is just the mean time to failure
${1 \over p}$.

The variance is given by

$$
\sum_{n=1}^{\infty} n^2 (1-p)^{n-1} p - {1 \over p^2}
$$

From earlier in the course we know that

$$
\sum_{n=1}^{\infty} n^2 x^{n-1} = {1 \over (1-x)^2} + {2x \over (1-x)^3}
$$

Setting $x = (1-p)$ we obtain

$\sum_{n=1}^{\infty} n^2 (1-p)^{n-1} p = {2 \over p^2} - {1 \over p}$

Therefore the variance is 
${2 \over p^2} - {1 \over p} - {1 \over p^2} = {1 \over p^2} -{1 \over p}$.

And putting $p=1/2$ we get that the variance is 2.

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

\bigskip

This is the same problem as the one studied in lecture for building a system 
with $n$ components.  The components are the girls and boys
are the failures in which case we have to start over (well, the couple has to
start over).

We have $p = 1/2$, $n = 2$.

$\E[T] = {1 \over p(1-p)^n}- {1 \over p} = {1 \over 1/8} - {1 \over 1/2}
= 6$


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

\bigskip

$$
\E[X] = {1 \over n} \sum_{i=1}^n i = {(n+1) \over 2}
$$

$$
\E(X^2) = {1 \over n} \sum_{i=1}^n i^2 = 
{1 \over n}{n(n+1)(2n+1) \over 6} = {(n+1)(2n+1) \over 6}
$$

so 

$$
\vari(X) = {(n+1)(2n+1) \over 6} - {(n+1)^2 \over 4} = {n^2 -1 \over 12}
$$


\begin{eqnarray*}
\vari{(aX+bY)} & = & \vari(aX)+\vari(bY)\\
& = & a^2 \vari(X) + b^2\vari(Y)\\
& = & (a^2+b^2)\vari(X)\\
& = & {(a^2+b^2) \over 12}(n^2-1)
\end{eqnarray*}

\ppart $\Ex{\max(X,Y)}$.

\bigskip

Observe that $\Pr[\max(X,Y) = i] = \Pr[X = i \mbox{ and } Y < i] +
\Pr[X < i \mbox{ and } Y = i] + \Pr[X = Y = i] = \frac{1}{n} \cdot
\frac{i-1}{n} + \frac{i-1}{n} \cdot \frac{1}{n} + \frac{1}{n} \cdot
\frac{1}{n} = \frac{2i-1}{n^2}$.  

This means that $\E[\max(X,Y)] = \sum_{i=1}^n \frac{i(2i-1)}{n^2} =
\frac{1}{n^2} \sum_{i=1}^n (2i^2 - i) = \frac{1}{n^2}(
\frac{2n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2}) = \frac{(n+1)(4n-1)}{6n}$.


\ppart $\E[\min(X,Y)]$.  ({\em Hint:}  There is a way to get the answer 
to this using the previous part.)

\bigskip

Observe that $\E[\max(X,Y)] + \E[\min(X,Y)] = \E[\max(X,Y) +
\min(X,Y)] = \E[X + Y] = \E[X] + \E[Y]$.  Now $\E[X] = \E[Y] =
\frac{n+1}{2}$.  so $\E[\min(X,Y)] = n+1 - \frac{(n+1)(4n-1)}{6n} =
\frac{(n+1)(2n+1)}{6n}$. 

\ppart $\E[|X-Y|]$

\bigskip

We have that $|X-Y| = \max(X,Y)-\min(X,Y)$, so by linearity of expectation
$\E[|X-Y|] = \E[\max(X,Y)]- \E[\min(X,Y)] = {(n+1)(4n-1) \over 6n} - 
{(n+1)(2n+1) \over 6n} = {(n^2-1) \over 3n}$.
 
\ppart $\vari(|X-Y|)$.

\bigskip

$\vari(|X - Y|) = \E[|X - Y|^2] - (\E[|X - Y|])^2$.  But $\E[|X -
Y|^2] = \E[(X - Y)^2] = \vari(X - Y) + (\E[X - Y])^2 = \vari(X - Y) =
2 \vari(X) = \frac{n^2 - 1}{6}$ (since $\E[X - Y] = \E[X] - \E[Y] = 0$).  


This means that $\vari[|X - Y|] = \frac{n^2 - 1}{6} - (\frac{n^2 -
1}{3n})^2 = \frac{(n^2 - 1)(n^2 + 2)}{18 n^2}$.

\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]$.

\bigskip

There are many examples to see that $X$ and $Y$ are not independent.
An easy one is to note that $\Pr[X = 2]\Pr[Y = 1] \ne 0$ 
but $\Pr[XY = 2] = \Pr[X^3 = 2] = 0$.  

To see that $\E[XY] = \E[X] \E[Y]$, note that $\E[X] = 0$ and $\E[XY]
= \E[X^3] = 0$ since $X$ and $X^3$ are both symmetrical.

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

\bigskip

We have that $\vari(X + Y) = \E[(X+Y)^2] - (\E[X+Y])^2 = \E[X^2 + 2XY +
Y^2] - (\E[X]+ \E[Y])^2 = \E[X^2] - (\E[X])^2 + \E[Y^2] - (\E[Y])^2 +
2\E[XY] - 2\E[X]\E[Y] = \vari{X} + \vari{Y}$. 

\eparts

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

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.

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?

\bigskip

Let $X$ be the random variable whose value is the number of dots obtained
 in the first stage.  

Let $Y_1, Y_2, \ldots, Y_X$ be the random variables that take the value of
$1$ if the coin comes up heads, and $0$ otherwise for each coin toss
in the second stage.  
Define $Y = Y_1 + \cdots + Y_X$.

Let $Z_1, Z_2, \ldots, Z_Y$ be the random variable whose values are
the number of dots in the third stage.  Define $Z = Z_1 + \cdots + Z_Y$.  
We want to find $\E[Z]$. 
 
All the rolls and tosses are mutually independent, so
we can use Wald's theorem to get $\E[Y] = \E[X]\E[Y_i] =
(\frac{7}{2})(\frac{1}{2}) = \frac{7}{4}$.
 
Since $Y$ is determined by tosses that are
independent of the rolls in the third stage,
$Y$ and $Z_i$ are independent.  So we apply Wald's theorem again to
get $\E[Z] = \E[Y]\E[Z_i] = (\frac{7}{2})(\frac{7}{4}) = \frac{49}{8}.$

The answer is $(\frac{49}{8})$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem {\bf [10 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 infected people on the $k$th day.
Assume that each day every sick person meets $n$ {\em different} persons.

\bigskip

Let $S_k$ be a random variable giving  the number infected 
people after $k$ days. \\
We can write a recurrence for $S_{k+1}$ in terms of $S_k$. \\
\\
Let the sick people after day $k$ be numbered $1,\ldots,S_k$. \\
Let $H_i$ be a random variable giving the number of healthy 
people infected by sick person $i$ in one day. \\
Then $H_i$ has a binomial distribution with parameters $n$ and $p$. \\
Then: \\
\[
S_{k+1} = S_k+ \sum_{i=1}^{S_k} H_i
\]
It follows from linearity of expectation that
\[
\E[S_{k+1}] = \E[S_k]+\E[ \sum_{i=1}^{S_k} H_i].
\]
Then by Wald's theorem,
\[
\E[S_{k+1}] = \E[S_k]+\E[S_k]\cdot \E[H]
\]
where $H$ is a variable with the binomial distribution with
parameters $n$ and $p$. \\
Thus, $\E[H] = np$.  \\
\\
So
\[
\E[S_{k+1}] = \E[S_k]+\E[S_k]\cdot np = (1 + np) \E[S_k]
\]
Also, $\E[S_0] = 1$. \\
So we have a recurrence involving these expectations. \\
Writing $e_i$ for $\E[S_i]$, we have:
\[
e_{k+1} = (1+np)e_k
\]
and 
\[
e_0 = 1
\]

\ppart Solve the recurrence of part (a).

\bigskip

$e_k = (1+np)^k$.

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

\bigskip

 Let $B_i$ be the indicator variable for whether the $i^{th}$ sick person gets better.  Then $\E[B_i] = r$.  Then
\[
S_{k+1} = S_k+ \sum_{i=1}^{S_k} (H_i-B_i)
\]
It follows that
\[
\E[S_{k+1}] = \E[S_k]+\E[S_k]\cdot \E[H]-\E[S_k]\E[B_i]
\]
and so

\begin{eqnarray*}
e_{k+1} &= & e_k(1+np-r)\\ &= &(1+np-r)^k
\end{eqnarray*}

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

\bigskip

We view this as an experiment where at each step we make a choice between
three equiprobable outcomes.

Let $X_i$ = number of hours to return to room on $i$th step.

Let $N$ = number of steps until good door is selected.

Then $N$ is geometrically distributed with probability $1/3$.

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

\bigskip

$\Pr(X_i = 2) = 1/3$

$\Pr(X_i = 4) = 1/3$

$\Pr(X_i = 8) = 1/3$

$\E[X_i] = 14/3$

$\E[N] = 3$

By Wald's Identity

$$
\E[\sum_{i=1}^N X_i] = 14
$$


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

\bigskip

$\Pr(R = 0) = \frac{N-1}{N}$

$\Pr(R = N) = \frac{1}{N}$

$\vari(R) = \E[R^2] - \E[R]^2 = \frac{N^2}{N} - 1 = N-1$


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

\bigskip

The strong form of Chebyshev's inequality states that

$$
\Pr(R - \E[R] \geq c \cdot \sigma_R) \leq {1 \over 1+c^2}
$$

Set $c = \sqrt{N-1}$. Then $c \cdot \sigma_R = N-1$ and

$$
\Pr(R \geq N) = \Pr(R - 1 \geq N-1)  \leq { 1 \over 1+(N-1)} = {1 \over N}
$$

Since we know that $\Pr(R \geq N) = {1 \over N}$ for this problem, the 
bound is tight.


\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 10
\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?

\bigskip

$\Pr({\mbox{choosing largest of $n$ numbers}}) = 1/n$.  

$\Pr({\mbox{$i_{k+1}$ in $k$ step is highest so far}})=1/(k+1)$.

%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 ]$?

\bigskip

$\E[C_k] = \Pr({C_k = 1}) 
	= \Pr({\mbox{ $i_k$ is highest so far}}) 
	= \frac{1}{k+1}$.

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

\bigskip

$\E[C] = \sum_k \E[C_k] = \sum_{k=2}^{n}\left( \frac{1}{k}\right)
	 \sim \ln n$. 

$C$ is the total number of swaps, 
so $\E[C]$ is the expected number of swaps.

\eparts


\end{problems}

\end{document}




