        \problemdata       % Takes 5 *mandatory* arguments
        {variance-6}             % latex-friendly label for the prob.
        {variance}               % The topic of the problem content.
        {Velleman}               % Source (if known)
        {S98 PS11-7; F97 PS11-8} % Usage (list ones you are aware of).
        {Theory Pig, S02}        % Last revision info (author, date).
\begin{problem}
A man has a set of $n$ keys, one of which fits the door
to his apartment.  He tries the keys until he
finds the correct one.  Give the expected number and variance
for the number of trials until success if

\begin{problemparts}

\problempart he tries the keys at random (possibly repeating a key tried
       earlier)


\solution{This problem can be modeled by the Polya Urn Scheme:
Consider an urn with $n-1$ wrong keys and $1$ right key. Each time the
man chooses a key, he tries it and then places it back in the urn. We
want to compute the waiting time, $T$, to pick the right key.

The probability of picking the right key on the first trial is $1/n$,
and the probability of picking the wrong key is $(n-1)/n$.  The
probability stays the same on all subsequent trials since the picked
key is always returned to the urn. Thus
\[
P(T=k) = \left(\frac{n-1}{n}\right)^{k-1}\frac{1}{n}{.}
\]
Note: this is the same as the waiting time for the first head in the
Bernouli process with a biased coin. Let $p=1/n$ and let $q=1-p$.
Then, the expectation of $T$ is
\[
E(T) = \sum_{k=1}^\infty{k q^{k-1}p}
= p\sum_{k=1}^\infty{k q^{k-1}}
= p\frac{1}{(1-q)^2} = \frac{1}{p} = n
\]

The variance of $T$ can be computed directly from the formula,
\[
\variance{T} = E(T^2) - E^2(T){.}
\]
Again, by definition we have
\[
E(T^2) = \sum_{k=1}^\infty{k^2 pq^{k-1}}{.}
\]
How do we evaluate this sum? We use the following trick. We know that
\[
\sum_{k=1}^\infty{kq^k} = q\sum_{k=1}^\infty{kq^{k-1}} = \frac{q}{(1-q)^2}{.}
\]
Moreover,
\begin{eqnarray*}
\sum_{k=1}^\infty{k^2 q^{k-1}} &=& \sum_{k=1}^\infty{\frac{d}{dq}k q^k}\\
 &=& \frac{d}{dq}\sum_{k=1}^\infty{k q^k}\\
 &=& \frac{d}{dq}\frac{q}{(1-q)^2}\\
 &=& \frac{1}{(1-q)^2} + \frac{2q}{(1-q)^3} = \frac{1}{p^2} + \frac{2q}{p^3}{.}
\end{eqnarray*}
Finally, the expectation $E(T^2)$ is
\[
E(T^2) = p \left(\frac{1}{p^2} + \frac{2q}{p^3}\right) = \frac{1}{p} + \frac{2q}{p^2} {,}
\]
and the variance is
\[
\variance{T} = \frac{1}{p} + \frac{2q}{p^2} - \frac{1}{p^2} = \frac{q}{p^2} = n(n-1){.}
\]
}

\problempart he chooses keys randomly from among those he has not
       yet tried.

\solution{
Again we look at this as a Polya Urn Process, but
without replacement. The event that the waiting time for the right
key, $T$, is $k$ is the event that we pick the wrong key on the first
trial, and we pick the wrong key on the second trial, etc, and we pick
the right key on the $k$-th trial. Let $K_i$ be the indicator random
variable for the $i$-th trial, i.e. $K_i=1$ if we pick the right key
on the $i$-th trial, and $0$ otherwise. Then
\[
P(T=k) = P((K_1=0) \& (K_2=0) \&\cdots\& (K_{k-1}=0) \& (K_k=1)){.}
\]
By the Multiplication Theorem we can compute
\begin{eqnarray*}
P(T=k) &=& P(K_1=0)P(K_2=0|K_1=0)P(K_3=0|K_1=0,K_2=0)\cdots\\
 & &\hspace{2in}\cdots P(K_k=1|K_1=0,\dots,K_{k-1}=0)\\
 &=& \frac{n-1}{n}\ \frac{n-2 }{n-1}\ \frac{n-3 }{n-2}\ \cdots\ \frac{n-k+1}{n-k+2}\ \frac{1}{n-k+1}\\
 &=& \frac{1}{n}{.}
\end{eqnarray*}
The expectation and variance are now easy to compute from the definitions.
\[
E(T) = \sum_{k=1}^n{kP(T=k)} = \frac{1}{n}\sum_{k=1}^n{k} = \frac{n+1}{2}{.}
\]
\begin{eqnarray*}
\variance{T} &=& E(T^2) - E^2(T)\\
 &=& \sum_{k=1}^n{k^2 P(T=k)} - \left(\frac{n+1}{2}\right)^2\\
 &=& \frac{1}{n}\sum_{k=1}^n{k^2} - \left(\frac{n+1}{2}\right)^2\\
 &=& \frac{1}{n}\ \frac{n(n+1)(2n+1)}{6} - \left(\frac{n+1}{2}\right)^2\\
 &=& \frac{n^2-1}{12}{.}
\end{eqnarray*}
}

\end{problemparts}
\end{problem}
