\documentclass[12pt]{article}
\usepackage{amsmath}
\begin{document}
\noindent
Tik-61.183 Special course on information technology III \\
Randomized algorithms \\ Spring 2000 \\ Heikki Mannila
\vspace{3mm}
\noindent
\textbf{Exercises 2, due February 16, 2000}
\begin{enumerate}
\item Assume we have a file containing~$N$ records, where $N$~is so
large that we cannot keep all of the file in memory at one time.
We wish to select a random subset of~$n$ records from the file.
We will use the following algorithm:
\begin{tabbing}
\qquad\=\qquad\=\kill
Set $t\leftarrow0$, $m\leftarrow0$.\\
Repeat until $m=n$:\\
\>Generate a random number $U$,\\
\>uniformly distributed between $0$ and $1$.\\
\>If $U<(n-m)/(N-t)$, then\\
\>\>Add the next record from the file into the subset.\\
\>\>Set $m\leftarrow m+1$.\\
\>Else\\
\>\>Skip the next record.\\
\>Set $t\leftarrow t+1$.
\end{tabbing}
Prove that the algorithm doesn't try to read more than~$N$ records
from the file. Prove that each of the~$\dbinom{N}{n}$
subsets is equally likely to be selected.
\item Let~$p(x,y)$ be the probability that exactly~$x$ records are
selected from among the first~$y$ by the previous algorithm.
Show that
\[ p(x,y) = \binom{y}{x}\binom{N-y}{n-x}\bigg/\binom{N}{n}. \]
\item What is the expected value of~$t$ when the algorithm
terminates? What is the variance?
\item Devise an algorithm to select a random permutation of~$n$
objects using~$O(n)$ random numbers. Each permutation should be
equally likely.
\end{enumerate}
\end{document}