\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps8
A biased coin has probability $p$ of heads and probability $1-p$ of tails.
Suppose we flip this coin $n$ times.
\begin{problemparts}
\problempart
What is the probability of getting exactly $k$ heads?
\problempart
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?
\problempart
Show that if $p=1/n$ then the probability of getting no heads is 
$\sim 1/e$ (for large $n$).
What is the ratio of the probability of no heads to the probability
of exactly one head?
\end{problemparts}

\omitsolution{
\begin{enumerate}
\item
Out of the $n$ tosses, $k$ of them are heads and $n-k$ of them are
tails.  The probability of any particular sequence is $p^k(1-p)^{n-k}$.
For a sequence of $n$ coins, there are ${n \choose k}$ ways 
to pick a sequence with $k$ heads.  Thus, the probability
of exactly $k$ heads is 
\[
{n \choose k} p^k (1-p)^{n-k}
\]

\item
Consider the ratio of the probability of $k$ heads over the
probability of $k-1$ heads.
\begin{eqnarray*}
\frac{{n \choose k}p^k(1-p)^{n-k}}{{n \choose {k-1}}p^{k-1}(1-p)^{n-k+1}}
& = &\frac{\frac{n!}{k!(n-k)!}p}{\frac{n!}{(k-1)!(n-k+1)!(1-p)}} \\
& = & \frac{(n-k+1)p}{k(1-p)}
\end{eqnarray*}

This quantity is greater than 1 if and only if $(n-k+1)p>k(1-p)
\Longleftrightarrow np+p>k$.
So, for $k<np+p$ the probability increase from $k-1$ to $k$,
and for $k>np+p$, the probability decreases.
The value of $k$ the maximizes the probability is thus
$\lfloor np+p \rfloor$.

\item
The probability of no heads is $(1-p)^n= (1-\frac{1}{n})^n$.  For
large $n$, this expression approaches $1/e$.  

The probability of
exactly one head is ${n \choose 1}p(1-p)^{n-1} =
(1-\frac{1}{n})^{n-1}$.  Forming the ratio, we find the probability of
no heads over the probability of exactly one head is
$\frac{1}{1-1/n}$, which is one over the probability of a tail.
\end{enumerate}
}

\problem %source: spring00 ps9
\begin{problemparts}

\problempart
Consider families with 3 children, assume that the events
that the lst, 2nd and 3rd child are girls are all independent, and have
probability 1/2.

Let $X$ be the event that ``the family has children of both sexes'', and
$Y$ the event that "the family has at most one girl".
Are these events independent?  Prove or disprove.

\solution{
To simplify scenario, think of this as flipping three fair coins. 
Then X is the event that there is at least one head and at least one tail, and
Y is the event that there is at most one head. 

For X:
\begin{eqnarray*}
\Pr(\text{at least one head and one tail}) 
  & = & 1 - \Pr(\text{zero heads or zero tails}) \\
  & = & 1 - \Pr(\text{zero heads}) - \Pr(\text{zero tails})\\
  & = & 1 - 1/8 - 1/8\\
  & = & 3/4
\end{eqnarray*}

For Y:
\begin{eqnarray*}
\Pr(\text{at most one head})  
& = & \Pr(\text{zero heads or one head})\\
& = & \Pr(\text{zero heads}) + \Pr(\text{one head})\\
& = & 1/8 + 3 * 1/8 \\
& = & 1/2
\end{eqnarray*}

For $X \cap Y$:
\begin{eqnarray*}
\Pr(\text{(at most one head) and (at least one head and one tail)})  
& = & \Pr(\text{exactly one head and two tails})   \\
& = & 3 * 1/8 \\
& = & 3/8 \\
\end{eqnarray*}

Since $Pr(X \cap Y) = Pr(X) * Pr(Y)$ the two are independent. 
}

\problempart
%Part (b):
Consider the same question for a family of 2 children.
\solution{

For X:
\begin{eqnarray*}
\Pr(\text{at least one head and one tail}) 
  & = & 1 - \Pr(\text{zero heads or zero tails}) \\
  & = & 1 - \Pr(\text{zero heads}) - \Pr(\text{zero tails})\\
  & = & 1 - 1/4 - 1/4\\
  & = & 1/2
\end{eqnarray*}

For Y:
\begin{eqnarray*}
\Pr(\text{at most one head})  
& = & \Pr(\text{zero heads or one head})\\
& = & \Pr(\text{zero heads}) + \Pr(\text{one head})\\
& = & 1/4 + 2 * 1/4 \\
& = & 1/4
\end{eqnarray*}

For $X \cap Y$:
\begin{eqnarray*}
\Pr(\text{(at most one head) and (at least one head and one tail)})  
& = & \Pr(\text{exactly one head and one tail})   \\
& = & 2 * 1/4 \\
& = & 1/2 \\
\end{eqnarray*}

Since $Pr(X \cap Y) \neq Pr(X) * Pr(Y)$ the two are not independent. 

}

\problempart
%Part (c)
Consider the same question for a family of 4 children.

