| The theory of infinitely exchangeable random partitions began with the work of Ewens as a model for species sampling in population biology, known as the Ewens sampling formula. Kingman established a correspondence between infinitely exchangeable partitions and probability measures on partitions of the unit interval, called the paintbox representation. Later, Kingman introduced the coalescent, an exchangeable Markov process on the space of set partitions, in the field of population genetics.;In this thesis, we build on Kingman's theory to construct an infinitely exchangeable Markov process on the space of partitions whose sample paths differ from previously studied coalescent and fragmentation type processes; we call this process the cut-and-paste process. The cut-and-paste process possesses many of the same properties as its predecessors, including finite-dimensional transition probabilities that can be expressed in terms of a paintbox process, a unique equilibrium measure under general conditions, a Poissonian construction, and an associated mass-valued process almost surely. A special parametric subfamily is related to the Chinese restaurant process and is reversible with respect to the two-parameter Pitman-Yor family. An extension of the this subfamily has a third parameter which is a symmetric square matrix with non-negative entries, called the similarity matrix .;From a family of partition-valued Markov kernels, we show how to construct a Markov process on the space of rooted fragmentation trees, called the ancestral branching process. If the family of kernels is infinitely exchangeable, then its associated ancestral branching process is infinitely exchangeable. In addition, the ancestral branching process based on the cut-and-paste Markov kernel possesses a unique equilibrium measure, admits a Poissonian construction and has an associated mass fragmentation-valued process almost surely. Furthermore, the results can be extended to characterize a Markov process on the space of trees with edge lengths.;Aside from the Erdos-Renyi process and its variants, infinitely exchangeable graph-valued processes are uncommon in the literature. We show a construction for a family of infinitely exchangeable Poisson random hypergraphs which is induced by a consistent family of Poisson point processes on the power set of the natural numbers. Infinitely exchangeable families of hereditary hypergraphs and undirected graphs are induced from an infinitely exchangeable Poisson random hypergraph by projection.;Finally, we consider balanced and even partition structures, which are families of distributions on partitions with a prespecified block structure. Consistency of these families can be shown under a random deletion procedure. We show Chinese restaurant-type constructions for a special class of these structures based on the two-parameter Pitman-Yor family, and discuss connections to randomization in experimental design. |
