Convergence of random increment of two bins

Question

If bins A and B are initialized to 1, and then I continually increment one of them by 1 with a probability proportional to their values, would A/B ever converge?

To demonstrate

A=1 B=1 , select A or B with 50-50 -> A chosen
A=2 B=1 , select A or B with 66-33 -> A chosen
A=3 B=1 , etc

For A=1 and B=1 it seems to diverge most of the time. But if I start from larger numbers A=100 B=100 it seems that it will converge to 50-50 after many iterations. And If I start from A=100 B=200 it would converge to 33-66 etc. So the initial value is important.

What is the mathematical explanation for this behavior? Maybe the initial value is a function of the increment (1 in this case) in some way to be able to ensure convergence.

Answer 1

The problem can be formulated as a special random walk.

Let $X_n$ ($n\ge 1)$ be a set of Bernoulli variables, taking values on $\{1,-1\}$, and let $Y_n=\sum_{i=1}^n X_n$ be our random walk. Making the event $X_n=1$ correspond to incrementing $A_n$, we have:

$$ (A_n-A_0)-(B_n-B_0) = Y_n$$ $$ (A_n-A_0)+(B_n-B_0) = n$$

Hence $A_n = A_0 + (Y_n+n)/2$ and $A_n + B_n = n+A_0+B_0$

Then

$$p_n= P(X_n=1) = \frac{A_{n-1}}{A_{n-1}+B_{n-1}} = \frac{1}{2}\frac{Y_{n-1}+n-1+2A_0}{n-1+A_0+B_0}$$

Letting $\mu_n=E(X_n)$, conditioning on the past, and applying the tower expectation, we get (I spare the details) :

$$ \mu_n= \frac{\alpha +\sum_{i=1}^{n-1}\mu_i}{\beta +n} $$

where $\alpha=A_0-B_0$ and $\beta = A_0+B_0-1$. This has the constant solution: $\mu_n = \frac{\alpha}{\beta+1}=\frac{A_0-B_0}{A_0+B_0}$. Therefore

$$E(Y_n)=n \frac{A_0-B_0}{A_0+B_0}$$

and hence $A_n$ grows (in average) as $A_0 + n (\frac{A_0-B_0}{A_0+B_0}+\frac{1}{2})$

What remains is to compute the variance of $Y_n$, which requires to compute the correlations $E(X_n X_m)$. As a starting point, note that $\sigma_X^2=4 A_0 B_0 /(A_0+B_0)^2$. If $X_n$ were indepdent, $\sigma_Y^2= n \sigma_X^2$ . Because they have positive correlation, one would expect the variance to be larger - but not larger than $n^2 \sigma_X^2$.

Update: A straightforward but tedious computation [*] gives me: $$r=E(X_n X_m) = \frac{s+d^2}{ s(s+1)} \hskip{1cm} n\ne m, \;s=A_0+B_0, \; d=A_0-B_0$$

Then $E(Y_n^2)=n+n(n-1) r$ ; and, because $E(Y_n)=n d/s$ then

$$ {\rm{Var}}(Y_n)=n\frac{s^2-d^2}{s(s+1)}\left(\frac{n}{s} +1\right) \approx n^2 \frac{s^2-d^2}{s^2(s+1)}$$

Going back to $A_n$, we see that its mean grows as

$$\overline{A_n} \approx n \left(\frac{1}{2}+\frac{d}{s}\right)$$

and the variance as

$$ {\rm Var}(A_n) \approx n^2 \frac{s^2-d^2}{4 s^2(s+1)}$$

In particular, $A_0=B_0=1$ ($d=0$, $s=2$) we have

$$\overline{A_n} =1+\frac{n}{2} \hskip{1cm} {\rm Var}(A_n) \approx n^2 \frac{1}{12}$$

If instead $A_0=B_0=100$

$$\overline{A_n} =100+\frac{n}{2} \hskip{1cm} {\rm Var}(A_n) \approx n^2 \frac{1}{804}$$

That is, the behaviour is basically the same in the mean, but the variance is smaller.

[*] I've checked my results against simulations, they seem to agree. BTW, I confess I was surprised to find that both the mean and the correlation of $X_n$ are constants, perhaps I'm missing some basic insight and some simpler solution.

Answer 2

What you are seeing is called the Law of large numbers.

The greater the number of random choices you make the more closely the numbers will converge to their probabilities.

As this is a Binomial distribution and therefore has a finite first moment (mean) then it satisfies the criteria for strong convergence.

So for a probability of selecting $A$ of $p_a$ and an initial value of $A_0$ and $B_0$, after $n$ trials you will almost surely converge to:

$$A_n=np_a+A_0$$ $$B_n=n(1-p_a)+B_0$$

And, because we know the structure of Binomial distribution very well we can go further and state that they will have a mean of $np_a+A_0$ and $n(1-p_a)+B_0$ respectively with a variance of $np_a(1-p_a)$.

Now, for sufficiently large $n$, $A_0$ and $B_0$ are insignificant. So the initial values are irrelevant. How irrelevant you can quantify from the variance.