Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability of consecutive elements in set

  1. Sep 17, 2008 #1
    Lets say i have some number 'N' of numbers - in a particular order.
    I then remove some fraction 'F' of those numbers.

    I want to know the probability of there being (some number) 'Y' consecutive initial-numbers remaining.

    Any ideas?

    Would it just be F^Y ?
     
  2. jcsd
  3. Sep 17, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    If the numbers are removed independently with probability p, then the chance that Y numbers follow some given sequence member (not too close to the end) is (1-p)^Y.

    If one element is removed uniformly at random from the sequence, then a second, a third, and so on until FN have been removed, then (for large N) this approximates the above with p = F.

    Thus for each remaining member, the chance that it is followed by Y-1 members is approximately (1-F)^(Y-1).

    Since we're assuming N is large, then very few members are close to the end, so we'll assume all N(1-F) remaining members are far from the end.

    Now the chance that a given member is not followed by Y-1 others is, of course, 1 - (1-F)^(Y-1) in our approximation. Thus the chance that all N(1-F) remaining members are not followed by Y-1 others is about
    (1 - (1-F)^(Y-1))^(N(1-F))
    and so the chance that at least one not-removed member is followed by Y-1 others
    1 - (1 - (1-F)^(Y-1))^(N(1-F))

    For example, removing half of a million members, the chance that 20 in a row remain is about 62%.

    If N is not large, the formula falls apart. I'm not sure how large you'd need, but maybe N > 50Y would be good enough.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?