Lesson 1

Basic Problems.

1. (5 points) Compute the variance of the random variable equal to the number rolled on a fair die.
2. (5 points) A biased coin shows heads with probability \(p\). The coin is tossed \(n\) times. Find the variance of the number of heads.
3. (10 points) The discrete random variable \(\xi\) takes only two values \(x_{1} < x_{2}\) with \(\Pr[\xi=x_{1}]=0.2\), \(E[\xi]=2.6\), and \(\operatorname{Var}[\xi]=0.64\). Determine \(\Pr[\xi=x_{2}]\), \(x_{1}\), and \(x_{2}\).
4. (10 points) When making a purchase, one of \(10\) coupons is given uniformly at random. Prove that with probability at least \(0.5\), after \(59\) purchases you have collected all coupons.
   Hint:

   Let \(T\) be the number of purchases required to collect all coupons. First, determine the expected value \(E[T]\). Then, apply Markov's inequality to bound the probability of the complementary event, specifically that collecting all coupons takes \(60\) or more steps.
5. (10 points) In a lottery, \(40\%\) of ticket revenue goes to prizes. Each ticket costs 100 rubles. Prove that the probability to win at least 5000 rubles on a single ticket is \(<1\%\).
6. (15 points) Let \(n\ge2\) and consider a random permutation on \(n\) numbers (all \(n!\) permutations are equally likely). Let \(X\) be the number of fixed points. Compute \(E[X]\) and \(\operatorname{Var}[X]\).
7. (15 points) Computers of the Horns-and-Hooves company work on average 3 years without failure; the standard deviation is 2 months. Give a lower bound on the percentage that work between 31 and 41 months without failure.
   Hint:

   Convert the average lifetime into months to match the units of the standard deviation. Then, identify the deviation from the mean and apply Chebyshev's inequality.
8. (15 points) Let the random variable \(\alpha \sim \operatorname{Geom}(p)\). Find \(\operatorname{Var}[\alpha]\).
   Hint:

   Recall that \(\operatorname{Var}[\alpha] = E[\alpha^{2}] - (E[\alpha])^{2}\). Use the Law of Total Expectation to determine \(E[\alpha^{2}]\) by conditioning on the outcome of the first trial. Note that if the first trial fails, the process restarts, so the total trials become \(1 + \alpha'\), where \(\alpha'\) has the same distribution as \(\alpha\).
9. (15 points) In an election, there are three candidates: \(A\), \(B\), and \(C\). A voter chooses \(A\) with probability \(p_{A}\), \(B\) with probability \(p_{B}\), and \(C\) with probability \(p_{C}\), where \(p_{A} + p_{B} + p_{C} = 1\). You sample \(n\) voters to estimate \(p_{A}\). Let \(N_{A}\) be the count of voters for \(A\). Simultaneously, you want to estimate \(p_{B}\). Let \(N_{B}\) be the count of voters for \(B\). We want to ensure that both estimates are correct within an error of \(0.05\) with probability at least \(0.90\). Show that \(n = 2000\) is enough to ensure that: \[\Pr\left[ \left| \frac{N_A}{n}- p_{A} \right| \le 0.05 \text{ and }\left| \frac{N_B}{n}- p_{B} \right| \le 0.05 \right] \ge 0.90.\]
10. (15 points) Show that Markov’s and Chebyshev’s inequalities are tight: give examples of a non-constant random variable \(\alpha\) for which they become equalities.
11. (15 points) Let \(Y\) be a nonnegative integer random variable such that \(0<E[Y^{2}]<\infty\). Prove the following:
    • \(\Pr[Y=0] \le \frac{E[Y^2]-E[Y]^2}{E[Y]^2}\),
    
    
    • \(\Pr[Y \ne 0] \le E[Y]\).
    
    
    • \(\frac{E[Y]^2}{E[Y^2]}\le \Pr[Y \ne 0]\),
    
    

12. (15 points) Assume that for a problem \(P\) you have a Las Vegas randomized algorithm \(A\): whenever it finishes, its answer is correct, and its running time has expectation \(10n^{2}\). Build an algorithm \(A'\) that always finishes in \(O(n^{2})\) time and outputs a correct answer with probability \(99\%\), otherwise reports “don’t know”.