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

\begin{document}
\psol{9}{April 28, 1998}{}


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem [15 pts]

Suppose the game {\em Let's Make A Deal} is changed slightly. Instead of having 3 doors with 1 grand prize, in the new game there are 4 doors with 2 grand prizes. The rule of the game remains the same. Therefore the game now becomes:

\begin{quote}
At one stage of the game, a contestant is shown 4 doors. The contestant knows that there are 2 grand prizes behind 2 of the doors and that there are goats behind the 2 other doors. At the beginning, the contestant picks a door. To build suspense, the assistant of the game then opens a {\em different} door, revealing a goat. The contestant can then stick with his original door or switch to another unopened door. He wins a prize only if he now picks the door with the prize.
\end{quote}

In the new game, what is the probability of winning with the ``stick'' strategy? How about the ``switch'' strategy? Can you explain why the two probabilities do not sum up to 1?   



\vspace{0.3in}
{\bf Solution}

The player wins with a ``stick'' strategy iff he chooses the ``correct door'' in the 
first place. Therefore the probability of winning with the ``stick'' strategy
is $\frac{1}{2}$.

To calculate the probability of winning with a ``switch'' strategy, let 
$E_1$ be the event that ``the player chooses the correct door at his first chance''. Let $E_2$ be the event that ``the player switches to the correct door at his second chance''. 
\begin{eqnarray*}
P(\mbox{winning with ``switch'' strategy})&=&P(E_2|E_1)P(E_1)+P(E_2|\overline{E_1})P(\overline{E_1})\\
&=&\frac{1}{2}\cdot\frac{1}{2}+1\cdot\frac{1}{2}\\
&=&\frac{3}{4}
\end{eqnarray*}

The two probabilities do not need to sum up to 1. They are calculated in a different probability space. In particular, the player winning by the ``switch'' strategy does not imply he will lose by the ``stick'' strategy, and vice versa. Therefore, the same winning event can be counted in both cases at the same time.

%The 2 probabilities do not sum up to 1 because the 2 events, namely ``stick and win'' and ``switch and win'' are not disjoint. For example, they both contain the event where the first and second doors contain the grand prize, the player chooses the first door, Carol opens the third door, and the player 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2

\problem [20 pts]

A sequence of numbers $<{\tt 0},{\tt 2},{\tt 2},{\tt 2},{\tt 2},{\tt 5},{\tt 5},{\tt 7},{\tt 7}>$ is randomly permuted to form a 
9-digit integer, in such a way that the digit {\tt 0} does not come first. (In other words, if 
the digit {\tt 0} comes first in the permutation, we try a new permutation until this 
does not occur.) Let $p$ be the 9-digit number. Find the probabilities of the
following:

\bparts
\ppart $p$ is a multiple of 2.
\vspace{0.3in}

%{\bf Solution}
We have two ways to solve the problem. Method 1 counts the number of outcomes in the event spaces and sample space. Since each outcome is equally likely to occur, the probability is simple the ratio of the two numbers. Method 2 finds the probability of the desired outcome using conditional probability. 

{\bf Method 1: Counting}

To find the total number of permutations, first note that the digit {\tt0} can appear as the $2^{nd}, 3^{rd},\ldots,9^{th}$ position. So there are 8 ways to put the number {\tt0}. The remaining 8 numbers (some of them are repeated) can permute among the remaining 8 positions. Therefore the total number of permutations is $8\cdot\frac{8!}{4!2!2!}=3360$. 

$p$ is a multiple of 2 iff $p$ ends {\tt0} or {\tt2}. The number of outcomes which end with {\tt0} is $\frac{8!}{4!2!2!}=420$. This is because once {\tt0} is fixed at position 9, the other 8 numbers can permute in the remaining 8 positions in any way.

The number of outcomes which end with {\tt2} is $7\cdot\frac{7!}{3!2!2!}=1470$. This is because with the number {\tt2} fixed at the $9^{th}$ digit, the number {\tt0} has to choose among the $2^{nd},3^{rd},\ldots,8^{th}$ positions. Therefore there are 7 choices to put {\tt0}. The remaining 7 numbers can permute in the remaining 7 positions in $\frac{7!}{3!2!2!}$ ways.

Therefore, the probability that $p$ is even is $\frac{420+1470}{3360}=\frac{9}{16}$.


{\bf Method 2: Conditional Probability}

First note that the probability distribution for {\tt 0} to appear in any places is different from other numbers because it cannot appear in the first place. So we have to deal with it separately. In fact, the probability that {\tt 0} appears in the $n^{th}$ digit is $\frac{1}{8}$ for $n=2,3,\ldots,9$, since it can be placed in any of the 8 positions.  

We need to find the probability that $p$ ends with an even integer.
%We have 2 approaches to find the probability.

%{\bf Method 1:}
%\begin{eqnarray*}
%P(p \mbox{ is even})&=&P(p\mbox{ ends with 0})+P(p\mbox{ ends with 2})\\
%	&=&P(p \mbox{ ends with } 0)\\
%	&&+P(p \mbox{ ends with 2}|p \mbox{ does not end with 0})P(p \mbox{ does not end with 0})\\
%	&&+P(p \mbox{ ends with 2}|p \mbox{ ends with 0})P(p \mbox{ ends with 0})\\
%			&=&\frac{1}{8}+\frac{4}{8}\cdot\frac{7}{8}+0\cdot\frac{1}{8}\\
%			&=&\frac{9}{16}\\
%\end{eqnarray*}

%{\bf Method 2:}
We first find the probability for each number to appear at the last position. Since the probability that $p$ ends with {\tt 0} is $\frac{1}{8}$, the probability that $p$ ends with other numbers is $\frac{7}{8}$. If we treat all the repeated numbers as distinct numbers, the probability for each of them to appear as the last digit is $\frac{7}{8}\cdot\frac{1}{8}=\frac{7}{64}$. Since {\tt 2} has appeared four times among the eight numbers, the probability that {\tt 2} appears as the last digit is $4\cdot\frac{7}{64}=\frac{7}{16}$. (Same reasoning can be applied to other positions. We will use this reasoning for the following parts.)

The probability that $p$ is a multiple of 2 is equal to the probability that $p$ ends with a {\tt 0} or {\tt 2}. Since the two events are disjoint, we can apply the sum rule:
\begin{eqnarray*}
P(p\mbox{ is a multiple of 2})&=&\underbrace{\frac{1}{8}}_{\mbox{{\em p} ends with {\tt 0}}}+\underbrace{\frac{7}{16}}_{\mbox{{\em p} ends with {\tt 2}}}\\
&=&\frac{9}{16}\\
\end{eqnarray*}



%\ppart  $p$ is a multiple of 3.
%\vspace{0.3in}
%{\bf Solution}

%Since the sum of the digits is not a multiple of 3, $p$ is not divisible by 3. Therefore the probability that $p$ is a multiple of 3 is 0.

\ppart  $p$ is a multiple of 25.
\vspace{0.3in}
%{\bf Solution}

{\bf Method 1: Counting}

If $p$ is a multiple of 25, it has to end with either {\tt 25}, {\tt 50} or {\tt 75}. We count the number of outcomes that end with either {\tt25, 50} or {\tt75}.

The number of outcomes that end with {\tt25} is $6\cdot\frac{6!}{3!1!2!}=360$. The number of outcomes that end with {\tt50} is $\frac{7!}{4!1!2!}=105$. The number of outcomes that end with {\tt75} is $6\cdot\frac{6!}{4!1!1!}=180$. Therefore the probability that $p$ is a multiple of 25 is $\frac{360+105+180}{3360}=\frac{43}{224}$.


{\bf Method 2: Conditional Probability}

If $p$ is a multiple of 25, it has to end with either {\tt 25}, {\tt 50} or {\tt 75}. 
We calculate the probability for each event separately, using the same reasoning as in part a). 


