0
$\begingroup$

Suppose I have a range of integer numbers varied from 0 to L (L is a positive integer). I now randomly select two random integers from 0 to L to form a sub-range of integers. What is the relationship between the number of these sub-ranges and the probability for all these sub-ranges to cover the entire integer range?

Please note: It does not need to choose all L+1 integers to cover the entire range. For example, assuming L is 10. For the first time, the random machine chooses 2 and 5. so the range [2,5] is covered. For the second time, the machine chooses 3 and 10. Then the accumulative range is now updated to [2,10]. The third time, the machine chooses 0 and 4. The accumulative range will be updated to [0,10], which has completely covered all the 11 integers from 0 to 10 and attempts in this run is 3 times. So I am after the relationship between the probability of the entire range being covered and number of attempts.

$\endgroup$
  • $\begingroup$ Based on OPs comment to my answer, the points that can be picked are only the ones at whole number coordinates from $0$ to $L$. It is not a continuous line segment. I asked OP to edit this in, but it has not happened. It makes the problem much harder. $\endgroup$ – Ross Millikan Nov 7 '17 at 5:43
0
$\begingroup$

For any finite number of segments the chance is zero because you have no chance of covering the endpoints. Even if your line segment is open, there is a point near the end that has probability less than any $\epsilon \gt 0$ that you pick of being covered.

$\endgroup$
  • $\begingroup$ I think the probability of the end points being picked up is 1/L rather than 0 (assuming that there are L points available for pickup)?? Also, the more line segments are chosen, the more the entire line will be covered by them, why is the chance still 0?? $\endgroup$ – Micfox Nov 7 '17 at 4:58
  • $\begingroup$ I was assuming the line (segment-lines are infinitely long) was continuous and the points you choose could be anywhere along it. You seem to be thinking of points at the integer positions, so you really have the ordered tuple $(0,1,2,3,\ldots L)$. Do you include both endpoints? That means there are $L+1$ points. Please clarify. I will delete this once you do, because it does not apply. $\endgroup$ – Ross Millikan Nov 7 '17 at 5:12
  • $\begingroup$ Thanks. I have changed the question now it should be more explicit (and easier to solve) as it changed from continuous to discrete? $\endgroup$ – Micfox Nov 7 '17 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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