Results 1 to 2 of 2

Math Help - Sampling with replacement

  1. #1
    Member
    Joined
    Dec 2007
    Posts
    80
    Awards
    1

    Sampling with replacement

    A = {1, 2, ..., N} is a set of N integers.

    I'm sampling from A, one element each time, with replacement.

    How many sampling may I expect to perform, in average, before obtaining one element that already came out?

    I would appreciate some guidance. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by paolopiace View Post
    A = {1, 2, ..., N} is a set of N integers.

    I'm sampling from A, one element each time, with replacement.

    How many sampling may I expect to perform, in average, before obtaining one element that already came out?

    I would appreciate some guidance. Thanks!
    There are N^i possibilities for the first i samples; we assume these are all equally likely.

    How many of the arrangements have a first duplication on sample number i? There are N ways to choose the ith sample. This element also appears exactly once in samples 1 through i-1, and disregarding order, there are \binom{N-1}{i-2} possible choices for the other elements. Each set of elements in samples 1 through i-1 can be ordered in (i-1)! ways. So altogether, there are

    N \binom{N-1}{i-2}(i-1)! = \frac{N! \; (i-1)}{(N-i+1)!}

    possible sequences of samples which have a first match on the ith sample.

    So the probability that a first match happens on sample number i is

    p_i = \frac{N! \; (i-1)}{(N-i+1)! N^i},

    and the expected number of samples required to achieve a match is

    \sum_{i=2}^N i \; p_i.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sampling withOUT replacement.
    Posted in the Statistics Forum
    Replies: 2
    Last Post: May 4th 2011, 04:56 AM
  2. Sampling without replacement
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: March 19th 2011, 05:10 PM
  3. sampling without replacement
    Posted in the Statistics Forum
    Replies: 3
    Last Post: August 7th 2010, 01:20 AM
  4. Sampling with replacement
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: January 20th 2010, 10:19 PM
  5. Sampling with replacement
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 7th 2007, 05:35 PM

Search Tags


/mathhelpforum @mathhelpforum