Law of large numbers

for urn models

In this short course, we shall consider law of large numbers for urn models with balls of finitely many colours only. In the first half, we shall start with building the model and review the classical results including the cases of Polya urn with replacement matrix being a multiple of an identity matrix, as well as that of an irreducible replacement matrix. We shall see independent proofs of the irreducible case in the second half of this short course under a more generalized adaptive setup, and in the other short course for infinitely many colors.

However, in the first part of this short course, we shall consider replacement matrices which are in between the two extreme cases of Polya urn and irreducible replacement matrices. We shall classify the colors, so that the counts of the colors within a class will have same rate of growth. We shall identify the rates explicitly through an inductive algorithm. Under a further technical condition, we shall also identify the dependence structure of the limits obtained. (This part of the lecture will be based on a series of papers jointly with Arup Bose and Amiter Dasgupta, both from Indian Statistical Institute Kolkata.)

In the later part of the first half of the course, we shall consider a nonstationary setup where the matrices are irreducible but converging to a reducible one in the limit. We shall classify the limits to be that of the irreducible case or the triangular case based on the rate of convergence. (This part of the work is based on ongoing research jointly with Rohan Sarkar, presently with Cornell University. The work began as Master's dissertation of Sarkar at Indian Statistical Institute Kolkata.) The results in the first half of this short course will be proved using martingale techniques.

In the second half of the short course, we shall generalize to adaptive models, where the replacement matrices are allowed to be random, not necessarily balanced (i.e. with all row sums same) and depend on the past history. Such adaptive models appear naturally in clinical trials. The conditional expectations of the replacement matrices will concentrate around a (possibly random) irreducible matrix. We shall review the results and methodology available in literature. Such results obtain central limit type theorems under second moment conditions. However, we shall consider laws of large numbers under more natural first moment conditions using stochastic approximation techniques. We derive new results for convergence in probability for stochastic approximation with random step size. Under first moment and uniform integrability conditions, we obtain $L^1$ convergence. The convergence is improved to almost sure under additional majorization and $L \log L$ conditions. The proofs simplify the existing ones through random step size stochastic approximation resulting in a simpler Lotka-Volterra type differential equation. (This part of the work is based on published and ongoing work jointly with Ujan Gangopadhyay, presently with University of South California. The published work began as Master's project of Gangopadhyay at Indian Statistical Institute Kolkata.) The law of large numbers for urn models with constant and deterministic irreducible replacement matrix can be read off as special case.



Random recursive tree, branching Markov chains
and urn models

In the first part of this mini course, we will show that any branching Markov chain defined on the random recursive tree is nothing but a balanced urn model. This is a novel connection between these two apparently unrelated probabilistic models, namely, a branching Markov chain and a balanced urn models. Exploring the connection further we will derive fairly general scaling limits for balanced urn models with colors indexed by any Polish Space. Thus generalizing the classical urn models defined on finitely many colors to a measure valued process on a general Polish Space.

In the second part of the course, we will use the connection established in the first part, and show that several exiting results on classical finite color urn schemes, as well as, recently introduced infinite color urn schemes, can be derived easily from the general asymptotic. In particular, we will prove that the well known classical result of the finitely many color balanced urn, when the replacement matrix is irreducible will also holds for countably infinite many colors (under certain technical assumptions). We will also discuss the special case, of null recurrent replacement matrices, which can only arise in the context of infinitely many colors. We will further show that the connection can also be used to derive exact asymptotic of the sizes of the connected components of a random recursive forest, which is obtained by removing the root of a random recursive tree.


The mini course will be based on a series of four papers, three of which are joint work with Debleena Thacker and one is a joint work with Debleena Thacker and Svante Jonson