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

Table of contents
- Solution ii

Solution

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

, so linearity of expectation gives

E M_{n} \leq n < \infty

. The tail integral formula for expectation, followed by the finite binomial theorem expansion, gives

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

, the harmonic number

H_{n}

.

 Ancestors (13)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version