Set nibbling

[bonanova]

From the set of integers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} I randomly choose an element, say 3. I subtact 3 from 10, getting 7.

Now I have the set {1, 2, 3, 4, 5, 6, 7}. I choose another element at random, say 5. I subtract 5 from 7, getting 2.

Now I have the set {1, 2}. I randomly choose one of these elements, say 1. I subtract 1 from 2, getting 1.

Now I have the set {1}. I randomly choose one of these elements. It turns out to be 1. I subtract 1 from 1, getting 0.

Now I have the empty set.

Each step took away a nibble, leaving a smaller set.

This example nibbled a set of 10 elements down to zero in four steps.

Starting with a set of p elements, what is the expected number n of nibbles required to empty the set?

[m00li]

From {1,2,3,...k,...,p-1,p}, kth element can be chosen with 1/p probability. If k is chosen, then p-k elements remain to be nibbled. So expected number of nibbles in this case become = 1 + expected number of nibbling p-k elements. (here 1 is added as 1 step is consumed in selecting the kth element). Let the number required to nibble p elements be denoted by N_p

N_p = (1/p)*(1+N_p-1) +(1/p)*(1+N_p-2)..... (1/p)*(1+N₁) + (1/p)*(1+N₀)

Clearly N₀ and N₁ are 0 and 1, respectively.

Hence,

N_p = (1/p)*(p+N_p-1+N_p-2+...N₁) = 1+ (1/p)(N_p-1+N_p-2+...N₁₎ = 1 + (1/p)(1+(1/(p-1))(N_p-2+...N₁) + (N_p-2+...N₁)) = 1 + 1/p + (1/(p-1))(N_p-2+...N₁)

Hence, N_p = 1/p+1/(p-1)+1/(p-2)+...+1/3+1/2+1