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

\begin{document}
\psol{10}{May 5, 1998 (typos corrected 9:30pm)}

\begin{problems}
\problem{\bf [8 points]}

Show that if two positive random variables $R$ and $T$ are independent, then 
$2R$ and $e^T$ are also independent.

{\bf Solution}

\begin{eqnarray*}
\Pr((2R=r)\wedge (e^T=t)) &=& \Pr((R=r/2 )\wedge( T=\ln t))\\
&=& \Pr(R=r/2)Pr(T=\ln t)\\
&=& \Pr(2R=r)Pr(e^T=t)
\end{eqnarray*}

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

\problem{\bf [12 points]}

\bparts

\ppart{\bf [6 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.

$\Pr(R_2=1) = 1/2$\\
$\Pr(R_2=2) = 1/4$\\
$\Pr(R_2=4) = 1/4$

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

{\bf Solution}

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

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

\ppart{\bf [6 points]}

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

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

{\bf Solution}

$\Pr(X = 1) = \Pr(R_2 = 1) = 1/2$.\\
$\Pr(X = 4) = \Pr(R_2 = 2) = 1/4$.\\
$\Pr(X = 8) = \Pr(R_2 = 4) = 1/4$.\\

\eparts




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf [24 points]}

Consider the process of tossing a biased coin with
$\mbox{Prob(Heads)}=p$. Assume that all tosses are mutually independent.

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

What is the probability that exactly $k$ of the first 100 tosses will
turn up heads? 

{\bf Solution}

The result of each toss is the outcome of a Bernoulli trial with
probability of success $p$.  Therefore the number of heads
observed in the first 100 tosses is binomially distributed.

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



\ppart{\bf [7 points]}

Consider the first 100 tosses. For what values of $k$ is the
probability of getting exactly $k$ heads greater than the probability
of getting exactly $k-1$ heads? For what values of $k$ is it less?
What value of $k$ is the most likely number of heads?



{\bf Solution}

Consider the ratio of the probability of $k$ heads over the
probability of $k-1$ heads.

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

This quantity is greater or equal to $1$ if and only if $(100-k+1)p \geq k(1-p)
\Longleftrightarrow 101p \geq k$.
So, for $k \leq 101p$ the probability increases from $k-1$ to $k$,
and for $k \geq 101p$, the probability decreases.
The value of $k$ that maximizes the probability is thus
$\lfloor 101p \rfloor$.



\ppart{\bf [6 points]}

Define $W_k$ to be the waiting time until the
$k$th head, that is, the number of tosses necessary to reach a total
of $k$ heads. For example, if the sequence of flips is {\em
HTTHHT...}, then $W_1=1, W_2=4,$ and $W_3=5$.

Determine $E(W_k)$ in terms of $k$ and $p$. (Hint: determine $E(W_1)$
and use linearity of expectation.)

{\bf Solution}

$E(W_1)$ is the mean time to failure. From class, we have that 
$E(W_1)=1/p$.

Since future heads are independent of past ones, the time to get heads
twice is $W_1+W_1 = 2W_1$, and more generally the time to see $k$
heads is $kW_1$.  Therefore 
\begin{eqnarray*}
E[W_k] &=& E[kW_1]\\
&=& kE[W_1]\\
&=& k/p
\end{eqnarray*}

\ppart{\bf [6 points]}

Determine $\mbox{Prob}(W_k=n)$ in terms of $k$, $p$, and $n$.

{\bf Solution}

Consider the event $\{W_k = n\}$.  This means that the $n$th flip was
heads, and there were $k-1$ heads on the previous $n-1$ flips.

Since the arrivals at each second are independent, we have:
\begin{eqnarray*}
\Pr(W_k = n) & = & \Pr(\text{$k-1$ heads in $n-1$ flips})P(\text{1 arrival 
on the $n$th second})\\
& = & {n-1 \choose k-1} p^{k-1}(1-p)^{l-k} p\\
& = & {n-1 \choose k-1} p^{k}(1-p)^{l-k}\\
\end{eqnarray*}

\eparts

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

\problem{\bf [15 points]}

Chuck-A-Luck is played in many casinos. One version of it is as
follows.  There is a cage with three dice in it.  The player pays
$\$1$ to guess a number between 1 and 6. The three dice are then
rolled. If one die shows the player's number, he wins $\$2$ (i.e., he
wins his old dollar back plus a dollar profit). If two dice show his
number, he wins $\$3$. If three dice show his number, he wins
$\$4$. If no die shows the number, he wins nothing.

If Bobo spends his last dollar on a game of Chuck-A-Luck, what is his
expected wealth after the game?

{\bf Solution}

Let random variable $Y$ be the number of dice showing the chosen number, and
$X$ be his wealth after one play.  Then $X=0$ if $Y=0$ and $X=i+1$, if
$Y=i$, for $i=1,2,3$. 
$P(Y=i) = \displaystyle {3 \choose i} \left( \frac{1}{6} \right)^i
			\left( \frac{5}{6} \right)^{3-i} $, $i=0,1,2,3$.
