\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\begin{document} 
\inclassproblems{10, Wed}

\begin{problem} 
Suppose there is a system with $n$~components, and we know from past
experience that any particular component will fail in a given year with
probability~$p$.  That is, letting $F_i$ be the event that the $i$th
component fails within one year, we have
\[
\pr{F_i} = p
\]
for $1 \leq i \leq n$.  The \emph{system} will fail if \emph{any one} of
its components fails.  What can we say about the probability that the
system will fail within one year?

Let $F$ be the event that the system fails within one year.  Without any
additional assumptions, we can't get an exact answer for $\pr{F}$.
However, we can give useful upper and lower bounds, namely,
\begin{equation}\label{pFnp}
p \le \pr{F} \le np.
\end{equation}
So for example, if $n = 100$ and $p = 10^{-5}$, we conclude that there is
at most one chance in 1000 of system failure within a year and at least
one chance in 100,000.

Let's model this situation with the sample space $\sspace \eqdef
\power(\set{1, \dots,n})$ of subsets of positive integers $\le n$, where
$s \in \sspace$ corresponds to the numbers of the components which fail
within one year.  For example, $\set{2, 5}$ is the outcome that the second
and fifth components failed within a year and none of the other components
failed.  So the outcome that the system did not fail corresponds to the
emptyset, $\emptyset$.

\bparts

\ppart Show that the probability that the system fails could be as small
as $p$ by describing appropriate probabilities for the sample points.

\solution{There could be a probability $p$ of system failure if the all
individual failures occur together.  That is, let $\pr{\set{1, \dots,n}}
\eqdef p$, $\pr{\emptyset} \eqdef 1-p$, and let the probability of all
other outcomes be zero.  So $F_i = \set{s \in \sspace \suchthat i \in s}$
and $\pr{F_i} = 0 + 0 + \dots + 0 + \pr{\set{1, \dots,n}} = \pr{\set{1,
\dots ,n}} = p$.  Also, the only outcome with positive probability in $F$
is $\set{1, \dots ,n}$, so $\pr{F} = p$, as required.}

\ppart Show that the probability that the system fails could actually
could be as large as $np$ by describing appropriate probabilities for the
sample points.

\solution{Suppose at most one component ever fails at a time.  That is,
$\pr{\set{i}}=p$ for $1 \le i \le n$, $\pr{\emptyset}=1-np$, and
probability of all other points is zero.  The sum of the probabilities of
all the points is one, so this is a well-defined probability space.  Also,
the only sample point in $F_i$ with positive probability is $\set{i}$, so
$\pr{F_i} = \pr{\set{i}} = p$ as required.  Finally, $\pr{F} = np$ because
$F = \set{A \subseteq \set{1,\dots,n} \suchthat A \neq \emptyset}$, so $F$
in particular contains all the $n$ outcomes of the form $\set{i}$.}

\ppart Prove the inequality~(\ref{pFnp}).

