I am trying to find a way to solve the following problem :

I have some set A, which contains a set of N numbers, X, where Xi is a number within X. The numbers in X are unique and they are in sorted order.

I will draw K random subsets of size L from X. There are no restrictions on how many subsets I can draw, the only restriction is that the numbers in the subset are contiguous. Subsets are drawn with replacement.

For example, if my set was (1,2,3,4,5,6,7,8,9,10) then valid subsets of size 3 is 1,2,3 or 8,9,10 or 3,4,5 and so on

What is the probability of selecting Xi in anyone of these K subsets given some subset size L?

If the subset size were 1, then the problem is solved by the binomial distribution, or a poisson distribution when N is very large. Also, when the size of the subset =N, then everything has a 1/N probability of being selected. But I am not sure how to solve the problem when L is neither 1 nor N. This is because the positions are not independent because the subset represents contiguous numbers.

Are there any suggestions for how to tackle this problem? Is it similar to other problems?

  • $\begingroup$ If you work this problem for tiny examples the pattern will become clear. For instance, with $N=4$ and $L=2$ There are only $N+1-L=3$ possible subsets. One subset contains $X_1$, two subsets contain $X_2$, two contain $X_3$, and one contains $X_4$. $\endgroup$
    – whuber
    Commented Dec 5, 2013 at 8:01
  • $\begingroup$ I think I see what you mean. Part of the solution is how many ways I can choose N + 1 - L subsets from K draws. The next part is in how many of those subsets does each number occur. I am yet sure how to consolidate the fact that I know there are M possible subsets with how many of those subsets I know contains come number Xi. It does follow a pattern, but I don't yet know how to express it. $\endgroup$
    – user4673
    Commented Dec 6, 2013 at 23:16


Your Answer

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