Mohan Gopaladesikan, PhD Candidate, Center for Science of Information and Department of Statistics, Purdue University

Date:Friday, 14 November 2014

Time:12:30 pm to 2:00 pm.

Venue: UNIV 019

Committee members: Dr. Burgess Davis, Dr. Hosam Mahmoud, Dr. Thomas Sellke, Dr. Frederi Viens and Dr. Mark Daniel Ward.

Title: On the occurrences of motifs in recursive trees, with applications to random structures.

Abstract:
In this dissertation we study three problems related to motifs and recursive trees. In the first problem we consider a collection of uncorrelated motifs and their occurrences on the fringe of random recursive trees. We compute the exact mean and variance of the multivariate random vector of the counts of occurrences of the motifs. We further use the Cramer-Wold device and the contraction method to show an asymptotic convergence in distribution to a multivariate normal random variable with this mean and variance.

The second problem we study is that of the probability that a collection of motifs (of the same size) do not occur on the fringe of recursive trees. Here we use analytic and complex-valued methods to characterize this asymptotic probability. The asymptotics are complemented with human assisted Maple computation. We are able to completely characterize the asymptotic probability for two families of growing motifs.

In the third problem we introduce a new tree model where at each time step a new block (motif) is joined to the tree. This is one of the earlier investigations in the random tree literature where such a model is studied, i.e., in which trees grow from building blocks which are themselves trees. We consider the building blocks to be of the same size and characterize the number of leaves, the depth of insertion, the total path length and the height of such trees. The tools used in this analysis include stochastic recurrences, Polya urn theory, moment generating functions and martingales.