\documentstyle[12pt]{article}

\begin{document}

\noindent
Tik-61.183 Special course on information technology III \\
Randomized algorithms \\ Spring 2000 \\ Heikki Mannila

\vspace{3mm}

\noindent
{\bf Exercises 1, due February 9, 2000}

\begin{enumerate}

\item
The variance $D^2(X)$ of a random variable $X$ is 
the expectation of the random variable $(X-E(X))^2$,
i.e., $D^2(X) = E((X-E(X))^2)$.
The variance is also denoted by $\sigma_X$, or by {\bf var}$[X]$.
Show that
$D^2(X) = E(X^2) - (E(X))^2$.

\item
Let $X(n)$ be the number of tails obtained when flipping
a fair coin $n$ times.
What is $E(X(n))$? What is $D^2(X(n))$?

\item
Let $X(n,p)$ be the number of heads obtained when flipping
a biased coin (probability of head  $= p$) $n$ times.
Compute $E(X(n,p))$ and $D^2(X(n,p))$.

\item
Find {\em Markov's inequality} from a textbook and give an
informal justification of it.
State Chebyshev's inequality.

\item
Approximate (either analytically or by simulation)
the probability of the following event:
``When flipping a fair coin 1000 times, the number of
heads is less than 450''.

\end{enumerate}

\end{document}