[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] HUT - CIS /Opinnot/T-61.183/k2000/exercises/1/exercise1.shtml [an error occurred while processing this directive]
[an error occurred while processing this directive] Index of /style/plain

# Index of /style/plain

Parent Directory  -
blue20.gif1999-11-03 19:09 37
blue120.gif1999-11-03 19:08 42
cis_plain.css2000-04-20 12:16 3.1K
cis_plain.css.old2000-01-25 10:42 2.3K
cis_plain_footer.shtml2000-09-08 16:08 322
scientific.shtml2000-03-08 14:05 4.8K
template.html1999-12-03 14:11 332
template.shtml1999-11-12 12:58 321
template.shtml.krista1999-12-03 14:11 267
template.txt1999-11-12 12:58 321

Apache/2.4 Server at www.cis.hut.fi Port 80

# Tik-61.183 Special course on information technology III

Randomized algorithms
Spring 2000
Heikki Mannila

## Exercises 1, due February 9, 2000

1.
The variance D2(X) of a random variable X is the expectation of the random variable (X-E(X))2, i.e., D2(X) = E((X-E(X))2). The variance is also denoted by , or by var[X]. Show that D2(X) = E(X2) - (E(X))2.
2.
Let X(n) be the number of tails obtained when flipping a fair coin n times. What is E(X(n))? What is D2(X(n))?
3.
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 D2(X(n,p)).
4.
Find Markov's inequality from a textbook and give an informal justification of it. State Chebyshev's inequality.
5.
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''.

http://www.cis.hut.fi/Opinnot/T-61.183/k2000/exercises/1/exercise1.shtml
webmaster@www.cis.hut.fi
Wednesday, 09-Feb-2000 20:47:36 EET