FLUCTUATION BOUNDS FOR CONTINUOUS TIME BRANCHING PROCESSES AND EVOLUTION OF GROWING TREES WITH A CHANGE POINT

We consider dynamic random trees constructed using an attachment function f : N & RARR; R+ where, at each step of the evolution, a new vertex attaches to an existing vertex v in the current tree with probability propor-tional to f (degree(v)). We explore the effect of a change point in the sys-tem; the dynamics are initially driven by a function f until the tree reaches size & tau;(n) & ISIN; (0, n), at which point the attachment function switches to another function, g, until the tree reaches size n. Two change point time scales are considered, namely the standard model where & tau;(n) = & gamma; n, and the quick big bang model where & tau;(n) = n & gamma;, for some 0 < & gamma; < 1. In the former case, we obtain deterministic approximations for the evolution of the empirical degree distribution (EDF) in sup-norm and use these to devise a provably consistent nonparametric estimator for the change point & gamma; . In the latter case, we show that the effect of pre-change point dynamics asymptotically vanishes in the EDF, although this effect persists in functionals such as the maximal degree. Our proofs rely on embedding the discrete time tree dynamics in an associ-ated (time) inhomogeneous continuous time branching process (CTBP). In the course of proving the above results, we develop novel mathematical tech-niques to analyze both homogeneous and inhomogeneous CTBPs and obtain rates of convergence for functionals of such processes, which are of indepen-dent interest.

Automated summary

This study considers dynamic random trees constructed using an attachment function f: N → R+, where a new vertex attaches to an existing vertex in the current tree with probability proportional to the degree of the existing vertex. The effect of a change point in the system is explored, where the attachment function switches from f to another function g at a certain tree size. The study provides deterministic approximations for the evolution of the empirical degree distribution and develops mathematical techniques to analyze both homogeneous and inhomogeneous continuous time branching processes.