Large deviations for generalized polya urns with general urn functions

Abstract

We consider a generalized two-colorPolya urn (black and withe balls) first introduced by Hill, Lane, Sudderth, where the urn composition evolves as follows: let : [0; 1] ! [0; 1], and denote by xn the fraction of black balls at step n, then at step n + 1 a black ball is added with probability (xn) and a white ball is added with probability 1 􀀀 (xn). We discuss large deviations for a wide class of continuous urn functions. In particular, we prove that this process satis es a Sample-Path Large Deviations principle (SPLDP), also providing a variational representation for the rate function. Then, we derive a variational representation for the limit (s) = limn!1 1 n log P (fnxn = bsncg) ; s 2 [0; 1] ; where nxn is the number of black balls at time n, and use it to give some insight on the shape of (s). Under suitable assumptions on we are able to identify the optimal trajectory. We also find a non-linear Cauchy problem for the cumulant generating function and provide an explicit analysis for some selected examples. In particular, we discuss the linear case, which is strictly related to the so-called Bagchi-Pal urn, giving the exact implicit expression for in therms of the Cumulant Generating Function.