Positive Reinforced Generalized Time-Dependent Pólya Urns via Stochastic Approximation

Consider a generalized time-dependent Pólya urn process defined as follows. Let d∈ N d ∈ N be the number of urns/colors. At each time n , we distribute σ ₙ σ 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 R R assuming some monotonicity and growth condition. The class R R includes convex functions and the classical case f(x)=xα f ( x ) = x α , α >1 α > 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 anymore.