Date of Award

Fall 2014

Degree Type


Degree Name

Doctor of Philosophy (PhD)



First Advisor

Mark Daniel Ward

Second Advisor

Hosam Mahmoud

Committee Chair

Mark Daniel Ward

Committee Co-Chair

Hosam Mahmoud

Committee Member 1

Burgess Davis

Committee Member 2

Thomas Sellke

Committee Member 3

Frederi Viens


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.