2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mean you continue until you have both pulled at least $k$ blue balls from the first bag and at least $k$ blue balls from the second bag? Or you continue until you have pulled a total of $k$ blue balls (between both bags)? $\endgroup$ – Brent Kerby Jul 29 '17 at 15:04
  • $\begingroup$ total of $k$ blue balls (between both bags) $\endgroup$ – Alon Jul 29 '17 at 19:03
  • 1
    $\begingroup$ It is not a homework. It is something I am doing for my research. The real problem is much more complicated. I made it simpler to isolate just the thing that I am currently stuck on. I am not sure it has a simple answer. However, I hope someone here could help me solve it ,or give me an idea how to progress from here. $\endgroup$ – Alon Jul 29 '17 at 19:19
  • 2
    $\begingroup$ @Brent Thank you for pointing out that edit: it represents a significant (and confusing) modification of the question. In light of that change, my answer no longer applies. $\endgroup$ – whuber Jul 30 '17 at 2:45
  • 1
    $\begingroup$ @whuber, I thought your answer was also interesting and could be useful for comparison (to see how the new condition in the edit affects the results), especially since I referenced your plots in my answer. Might you consider undeleting it? $\endgroup$ – Brent Kerby Jul 30 '17 at 2:51
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you very much for the solution. I am trying to understand the code you wrote. Why did you write p in the prob function just before the end of the function? $\endgroup$ – Alon Jul 31 '17 at 7:21
  • $\begingroup$ That is R's way of returning a value from a function. You can also write return(p), but the return keyword is optional when it's the last expression in a function. $\endgroup$ – Brent Kerby Jul 31 '17 at 14:05

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.