4
$\begingroup$

This is the motivation for my question: Suppose we have $n$ tickets in a bag, and we draw $k$ of them uniformly at random without replacement. Now, repeat the same procedure independently (same $n$ tickets, draw $k$ of them UAR without replacement). I can straightforwardly show that, if $S$ is the number of overlapping tickets between the two samples, then $\mathbb{P}\left(S=j\right)={k \choose j}\left(\prod_{i=0}^{j-1}\frac{k-i}{n-i}\right)\left(\prod_{i=0}^{k-j-1}\frac{n-k-i}{n-j-i}\right)$.

Now, my question is a generalization of this--essentially, I'm curious about what happens to this overlap when we don't have the same probability of drawing each ticket.

To investigate this, my approach is to assign ''weights'' to tickets by creating duplicates To make this more concrete, suppose we have $g$ groups, each with a different number of tickets $n_{i}$, where each $n_{i}$ corresponds to the ''weight'' we want to assign to a particular ticket type. Now we can draw $k$ tickets uniformly at random and without replacement, but instead of looking at the number of individual tickets that are shared between two samples, I am curious about the number of groups that are shared, which we can denote by $R$. That is, if both samples include tickets from group $i$ but the groups of all the other tickets in sample 1 are different from the groups of all the other tickets in sample 2, then we have $R=1$.

How can I find $\mathbb{P}\left(R=j\right)$? To tell you the truth I'm having trouble even finding $\mathbb{P}\left(R=0\right)$. Also, if this is a well-known probability question, I would appreciate someone giving me the name of it, so that I could learn about it some more on my own. Thanks!

Update:

I've written some basic R code that can be used to simulate this kind of problem and check any analytical results people have:

nGroups <- 3
nPerGroup <- c(4, 2, 5)
tickets <- vector(length = sum(nPerGroup))
curPos <- 1
for(i in 1:nGroups){
    tickets[curPos:(curPos + nPerGroup[i] - 1)] <- rep(i, nPerGroup[i])
    curPos <- curPos + nPerGroup[i]
}


Group.Overlap <- function(tickets, k){
  sample1 <- sample(tickets, size = k)
  sample2 <- sample(tickets, size = k)
  sharedGroups <- intersect(unique(sample1), unique(sample2))
  return(length(sharedGroups))
}
$\endgroup$
0

1 Answer 1

2
$\begingroup$

This is not a standard question because it soon becomes very complicated. For example, with two groups the probability of no overlaps is

$$\Pr(R=0) = 2 \frac{{n_1 \choose k}{n_2 \choose k}}{{n \choose k}^2}.$$

With three groups it becomes

$$\Pr(R=0) = 2 \frac{{n_1 +n_2 \choose k}{n_3 \choose k}+{n_1 +n_3 \choose k}{n_2 \choose k}+{n_2 +n_3 \choose k}{n_1 \choose k} - {n_1 \choose k}{n_2 \choose k}-{n_1 \choose k}{n_3 \choose k}-{n_2 \choose k}{n_3 \choose k}}{{n \choose k}^2}.$$

In your example of 11 tickets in groups of sizes 4, 2 and 5, and with $k=2$ this gives $\Pr(R=0) = \frac{472}{3025}\approx 0.156$. With $k=3$ it gives $\Pr(R=0) = \frac{8}{363}\approx 0.022$.

and you can extend this with the inclusion-exclusion principle for more groups. You can make similar statements for $Pr(R=j)$ but it just gets ugly.

$\endgroup$

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.