\problemdata
{s96 ps9}
{indicator random variable}

\begin{problem }
Let $S$ be the set of functions
from $\{1,\ldots,n\}$ to $\{1,\ldots,k\}$,
and $\Pr$ the uniform probability distribution 
on $S$: $\Pr(f)=1/|S|$ for all $f\in S$.

Define the random variable $R\colon S\to \nat$
as $R(f) = |\mbox{range}(f)|$,
that is the random variable $R$ expresses
the size of the range of a function 
selected uniformly at random from $S$.

What is the expected value of $R$?
(your answer should be a function of $n$ and $k$).

\solution{
Let $I_a$ be the indicator variable for $a$ being in the $\mbox{range}(f)$.
Then, 
\[
R= I_1 + I_2 +\dots +I_k
\]
and
\[
E(R) = E(I_1) + E(I_2) + \dots + E(I_k) = kE(I_1)
\]
by symmetry.

$E(I_1)$ is the probability that $1$ is the $\mbox{range}(f)$.  This
probability is just 1 minus the probabilility that $1$ is {\em not} in
the $\mbox{range}(f)$.

The set of functions that do not have $1$ is the range is $(k-1)^n$.
Since $|S|$ is $k^n$, the probability that 1 is not in the range
is $(1-\frac{1}{k})^n$.  Therefore,
\[
E(R) = k (1- (1-\frac{1}{k})^n)
\]
For large $k$, this is approximately
$k(1- e^{-n/k})$.
}

\end{problem}