Let $A_i$ be the event that ``The $8^{th}$ digit of $p$ is {\tt $i$}''.

Let $B_i$ be the event that ``The last digit of $p$ is {\tt $i$}''.

\begin{eqnarray*}
P(p\mbox{ ends with {\tt 25}})&=&P(A_2 \cap B_5)\\
&=&P(A_2|B_5)P(B_5)\\
&=&\underbrace{(1-\frac{1}{7})\cdot4\cdot\frac{1}{7}}_{P(A_2|B_5)}\cdot2\cdot\frac{7}{64}\\
&=&\frac{3}{28}\\
\\
P(p\mbox{ ends with {\tt 50}})&=&P(A_5\cap B_0)\\
&=&P(A_5|B_0)P(B_0)\\
&=&\underbrace{2\cdot\frac{1}{8}}_{P(A_5|B_0)}\cdot\frac{1}{8}\\
&=&\frac{1}{32}\\
\\
P(p\mbox{ ends with {\tt 75}})&=&P(A_7 \cap B_5)\\
&=&P(A_7|B_5)P(B_5)\\
&=&\underbrace{(1-\frac{1}{7})\cdot2\cdot\frac{1}{7}}_{P(A_7|B_5)}\cdot2\cdot\frac{7}{64}\\
&=&\frac{3}{56}\\
\end{eqnarray*}

