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?

  • $\begingroup$ 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}$? $\endgroup$ – Gâteau-Gallois Aug 12 at 19:38
  • $\begingroup$ Btw you implicitey assumed that $t_1$ is the time after the first random allocation, but never specified it. $\endgroup$ – Gâteau-Gallois Aug 12 at 19:41
  • $\begingroup$ @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) ... $\endgroup$ – 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.

  • $\begingroup$ 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 ? $\endgroup$ – Gâteau-Gallois Aug 13 at 8:30
  • $\begingroup$ @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}$). $\endgroup$ – 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}$.


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


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.