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

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.

• 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)? – Brent Kerby Jul 29 '17 at 15:04
• total of $k$ blue balls (between both bags) – Alon Jul 29 '17 at 19:03
• 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. – Alon Jul 29 '17 at 19:19
• @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. – whuber Jul 30 '17 at 2:45
• @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? – Brent Kerby Jul 30 '17 at 2:51

## 1 Answer

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

• 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? – Alon Jul 31 '17 at 7:21
• 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. – Brent Kerby Jul 31 '17 at 14:05