 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/discrete-mathematics-continuous-mathematics-and-probability/probability/9/b/ii/solution

0 \leq M_{n} \leq \sum_{i} E_{i}

E M_{n} \leq n < \infty

E M_{n} = \int_{0}^{\infty} [1 - (1 - e^{- x})^{n}] d x = k = 1 \sum n (- 1)^{k + 1} (k n) \int_{0}^{\infty} e^{- k x} d x = k = 1 \sum n (k n) \frac{( - 1 ) ^{k + 1}}{k} .

The exchange involves only a finite sum. As a useful check, substitution

t = e^{- x}

rewrites the integral as

\int_{0}^{1} [1 - (1 - t)^{n}] / t d t = \sum_{j = 0}^{n - 1} \int_{0}^{1} (1 - t)^{j} d t = \sum_{k = 1}^{n} 1/ k

H_{n}

 New to topics? Read the docs here!