Generalized Polya Urns

Abstract

Random processes with reinforcement have been studied mathematically since the beginning of the twentieth century. Such processes have deep connections to business problems such as design of medical trials, neural networks and formation of networks such as the Internet and Social Networks. One of the most simple and elegant of these models is known as Pólya’s urn: starting with one black and one red ball in an urn, select a ball at random from the urn, replace it in addition to another ball of the same colour. The interest is to study the proportion of black balls Xt in the urn after t balls have been added. In the last hundred years or so, various generalizations have been studied (see, e.g., [1],[2]). One direction of generalization of Pólya’s urns is to modify the selection probability (see, e.g., [3]). A further generalization involves having multiple interacting urns, where colours may be present in more than one urn and where multiple balls may be added to one or more urns depending on what colour is selected (see, e.g., [4], [5], [6]).