Therefore, $P(p$ is a multiple of 25$)=\frac{3}{28}+\frac{1}{32}+\frac{3}{56}=\frac{43}{224}$  

\ppart  the first and the last digits of $p$ are {\tt 2}.
\vspace{0.3in}

{\bf Method 1: Counting}

The number of outcomes that both start and end with a {\tt2} is $\frac{7!}{1!2!2!2!}=630$. Therefore the probability that the first and the last digits of $p$ are both {\tt2} is $\frac{630}{3360}=\frac{3}{16}$.


{\bf Method 2: Conditional Proability}

In this part, let $A_i$ be the event that ``The first digit of $p$ is {\tt $i$}''.
Let $B_i$ be the event that ``The last digit of $p$ is {\tt $i$}''. Note that {\tt 0} cannot be the first digit of $p$. Therefore the remaining eight integers have equal chance of $\frac{1}{8}$ to be the first digit.

\begin{eqnarray*}
P(p\mbox{ starts and ends with {\tt 2}})&=&P(A_2 \cap B_2)\\
&=&P(A_2|B_2)P(B_2)\\
&=&\underbrace{3\cdot\frac{1}{7}}_{P(A_2|B_2)}\cdot4\cdot\frac{7}{64}\\
&=&\frac{3}{16}
\end{eqnarray*}


\ppart $p$ is symmetric. (i.e., the number does not change if the sequence of digits is reversed)
\vspace{0.3in}
%{\bf Solution}
In this part counting is a much simpler method to use. 

For $p$ to be symmetric, the $5^{th}$ digit of $p$ has to be 0. The first four digits must consist of {\tt 2},{\tt 2},{\tt 5},{\tt 7} permuted in any way, with the last four digits being the reverse of the permutation. 

Therefore, the total number of symmetric numbers is $\frac{4!}{2!1!1!}=12$. On the other hand, the number of all possible permutations of the 9 integers is $\frac{8\cdot8!}{4!2!2!1!}$. Since each number is equally likely to appear, the probability that $p$ is symmetric is $\frac{12}{\frac{8\cdot8!}{4!2!2!1!}}=\frac{1}{280}$. 

\eparts




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3

\problem [10 pts]

In a lottery, 6 distinct integers are drawn randomly from 1 to 45 without replacement. What is the 
probability that the maximum of the 6 numbers is $k$, where $1\leq k\leq45$?

\vspace{0.3in}
{\bf Solution}

{\bf Method 1: Counting}

There are ${45\choose6}$ ways to pick 6 numbers out of 45. For a set of 6 numbers whose maximum element is $k$, it has to have $k$ and all of 5 other numbers are smaller than $k$. Therefore there are ${k-1\choose5}$ such sets. Since every set of 6 numbers are equally likely to occur, the desired probability is simply $\frac{{k-1\choose5}}{{45\choose6}}$.


{\bf Method 2: Conditional Probability}

Let $M$ be the maximum of the 6 drawn numbers. We want to find $P(M=k)$.
Let $A_k$ be the event that ``$k$ is selected''. Let $B_k$ be the event that ``all selected numbers $\leq k$''. 

For $1\leq k\leq5, P(M=k)=0$ because the maximum number has to be $\geq 6$.

