Exchanging balls in two urns

76 Views Asked by At

Consider two urns. First urn has initially $N$ white balls and second urn has initially $N$ black balls. In each step we draw one of the balls from the first urn and one of the balls from the second urn and exchange them.

Denote by $X_k$ the number of black balls in the first urn after $k$ draws.

The goal is to calculate $p(m)=\lim_{k\to\infty}P(X_k=m)$

I derived this recursive formula:

$$P(X_k=m)=\frac{2m(N-m)}{N^2}P(X_{k-1}=m)+\frac{(N-m+1)^2}{N^2}P(X_{k-1}=m-1)+\frac{(m+1)^2}{N^2}P(X_{k-1}=m+1)$$

Now take the limit $k\to\infty$. I got

$$p(m)=\frac{2m(N-m)}{N^2}p(m)+\frac{(N-m+1)^2}{N^2}p(m-1)+\frac{(m+1)^2}{N^2}p(m+1)$$

Which is equivalent to

$$p(m)(1-\frac{2m(N-m)}{N^2})=\frac{(N-m+1)^2}{N^2}p(m-1)+\frac{(m+1)^2}{N^2}p(m+1)$$

At this point I got stuck. This is recursive equation with non-constant coefficients, hence the solution is not trivial. Please help.

1

There are 1 best solutions below

4
On

The point here is to derive a formula for $p(0)$ which looks little different (does not depend on $p(-1)$). From this formula I can express $p(1)$ as a function of $p(0)$. Then using the recursive eqn I can express $p(2)$ as a function of $p(0)$ and $p(1)$, hence $p(2)$ depends only on $p(0)$. Continuing this procedure I have found that $$p(m)=p(0){N \choose m}^2$$.

Now it is obvious how to calculate $p(0)$.