\solution{
$F = \lgunion_{i=1}^n F_i$ so
\begin{align}
p & = \pr{F_1} & \text{(given)}\\
& \le \pr{\lgunion F_i} & \text{(monotonicity)}\\
& \le \sum_{i=1}^n \pr{F_i} & \text{(Boole's inequality)}\\
& = np.
\end{align}
}

\eparts
\end{problem}

\textbf{(WE DIDN'T GET TO THE NEXT TWO PROBLEMS IN CLASS ON WEDNESDAY.)}

\begin{problem}
Smith and Wesson are shooting at a target.  Suppose Smith's chance of
hitting the target is double that of his friend Wesson, and the
probability that at least one of them hits the target is $1/2$.  Whether
or not one of them hits the target has no effect on the probability that
the other one will hit.  What is the probability that Wesson hits the
target?

\solution{A simple sample space has length two sequences of \emph{H}its
and \emph{M}iss indicating whether Smith hit the target and then Wesson did:
\[
\sspace \eqdef \set{HH,HM,MH,MM}.
\]

Let $S$ be the event that Smith hits, that is
\[
S \eqdef \set{HH,HM}.
\]
Similarly, let $W$ be the even that Wesson hits:
\[
W \eqdef \set{HH,MH}.
\]
First we have two facts:
\begin{eqnarray}
\pr{S}      & = &   2 \pr{W} \label{f1}\\
\pr{S \cup W}   & = &   \frac{1}{2}\label{f2},
\end{eqnarray}

To define the probability space, we would draw a binary tree assigning
probability $\pr{S} \cdot \pr{W}$ to the event $\set{HH} = S \intersect
W$ and also $\pr{\bar{S}} \cdot \pr{W}$ to $\set{MH}$.  That is,
the probability that Smith hits the target and \emph{then}
Wesson does is the probability that Smith hits the target \emph{times} the
probability that Wesson does.
\begin{equation}\label{indep}
\pr{S \intersect W} = \pr{S}\pr{W}
\end{equation}

We should verify that in this probability space, event $S$ has the
required probability.  Namely,
\begin{align*}
\pr{S} \eqdef & \pr{\set{HH,HM}} & \text{(def of $S$)}\\
         & = \pr{S}\pr{W} + \pr{S}\pr{\bar{W}}, & \text{(probabilities
         from the tree)}\\
        & =  \pr{S}\pr{W} + \pr{S}(1-\pr{W}) & \text{(Complement rule)}\\
        & = \pr{S}(\pr{W} + (1-\pr{W}))  &\text{(distributivity)}\\
        & = \pr{S},
\end{align*}
and similarly for $\pr{W}$.

Expanding equation~(\ref{f2}) using inclusion-exclusion gives:
\begin{align}
\frac{1}{2} & =  \pr{S \cup W} & \text{by~(\ref{f2})}\\
& = \pr{S} + \pr{W} - \pr{S \cap W} & \text{(inclusion-exclusion)}\\
& = \pr{S} + \pr{W} - \pr{S} \cdot \pr{W}   & \text{(by~(\ref{indep}))}\\
& = 2 \pr{W} + \pr{W} - 2 \pr{W} \cdot \pr{W} & \text{by~(\ref{f1})}.
\end{align}
Hence,
\begin{equation}\label{quad}
3 \pr{W} - 2 \pr{W}^2 - \frac{1}{2} = 0.
\end{equation}
Equation~(\ref{quad}) is a quadratic in $\pr{W}$; only one of its roots
lies between 0 and 1 and so makes sense as a probability, namely,
\[
\frac{3}{4} - \frac{1}{4} \sqrt{5} \approx 0.19.
\]}

\end{problem}


%nikos
%TUT10s - last used Spring 99 Tutorial 11, Problem 2
%LEARNING OUTCOMES:8 (calculate probabilities)
%                  10 (study in a small group)
%New problem added S02

\begin{problem}
Carried over to
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/miscellaneous/cp10F.pdf}
{in-class Problem 1} Friday, Week 10.
\end{problem}

\instatements{

\newpage
\appendix

\section*{Probability Rules}

\subsection*{Events}

\begin{align}
\pr{\lgunion_{n \in \naturals} A_n} = & \sum_{n \in \naturals} \pr{A_n}
\mbox{ for pairwise disjoint } A_n  \tag{Sum Rule}\\
\pr{A-B}  = &  \pr{A} - \pr{A \intersect B} \tag{Difference Rule}\\
%
% \item $\pr{A \intersect B}  \le  \pr{A}, \label{ab<a}$
%
\pr{\bar{B}}  = &  1 - \pr{B} & \tag{Complement Rule}\\
\pr{A \union B}  = &  \pr{A} + \pr{B} - \pr{A \intersect B}
        \tag{Inclusion-Exclusion}\\
\pr{A \union B}  \leq & \pr{A}+ \pr{B} \tag{Boole's inequality} \\
\pr{A} \le & \pr{A \union B} \tag{Monotonicity}
%
%\item $\pr{\lgintersect_n A_n} \ge 1 - \sum_n \pr{\overline{A_n}}$
%
\end{align}

[Law of Total Probability] 
Let $B_0, B_1, \ldots$ be disjoint events whose union is the
entire sample space.  Then for all events $A$,
\begin{equation*}
\pr{A} = \sum_{i \in \naturals} \pr{A \cap B_i}.
\end{equation*}


\subsection*{Conditional Probability}
\begin{align}
\prcond{A}{B} \eqdef &  \frac{\pr{A \intersect B}}{\pr{B}} \notag\\
\pr{A \intersect B} = & \prcond{A}{B} \pr{B} \tag{Product Rule}\\
\prcond{A}{B} = & \frac{\prcond{B}{A}\pr{A}}{\pr{B}} \tag{Bayes Rule}
\end{align}

[Law of Total Probability - Conditional form]
Let $B_0, B_1, \ldots$ be disjoint events whose union is the
entire sample space.  Then for all events $A$,
\begin{equation*}
\pr{A} =  \sum_{i \in \naturals} \prcond{A}{B_i}\pr{B_i}.
\end{equation*}
}


\end{document}
