• 0

Set nibbling

Question

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites

1 answer to this question

  • 0

Posted · Report post

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 Np

Np = (1/p)*(1+Np-1) +(1/p)*(1+Np-2)..... (1/p)*(1+N1) + (1/p)*(1+N0)

Clearly N0 and N1 are 0 and 1, respectively.

Hence,

Np = (1/p)*(p+Np-1+Np-2+...N1) = 1+ (1/p)(Np-1+Np-2+...N1) = 1 + (1/p)(1+(1/(p-1))(Np-2+...N1) + (Np-2+...N1)) = 1 + 1/p + (1/(p-1))(Np-2+...N1)

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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.