Positive reinforced generalized time-dependent Pólya urns via stochastic approximation

Abstract

Consider a generalized time-dependent Pólya urn process defined as follows. Let $d\in \mathbb{N}$ be the number of urns/colors. At each time $n$, we distribute ${\sigma }_n$ balls randomly to the $d$ urns, proportionally to $f$, where $f$ is a valid reinforcement function. We consider a general class of positive reinforcement functions $\mathcal{R}$ assuming some monotonicity and growth condition. The class $\mathcal{R}$ includes convex functions and the classical case $f(x)=x^{\alpha }$, $\alpha >1$. The novelty of the paper lies in extending stochastic approximation techniques to the $d$-dimensional case and proving that eventually the process will fixate at some random urn and the other urns will not receive any balls any more.

22 pages