Therefore, 
\begin{eqnarray*}
E(X) &=& 0 \cdot P(Y=0) + \sum_{i=1}^{3}(i+1) \cdot P(Y=i) \\
     &=& \sum_{i=1}^{3}(i+1) \cdot {3 \choose i} \left( \frac{1}{6} \right)^i
			\left( \frac{5}{6} \right)^{3-i} \\
     &=& \frac{1}{216} (2 \cdot 75 + 3 \cdot 15 + 4 \cdot 1) \\
     &=& 199/216 = .921
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%55

\problem{\bf [14 points]}

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 [7 points]}

Assume that the system fails iff at least one component fails. Find
the system's mean time to failure.

{\bf Solution}

At any particular step, the probability that at least one component
fails is $1-(1-p)^2 = 2p-p^2$.

Let $X$ be the random variable whose value is the time to failure. The
distribution of $X$ is

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

From class, the mean time to failure $E(X)={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 [7 points]}

Now assume that the system fails iff both components fail
simultaneously. Find the system's mean time to failure.

{\bf Solution}

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

Let $Y$ be the random variable whose value is the step number of the
first step at which both components fail simultaneously. The
distribution of $Y$ is

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

so the mean time to failure is $E(Y) = {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

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

Suppose that we toss two hundred mutually independent coins, each with
Pr(Heads$)=.4$. Use the formula given in lecture to estimate the
probability that 60 or fewer coins will be heads.

{\bf Solution}

We note that $n=200$, $p=.4$, and $\alpha=60/200=.3$.
\begin{eqnarray*}
F_{200,.4}(60) &\leq& {{1-.3}\over{1-{{.3}\over{.4}}}}f_{200,.4}(60)\\
&=&{{.7}\over{.25}}
{{2^{\left(.3\log_2\left({{.4}\over{.3}}\right)+
(1-.3)\log_2\left({{1-.4}\over{1-.3}}\right)\right)\times 200}
e^{a_{200}-a_{60}-a_{140}}}
\over{\sqrt{2\pi (.3) (1-.3)(200)}}}\\
&\approx&(2.8){{2^{(.1245-.1557)\times 200}\times .99...}
\over
{16.24}}\\
&\approx& 2.2811 \times 10^{-3}
\end{eqnarray*}

So Pr(less than or equal to 60 heads$)\leq 2.2811\times 10^{-3}$.
%%%%%%%%%%%%%%%%%%%%%
\problem{\bf [12 points]}

An airport bus deposits 8 passengers at 6 stops.
Assume that each passenger is as likely to get off at 
any stop as another and that they act independently.
The bus stops only if someone wants to get off.
What is the probability that nobody gets off at the 
third stop?
What is the expected number of stops it will make?

{\bf Solution}

For each individual, the probability he {\em does not} get off at the
third stop is $\frac{5}{6}$.  Therefore, the probability
that no one gets off at the third stop is $(\frac{5}{6})^{8} = 
0.2326$.

Let $I_k$ be an indicator variable for whether the bus stops at the
$k$-th stop.  Then, $X=\sum_k I_k$ is the total number of stops.  By
linearity of expectation,
\[
E(X) = E(I_1) + E(I_2) + E(I_3) + E(I_4) + E(I_5) + E(I_6)
\]

For each $I_k$, the $E(I_k)$ is the probability the bus stops at the
$k$-th stop, or $1-0.2326=0.7674$.  Therefore, $E(X) = 6(0.7674) = 4.6044$.

\end{problems}

\end{document}

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

\problem 

Let $S$ be the set of functions from $\{1,\ldots,n\}$ to
$\{1,\ldots,k\}$, and let $\Pr:S\rightarrow [0,1]$ be the uniform
probability distribution on $S$, so that $\Pr(f)=1/|S|$ for all $f\in
S$.

Define the random variable $R\colon S\to \nat$
as $R(f) = |\mbox{range}(f)|$,
that is the random variable $R$ expresses
the size of the range of a function 
selected uniformly at random from $S$.

Express the expected value of $R$ as a function of $n$ and $k$.

{\bf Solution}

Let $I_a$ be the indicator variable for $a$ being in the $\mbox{range}(f)$.
Then, 
\[
R= I_1 + I_2 +\dots +I_k
\]
and
\[
E(R) = E(I_1) + E(I_2) + \dots + E(I_k) = kE(I_1)
\]
by symmetry.

$E(I_1)$ is the probability that $1$ is the $\mbox{range}(f)$.  This
probability is just 1 minus the probabilility that $1$ is {\em not} in
the $\mbox{range}(f)$.

The set of functions that do not have $1$ is the range is $(k-1)^n$.
Since $|S|$ is $k^n$, the probability that 1 is not in the range
is $(1-\frac{1}{k})^n$.  Therefore,
\[
E(R) = k (1- (1-\frac{1}{k})^n)
\]
For large $k$, this is approximately
$k(1- e^{-n/k})$.


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

We want to determine the percentage $r$ of people who intend to watch
the final episode of {\em Seinfeld.} Our polling method is the same as
that discussed in lecture: we sample the opinion of $n$ people chosen
uniformly and at random, with replacement.

How many people should be polled so that $r$ is within 3 points of the
true percentage, with probability at least .96?

{\bf Solution}

$\epsilon = .03, \delta = .04$

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

