Limits of (randomly) growing Schröder trees and exchangeability
We consider finite rooted ordered trees in which every internal node has at least two children, sometimes called Schröder trees; the size |t| of such a tree t is the number of its leaves. An important concept with trees is that of inducing subtrees. Given a tree t of size k and a larger tree t’ of size n\geq k we define 0 \leq \theta(t,t’)\leq 1 to be the probability of obtaining t as a randomly induced subtree of size k in t’. One can think of \theta(t,t’) to be the density of the pattern t in t’. In this talk we consider two closely related questions concerning the nature of \theta:
1. A sequences of trees (t_n)_n with |t_n|\rightarrow\infty is called \theta-convergent, if \theta(t,t_n) converges for every fixed tree t. The limit of (t_n)_n is the function t\mapsto \lim_n\theta(t,t_n). What limits exist?
2. A Markov chain (X_n)_n with X_n being a random tree of size n is called a \theta-chain if P(X_k=t|X_n=t’)=\theta(t,t’) for all k \leq n. What \theta-chains exist?
Similar questions have been treated for many different types of discrete structures (words, permutations, graphs \dots); binary Schröder trees (Catalan trees) are considered in [1]. We present a De Finetti-type representation for \theta-chains and a homeomorphic description of limits of \theta-convergent sequences involving certain tree-like compact subsets of the square [0,1]^2. Questions and results are closely linked to the study of exchangeable hierarchies, see [2].
[1] Evans, Grübel and Wakolbinger. “Doob-Martin boundary of Rémy’s tree growth chain”. The Annals of Probability, 2017.
[2] Forman, Haulk and Pitman. “A representation of exchangeable hierarchies by sampling from random real trees”. Prob.Theory and related Fields, 2017.
[3] Gerstenberg. “Exchangeable interval hypergraphs and limits of ordered discrete structures”. arXiv, 2018.
Date:
8 October 2018, 12:00 (Monday, 1st week, Michaelmas 2018)
Venue:
Mathematical Institute, Woodstock Road OX2 6GG
Venue Details:
L4
Speaker:
Julian Gerstenberg (Leibniz Universität Hannover)
Organising department:
Department of Statistics
Organisers:
Christina Goldschmidt (Department of Statistics, University of Oxford),
James Martin (Department of Statistics, University of Oxford)
Part of:
Probability seminar
Booking required?:
Not required
Audience:
Public
Editor:
Christina Goldschmidt
