\documentclass[12pt]{amsart}    % !! document class is: amsart
\usepackage{course}		% !! call course.sty & course.dat

%\backwardscompatibility	% !! use for backwards compatibility
%\showsolutions	 		% !! use to force solutions & skip query
%\hidesolutions			% !! use to force no solutions & skip query


\begin{document} 
\tutorial{11}			% !! start the paper


\begin{problem}[Birthdays Again]
Suppose there are 100 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 99 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 99 people we asked all had
different birthdays, it follows that with probability greater
than~99\% Jane has the same birthday as some other person in the
room. 
\end{quotation}

\solution{			% !! use \solution for a 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 99 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 99 people in the room
other than Jane. By assumption, $|S| = 99$. 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{A\mid B} = 
\prob{b\in S} = 
\frac{|S|}{365} = 
\frac{99}{365} \approx
27.1\%,
\end{align*}
where $B$ is the event that the 99 people we asked all have
different birthdays.
}
\end{problemparts}
\end{problem} 










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

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

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

\solution{
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 $\binom{n}{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~1 over the probability of a tail.
}
\end{problemparts}
\end{problem} 












\begin{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. 
\begin{problemparts}

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

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

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. 

\begin{problemparts}
\addtocounter{problempart}{1}
\problempart 
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$.

\solution{
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. Unfortunately, this is not the case here: for any
$i\neq j$, the events $E_i$, $E_j$ aren't disjoint, since, e.g., the
outcome $\set{i,j}$ that both the $i$th and the $j$th components fail 
is in $E_i\cap E_j$. 

Fortunately, though, 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. 
}


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

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

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

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

\end{problemparts}
\end{problem} 














\begin{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:

\begin{problemparts}

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

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

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

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

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

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

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

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

\end{problemparts}
\end{problem} 




\end{document}

