# Probability of consecutive elements in set

1. Sep 17, 2008

### lzkelley

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. Sep 17, 2008

### CRGreathouse

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.