\problemdata                                                             
        {Lucky Numbers} % latex-friendly label for the prob.
        {Random variables} % The topic(s) of the problem content.  
        {from http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/Site/} % Source (if known)                                          
        {S01 Final, 11} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
David and Lars decide to select their lucky numbers from the set of
numbers $\{1,\ldots,n\}$, where $n=k^2$ for some positive integer $k$.
Lars selects his $k$ distinct lucky numbers uniformly at random.
David also selects his $k$ distinct lucky numbers uniformly at random,
independent of which numbers were selected by Lars.

\begin{problemparts}
\problempart What is the probability that the number~$i$ (where
$1 \le i \le n$) ends up in Lars's set of lucky numbers?

\solution{  It may seem pretty obvious that since Lars chooses $k$
  out of $k^2$ numbers, there is a $k/k^2 = 1/k$ chance that a
  particular number gets chosen, but let's work this our carefully.
  We count the number of choices which include a specific number~$i$
  over the total number of choices Lars made:
  \[
  \frac{\binom{k^2-1}{k-1}}{\binom{k^2}{k}} = 
  \frac{(k^2-1)!}{(k-1)!(k^2-k)!}\frac{k!(k^2-k)!}{(k^2)!}=
  \frac{k}{k^2}=
  \frac{1}{k}
  \]
  }

\problempart What is the expected size of the intersection of
the sets of lucky numbers chosen by Lars and David, i.e., what is the
expected number of lucky numbers that Lars and David agree on?

\solution{  Let $Y$ be the number of lucky
numbers on which they agree. For $i\in\{1,\ldots,k^2\}$, let $X_i$ be
an indicator variable on whether they agree $i$ is a lucky number

Since $Y=\sum_{i=1}^{k^2} X_i$, by linearity of expectation:
\[
E[Y] = \sum_{i=1}^{k^2} E[X_i] = \sum_{i=1}^{k^2} \Pr(X_i=1).
\]
What the probability that $X_i=1$, or in other words the probability
that both Lars and David pick the number~$i$? Since their choices were
independent, we can just multiply the probability that Lars picks~$i$
with the probability that David picks~$i$ to get $\Pr(X_i=1)$.  Since
both Lars and David has a $1/k$ chance of picking $i$, so the
probability that they both did is $1/k^2$. For all $i$, $E[X_i]=1/k^2$
so
\[
E[Y] = k^2 \frac{1}{k^2} = 1
\]

}


\problempart What is the probability that Lars and David do not
agree on any lucky number?

\solution{  Suppose that Lars has chosen his $k$~numbers. Then
  David can choose his $k$~numbers in $\binom{n}{k}$ ways;
  $\binom{n-k}{k}$ of those choices do not intersect with Lars's set at
  all. Therefore, the probability that Lars and David do not agree on
  an lucky number is $\binom{n-k}{k} / \binom{n}{k} = ((n-k)!)^2 /
  (n!(n-2k)!$.}



\problempart 
%from http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/Site/
% final exam 1997
What is the expected sum of a randomly chosen subset $S$ of $\{1, 2,
3, \ldots, 20\}$? (In other words, $S$ is equally likely to be any of
the $2^{20}$ subsets.  The sum of $S$ is the sum of all its elements.
The sum of the empty set is 0. What is the expectation of this sum?)

\solution{ 

Define the random variable $X_i$ as follows: $X_i=i$ if $i$ is in the
chosen subset; otherwise $X_i=0$.  Thus $S = X_1 + X_2 + \cdots +
X_{20}$.  By linearity of expectation, $E[S] = E[X_1] + E[X_2] + \cdots
+ E[X_{20}]$.  Since each $i$ is equally likely to be in the set as not,
$E[X_i] = {i \over 2}$.  Thus
\begin{eqnarray*}
E[S] & = & \sum_{i=1}^{20} {i \over 2} \\
& = & {1 \over 2} \sum_{i=1}^{20} i \\
& = & {1 \over 2} {20 \cdot 21 \over 2} \\
& = & 105
\end{eqnarray*}
}

\end{problemparts}
\end{problem}
                                 