Finite and Infinite Polya Processes

Abstract

In this thesis we shall consider a generalization on Pólya Processes as
have been described by Chung et al. [7]. Given finitely many bins, containing
an initial configuration of balls, additional balls arrive one at a time. For
each new ball, a new bin is created with probability 푝, or with
probability 1 − 푝 this new ball
shall be placed in an existing bin such that the probability of this ball
ending in a specific bin, is proportional to 푓(푚) where 푚 is the number of
balls currently in that bin and 푓 is some feedback
function. We shall show that for 푝 = 0, which will be
defined as Finite Pólya Processes, the behaviour of the process can be
classified into one of three mutual exclusive regimes: Monopolistic Regime,
Eventual Leadership Regime or Almost-Balanced Regime. This behaviour solely
depends on the convergence of the following sums: Ση≥1 푓(푛)–1 and Ση≥1 푓(푛)-2. We shall explore the limiting distribution of
fractions of balls in bins when 푓(푥) = 푥, which is a
known result for classical multi-coloured Pólya Urn problems.Using a similar
method, we find a limiting distribution for Finite Pólya Processes with general
positive linear feedback functions, which has not previously been researched. We
then consider the case where 푝 >
0,
which are defined as Infinite Pólya Processes and restrict the feedback
function to be of the form 푓(푥) = 푥γ where 훾 ∈ ℝ. We shall show that if 훾 > 1, almost surely one bin will dominate or a new bin
will be created. We shall show that for 훾 = 1 a preferential
attachment scheme arises. We consider 훾 <
1 under
the assumptions that some limits exist and show that the fraction of bins
having 푚 balls shrinks
exponentially as a function of 푚. Finally, we
reflect on our results and discuss interesting future research subjects.