The following related discrete problem also gives a good clue for the answer to Exercise Exercise. Randomly select with replacement [math]t_1[/math], [math]t_2[/math],..., [math]t_r[/math] from the set [math](1/n, 2/n, \dots, n/n)[/math]. Let [math]X[/math] be the smallest value of [math]r[/math] satisfying

[[math]] t_1 + t_2 +\cdots+ t_r \gt 1\ . [[/math]]

Then [math]E(X) = (1 + 1/n)^n[/math]. To prove this, we can just as well choose [math]t_1[/math], [math]t_2[/math], ..., [math]t_r[/math] randomly with replacement from the set [math](1, 2, \dots, n)[/math] and let [math]X[/math] be the smallest value of [math]r[/math] for which

[[math]] t_1 + t_2 +\cdots+ t_r \gt n\ . [[/math]]

• Use Exercise to show that
  [[math]] P(X \geq j + 1) = {n \choose j}{\Bigl(\frac {1}{n}\Bigr)^j}\ . [[/math]]
• Show that
  [[math]] E(X) = \sum_{j = 0}^n P(X \geq j + 1)\ . [[/math]]
• From these two facts, find an expression for [math]E(X)[/math]. This proof is due to Harris Schultz.

Notes