For $6\leq k\leq45$, 
\begin{eqnarray*}
P(M=k)&=&P(A_k\cap B_k)\\
      &=&P(B_k|A_k)P(A_k)\\
      &=&\frac{{k-1\choose5}}{{44\choose5}}\cdot\frac{6}{45}\\
      &=&\frac{\frac{(k-1)!}{5!(k-6)!}}{\frac{44!}{5!39!}}\cdot\frac{6}{45}\\
      &=&\frac{(k-1)!\cdot39!\cdot6}{(k-6)!45!}\\
\end{eqnarray*}

$P(B_k|A_k)$ is the probability that the other 5 numbers are smaller than $k$ given that $k$ is selected. There are ${k-1\choose5}$ ways to choose 5 numbers from $\{1,2,\ldots,k-1\}$. Since each combination of 6 numbers is equally likely to appear, the probability is $\frac{{k-1 \choose 5}}{{44\choose 5}}$.

To find $P(A_k)$, notice that the the probability for $k$ to be selected as the first number is $\frac{1}{45}$. Since $k$ can also appear as the $2^{nd}, 3^{rd},\ldots,6^{th}$ number, the probability that $k$ is selected as one of the six numbers is $\frac{6}{45}$.

To check the answer, try $k=45$. The probability that 45 is the maximum of the 6 numbers is equal to the probability that $45$ is drawn, which is equal to $\frac{6}{45}$ as explained. From the formula, we have $P(M=45)=\frac{44!\times39!\times6}{39!45!}=\frac{6}{45}$ as expected.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem 4 (Taken 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 $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]
\eparts

\vspace{0.3in}
{\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)}\\
%  &=& 1000\cdot P(A_1)\\
  &\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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem 
There are 4 coins in a box, namely $c_1, c_2, c_3, c_4$. The probability $p_i$ that the coin $c_i$ gives a Head is $\frac{1}{i}$ for $1\leq i\leq4$. A coin is selected from the box randomly, and is being tossed until a Head is seen. 

\bparts
\ppart
Write down the sample space of the experiment. [2 pts]
\vspace{0.3in}
%{\bf Solution}

The sample space is $\{(c_1,H)\}\cup\{c_2,c_3,c_4\}\times\{H,TH,TTH,TTTH,\dots\}$
 
\ppart
What is the probability that a Head is first seen in the $2^{nd}$ toss? [9 pts]
\vspace{0.3in}
%{\bf Solution}

For this part and the following part, let $H_i$ be the event that ``a Head is first seen in the $i^{th}$ toss''. Let $C_i$ be the event that ``$c_i$ is drawn from the box''.


\begin{eqnarray*}
P(H_2)	&=&P(H_2|C_1)P(C_1)+P(H_2|C_2)P(C_2)+P(H_2|C_3)P(C_3)+P(H_2|C_4)P(C_4)\\
	&=&0\cdot\frac{1}{4}+\underbrace{\frac{1}{2}\cdot\frac{1}{2}}_{P(H_2|C_2)}\cdot\frac{1}{4}+\underbrace{\frac{2}{3}\cdot\frac{1}{3}}_{P(H_2|C_3)}\cdot\frac{1}{4}+\underbrace{\frac{3}{4}\cdot\frac{1}{4}}_{P(H_2|C_4)}\cdot\frac{1}{4}\\
	&=&\frac{95}{576}\\
\end{eqnarray*}

\ppart
Given that a Head is first seen in the $2^{nd}$ toss, what is the 
probability that $c_i$ is selected from the box? [9 pts]
\vspace{0.3in}
%{\bf Solution}

\begin{eqnarray*}
P(C_i|H_2)&=&\frac{P(C_i\cap H_2)}{P(H_2)}\\
	 &=&\frac{P(H_2|C_i)P(C_i)}{P(H_2)}\\
	 &=&\frac{\frac{i-1}{i}\cdot\frac{1}{i}\cdot\frac{1}{4}}{\frac{95}{576}}\\
	 &=&\frac{144(i-1)}{95i^2}
\end{eqnarray*}

{\bf Checking:} $P(C_1|H_2)+P(C_2|H_2)+P(C_3|H_2)+P(C_4|H_2)=0+\frac{144}{95\cdot4}+\frac{144\cdot2}{95\cdot9}+\frac{144\cdot3}{95\cdot16}=1$. This makes sense.

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6 (Left for PS10)
\problem [10 pts]

