## Date of Award

Fall 2014

## Degree Type

Dissertation

## Degree Name

Doctor of Philosophy (PhD)

## Department

Statistics

## 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

## 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 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.

## Recommended Citation

Gopaladesikan, Mohan, "On the occurrences of motifs in recursive trees, with applications to random structures" (2014). *Open Access Dissertations*. 274.

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