\solution{

For X:
\begin{eqnarray*}
\Pr(\text{at least one head and one tail}) 
  & = & 1 - \Pr(\text{zero heads or zero tails}) \\
  & = & 1 - \Pr(\text{zero heads}) - \Pr(\text{zero tails})\\
  & = & 1 - 1/16 - 1/16\\
  & = & 7/8
\end{eqnarray*}

For Y:
\begin{eqnarray*}
\Pr(\text{at most one head})  
& = & \Pr(\text{zero heads or one head})\\
& = & \Pr(\text{zero heads}) + \Pr(\text{one head})\\
& = & 1/16 + 4 * 1/16 \\
& = & 5/16
\end{eqnarray*}

For $X \cap Y$:
\begin{eqnarray*}
\Pr(\text{(at most one head) and (at least one head and one tail)})  
& = & \Pr(\text{exactly one head and three tail})   \\
& = & 4 * 1/16 \\
& = & 1/4 \\
\end{eqnarray*}

Since $Pr(X \cap Y) \neq Pr(X) * Pr(Y)$ the two are not independent. 

}
\end{problemparts}

%[[[How could these be independent? Seems unreasonable]]]

\problem %source: spring00 ps9
Shishir, David, and Ken went target shooting last weekend.
They shot simultaneously at an empty soda can, which fell over.
They have probabilities $p_s$, $p_d$ and $p_k$ of hitting it.
Calculate the following probabilities; state any independence
assumptions you need.

\begin{problemparts}
\problempart The probability that all three hit the can.

\solution{
Let S, D, and K (respectivelly) be the events that they each hit the can. 
And let F be the event that the can fell over. 

Assume that the can needs to be hit to fall over. Also assume mutual exclusivity 
on whether or not each person hits the can.

So we want $\Pr (S \cap D \cap K | F)$.

\begin{eqnarray*}
\Pr(S \cap D \cap K \mid F) & = & \frac{\Pr (S \cap D \cap K \cap F) }{\Pr(F)}\\
& = & \frac{\Pr(F \mid S \cap D \cap K) \Pr (S \cap D \cap K)}{\Pr(F)} \\
& = & \frac{p_sp_dp_k}{\Pr(F)}
\end{eqnarray*}

To calculate $\Pr(F)$:
\begin{eqnarray*}
\Pr(F) & = & Pr (F \mid S \cup D \cup K) \Pr(S \cup D \cup K) 
             + Pr (F \mid \bar{S \cup D \cup K}) \Pr(\bar{S \cup D \cup K}) \\
       & = & 1 * \Pr(S \cup D \cup K) 
             + 0 * \Pr(\bar{S \cup D \cup K}) \\
       & = & p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k 
\end{eqnarray*}

Altogether:
\begin{eqnarray*}
\Pr(S \cap D \cap K \mid F) & = & \frac{p_sp_dp_k}{\Pr(F)} \\
         & = & \frac{p_sp_dp_k}{p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k} \\
\end{eqnarray*}
}

\problempart The probability that Shishir hit the can.

\solution{
\begin{eqnarray*}
\Pr(S) & = & \frac{\Pr (S \cap F) }{\Pr(F)}\\
& = & \frac{\Pr(F \mid S) \Pr (S)}{\Pr(F)} \\
& = & \frac{p_s}{p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k }
\end{eqnarray*}
}

\problempart The probability that exactly two of them hit the can.

\solution{
\begin{eqnarray*}
\Pr(\text{exactly two hit the can} \mid F) & = & 
\frac{\Pr(F \mid \text{exactly two hit can}) \Pr(\text{exactly two hit can})}{\Pr(F)} \\
& = & 
\frac{\Pr(\text{exactly two hit can})}{p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k }\\
& = & 
\frac{p_sp_d(1-p_k) + (1-p_s)p_dp_k + p_s(1-p_d)p_k}{p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k }\\
\end{eqnarray*}
}


\end{problemparts}

\problem %source: spring00 ps9
Imagine a random length n string of 0s and 1s. We would like to find a
method for determining the probability of a length k substring consisting of only 0s.

\problempart 

Develop a recurrence for the probability of seeing the substring 00 in a random 
bit string of length n.

\solution{
Let p(n) be the probability of seeing 00 in a random string of length n. Now 
segment across three possibilities for the start of the string: 
\begin{enumerate}
\item Starts with 00: This happens with probability $1/4$. When it happens, then we are done.
\item Starts with 1: This happens with probability $1/2$. When it happens, then our chance of having a 00 in the string is now p(n-1).
\item Starts with 01: This happens with probability $1/4$. When it happens, then our chance of having a 00 in the string is now p(n-2).
\end{enumerate}
All total, our recurrence is:
\[ p(n) = 1/4 + (1/2) p(n-1) + (1/4) p(n-2) \]
}

\problempart
Solve the recurrence.

\solution{

The roots are $(1 + \sqrt{5})/4$ and $(1-\sqrt{5})/4$
and the particular solution is $p(n) = 1.$
The coefficients are 
$(-5+3\sqrt{5})/10$ and $(-5-3\sqrt{5})/10$.

The full solution is:
\[
\frac{-5-3\sqrt{5}}{10}
\left(
\frac{1+\sqrt{5}}{4}
\right)^n
+
\frac{-5+3\sqrt{5}}{10}
\left(
\frac{1-\sqrt{5}}{4}
\right)^n
+1
=
0
\]

}



\problempart
Write a general recurrence for seeing a k-length string of all 0s within a
random string of length n.

\solution{
The strings partion by starting points again. The partions are strings that start with
1, 01, 001, 0001, \ldots 0000001 (of length k).and 0000000 (of length k)

This means the recurrence is:

\[p(n) = \frac{1}{2^k} + \frac{p(n-1)}{2} + \frac{p(n-2)}{4} + \ldots \frac{p(n-i)}{2^i} 
+ \ldots \frac{p(n-k)}{2^k} 
\]
}

