Randomized algorithms |
Exercises 1, due February 9, 2000
- The variance D2(X) of a random variable X is
the expectation of the random variable
D2(X) = E((X-E(X))2).
The variance is also denoted by ,
or by var[X].
D2(X) = E(X2) - (E(X))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))?
- 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
- Find Markov's inequality from a textbook and give an
informal justification of it.
State Chebyshev's inequality.
- 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''.
Wednesday, 09-Feb-2000 20:47:36 EET