\problemdata                                                             
        {Interviewing for jobs} % latex-friendly label for the prob.
        {Inclusion-exclusion} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 11, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Since his appointment at MIT ends this summer, Dr
  Engebretsen is currently in the process of applying for jobs. He
  reasons that his chances of getting interviewed should increase if
  he praises his future employer in the application; therefore, he
  writes separate, personalized letters to all his prospective employers.
  
  Being eager to complete the application process, Dr. Engebretsen remembered to write the addresses on the envelopes only \emph{after} having sealed them. In order to avoid having to open all the envelopes, he
  adopts the strategy of writing the addresses on the letters
  uniformly at random. What is the probability that at least one
  prospective employer gets the right letter (the one addressed to him)?

  \begin{problemparts}
    \problempart First suppose that Dr Engebretsen sends 3~letters and
    compute the probability in this case.
    \solution{
Consider the events $A_1, A_2, A_3$ where $A_i$ means that the $i$th envelope contains the right letter. The probability that at least one of these occurs is then:
\[
\Pr[A_1\union A_2\union A_3]
\]
The events are not independent, so we need to use the inclusion/exclusion principle to figure out this probability. We notice that
\[
\Pr[A_1]=\Pr[A_2]=\Pr[A_3]=\frac{(3-1)!}{3!}=\frac{1}{3}
\]
This is because if the first letter is placed correctly ($A_1$), the remaining two can be arranged in $2!$ ways, and similarly for the other two cases.
Moreover,
\[
\Pr[A_1\intersect A_2]~=~\frac{(3-2)!}{3!}=\frac{1}{6}
\]
and likewise for all $\binom{3}{2}$ pairwise intersections.
Finally,
\[
\Pr[A_1\intersect A_2\intersect A_3]~=~\frac{(3-3)!}{3!}=\frac{1}{6}
\]
So, according to the inclusion/exclusion principle, 
\[
\Pr[A_1\union A_2\union A_3]=\binom{3}{1}\frac{1}{3}-\binom{3}{2}\frac{1}{6}+\binom{3}{3}\frac{1}{6}=\frac{2}{3}
\]
It would seem simpler to instead consider the complement event
\[
\Pr[A_1\union A_2\union A_3]
=
1 - \Pr[\bar{A_1}\intersect\bar{A_2}\intersect\bar{A_3}].
\]
However, \emph{the events $\bar{A_1}$, $\bar{A_2}$ and~$\bar{A_3}$
  are not independent!} In fact, they are not even pairwise
independent. To see this, consider $\prcond{A_2}{A_1}$. (We can
consider $\prcond{A_2}{A_1}$ instead of $\prcond{\bar{A_2}}{\bar{A_1}}$ by problem~1 above.) When the first letter has the
correct address, the probability that the second letter has the
correct address is $1/2$.  However $\Pr[A_2] = 1/3 \neq \prcond{A_2}{A_1}$.  Using the product rule, we could rewrite the probability we
are interested in as
\[
\Pr[A_1\union A_2\union A_3]
=
1 - \Pr[\bar{A_1}]\prcond{\bar{A_2}}{\bar{A_1}}
\prcond{\bar{A_3}}{\bar{A_2}\intersect\bar{A_1}}
\]
and then compute the conditional probabilities, but this would
most likely not be simpler than inclusion-exclusion.}

    
    \problempart Being a theoretician, Dr Engebretsen of course sent
    $n$~letters.  Find an approximation of the probability in this case.
    \solution{ Let $A_i$ be the event that envelope~$i$ has the
      correct address. We are interested in $\Pr[\cup A_i]$.  To apply
      the inclusion-exclusion formula, we need to compute the
      probabilities of individual intersection events---namely, to
      determine the probability $\Pr[A_{i_1}\cap A_{i_2} \cap
      \cdots\cap A_{i_k}]$ that the addresses on envelopes $i_1,
      \ldots, i_k$ are correct.  To do so we apply our standard four
      steps.
      \begin{description}
      \item[The sample space.] The sample space involves a permutation
        of the addresses written on the envelopes. There are $n!$
        permutations, so the sample space has size~$n!$.
      \item[Determine atomic event probabilities.] We assume a uniform
        sample space, so each event has probability $1/(n!)$.
      \item[Determine the event of interest.] These are the
        permutations where envelopes $i_1,\ldots,i_k$ have the correct
        address.
      \item[Find the event probability.] Since the sample space is
        uniform, this is equivalent to determining the \emph{number}
        of atomic events in our event of interest. How many
        permutations have the property that letters $i_1,\ldots, i_k$
        have the correct addresses? Well, the remaining $n-k$ letters
        can be addressed arbitrarily so the total number of atomic
        events of this type is $(n-k)!$. Thus, the \emph{probability}
        of the event in question is $(n-k)! / n!$.
      \end{description}
      We have found that the probability a specific set of
      $k$~addresses is correct is $(n-k)!/n!$. There are
      $\binom{n}{k}$ such sets of $k$ cards. So the term number~$k$ in
      the inclusion-exclusion expression is
      \[
      \binom{n}{k}\frac{(n-k)!}{n!} =
      \frac{n!}{(n-k)!k!} \times \frac{(n-k)!}{n!} =
      \frac{1}{k!}\,.
      \]
      Thus, the probability of at least one match is
      \[
      1-1/2!+1/3!-\cdots + (-1)^{n+1}/n!
      \]
      We can understand this expression by thinking about the Taylor
      expansion of
      \[
      e^{-x} = 1-x+x^2/2!-x^3/3!+\cdots
      \]
      In particular,
      \[
      e^{-1} = 1-1+1/2!-1/3!+\cdots
      \]
      Our expression takes the first $n+1$ terms of the Taylor
      expansion; the remainder is less than $1/(n+1)!$, which is
      negligible. So, our probability is approximately $1-1/e$.}
  \end{problemparts}
  


\end{problem}
                                 