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

<p>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 Cramér-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, Pólya urn theory, moment generating functions and martingales.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Statistics

Year

2014

Author dc:creator

• Gopaladesikan, Mohan

Contributors dc:contributor

• Mark Daniel Ward
• Hosam Mahmoud
• Burgess Davis
• Thomas Sellke
• Frederi Viens

• Computer Sciences
• Mathematics
• Statistics and Probability

Repository record dc:identifier

https://docs.lib.purdue.edu/open_access_dissertations/274

OAI identifier oai:identifier

oai:docs.lib.purdue.edu:open_access_dissertations-1324