What is the repetition distribution of Pulling balls out of two bags?

Question

I have two bags each with $m$ balls.

In the first bag I have $n_1$ blue balls.

In the second bag I have $n_2$ blue balls.

The target is to pull out a total of k blue balls from both bags ($m>n_1>n_2>k$).

I pull out one ball from the first bag and then one ball from the second bag, and so on. Once I pull out a ball I don't put it back.

All the balls have numbers on them, 1..m in each bag. If I pull two blue balls with the same number it counts only once for the k total blue balls I have to pull.

I want to find out the distribution of the number of times I need to pull a ball ( as a function of m,n,k ).

I have a solution for the case of one bag here.

Answer 1

This problem can be solved by considering a time-inhomogeneous Markov chain. Let $t$ represent the time at which $t$ balls have been drawn, and define

\begin{align*} X_t &= \text{number of distinct labels of blue balls drawn so far (i.e. by time $t$)}\\ Y_t &= \text{number of blue balls in first bag with labels not already drawn}\\ Z_t &= \text{number of blue balls in second bag with labels not already drawn}\\ \end{align*} The initial state is $(X_0, Y_0, Z_0) = (0, n_1, n_2)$. We need to consider the transition probabilities at time $t$.

For even $t$, say $t=2s$, the next draw will be from the first bag. At this time, the first bag has $Y_t$ blue balls and $m-s$ total balls, so with probability $Y_t/(m-s)$ a blue ball will be drawn with a label not previously drawn. In this case, under the random labeling assumption, with probability $Z_t/(m-X_t)$ the label will match one of the blue balls in the second bag. So we can describe the transition probabilities for even $t$ as follows: \begin{align*} &P((X_{t+1}, Y_{t+1}, Z_{t+1}) = (x, y, z) \ |\ (X_{t}, Y_{t}, Z_{t}) = (x, y, z)) \\ &\quad= 1-\frac{Y_{t}}{m-s}\\ \\ &P((X_{t+1}, Y_{t+1}, Z_{t+1}) = (x+1, y-1, z) \ |\ (X_{t}, Y_{t}, Z_{t}) = (x, y, z)) \\ &\quad= \frac{Y_{t}}{m-s}\left(1-\frac{Z_{t}}{m-X_{t}}\right)\\ \\ &P((X_{t+1}, Y_{t+1}, Z_{t+1}) = (x+1, y-1, z-1) \ |\ (X_{t}, Y_{t}, Z_{t}) = (x, y, z)) \\ &\quad= \frac{Y_{t}}{m-s}\frac{Z_{t}}{m-X_{t}} \end{align*} For odd $t$, say $t=2s-1$, the next draw will be from the second bag, and we similarly have \begin{align*} &P((X_{t+1}, Y_{t+1}, Z_{t+1}) = (x, y, z) \ |\ (X_{t}, Y_{t}, Z_{t}) = (x, y, z)) \\ &\quad = 1-\frac{Z_{t}}{m-s}\\ \\ &P((X_{t+1}, Y_{t+1}, Z_{t+1}) = (x+1, y, z-1) \ |\ (X_{t}, Y_{t}, Z_{t}) = (x, y, z)) \\ &\quad = \frac{Z_{t}}{m-s}\left(1-\frac{Y_{t}}{m-X_{t}}\right)\\ \\ &P((X_{t+1}, Y_{t+1}, Z_{t+1}) = (x+1, y-1, z-1) \ |\ (X_{t}, Y_{t}, Z_{t}) = (x, y, z)) \\ &\quad = \frac{Z_{t}}{m-s}\frac{Y_{t}}{m-X_{t}} \end{align*} In this way, beginning with $t=0$ the pmf of $(X_{t+1}, Y_{t+1}, Z_{t+1})$ can be computed in terms of the pmf of $(X_t, Y_t, Z_t)$. Summing up over all possible values of $Y_t$ and $Z_t$, we obtain the (marginal) pmf of $X_t$. If we let $J$ denote the required number of draws, then $P(J \leq t) = P(X_t \geq k)$, so we may find the pmf of $J$ using the pmf of $X_t$. Here is some (not particularly efficient) R code for carrying this out:

prob = function(m, n1, n2){
  p = array(0, dim = c(2*m+1, n1+n2+1, n1+1, n2+1))
  p[1, 1, n1+1, n2+1] = 1
  for(i in 0:(2*m-1)){
    for(x in 0:(n1+n2)){
      for(y in 0:n1){
        for(z in 0:n2){
          if(i%%2 == 0){
            s = i/2
            q = p[i+1, x+1, y+1, z+1]
            if(q>0){
              p[i+2, x+1, y+1, z+1] = p[i+2, x+1, y+1, z+1] + q * (1 - y/(m-s))
              if(y>0){
                p[i+2, x+2, y, z+1] = p[i+2, x+2, y, z+1] + q * y/(m-s) * (1 - z/(m-x))
                p[i+2, x+2, y, z] = p[i+2, x+2, y, z] + q * y/(m-s) * z/(m-x)
              }
            }
          }else{
            s = (i-1)/2
            q = p[i+1, x+1, y+1, z+1]
            if(q>0){
              p[i+2, x+1, y+1, z+1] = p[i+2, x+1, y+1, z+1] + q * (1 - z/(m-s))
              if(z>0){
                p[i+2, x+2, y+1, z] = p[i+2, x+2, y+1, z] + q * z/(m-s) * (1 - y/(m-x))
                p[i+2, x+2, y, z] = p[i+2, x+2, y, z] + q * z/(m-s) * y/(m-x)
              }
            }
          }
        }
      }
    }
  } 
  p
}

pmf_J = function(m, n1, n2, k){
  p = prob(m, n1, n2)
  cdf = numeric(2*m+1)
  for(i in 0:(2*m)){
    cdf[i+1] = sum(p[i+1, k:(n1+n2)+1,,])
  }
  diff(cdf)
}

And here are some example plots, using the same parameter combinations as in whuber's answer:

params = expand.grid(k = c(4, 12, 20), n1 = c(12, 19, 23), m = 50)
params$n2 = 24 - params$n1
png("charts.png", width=750, height=750)
par(mfrow = c(3,3), cex = 0.9)
for(i in 1:nrow(params)){
  pa = params[i,]
  pmf = pmf_J(pa$m, pa$n1, pa$n2, pa$k)
  print(sum(pmf))
  plot(1:(2*pa$m), pmf,
       xlab = "j",
       ylab = "Probability",
       main = paste0("m=",pa$m,", n1=",pa$n1,", n2=",pa$n2,", k=",pa$k)) 
}
dev.off()

For parameter choices where at least one of $n_1$, $n_2$, or $k$ is small compared to $m$, there is little impact from the condition that a blue ball with a repeated label does not count, and so the plots agree fairly closely in these cases. The starkest difference can be seen in the upper-right chart ($n_1= n_2 = 12$, $k=20$). Here $k$ exceeds $\max\{n_1, n_2\}$ (contrary to the assumption in the question), which means that there is positive probability that all balls in both bags will be exhausted without $k$ distinctly labeled blue balls being drawn; in this case, we could set $J = \infty$, but the chart only shows the probabilities for finite $J$.