$A$, $B$, $C$ are events of an experiment. If $C$ is independent of $A$ and $C$ is independent of $B$, is $C$ independent of $A\cap B$? Prove your answer or give a counterexample. 

\vspace{0.3in}
{\bf Solution}

It is {\em not} true. A counterexample would be an experiment as follows. Suppose we  are to draw a number from the set $\{1,2,\ldots,8\}$ randomly. Let $A$ be the event that the number is even. Let $B$ be the event that the number is prime.
Let $C$ be the event that the number is at least 5. Then we have $A=\{2,4,6,8\}, B=\{2,3,5,7\}, C=\{5,6,7,8\}$.

Then $P(A)=\frac{1}{2}$, $P(B)=\frac{1}{2}$, $P(C)=\frac{1}{2}$.

$C$ is independent of $A$ because $P(C|A)=\frac{P(C\cap A)}{P(A)}=\frac{\frac{1}{4}}{\frac{1}{2}}=\frac{1}{2}=P(C).$

$C$ is independent of $B$ because $P(C|B)=\frac{P(C\cap B)}{P(B)}=\frac{\frac{1}{4}}{\frac{1}{2}}=\frac{1}{2}=P(C).$

Note that the only number in $A\cap B$ is 2 (an even prime), which is not in $C$. Therefore, $C$ is not independent of $A\cap B$ because $P(C|A\cap B)=0\ne P(C)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem [10 pts]

A house is installed with a fire alarm to prevent fire accidents. If there 
is a fire, the probability for the fire alarm being turned on is 96\%. 
Even without a fire, there may be a false alarm with a probability of 2\%. 
Suppose the probability for a fire accident to happen in the house is 1\%. 
If the fire alarm is now on, what is the conditional probability that there is really a fire accident?

\vspace{0.3in}
{\bf Solution}

Let $F$ be the event that ``a fire accident happens''. Then let $A$ be the event that ``the alarm is on''.

From the question, we have:
\begin{itemize}
\item $P(A|F)=0.96$
\item $P(A|\overline{F})=0.02$
\item $P(F)=0.01$
\end{itemize}

We want to find:
\begin{eqnarray*}
P(F|A)&=&\frac{P(F\cap A)}{P(A)}\\
      &=&\frac{P(A|F)P(F)}{P(A|F)P(F)+P(A|\overline{F})P(\overline{F})}\\
      &=&\frac{0.96\times 0.01}{0.96\times0.01+0.02\times0.99}\\
      &=&\frac{16}{49}
\end{eqnarray*}

\end{problems}

\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Alternative Problem 4
%\problem
%
%In another lucky draw, a box contains 3 gold balls and 97 black balls.
%100 participants draw a ball randomly from the box in order without replacement. Only the 3 players who have drawn the gold ball get a prize. What is the probability that:  
%\bparts 
%\ppart the first player gets a prize? [2 pts]
%\ppart the last player gets a prize? [3 pts]
%\ppart the $30^{th}$ player gets a prize? [5 pts]
%\eparts
%
%\vspace{0.3in}
%%{\bf Solution}
%\bparts
%\ppart
%The probability that the first player gets a prize is $\frac{3}{100}$.
%\ppart
%\begin{eqnarray*}
%P(\mbox{The last player gets a prize})	&=& P(\mbox{2 gold balls are drawn by the previous 99 players})\\ 
%&=& \frac{{99\choose2}}{{100\choose3}}\\
%&=& \frac{\frac{99!}{97!2!}}{\frac{100!}{97!3!}}\\
%&=& \frac{3}{100}
%\end{eqnarray*}
%\ppart
%There are in total ${100\choose3}$ 3-player combinations  who win the prizes. For the $30^th$ player to get the prize, the remaining 2 prizes can be allocated to the rest of 99 people in ${99\choose2}$ ways. Therefore the probability of the $30^{th}$ person getting a prize is $\frac{{99\choose2}}{{100\choose3}}=\frac{3}{100}$
%
%
%\eparts
%
%In fact, the same argument in part c) can be applied to all other participants. Therefore, their chances of winning a prize are all equal to $\frac{3}{100}$.
