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

\newcommand\Ex[1]{\mbox{Ex}[\, #1 \, ]}
\newcommand\vari{\mbox{Var}}
\newcommand\Prob[1]{\mbox{Prob}[\, #1 \, ]}

\begin{document}

\pset{10}{November 18, 1997}{November 25, 1997}

{\bf Reading:} Lecture notes

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

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

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


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

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

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

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

\eparts

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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$?

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

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

\ppart 
Design a variant of the game (by modifying the amount paid while keeping it
exponential) in which Marylin's claim is not true.

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

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

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

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

\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 $\Ex{X}$. 

\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 $\Ex{Y}$.
\eparts

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


\end{problems}
\end{document}


