# Probability for drawing different balls from 2 urns under constant exchange of balls

Consider 2 urns (or bags), $$U_1$$ and $$U_2$$ with $$n_1$$ and $$n_2$$ balls. The balls can have $$k$$ different colors and we know the initial distribution of balls in both urns. Thus, we can calculate $$P_1 = 1 - \sum_{i=1}^k p_{1i}^2,$$ $$P_2 = 1 - \sum_{i=1}^k p_{2i}^2,$$ and $$P_3 = 1 - \sum_{i=1}^k p_{1i} p_{2i}$$ (with $$p_{1i}$$ and $$p_{2i}$$ as relative frequencies of balls with color $$i$$ in $$U_1$$ and $$U_2$$). $$P_1$$ and $$P_2$$ represent the probability for drawing randomly 2 different-colored balls from $$U_1$$ and $$U_2$$. $$P_3$$ is the probability for getting 2 different-colored balls after drawing 1 ball from each urn.

Now we randomly take a proportion of $$m_{12}$$ balls from $$U_1$$ and put it into $$U_2$$ and do the same (simultaneously) vice versa with $$m_{21}$$ balls from $$U_2$$.

What I'm interested in now is how $$P_3$$ changes after each round of random allocation.

Here are my thoughts ... We can calculate $$P_1^{t_1}$$ (and similar $$P_2^{t_1}$$),

$$P_1^{t_1} = \frac {\big( 1 - m_{12} \big)^2 P_1^{t_0} + 2 \big( 1 - m_{12} \big)m_{21}P_3^{t_0} + m_{21}^2 P_2^{t_0}}{\big( \big( 1 - m_{12} \big) + m_{21} \big)^2},$$ The superscripts $$^{t_1}$$ refer to the probabilities after 1 exchange of balls and thus refer to the system state that follows $$^{t_0}$$. It is obvious that $$P_1^{t_\infty}$$ and $$P_2^{t_\infty}$$ converges towards a common limit $$x$$ and that $$P_3^{t_\infty}$$ will converge towards $$x$$, too.

But which formula does the decay of $$P_3$$ follow? And how can $$x$$ be calculated?

• My intuition (but this needs some careful thinking) is that for $m_{12}$ and $m_{21}$ positive, after a sufficiently long time each ball is in each urn with probability $1/2$ and thus computing $P_3$ simply becomes computing the probability that considering all balls together, you don't pick the same colour twice. If this is true the easiest way to obtain this is probably through a coupling, and this will provide an upper bound for the convergence rate of $P_3$ in the right metric. Can you detail a bit how you obtained the formula for $P_1^{t_1}$? – Gâteau-Gallois Aug 12 at 19:38
• Btw you implicitey assumed that $t_1$ is the time after the first random allocation, but never specified it. – Gâteau-Gallois Aug 12 at 19:41
• @Gâteau-Gallois since there's too few space to completely reply to your question, I added an answer (which shouldn't be understood as an answer to my question) ... – Anti Aug 12 at 20:15

Gallois, thanks a lot for your reply. I think it could be thought that way. And: Thanks a lot for you hint with $$t_1$$ and $$t_0$$. I edited my post.

So, how did I came up with $$P_1^{t_1}$$? I remove $$m_{12} \times n_1$$ balls from $$U_1$$ and thus $$\big( 1 - m_{12} \big)$$ balls remain in the urn. The probability for drawing 2 different balls from $$U_1$$ remains $$P_1^{t_2}$$. However, $$U_1$$ receives $$m_{21} \times n_2$$ balls from $$U_2$$. If I put the balls from $$U_2$$ into the bag with the remaining balls from $$U_1$$ and draw randomly 2 balls, they can be either:

1. both originally (at $$t_0$$) from $$U_1$$ (see above),
2. both brought from $$U_2$$ in the last exchange round or
3. 1 could have been previously in $$U_1$$ and 1 could have been previously in $$U_2$$

Since we know the proportions for all 3 occurences as well as the probabilites of drawing different colors in all 3 scenaria, we can just calculate an expected values for $$P_1^{t_1}$$ by applying a formula for weighted averages (at least that's what I've thought).

That's the whole idea behind my question: I want to calculate the changes in $$P_1$$ and $$P_2$$ for given $$m_{12}$$ and $$m_{21}$$ without knowing the values of $$p_{1i}$$ and $$p_{2i}$$. And it seems to be only possible to calculate that changes with the introduction of $$P_3$$.

BTW - I just see that I also assumed $$n_1 = n_2$$ in the formula (see question) of my original post, so that I haven't added the population sizes to it.

• Ok thanks for the details, I think your computation is valid. What is your precise question now ? You want to compute $P_3^{\infty}$ to obtain both $P_1^{\infty}$ and $P_2^{\infty}$ ? With the decay rate as well ? – Gâteau-Gallois Aug 13 at 8:30
• @Gâteau-Gallois I'm especially looking for a formula to calculate $P_3^{t_1}$ using the available measures ($P_1^{t_0}$, $P_1^{t_1}$, $P_2^{t_0}$, $P_2^{t_1}$ and $P_3^{t_0}$). However, I guess that this formula should contain a term giving the limit $x$ (my idea was to first derive $x$ and thus maybe come up more easily with the remainding formula for $P_3^{t_1}$). – Anti Aug 13 at 9:23

I think I found an answer to my own question yesterday before I fell asleep ...

This is how the two urns look after 1 exchange of balls:

The 2 urns after 1 exchange of balls

Now let's first define

• $$\alpha:=m_{12} \times n_1^{t_0}$$
• $$\beta:=m_{21} \times n_2^{t_0}$$
• $$\gamma:= \big( 1 - m_{12} \big) \times n_1^{t_0}$$
• $$\delta:= \big( 1 - m_{21} \big) \times n_2^{t_0}$$

If we draw 2 balls randomly from both urns at $$t_1$$ we would get balls from

• $$U_1^{t_0}$$ and $$U_2^{t_0}$$ with a probability of $$\frac {\gamma}{\beta + \gamma} \times \frac {\delta}{\alpha + \delta}$$ which represents the measure $$P_3^{t_0}$$.
• $$U_2^{t_0}$$ and $$U_2^{t_0}$$ with a probability of $$\frac {\beta}{\beta + \gamma} \times \frac {\delta}{\alpha + \delta}$$ which represents the measure $$P_2^{t_0}$$.
• $$U_1^{t_0}$$ and $$U_1^{t_0}$$ with a probability of $$\frac {\gamma}{\beta + \gamma} \times \frac {\alpha}{\alpha + \delta}$$ which represents the measure $$P_1^{t_0}$$.
• $$U_2^{t_0}$$ and $$U_1^{t_0}$$ with a probability of $$\frac {\beta}{\beta + \gamma} \times \frac {\alpha}{\alpha + \delta}$$ which represents the measure $$P_3^{t_0}$$.

Thus:

$$P_3^{t_1} = \frac {\gamma}{\beta + \gamma} \times \frac {\delta}{\alpha + \delta} \times P_3^{t_0} + \\ + \frac {\beta}{\beta + \gamma} \times \frac {\delta}{\alpha + \delta} \times P_2^{t_0} + \\ + \frac {\gamma}{\beta + \gamma} \times \frac {\alpha}{\alpha + \delta} \times P_1^{t_0} + \\ + \frac {\beta}{\beta + \gamma} \times \frac {\alpha}{\alpha + \delta} \times P_3^{t_0}$$

Does it sound logical?