\problem %source: spring00 ps9
Suppose there are 120 people in a room. Assume that their
birthdays are independent and uniformly distributed. As stated in
lecture notes, with probability $> 99\%$ there will be two that have
the same birthday.

Now suppose you find out the birthdays of all the people in the room
except one---call her ``Jane''---and find all 119 dates to be different.

\begin{problemparts}

\problempart 
What's wrong with the following argument:
\begin{quotation}\noindent
With probability greater than 99\%, some pair of people in the room have
the same birthday.  Since the 119 people we asked all had different
birthdays, it follows that with probability at greater than 99\% Jane has
the same birthday as some other person in the room.
\end{quotation}

\solution{


Here's the problem with the argument: Let $A$ be the event that some two
people in the room have the same birthday.  Let $B$ be the event that the
119 people we asked all have different birthdays.

It is true that $\prob{A} > 0.99$ (that is indeed the probability
spoken about in the lecture notes). However, that is the \emph{a
priori} probability, i.e., assuming all the birthdays are
uniform and independent, with no other constraints. The argument
above makes the erroneous assumption that event $A$ has
probability of at least $99\%$ even once we know that event $B$
holds. But once we know that event $B$ holds, the birthdays are
no longer independent. Thus $\prob{A \mid B}$ is not necessarily
equal to $\prob{A}$ (in our case, they are actually quite
different, as will be computed in part~(b)).

}


\problempart 
What is the actual probability that Jane has the same birthday
as some other person in the room?

\solution{

Let $S$ be the set of birthdays of the 119 people in the room
other than Jane. By assumption, $|S| = 119$. Let $b$ be the date
of Jane's birthday. Since $b$ is uniformly distributed over a
set of size 365, and $b$ is independent of all the birthdays in
$S$, we have
\begin{align*}
\prob{b\in S\mid B} = \frac{|S|}{365} = \frac{119}{365} \approx
32.6\%,
\end{align*}
where $B$ is the event that the 119 people we asked all have
different birthdays.

}
\end{problemparts}

\problem %source: spring00ps9
%[[[I like this one a lot.  We should also include something of this
%kind on the tutorial.]]]

