Convergence of urn model with repeated binomial draws

45 Views Asked by At

I'm analyzing a simple urn model, defined for $N>1$ an integer. The setup is as follows: we have an urn with $\frac{N}{2}$ white balls and $\frac{N}{2}$ black balls. At each step $k$, we sample $N$ balls with replacement from the urn to observe $a_k$ white balls and $b_k$ black balls, and later replace the entire contents of the urn with new $N$ balls consisting of $a_k$ white balls and $b_k$ black balls. This can be shortly expressed as the system below where we sample repeatedly from a binomial distribution with past dependent parameters: $$ X_0 = \frac{N}{2} \\ X_k \sim \operatorname{Bin}\left(N, \frac{X_{k-1}}{N}\right) $$

Intuitively, the system should quickly converge to $X_K = N$ or $X_K = 0$ with high probability since these are the stable absorbing states. But how can I demonstrate a concentration inequality that shows convergence with high probability? In particular, can I quantify how long we would need to wait until all balls are the same color, in terms of $N$?

Simple applications of martingale concentration bounds doesn't seem to work in this case.