
%\problemdata
%{s96 ps9}
%{indicator random variable}

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

Define the random variable $R : S \to N$ as $R(f) = \card{\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 $\range{f}$.
Then, 
\[
R= I_1 + I_2 +\cdots +I_k
\]
and
\[
\expect{R} = \expect{I_1} + \expect{I_2} + \cdots + \expect{I_k} = k\expect{I_1}
\]
by symmetry.

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

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

\end{problem}


%\problemdata
%{f01 ps11}
%{s97 ps13}
%{grades}
% modifed from spring 97 Pset 13, 3

\begin{problem}
There are $n$ MIT students who are taking 6.042 and 6.003 this term.  To
make it easier on themselves, the professors in charge of these classes
have decided to randomly permute their class lists and then assign students
grades based on their rank in the permutation\footnote{\dots just as many
students have suspected \texttt{:-)}}.  Assume all permutations are equally
likely and that the ranking in each class is independent of the other.

\bparts

\ppart Write a closed form expression for the expected number of students
that have a higher rank in 6.042 than 6.003. 

\solution{

Let $X_i$ be random variable whose value is 1 if student i has higher rank
in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$ for
6.042 than the probability that student $i$ has higher rank on 6.042,
given that the student has rank $r$ in 6.042, is $(r-1)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the
probability that student $i$ has higher rank in 6.042 is
\[
\sum_{1\leq r \leq n}  \frac{1}{n} \frac{r-1}{n} = \frac{n-1}{2n}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x} = \expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{n-1}{2}.
\]

Another way to solve this problem is to observe that students with higher
rank in one class have lower rank in the other class, so by symmetry, the
expected number of higher- and lower-ranked students in either class is
the same.  The expected number of students with the same rank equals 1 by
linearity of expectation, since probability student ranked the same in
both classes is $1/n$.  These observations now yield same answer as above.

}

\ppart
\ppart Write a closed form expression for the expected number of students
that have a rank least $k$ higher in 6.042 than 6.003.

\solution{
This part can be done in the same way as the previous one.  Let $X_i$ be
the random variable whose value is 1 if student $i$ is ranked at least $k$
higher in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$
$(r>k)$ for 6.042 than the probability that student $i$ has at least $k$
higher rank in 6.042 given student ranked $r$ in 6.042 is $(r-k)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the probability
that student $i$ has at least $k$ higher rank in 6.042 is
\[
\sum_{k+1\leq r\leq n} \frac{1}{n} \frac{r-k}{n} = \frac{(n-k)(n-k+1)}{2n^2}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x}=\expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{(n-k)(n-k+1)}{2n}.
\]
}

\eparts

\end{problem}



%\problemdata
%{expectation}
%{graphs}
%{counting}
%{Eric Ho S02}
\begin{problem} Suppose we construct a simple $n$-node graph,
$G=(V,E)$, randomly as follows:

For every set of two distinct vertices $\set{v,v'}$, toss a biased
coin whose probability of coming up heads is $p$.  The undirected edge
between $v$ and $v'$ is included in $E$ iff the coin comes up heads.
Assume that all coin tosses are mutually independent.

A \emph{simple $k$-cycle} in a simple graph is an undirected path
going through each of $k>2$ vertices exactly once and ending where it
started.  A simple $k$-cycle can be represented by the sequence of $k$
vertices $v_1, v_2, \ldots, v_k$ along the path. Note that every
$k$-cycle can be represented by many sequences. For example, the
4-cycle represented by $1234$ is as the same cycle represented by
$2341$ or $3412$ because a cycle does not have to start at any
particular vertex.  It is also represented by $4321$, because the
cycle is undirected.

\bparts \ppart What is the probability that the $k$-cycle with
representation $v_1, v_2, \dots, v_k$ exists in $G$?

\solution{A particular $k$-cycle (call it $e$) will occur only if all of
the edges in that cycle exist in the randomly constructed $G=(V,E)$.  Since
each edge is independently added with probability $p$, we have $\pr{e \in
E} = p^k$.}

\ppart Write a closed form expression for the total number of distinct
possible $k$-cycles.  (In this problem, we consider factorials as closed
forms.)

\solution{There are $P(n,k)$ ways to choose the elements within the
cycle, where
\[
P(n,k) = \frac{n!}{(n-k+1)!}
\]
Since it is a cycle, the starting position does not matter, which means we
need to divide the answer by $k$.  In addition, we need to further divide
by two because the orderings of the set of two vertices $\set{v,v'}$ does
not matter.  The result yields $P(n,k)/2k$.}

\ppart Write a closed form for the expected number of $k$-cycles in $G$.

\solution{ Let $I_e$ be the indicator random variable of the event
that a particular $k$-cycle, $e$, occurs.  So the number, $N$, of
$k$-cycles is $\sum_e I_e$ where $e$ ranges over all possible
$k$-cycles, i.e., all $k$-cycles in the complete graph on $V$.

We know from a previous part that $\pr{I_e = 1} = p^k$, which means that
$\expect{I_e} = p^k$.
Therefore
\[
\expect{N} = \sum_e \expect{I_e} = \frac{P(n,k)}{2k} p^k.
\]
}

\eparts

\end{problem}


%F95 pset 11

\begin{problem}Deviations from the mean:
\bparts
\ppart Prove that if $X$ is a random variable with mean $m$,
then $X-m$ is a random variable with mean 0.

\solution{
$E(X-m) = E(X) - E(m) = m - m = 0$. Thus $X-m$ is a random variable
with mean $0$.}

\ppart
Suppose I flip $n$ unbiased independent coins.  We know that
the mean number of heads is $n/2$.  What is the {\em expected 
deviation from the mean}?  That is, if the number of heads is a
random variable $X$, what is
\[
\expect{\size{X-n/2}}?
\]

\solution{Assume $n$ is even.
\begin{eqnarray*}
E(|X - n/2|) & = 2^{-n}\left[ {\displaystyle \sum_{k=0}^n {n\choose k} |k - \frac{n}{2}|} \right] & \\
 & = 2^{-n}\left[2  {\displaystyle \sum_{k=0}^{\frac{n}{2}-1} {n\choose k} (\frac{n}{2} - k) } \right] & \\
 & = 2^{-n}\left[n{\displaystyle \sum_{k=0}^{\frac{n}{2}-1} {n\choose k} }\right] + 2^{-n}\left[2{\displaystyle \sum_{k=0}^{\frac{n}{2}-1} {n\choose k}k} \right] & \\
 & = 2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}}) \right] + 2^{-n}\left[2{\displaystyle \sum_{k=1}^{\frac{n}{2}-1} {n-1\choose k-1}(\frac{n}{k})k} \right] & \\
 & = 2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}}) \right] + 2^{-n}\left[2n{\displaystyle \sum_{k=0}^{\frac{n}{2}-2} {n-1\choose k}} \right] & \\
 & = 2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}}) \right] + 2^{-n}\left[2n(2^{n-2} - {n-1\choose \frac{n}{2} - 1}) \right] & \\
 & = 2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}})  + 2n(2^{n-2} - {n-1\choose \frac{n}{2} - 1}) \right] & \\
 & = 2^{-n}{n\choose \frac{n}{2}}(\frac{n}{2}).
\end{eqnarray*}
}

\eparts
\end{problem}
