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

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

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

\begin{document}

\psol{10}{November 22, 1997}

\bigskip

\begin{problems}


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

In a physics experiment, every second a $\pi$-meson passes through a detector
with probability $p$.  $\pi$-meson arrivals are mutually independent from 
second to second. 

\begin{problemparts}

\problempart
What is the probability of getting exactly $k$ $\pi$-mesons passing through
the detector in one minute?

\bigskip

At each second the appearance of a $\pi$-meson is the outcome of a
Bernoulli trial with probability of success $p$.  Therefore the number
of $\pi$-mesons observed in $60$ seconds is Binomially distributed.

$$
\Pr(k) = {60 \choose k} p^k (1-p)^{60-k}
$$

\problempart

Suppose the detector is on for one minute.
For what values of $k$ is the probability of getting exactly $k$ $\pi$-mesons 
greater than the probability of getting exactly $k-1$ $\pi$-mesons?
For what values of $k$ is it less?
What value of $k$ is the most likely number of $\pi$-mesons?

\bigskip

Consider the ratio of the probability of $k$ $\pi$-mesons  over the
probability of $k-1$  $\pi$-mesons.

\begin{eqnarray*}
\frac{{60 \choose k}p^k(1-p)^{60-k}}{{60 \choose {k-1}}p^{k-1}(1-p)^{60-k+1}}
& = &\frac{\frac{60!}{k!(60-k)!}p}{\frac{60!}{(k-1)!(60-k+1)!}(1-p)} \\
& = & \frac{(60-k+1)p}{k(1-p)}
\end{eqnarray*}

This quantity is greater or equal to $1$ if and only if $(60-k+1)p \geq k(1-p)
\Longleftrightarrow 61p \geq k$.
So, for $k \leq 61p$ the probability increases from $k-1$ to $k$,
and for $k \geq 61p$, the probability decreases.
The value of $k$ that maximizes the probability is thus
$\lfloor 61p \rfloor$. (Note: at the maximum value, the probability might
change).

\problempart
Suppose that we keep observing until $m$ $\pi$-mesons are observed. Find the
probability distribution for the time $T$ to see $m$
$\pi$-mesons. What is the expected value of $T$?

\bigskip

Consider the event $\{T = l\}$.  This means that there was one $\pi$-meson
observed in the $l$th second, and there were $m-1$ $\pi$-meson arrivals 
on the previous $l-1$ seconds.

Since the arrivals at each second are independent, we have:

\begin{eqnarray*}
\Pr(T = l) & = & \Pr(\text{$m-1$ arrivals in $l-1$ seconds})P(\text{1 arrival 
on the $l$th second})\\
& = & {l-1 \choose m-1} p^{m-1}(1-p)^{l-m} p\\
& = & {l-1 \choose m-1} p^{m}(1-p)^{l-m}\\
\end{eqnarray*}

Let $X$ be the time to observe one $\pi$-meson.  Since future arrivals are 
independent of past arrivals, the time to see two $\pi$-mesons is $X+X = 2X$,
and more generally the time to see $m$ $\pi$-mesons is $mX$.
Therefore $E[T] = mE[X] = {m \over p}$.

\end{problemparts}

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

A couple keeps having children until they have at least one boy and one girl.
What is the expected number of children? Assume that boys and girls are 
equiprobable and that births are mutually independent.

\bigskip

The first birth is either a boy or a girl.  Say it's a girl.  Then they are
having children until they get a boy.  
In class we showed that the expected number of children to get a boy is
$1/{1 \over 2} = 2$.  So the total expected number of children until they
get a boy and a girsl is $1+2 = 3$.

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

Remember the game demonstrated in lecture.
Professor Leighton  shows you two envelopes, each lying face
down on a table. He tells you there's a number from the range
$\{0,\ldots, n\}$ written in each. You pick an envelope, and
Prof. Leighton shows you the number written in it.  
He now tells you that you
can either choose to stay with that number, or switch to the number
written in the other envelope. 
You {\em win} if the number you end up with
is the biggest of the two (that is, if either you originally picked
the biggest and decided to stay, or if you originally picked the
smallest and decided to switch).
A randomized strategy for this game
is a function that, for each number $i$, assigns a probability $p_i$
of switching {\em given} that the first card you picked was $i$. 
Prove that the strategy described in class for winning with probability
better that $1/2$ is optimal. (i.e prove that if Prof. Leighton picks $i$
and $i+1$ for the two numbers, where $i$ is chosen uniformly in 
$[0,n-1]$, then your expected return is at most ${1 \over 2}
+{1 \over 2n}$).

