\problemdata                                                             
        {Circuit Board Failure} % latex-friendly label for the prob.
        {boole's inequality} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 10, 3} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           

         We know that
\[
\prob{A \union B}  =  \prob{A} + \prob{B} - \prob{A \intersect B}.
\]
A weaker statement known as \emph{Boole's inequality} is 
an immmediate corollary:
\[
\prob{A \union B}  \le  \prob{A} + \prob{B}.
\]

Obvious as it is, Boole's inequality can be useful.  For example, we will
use it to analyse reliability in manufacturing circuit boards.

Say that each board requires a total of $n$ wiring connections to be made
among it components.  Based on past experience, we judge that any
particular connection will be made \emph{incorrectly} with probability $p$, for
some (hopefully small) number $p$.  That is, we assume
\[
\prob{\mbox{$i^{th}$ connection is wrong}} = p
\]
for $1 \le i \le n$.  What is the probability that a circuit is wired
correctly, i.e., there are no incorrect connections?  Although we can't
give a definite answer without more information, we can still come up with
useful bounds on the probability of boards with buggy wiring.

\begin{problemparts}

\problempart
Prove that if we select a circuit board at random from the assembly line, then
\[
1-p \geq \prob{\mbox{all connections on the board are OK}} \geq 1-np.
\]

\hint Let $A_i$ denote the event that connection $i$ is made
\emph{correctly}.  Now
\[
\prob{\mbox{all connections are OK}}  = \prob{\intersect A_i}.
\]
Remember that $\prob{\overline{B}} =  1 - \prob{B}$.

\solution{
\textbf{Solution:}\\
Then $\overline{A_i}$ is the event that connection $i$
is made incorrectly, so $\prob{\overline{A_i}} = p$.  Now,
\begin{eqnarray*}
1-p & = & \prob{A_1}\\
& \geq &  \prob{\intersect A_i} \qquad\mbox{(because $A
    \subseteq A_1$ implies $\prob{A} \leq \prob{A}$)}\\
& = & 1 - \prob{\cup \overline{A_i}} \qquad\mbox{(by DeMorgan
             and the hint)}\\
& \ge & 1 - \sum_{i=1}^n \prob{\overline{A_i}} \qquad\mbox{(by Boole's Inequality)}\\
& = & 1-np.
\end{eqnarray*}
}

\end{problemparts}

So for example, if $n = 10$ and $p = 0.01$, the previous part
establishes that
\[
0.99 \geq \prob{\mbox{all connections are OK}} \geq 0.9.
\]
In other words, the chance is somewhere between 90\% and 99\% that all
connections on a board are okay.

These bounds are actually the best ones possible when the only information
available is the probability of failure of each connection.  To show why
this holds, we can model the wiring scenario with a sample space, $S$, of
binary words of length 10.  Each point $(b_1,b_2,\dots,b_{10}) \in S$
describes the bad set of connections in a circuit: $b_i= 0$ if the $i$th
connection is bad and $b_i = 1$ if it is OK.

\begin{problemparts}

\problempart

Show that the probability that a circuit gets wired correctly actually
could be as high as 99\% by describing appropriate probabilities for the
sample points in $S$.

\solution{

\textbf{Solution:}\\
There could be 99\% reliability if the individual errors occur
in such a way that whenever you make one connection wrong, all the
connections are wrong.

So let $\prob{(1,1,\dots, 1)} \eqdef 0.99$, $\prob{(0,0, \dots, 0)}\eqdef
0.01$, and let the probability of all other points be zero.  So $A_i =
\set{(b_1,\dots,b_{10}) \in S : b_i = 1}$.  But since except for
$(1,1,\dots,1)$, all points in $A_i$ have probability zero, we have
$\prob{A_i} = \prob{(1,1,\dots,1)} = 0.99$.

}

\problempart Show that the probability that a circuit gets wired correctly
actually could be as low as 90\% by describing appropriate probabilities
for the sample points.

\solution{

\textbf{Solution:}\\
Suppose there is never more than one wrong connection.  That is,
\begin{eqnarray*}
\prob{(1,1,\dots,1)} & \eqdef & 0.9,\\
\prob{(b_1,\dots,b_{10})} & \eqdef & 0.01\text{ if } \sum_{i=1}^{10}b_i =9,\\
\prob{(b_1,\dots,b_{10})} & \eqdef & 0  \text{ otherwise}.
\end{eqnarray*}
Note that the sum of the probabilities of all these points is one, so this
is a well-defined probability space.  Also, the only sample point in
$\overline{A_i}$ with positive probability is $1^{i-1}01^{n-i}$, so
$\prob{\overline{A_i}} = \prob{1^{i-1}01^{n-i}} = 0.01$ as required.

}

\end{problemparts}
\end{problem}                        