The Power of Choice in a Generalized Polya Urn Model

The Power of Choice in a Generalized Polya Urn Model

Tue, 10/11/2009
16:30 		Gregory Sorkin (IBM Research NY) Combinatorial Theory Seminar Add to calendar SR2
The Power of Choice in a Generalized Polya Urn Model
HTML clipboard We introduce a "Polya choice" urn model combining elements of the well known "power of two choices" model and the "rich get richer" model. From a set of $ k $ urns, randomly choose $ c $ distinct urns with probability proportional to the product of a power $ \gamma>0 $ of their occupancies, and increment one with the smallest occupancy. The model has an interesting phase transition. If $ \gamma \leq 1 $, the urn occupancies are asymptotically equal with probability 1. For $ \gamma>1 $, this still occurs with positive probability, but there is also positive probability that some urns get only finitely many balls while others get infinitely many.