\bigskip

Let $p_i$ denote the probability that you switch if you see the pair
$i$.  Then, the  probability that you win if Prof. Leighton picks
the pair $(i,i+1)$
is the probability that you will see the smaller number and switch or that you
will see the bigger number and stay.  Since the probability of picking either
number is $1/2$, the probability that you win is

${1 \over 2}p_i + {1 \over 2}(1-p_{i+1})$.

%Let $\pi_i$ be the probability 
%with which Prof. Leighton chooses the pair $(i,i+1)$

Then, the total
probability that you win is:

%$$
%\sum_{i=0}^{n-1} \pi_i \left({1\over 2}p_i + {1\over 2}(1-p_{i+1})\right)
%= {1\over 2} + {1\over 2}\sum_{i=0}^{n-1} \pi_i (p_i-p_{i+1})
%$$

%Using the strategy described in class we have that 
%$\forall i,p_i-p_{i+1} = {1 \over n}$, therefore the above sum evaluates to
%${1 \over 2} + {1 \over 2n}$.

%If we use another strategy, then there exists an $i$ such that 
%$p_i-p_{i+1} < {1 \over n}$.  In that case Professor Leighton can set
%$\pi_i=1$ and $\pi_j =0, forall j \neq i$, and the above sum will evaluate
%to ${1 \over 2} + {1\over 2}(p_i-p_{i+1}) < {1 \over 2} + {1\over 2n}$.
%Therefore the optimal policy is the policy described in class.


$$
\sum_{i=0}^{n-1} {1 \over n} \left({1\over 2}p_i + {1\over 2}(1-p_{i+1})\right)
= {1\over 2} + {1\over 2n}\sum_{i=0}^{n-1} (p_i-p_{i+1})
= {1\over 2} + {1\over 2n} (p_0 - p_n) \leq {1\over 2} + {1\over 2n}
$$

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

Now suppose the numbers from the problem above are drawn from
the set of natural numbers, $\naturals$. Design a strategy for
playing this game such that whatever numbers are picked by Prof. Leighton 
you will have  more than an even chance of winning.

\bigskip

Let $p_i = 2^{-i-1}$ be the probability of guessing the number $i$. 
The strategy is to switch if the number you see is smaller than the one you 
guessed.

Suppose that the pair $(i,i+1)$ is chosen.  Then the probability that you win
is 

${1 \over 2}p_i +{1 \over 2}(1-p_{i+1}) =  
{1 \over 2} + {1\over 2}(2^{-i-1}-2^{-i-2}) = 
{1 \over 2} + {1 \over 4} 2^{-i-1} > { 1\over 2}$

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

Show that if two positive random variables $R$ and $T$ are independent, then 
$\sqrt{R}$ and $\log T$ are also independent.


\begin{eqnarray*}
Pr((\sqrt{R}=r)\cap (\log T=t)) &=& Pr[(R=r^2 )\cap( T=e^t)]\\
&=& Pr(R=r^2)Pr(T=e^ t)\\
&=& Pr(\sqrt{R}=r)Pr(\log T=t)
\end{eqnarray*}

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

\bparts

\ppart{\bf [5 points]}

Let $R_1$ and $R_2$ be two independent random variables.
$R_1$ takes the values $0,1$ with equal probability.
$R_2$ has the following distribution.

$P(R_2=1) = 1/2$\\
$P(R_2=3) = 1/4$\\
$P(R_2=4) = 1/4$

Compute the distribution of $R_1 2 ^{R_2}$.

\bigskip

Let $X = R_1 2 ^{R_2}$. 

$\Pr(X = 0) = \Pr(R_1 = 0) = 1/2$.\\
$\Pr(X = 2) = \Pr(R_1 = 1 \wedge R_2 = 1) = 1/4$.\\
$\Pr(X = 8) = 1/8$.\\
$\Pr(X = 16) = 1/8$.\\

\ppart{\bf [5 points]}

