Consider a sequence of independent trials, each of which is equally likely to result in any of the outcomes 0, 1, . . . , m. Say that a round begins with the first trial, and that a new round begins each time outcome 0 occurs. Let N denote the number of trials that it takes until all of the outcomes 1, . . . , m − 1 have occurred in the same round. Also, let Tj denote the number of trials that it takes until j distinct outcomes have occurred, and let Ij denote the j th distinct outcome to occur. (Therefore, outcome Ij first occurs at trial Tj .)

(a) Argue that the random vectors (I1, . . . , Im) and (T1, . . . , Tm) are independent.

(b) Define X by letting X = j if outcome 0 is the j th distinct outcome to occur. (Thus, IX = 0.) Derive an equation for E[N] in terms of E[Tj ], j = 1, . . . , m−1 by conditioning on X.

(c) Determine E[Tj ], j = 1, . . . , m−1.

Hint: See Exercise 42 of Chapter 2.

(d) Find E[N].