Finite and Infinite Polya Processes

Finite and Infinite Polya Processes

Joyandeh, Arian (TU Delft Electrical Engineering, Mathematics and Computer Science)

Ruszel, Wioletta (mentor)
Söhl, Jakob (graduation committee)
Spandaw, Jeroen (graduation committee)

Delft University of Technology

2019-07-19

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.

Polya Processes
Finite Polya Processes
Infinite Polya Processes

http://resolver.tudelft.nl/uuid:74a05e7f-a717-480a-9bd8-fe73743dcc47

Student theses

bachelor thesis

© 2019 Arian Joyandeh