Now suppose that $R_1$ and $R_2$ are no longer independent.
In particular $R_1 = 0$ if $R_2$ is even, and $R_1 =1$ when $R_2$ is odd.
$R_2$ has the same distribution as in part (a).

Compute the distribution of $R_1 2 ^{R_2}$

\bigskip

$\Pr(X = 0) = \Pr(R_2 \mbox{ is even}) = 1/4$.\\
$\Pr(X = 2) = \Pr(R_2 = 1) = 1/2$.\\
$\Pr(X = 8) = \Pr(R_2 = 3) = 1/4$.\\

\eparts

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

Three gamblers meet at a bar.  Each wagers  1 dollar and the bartender flips 
a fair coin. The money is shared among the players who guessed correctly the
outcome of the coin. If no one guesses correctly, each player gets his money
back.

\bparts

\ppart 
The coin is fair and no player sees the outcome before guessing.
What is the expected return for each player if each player assumes that the
other players guess heads independently with probability $1/2$?

\bigskip

Let $X$ be the expected return of a player. It can take the values 
$-1,0,0.5,2$ with the following probabilities:

$P(X = -1) =(1/2)(3/4)$ (half a chance that he will guess wrong and 
(3/4) the others will guess right)\\
$P(X = 0) = (1/8)+(1/8)$ 
(everybody will guess correctly or everybody will guess wrong)\\
$P(X = 0.5) = (1/2)(1/2)$ (one other player will guess correctly)\\
$P(X = 2) = (1/2)(1/4)$ (only he will guess correctly)\\

Therefore $E[X] = (3/8)(-1) + (1/4)0+(1/4)(0.5)+(1/8)2 = 0$.

\ppart
Show that the answer you got in part (a) is not always correct if we don't
assume that the player's choices are mutually independent. 
(i.e show how two players can cooperate to improve their expected return).

\bigskip

Suppose players $B$ and $C$ decide to bet always the opposite (one bets 
head the other bets tail). 
Then $X_A$, the expected return of player $A$,
 can take only the values $-1$ and $0.5$ with probability $1/2$
each, so the expected return is $-0.25$.

On the other hand the expected return for either of the other players, 
say $X_B$ has the following distribution

