Question

Compute ?(?) for the following random variable ?:

?=Number of tosses until all 10 numbers are seen (including the last toss) by tossing a fair 10-sided die.

To answer this, we will use induction and follow the steps below:

Let ?(?) be the expected number of additional tosses until all 10 numbers are seen (including the last toss) given ? distinct numbers have already been seen.

1. 1. Find ?(10).

   ?(10)=?

1. 2.

   Write down a relation between ?(?) and ?(?+1). Answer by finding the function ?(?) in the formula below.

   For ?=0,1,…,9:

   ?(?)=?(?+1)+?(?)

   where ?(?)=?

1. 3

   Finally, using the results above, find ?[?].

   (Enter an answer accurate to at least 1 decimal place.)

   ?[?] = ?

Answer 1

1.

E(10) = Expected number of additional tosses until all 10 numbers are seen given 10 distinct numbers have already been seen = 0

2.

f(i) = E(i) - E(i+1) = Expected number of additional tosses until all 10 numbers are seen given i distinct numbers have already been seen - Expected number of additional tosses until all 10 numbers are seen given i+1 distinct numbers have already been seen

= Expected number of additional tosses to get the next (i+1)th distinct number given i distinct numbers have already been seen

When i distinct numbers have already been seen, remaining distinct numbers = 10 - i

Probability to find next distinct number = (10 - i) / 10

Let X be the number of trails to get the next (i+1)th distinct number. Then X ~ Geom(p = (10 - i) / 10)

E(X) = 1/p = 10/(10-i)

Thus,

f(i) = Expected number of additional tosses to get the next (i+1)th distinct number given i distinct numbers have already been seen = 10/(10-i)

3.

E[X] = E[0] = E[1] + f(0)

= E[2] + f(1) + f(0)

= E[3] + f(2) + f(1) + f(0)

.....

= E[10] + f(9) + .... + f(1) + f(0)

= 0 + f(9) + f(8) + ... + f(1) + f(0)