0
$\begingroup$

If I have a domain of 0 to 1000000 (but I doubt the domain matters, just that the ranges can overlap). I then chose 1% ranges uniformly, allowing for ranges to overlap completely or partially.

How do I find the expected percent of the domain that will be covered after K selections?

This seems like a simple selection with replacement but since the ranges can overlap I'm not sure how to find it. Is it as simple as repeatedly adding the useful part of the next selection? The first selection covers 1% if the domain. The second selection also covers 1% of the domain but since only 99% is uncovered, the expected coverage of the second selection is 0.99%, thus after 2 selections it is 1.99%...and so on with decreasing returns on each selection?

An example might be:

Domain: 0-999999 (in a dense sequence)
Percent selected per instance: 1%
Selection count: 50
Each range is chosen uniformly.
And I want to know what the expected % of the whole domain was covered (or remains uncovered as it provides the same information).

So on the first choice maybe the range is 128774-138773. Now after one selection 1% of the values have been covered. The second selection is 250791-260790 and now 2% is selected (but it also could have been 131456-141455 which would have overlapped with the first range resulting in less than 2% currently being covered). And so on for the remaining 48 selections.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Can you add some more context here? This is awfully abstract at present. $\endgroup$
    – gung - Reinstate Monica
    Commented Jul 2, 2015 at 3:36
  • $\begingroup$ how are you choosing the locations of (say) the left edge of the subranges? $\endgroup$
    – Glen_b
    Commented Jul 2, 2015 at 4:09
  • $\begingroup$ Each selected range can start anywhere from 0 to MAX - range width, so in the example I choose an integer between 0 and 999000 uniformly. $\endgroup$
    – user1794469
    Commented Jul 2, 2015 at 4:13
  • $\begingroup$ The endpoints must fall on integers? $\endgroup$
    – Charles Pehlivanian
    Commented Jul 2, 2015 at 4:19
  • $\begingroup$ Yes, endpoints must be integers. But if a solution assumed continuous it would be correct up to some % for discrete ranges like these right? $\endgroup$
    – user1794469
    Commented Jul 2, 2015 at 4:35

1 Answer 1

Reset to default
0
$\begingroup$

You can estimate this by simplifying the problem: say you have $N$ bins, and you place $M$ marbles into them selecting a bin at random; you want to count the number of bins with at least one marble. You relate this estimate to your real problem by dividing the size of the domain by the "percent selected per instance".

The formula for the simplified model is going to look a lot like this.

Improve this answer
$\endgroup$
1
  • $\begingroup$ please reproduce the formula in case the link changes in the future $\endgroup$
    – Antoine
    Commented Oct 9, 2015 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.