% [[[From Sheldon Ross' book, "a first course in probability", p. 95]]]

% [[[Needs writing]]]

Consider a complete graph on $6$ vertices (a complete graph means there is
an edge between every pair of vertices).

We would like to prove the following theorem:
\begin{quote}
It is
possible to color the {\em edges\/} of the complete graph on 6
vertices, with colors red or blue, in
such a way that no set of 4 vertices has all of its 
$\left( \begin{array}{c} 4 \\ 2 \end{array} \right)$
connecting edges colored the same way.
Call such a coloring a "mixed-up" coloring.
\end{quote}

One way of solving this problem would be to actually exhibit a mixed-up
coloring.  But that's not the way they're going to do it in this
problem\ldots

%The preferred way is to demonstrate that, if all the edges are
%colored by independent coin tosses (1/2 probability red, 1/2
%probability blue) for each edge, then the probability of a non-mixed-up
%coloring (one in which some 4-subset has all its edges colored the same)
%is strictly less than 1.
%That will imply that there has to be at least one mixed-up coloring in
%the sample space.
%
%Here are some parts that should guide them toward the solution:
%
%We might ask them to show their work, especially saying where they are
%using various facts about probability.

\begin{problemparts}

\problempart
Start by numbering all the 4-subsets of the vertices, 1,2,\ldots
%Part (a):
How many 4-subsets are there? 

\solution{

$\left( \begin{array}{c} 6 \\ 4 \end{array} \right) = 15$

%[[[6 choose 4 = 15]]]
}

\problempart
Define $A_i$ to be the event that the ith 
subset (in the numbered list) has all its edges colored the same color.
Compute $\Pr(A_i)$. 

\solution{
The chance that they are all red is $(1/2)^6$ so the chance that
they are all either blue or red is $2 * (1/2)^6$ or $1/32$.
%$2 * (1/2)^6 = 1/32$.  Uses independence and product rule.
}

\problempart
%Part (c):
Give an upper bound for $\Pr( \cup_i A_i)$. 
Your bound should come out less than 1.

\solution{

Using Boole's Law ($Pr(\cup A_i) \leq \sum Pr(A_i)$),
we have an upper bound of $\binom{6}{4} * \frac{1}{32}$ or
$\frac{15}{32}$.

%[[[15/32]]]
%
%[[[Use Boole's law, just adding up the probabilities---that is, just
%multiply the probability from part b by 6-choose-4.]]]

}

\problempart
Explain in your own words why that shows that a mixed-up coloring
exists. 

\solution{
Since the probability that a mixed up coloring does not exist is less than 1, then 
the probability that one does exist is greater than 0. Since this event has a 
nonzero probability, some such coloring must exist.
}

\problempart
(Optional)
Can you come up with a specific mixed-up coloring for this graph?

\problempart
%Part (f):
(Optional)
Try to generalize your reasoning in this problem to a condition on a
pair of numbers $n$ and $k$ that allows such a theorem to be proved (for
size $k$ subsets of an $n$-vertex graph).

%[[[Worked out in detail in Ross, if you want to check it.]]]
\end{problemparts}


%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%%% S99 ps10


\problem{\bf (12 points)}

Lockheed-Martin is currently in the process of designing the new space
shuttle, the ``Venture Star''.  Suppose that it has $100,000$ parts
and the probability that each part will fail is $1/1000$.  Redundancy
has been designed into the spacecraft so that it will fly as long as
no more than $125$ parts fail.  The failure of each part is
independent of the failure of any other part.  Prove that the
probability that Venture Star will fly successfully is at least
$99\%$.

\solution{You have to upper bound the probability that less than
$100,000-125=99,875$ parts will be OK.  This upper bound turns out to be
slightly less than $1 \%$.  You take $n=100,000$,
$\alpha=99,875/100,000=0.99875$ and $p=1-1/1000=0.999$ (then $\alpha<p$),
and compute an upper bound for $F_{n,p}(\alpha n)$ using Theorem 3.1 from
Lecture 21 in the lecture notes.  First you should get that
$f_{n,p}(\alpha n)\approx{0.001972}$.  Then
\[F_{n,p}(\alpha n)
\leq \frac{1-\alpha}{1-\frac{p}{\alpha}}f_{n,p}(\alpha n) \approx
4.995 * 0.001972 \approx 0.0098.\]
}



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset9 problem4 spring98, (Modified from Fall 96 Pset 10 Problem 3)
\problem 

In a complex system with 1,000 different components, each component is
known to fail with probability at most $\frac{1}{10,000}$. The failures may not be independent events. 

\bparts
\ppart Prove that $\frac{1}{10}$ is an upper bound for the probability that one or more components in the system fail. [10 pts]

\ppart Show that this upper bound is optimal by giving a case where the
probability that one or more components in the system fail is exactly
$\frac{1}{10}$. [5 pts]

\solution{
{\bf Solution}

Let $A_i$ be the event that component $i$ fails. Let $A$ be the probability
that one or more components fail. Then we have:
\begin{eqnarray*}
P(A) &=& P(\bigcup_{i=1}^{1000}A_i)\\
&\leq& \sum_{i=1}^{1000}{P(A_i)}\\
  &\leq& 1000\cdot \frac{1}{10,000}\ \mbox{   since $P(A_i)\leq 1/10,000\ \ \ \forall i=1,2,\ldots,1000$}\\
  &=& 1/10
\end{eqnarray*}

In a case where $\{A_1,A_2,\ldots,A_{1000}\}$ are disjoint events, i.e., no
two components can fail simultaneously, the equality holds for the second line.
If $P(A_i)=\frac{1}{10000}$ for all $i=1,2,\ldots,1000$, the equality holds for
the third line. Therefore the probability that one or more components in the
system fail is exactly $\frac{1}{10}$ when all the failure events are disjoint
and the probability of failure is $\frac{1}{10000}$ for each of the events.
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset10 problem3 spring98
\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 [6 points]}
What is the probability that exactly $k$ of the first 100 tosses will
turn up heads? 

\solution{
{\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 [6 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?

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

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

\solution{
{\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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset10 problem6 spring98
\problem{\bf [15 points]} Suppose that we toss two hundred mutually
independent coins, each with Pr(Heads$)=0.4$

\noindent
Use the formula given in lecture to estimate the probability that 60
or fewer coins will be heads.

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

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000 PS 11    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem \textbf{Wald's Theorem.}
% Spring 99 Final. 

Suppose successive digits from zero to nine are generated independently
until the four digit sequence \textbf{9999} appears.

What is the expected number of digits generated? 

\hint Parse the sequence into consecutive ``tries to get 9999'', where a
``try'' is either a single digit other than 9, or a 9 followed by a single
digit other than 9, etc.  For example, the sequence 92349982999769999
parses into eight tries:
\[
/92/3/4/998/2/9997/6/9999/.
\]

\solution{
\textbf{Solution:}
11110.

By Wald's Theorem, the expected number is the mean time to a successful
try, namely $10^4$, times the expected length of a try.  Notice that a try
is of length four iff it begins with three nines, so the probability of a
length four try is $1/10^3$.  That means the expected length of a try is
\[
1 \cdot \frac{9}{10} + 2 \cdot \frac{1}{10}\frac{9}{10} + 3 \cdot
(\frac{1}{10})^2\frac{9}{10} + 4 \cdot (\frac{1}{10})^3
 =  (900 + 180 + 27 + 4)/1000 = 1111/1000
\]
Thus on average, we will have to read 11110 digits in order to see
``9999''.}      

%%%%%%%%%%%%%%  Fall 2000  ps11 %%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem

Consider the process of tossing a sequence of $n$ independent fair
coins $X_1,X_2,\ldots,X_n$.  Let $V$ be the first time two consecutive
heads occur in the sequence, i.e. $(X_{V-1},X_V)=(H,H)$ and
$(X_{i-1},X_i)\neq (H,H)$ for all $2\leq i<V$.  If the sequence of $n$
coin tosses does not contain two consecutive heads, then we assign
$V=n+1$.

Prove that $V$ has distribution
\[\Pr(V=k) = \frac{\Fib(k-2)}{ 2^k} \ \ \ \ (2\leq k\leq n) \]
where $\Fib(k)$ is the $k$-th Fibonacci number (assume 
$\Fib(0)=\Fib(1)=1$.)

\solution{
% This problem is taken from spring 96, problem 10
%
\textbf{Solution:}\\
Let's count the sequences of coin tosses of length $k$ such that the
only pair {\em HH} that occurs in the sequence is at the end. Let
$H(k)$ be the number of such sequences that start with $H$, and let
$T(k)$ be the number of such sequences that start with $T$.  Observe
that $H(2) = 1$ and $T(2) = 0$. Similarly, $H(3) = 0$ and $T(3) =
1$. Given a valid sequence {\em HS} of length $k$ that starts with
$H$, the sequence {\em THS} is also valid and starts with $T$.  Given
a valid sequence {\em TS} of length $k$ that starts with $T$, the
sequences {\em HTS} and {\em TTS} are also valid and start with $H$
and $T$ respectively. From this we deduce the recurrence relations
\begin{eqnarray*}
H(k+1) &=& T(k)\\
T(k+1) &=& H(k) + T(k){.}
\end{eqnarray*}
The total number of valid sequences of length $k$ is $T(k)+H(k)$,
hence it satisfies the following recurrence
\begin{eqnarray*}
T(k+1)+ H(k+1) &=& (T(k) + H(k)) + T(k)\\
&=& (T(k) + H(k)) + (T(k-1) + H(k-1)){.}
\end{eqnarray*}
This is the same recurrence relation that defines the Fibonacci
numbers, and with the given initial conditions we can conclude that
the total number of valid sequences of length $k$ is $\Fib(k-2)$.

Now the total number of sequences of length $n$ such that the first
pair of heads occurs after $k$-th toss is $\Fib(k-2)2^{n-k}$, since we
don't care what the coin tosses are in the last $n-k$ places.

The sample space in this problem is the set of all sequences of coin
tosses of length $n$, so its size is $2^n$. Therefore the probability
\[
P(V=k) = \frac{\Fib(k-2)2^{n-k}}{ 2^n} = \frac{\Fib(k-2)}{ 2^k}{,}
\]
as desired.
}

%%%%%%%%%%%%%%  Fall 2000   PS 11  %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem  \textbf{The World Series}

The Yankees and Mets have both made it to the World Series again in 2001.
Assume that the Yankees win each game with probability 2/3 independently of
the outcomes of other games.  Let $R$ be the
random variable denoting the number of the 4th game won by the Yankees, e.g.,
if the Yankees win the 1st, 2nd, 4th, and 6th games, then $R=6$; let $R \eqdef 0$ if
the Yankees do not win four games.

Let's generalize the rules slightly and assume the
teams keep playing, possibly forever, until the Yankees have indeed
won 4 games.  This makes $R$ a random variable taking on all natural
number values.

\bparts

\ppart For $n>0$, give a simple closed form expression for $\prob{R = n}$.

\solution{
\textbf{Solution:}\\
For $0<n<3$, we have $\prob{R=n} = 0$. For $4\leq n$, we have
\[
\prob{R=n} = \binom{n-1}{3} \cdot (2/3)^4  \cdot \frac{1}{3^{n-4}}=
\frac{8(n-1)(n-2)(n-3)}{3^{n+1}}.
\]
}
 
\ppart What is the probability that Yankees never win 4 games under
the generalized rules?

\solution{
\textbf{Solution:}\\
0
}


\ppart What is the probability that the Yankees really win the 7 game
Series?

\solution{
\textbf{Solution:}
\[
\prob{4 \leq R\leq 7}= \prob{R=4}+\prob{R=5}+\prob{R=6}+\prob{R=7} = 0.8267
%\frac{?}{?}.
\]
}

\eparts   
%%%%%%%%%%%%%%
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems




%BEGIN Christos Fall 01

%-----------------------------------	
% source: spring00 ps8, problem repository
% topics: probability, binomial distribution
% outcome : 8

\problem 
A biased coin has probability $p$ of heads and probability $1-p$ of tails.
Suppose we flip this coin $n$ times.

\begin{problemparts}

\problempart
What is the probability of getting exactly $k$ heads?

\solnospace{
There are $\binom{n}{k}$ sequences of $n$ coin tosses that contain
exactly $k$ heads. Each one of them occurs with probability
$p^k(1-p)^{n-k}$, since the coin tosses are mutually independent.
Thus, the probability of getting exactly $k$ heads is 
\[
\binom{n}{k} p^k (1-p)^{n-k}.
\]
}

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

\solnospace{
\hyperdef{binomial}{max-term}{Consider the ratio of the
probability of $k$ heads over the probability of $k-1$ heads.}
\begin{align*}
\frac{ \tbinom{n}{k} p^k (1-p)^{n-k}}{\tbinom{n}{k-1} p^{k-1}(1-p)^{n-k+1}}
&= \frac{\frac{n!}{k!(n-k)!} p}{\frac{n!}{(k-1)!(n-k+1)!} (1-p) } \\
&= \frac{ (n-k+1) p}{k (1-p)}
\end{align*}
This quantity is greater than 1 if and only if $(n-k+1)p>k(1-p)$.
Simplifying, we have $np+p>k$.  So, for $k<np+p$ the probability increases
as $k$ increases, and for $k>np+p$, the probability decreases as $k$
increases.  The value of $k$ the maximizes the probability is thus
$\lfloor np+p \rfloor$.}

\problempart
Show that if $p=1/n$ then the probability of getting no heads is 
$\sim 1/e$ (for large $n$).
What is the ratio of the probability of no heads to the probability
of exactly one head?

\solnospace{
The probability of no heads is $(1-p)^n= (1-\frac{1}{n})^n$.  For
large $n$, this expression approaches $1/e$.  

The probability of exactly one head is ${n \choose 1}p(1-p)^{n-1} =
(1-\frac{1}{n})^{n-1}$.  Forming the ratio, we find the probability of
no heads over the probability of exactly one head is $1-\tfrac{1}{n}$,
which is the probability of a tail. 
}

\end{problemparts}




%---------------------------
% source : problem repository, severely modified
% topic  : probability, independence of events
% outcome : 8


\problem 
A complex system contains 1,000 different components, numbered
$1,2,\dots,\linebreak[2]1000$. Each component is known to fail with probability
exactly $\frac{1}{10,000}$ (the failures may not be independent) and
the system fails if any of these component fails. 

\bparts
\ppart 
We can represent the sample space $S$ as
$$
S \eqdef \power( \set{1,2,\dots, n} ),
$$
where an outcome is interpreted to be the set of numbers of the
components which fail during a run of the system. What set of outcomes
is the event $E_i$ that the $i$th component fails? What set of
outcomes is the event $F$ that the system fails? 

\solnospace{
Clearly, $E_i$ is the set of all outcomes that contain $i$, 
$$
E_i = \set{ w\in S \mid i\in w }.
$$
Then, $F$ is the union of all these events, 
$$
F = \bigcup_{i=1}^{1000} E_i.
$$
Clearly, an outcome $w$ belongs to $F$ iff it contains some $i$; that
is, iff $w\neq\emptyset$. In other words, $F$ contains exactly all
non-empty outcomes, 
$$
F = S - \set{ \emptyset }.
$$
}

\bigskip
Note that the fact that each of the $E_i$'s occurs with the same
probability $\tfrac{1}{10,000}$ doesn't uniquely determine what the
probability of every possible outcome is. As a result, the
probability of the failure event $F$ is not uniquely determined,
either. Different assignments of probabilities to all outcomes may
lead to different values for the probability of~$F$. In the following
parts, we will try to find some of these assignments. 

\ppart 
Find an assignment of probabilities to all outcomes so that the  
probability of $F$ is as large as possible. Prove that your assignment  
maximizes the probability of $F$.


\solnospace{
First note that, since
\begin{equation} \label{eq:disjoint}
\prob{F} = 
\prob{\bigcup_{i=1}^{1000} E_i} \leq 
\sum_{i=1}^{1000} \prob{E_i} = 
\tfrac{1}{10},
\end{equation}
it suffices to find an assignment such that
$\prob{F}=\tfrac{1}{10}$. In other words, it suffices to force the
equality in~\eqref{eq:disjoint}. 

Now, if the $E_i$'s were pairwise disjoint, we would be done: the
equality would hold, by the Sum Rule, no matter what the probability
assignment is. However, this is not the case here: for any
$i\neq j$, the outcome $\set{i,j}$ that both the $i$th and the $j$th
components fail is in both $E_i$, $E_j$, hence $E_i\cap
E_j\neq\emptyset$.  

We can have the same effect by forcing the
intersection of any two distinct $E_i$'s to be of zero
probability. Then the Sum Rule holds again, as one can trivially show,
and the equality in~\eqref{eq:disjoint} holds.  So, let's start by
assigning probability~0 to every outcome that involves the failure of 
more than one component, 
\begin{equation} \label{eq:size>1}
\text{for all $w\in S$ such that $|w|\geq 2$}:
\quad
\prob{w} = 0.
\end{equation}
That fixed, we know that the probability of each one of the $E_i$'s
has to equal the probability of the singleton event $\set{i}$ that
exactly the $i$th~component fails (all other outcomes in $E_i$ contain
more that one components, and hence have already been given zero
probability). Since we finally have to have
$\prob{E_i}=\tfrac{1}{10,000}$, we know what the probability of these
singleton events has to be:
\begin{equation} \label{eq:size=1}
\text{for all $w\in S$ such that $|w|=1$}:
\quad
\prob{w} = \tfrac{1}{10,000}.
\end{equation}
Now, the only outcome we haven't taken care of yet is the empty
outcome (that no component fails), and there is little choice how
to do that: 
\begin{equation} \label{eq:size=0}
\prob{\emptyset} = \tfrac{9}{10},
\end{equation}
since we have already assigned
$1000\times\tfrac{1}{10,000}=\tfrac{1}{10}$ of the unit of the entire
probability mass to the rest of the
outcomes. Equations~\eqref{eq:size>1},
\eqref{eq:size=1}~and~\eqref{eq:size=0} fully define the probability
function we have been after. 

So, the probability of failure is maximized if the individual
component failures occur in a disjoint fashion; that is, if two or 
more components cannot fail simultaneously. 
}


\ppart
Same as part~(b), but with ``small'' for ``large''.

\solnospace{
Since the probability of failure is maximum when the individual 
components can only fail one at a time, intuition suggests that the
minimum value for $\prob{F}$ is the one we get when the components 
can only fail simultaneously. Intuition is correct! 

First note that the components failing only simultaneously means that
all outcomes in $F$ have probability~0, except for the
outcome $w_{\text{all}}=\set{1,\dots,1000}$ that all components
fail. That is, 
\begin{equation} \label{eq:but w_all}
\text{for all $w\in S$ such that $w\neq\emptyset,w_{\text{all}}$}: 
\quad
\prob{w} = 0.
\end{equation}
That fixed, the probability of each of the $E_i$'s is exactly the
probability of $w_{\text{all}}$ (the $i$th component fails exactly
when all components fail). Hence, we should also have
\begin{equation} \label{eq:w_all}
\prob{w_{\text{all}}} = \tfrac{1}{10,000},
\end{equation}
to make sure that $\prob{E_i}=\tfrac{1}{10,000}$, for all
$i=1,\dots,1000$. Finally, the probability of the empty outcome 
has to be
\begin{equation} \label{eq:empty}
\prob{\emptyset} = \tfrac{9,999}{10,000},
\end{equation}
since we have assigned only $\tfrac{1}{10,000}$ of the unit of the
entire probability mass to the rest of the
outcomes. 

Equations~\eqref{eq:but w_all}, \eqref{eq:w_all}~and~\eqref{eq:empty}
fully define the probability function we were looking for. Under this
assignment, the failure event occurs with probability 
$$
\prob{F} = \prob{ w_{\text{all}} } = \tfrac{1}{10,000}.
$$
To see why this is minimun, note that $E_1\Rightarrow F$, therefore 
$$
\prob{E_1} \leq \prob{F}
$$
and we have to have $\prob{E_1}=\tfrac{1}{10,000}$.
}

\ppart
Find an assignment of probabilities so that the component failures are
mutually independent. Prove that this assignment yields a probability
space, i.e., the outcome probabilities are all non-negative and sum
to~1. What is now the probability of~$F$?

\solnospace{
Consider the outcome $w_{2,4}=\set{2,4}$. The event $\set{w_{2,4}}$
that exactly the components of this outcome fail can be written in
terms of the $E_i$'s as
$$
\overline{E_1}\cap
E_2\cap
\overline{E_3}\cap
E_4\cap
\overline{E_5}\cap
\overline{E_6}\cap\cdots\cap
\overline{E_{1000}},
$$
and hence its probability is
$$
\prob{
\overline{E_1}\cap
E_2\cap
\overline{E_3}\cap
E_4\cap
\overline{E_5}\cap
\overline{E_6}\cap\cdots\cap
\overline{E_{1000}}
}.
$$
Assuming that the $E_i$'s are mutually independent (which implies that
$E_1,\dots,E_{1000},\overline{E_1},\dots,\linebreak[2]\overline{E_{1000}}$
are mutually independent, too), we must have  
\begin{align*}
\prob{w_{2,4}} 
&= 
\prob{\overline{E_1}}\cdot
\prob{E_2}\cap
\prob{\overline{E_3}}\cdot
\prob{E_4}\cdot
\prob{\overline{E_5}}\cdot
\prob{\overline{E_6}}\cdots
\prob{\overline{E_{1000}}} 
\\
&= 
\bigl( \tfrac{1}{10,000} \bigr)^2 
\cdot
\bigl( 1 - \tfrac{1}{10,000} \bigr)^{998}
\\
&= 
\bigl( \tfrac{1}{10,000} \bigr)^2 
\cdot
\bigl( \tfrac{9,999}{10,000} \bigr)^{998}.
\end{align*}

Similarly, for any outcome $w\in S$, we must have
\begin{align*}
\prob{ w } 
&= 
\prob{
\Bigl( \bigcap_{i\in w} E_i \Bigr)
\cap
\Bigl( \bigcap_{i\notin w} \overline{E_i} \Bigr)
}
\\
&=
\Bigl( \prod_{i\in w} \prob{E_i} \Bigr) 
\cdot
\Bigl( \prod_{i\notin w} \prob{\overline{E_i}} \Bigr)
\\
&=
\bigl( \tfrac{1}{10,000} \bigr)^{|w|}
\cdot
\bigl( \tfrac{9,999}{10,000} \bigr)^{1000-|w|}.
\end{align*}
This fully defines the assignment we are looking for. Note that, the
probability of an outcome depends only on the outcome's size, which
agrees with our intuition that the components should be treated
symmetrically. 

To make sure our assignment of probabilities is correct, let's check
that it is indeed a valid \emph{probability function}: it is obviously
assigning a non-negative value to each outcome, so we need only check
that the sum of all these values is~1. Letting $p_k$ to denote the
probability of any outcome of size~$k$, we have 
\begin{align*}
\sum_{w\in S} \prob{w} 
&=
\sum_{k=0}^{1000} \sum_{w\in S, |w|=k} \prob{w} 
\\
&=
\sum_{k=0}^{1000} \sum_{w\in S, |w|=k} p_k  
\\
&=
\sum_{k=0}^{1000} \tbinom{1000}{k} p_k  
\\
&=
\sum_{k=0}^{1000} \tbinom{1000}{k} 
\bigl(\tfrac{1}{10,000}\bigr)^k
\bigl(\tfrac{9,999}{10,000}\bigr)^{1000-k}
\\
&=
\bigl(\tfrac{1}{10,000} + \tfrac{9,999}{10,000}\bigr)^{1000}
\\
&= 1.
\end{align*}
In the first line, we simply turn the sum over all outcomes into a
sum over all outcomes of size $k$, for all $k=0,\dots,1000$. Then, the 
probability of an outcome of size~$k$ is $p_k$ (second line) and
there are exactly $\tbinom{1000}{k}$ such outcomes (third
line). Replacing the value of $p_k$, we see a familiar expansion
(fourth and fifth line).

Finally, note that the probability of the failure event under this
assignment is 
$$
\prob{F} = 
1 - \prob{\emptyset} = 
1 - \bigl( \tfrac{9,999}{10,000} \bigr)^{1000}.
$$
}

\eparts







%---------------------------
% source : problem repository, severely modified
% topic  : probability, independence of events
% outcome : 8

\problem
Let $A,B,C$ be events of some experiment.  For each of the following 
statements, prove it if it is true or give a counterexample if it is
false:

\bparts

\ppart 
If $A$ is independent of $B$, 
then $A$ is also independent of $\overline{B}$.

\solnospace{ 
This is true. To prove it, suppose $A$ is independent of $B$; that
is, $\prob{A\cap B}=\prob{A}\prob{B}$. Then
\begin{align}
\label{eq:pr-rule-1}
\prob{A\cap \overline{B}}
&=
\prob{A}\prob{\overline{B} \mid A}
\\
\label{eq:co-rule-1}
&=
\prob{A}(1-\prob{B\mid A})
\\
\nonumber
&=
\prob{A}-\prob{A}\prob{B\mid A}
\\
\label{eq:pr-rule-2}
&=
\prob{A}-\prob{A\cap B}
\\
\label{eq:independence}
&=
\prob{A}-\prob{A}\prob{B}
\\
\nonumber
&=
\prob{A}(1-\prob{B})
\\
\label{eq:co-rule-2}
&=
\prob{A}\prob{\overline{B}}
\end{align}
Equations~\eqref{eq:pr-rule-1} and~\eqref{eq:pr-rule-2} make use of 
the Product Rule. The Complement Rule is used in~\eqref{eq:co-rule-1}
and~\eqref{eq:co-rule-2}. We use independence of $A$ and $B$
in~\eqref{eq:independence}. 
}

\ppart 
If $A$ is independent of $B$, and $A$ is independent of $C$, 
then $A$ is independent of $B\cap C$.

\solnospace{
This is false. To see why, consider the usual random experiment of
rolling a die and let $A$, $B$, $C$ be the events that the die rolls
less than 3, rolls an even number, or rolls a prime number,
respectively. I.e., 
$$
A = \{1,2\} \qquad
B = \{2,4,6\} \qquad
C = \{2,3,5\}.
$$
Then, 
$$
\prob{A}=\tfrac{1}{3}, 
\qquad
\prob{B}=\prob{C}=\tfrac{1}{2},
$$
and
$$
\prob{A\cap B}=
\prob{A\cap C}=
\prob{B\cap C}=
\prob{A\cap B\cap C}=
\prob{\{2\}}=
\tfrac{1}{6}.
$$
Easily, 
$$
\prob{A\mid B}=
\prob{A\mid C}=
\tfrac{1}{6}/\tfrac{1}{2}=
\tfrac{1}{3}=
\prob{A},
$$
which proves $A$ is independent of $B$ and also independent of
$C$. However, 
$$
\prob{A\mid B\cap C}=
\prob{A\cap B\cap C}/\prob{B\cap C}=
\tfrac{1}{6}/\tfrac{1}{6}=
1\neq
\prob{A},
$$
which implies $A$ is not independent of $B\cap C$.
}

\ppart 
If $A$ is independent of $B$, and $A$ is independent of $C$, and $A$
is independent of $B\cap C$, 
then $A$ is independent of $B\cup C$.

\solnospace{
This is true. To prove it, suppose $A$ is independent of any one of
$B$, $C$, and $B\cap C$; that is, 
\begin{align*}
\prob{A\cap B} &= \prob{A}\prob{B} \\
\prob{A\cap C} &= \prob{A}\prob{C} \\
\prob{A\cap (B\cap C)} &= \prob{A}\prob{B\cap C}.
\end{align*}
Then, 
\begin{align}
\nonumber
\prob{A\cap(B\cup C)}
&=
\prob{(A\cap B)\cup (A\cap C)} 
\\
\label{eq:ie-rule-1}
&=
\prob{A\cap B}+\prob{A\cap C}-\prob{(A\cap B)\cap(A\cap C)}
\\
\nonumber
&=
\prob{A\cap B}+\prob{A\cap C}-\prob{A\cap B\cap C}
\\
\label{eq:indep}
&=
\prob{A}\prob{B}+\prob{A}\prob{C}-\prob{A}\prob{B\cap C}
\\
\nonumber
&=
\prob{A}(\prob{B}+\prob{C}-\prob{B\cap C})
\\
\label{eq:ie-rule-2}
&=
\prob{A}\prob{B\cup C}.
\end{align}
Equations~\eqref{eq:ie-rule-1} and~\eqref{eq:ie-rule-2} use the
Inclusion-Exclusion Rule. Equation~\eqref{eq:indep} uses the
independences of $A$.
}

\ppart 
If $A$ is independent of $B$, and $A$ is independent of $C$, 
then $A$ is independent of $B\cup C$.

\solnospace{
This is false. E.g., look again at the counter-example for part~(b)
and notice that  
$$
\prob{B\cup C}=\tfrac{5}{6}, \qquad
\prob{A\cap(B\cup C)}=\tfrac{1}{6}.
$$ 
Hence,
$$
\prob{A\mid B\cup C}=
\tfrac{1}{6}/\tfrac{5}{6}=
\tfrac{1}{5}\neq
\prob{A}
$$
which again implies $A$ is not idependent of $B\cup C$.
}

\eparts

%END Christos Fall 01


\end{problems}

\end{document}



