Pólya Urn Schemes with Infinitely Many Colors

Abstract: In this work, we introduce a class of balanced urn schemes with infinitely many colors indexed by ℤd, where the replacement schemes are given by the transition matrices associated with bounded increment random walks. We show that the color of the nth selected ball follows a Gaussian distribution on ℝd after O(log n) centering and O(√log n) scaling irrespective of whether the underlying walk is null recurrent or transient. We also provide finer asymptotic similar to local limit theorems for the expected configuration of the urn. The proofs are based on a novel representation of the color of the nth selected ball as "slowed down" version of the underlying random walk.