$P(X_B = -1) = (1/2)$ (probability that he will guess wrong. In this case
$C$ guesses right).\\
$P(X_B = 0) = 0$ (It's never the case that they all guess the same outcome).\\
$P(X_B = 0.5) = (1/2)(1/2)$ (He and $A$ will guess correctly)\\
$P(X_B = 2) = (1/2)(1/2)$ (He will guess correctly and $A$ wrong).\\

$E[X_B] = (1/2)(-1) + (1/4)0.5 +(1/4)2 = 0.125$

\eparts

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

In a recent column Marilyn analyzed the following game:

A fair coin is flipped until you get heads.

You pay $2^{i-1}$ dollars if the first head appears in the $i$th toss.
What is the expected amount paid?

Marilyn argued that the expected amount is infinite because you might get very
unlucky and pay a lot.  

In this problem you will demonstrate that Marilyn's claim is right but 
her ``proof'' is wrong.

\bparts
\ppart
Show that the expected payment for the game described is indeed infinite.

\bigskip

The probability that the 1st head appears in the $i$th toss is 
$(1/2)^{i}$ ,therefore the expected payment is

$$
\sum_{i=1}^{\infty}(1/2)^{i}2^{i-1} = \sum_{i=1}^{\infty} (1/2) = \infty
$$
 
\ppart 
Design a variant of the game (by modifying the amount paid while keeping it
exponential) in which Marylin's claim is not true.

Let the amount be $(3/2)^{i-1}$.

The expected payment is

$$
\sum_{i=1}^{\infty}(1/2)^{i}(3/2)^{i-1} = 
(2/3)\sum_{i=1}^{\infty} (3/4)^i = 2
$$

\eparts

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

Flip a fair coin until you get heads.  What's the probability that you will
see an even number of tails?  Assume that the coin tosses are mutually 
independent.

\bigskip

The probability that  the 1st head appears on the $i$th toss is 
$\left({1 \over 2} \right)^i$.

\begin{eqnarray*}
\Pr(\text{even tails})  & = & \sum_{\text{$i$ is odd}} (1/2)^{i}\\
& = & \sum_{i=0}^{\infty} (1/2)^{2i+1}\\
& = & (1/2)\sum_{i=0}^{\infty} (1/4)^i\\
& = & 2/3
\end{eqnarray*}


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

We want to determine the percentage  $r$ of people that prefer Ben and Jerry's 
Chocolate Fudge Brownie over Toscannini's Cherry Garcia.
How many people should be polled so that the result is within 
1 point of the true percentage with probability at least .95?

\bigskip

$\epsilon = .01, \delta = .05$

\begin{eqnarray*}
\delta \geq 2 F_{1/2}((1/2- \epsilon)n) & \Rightarrow &
.05 \geq 2  F_{1/2}(0.49n)\\
& \Rightarrow & 0.025 \geq {0.51 \over 0.02}f_{1/2}(0.49n)\\
& \Rightarrow & 0.025 \geq {25.5 \over\sqrt{2n\pi (.49)(.51)}}2^{(H(.49)-1)n}\\
& \Rightarrow & 0.0012285 \geq {2^{(H(.49)-1)n} \over \sqrt{n}}\\
& \Rightarrow & 0.0012285 \geq {2^{-0.000288574n} \over \sqrt{n}}\\
& \Rightarrow & 0.0012285 \geq {(.9998)^n \over \sqrt{n}}\\
\end{eqnarray*}

Choosing $n=10388$ will do it.

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

Let $D_1$ and $D_2$ denote independent random variables 
uniformly distributed in $\{1,\ldots,n\}$.
Let $M_1= \max(D_1,D_2)$, and $M_2= \min(D_1,D_2)$.

\bparts

\ppart 
Compute the distribution function for $M_1$. 

\bigskip

\begin{eqnarray*}
\Pr(M_1=x) &=& \Pr(\max(D_1,D_2)=x)\\
&=& \Pr(D_1 = x~ \mbox{and}~ D_2 < x) + \Pr(D_1 < x~ \mbox{and}~ D_2 = x) +
\Pr(D_1=D_2=x)\\
&=& {1\over n}\cdot {{x-1\over n}} + {x-1\over n}\cdot {1\over n} + {1\over n}\cdot {1\over n}\\
&=& {{2x-1}\over n^2}
\end{eqnarray*}

\ppart
Are $M_1$ and $M_2$ 
independent random variables? Justify your answer.

\bigskip

$M_1$ and $M_2$ are not independent since we have:
\begin{eqnarray*}
\Pr(M_1 = x | M_2 > x) &=& 0 ~~~~~~\mbox{for $x\in \{1,2,\ldots n\}$} \\
                      &\not=& \Pr(M_1 = x)
\end{eqnarray*}
\eparts 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 12
\problem{\bf [8 points]}

% (Negative binomial distribution)

Consider a system consisting of $2$ components, each of which can
fail at each step with probability $p$.  Failures at different steps
and/or components are mutually independent (in particular, this means
that failure need not be permanent).  The steps are numbered $1,2,\ldots$.

\bparts
\ppart{\bf [5 points]}

Let $X$ be the random variable whose value is the step number of the
first step at which there is a failure (in either component).  Find $E[X]$. 

\bigskip

The probability that some of the components fail is $1-(1-p)^2 = 2p-p^2$.

The distribution of $X$ is

$\Pr(X = i) = (1-p)^{2(i-1)} (2p-p^2)$.

From class, the mean time to failure is ${1 \over 2p-p^2}$.

%$$
%E[X] = (2p-p^2)\sum_{i=1}^{\infty} i(1-p)^{2(i-1)} 
%=  (2p-p^2) { 1 \over (1 - (1-p)^2)^2} 
%= { 1 \over (2p-p^2)}  
%$$

\ppart{\bf [5 points]}

Let $Y$ be the random variable whose value is the step number of the
first step at which both components fail simultaneously.  Find $E[Y]$.

\bigskip

The probability that both components will fail simultaneously is $p^2$.

The distribution of $Y$ is

$\Pr(Y = i) = (1-p^2)^{i-1} p^2$.

so the mean time to failure is ${1 \over p^2}$.

%$$
%E[Y] = p^2 \sum_{i=1}^{\infty} i(1-p^2)^{i-1}
%= p^2 { 1 \over p^4}
%= { 1 \over p^2}
%$$

\eparts

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

\end{problems}
\end{document}





