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 : \mathbb{N} \to \mathbb{R}_+$ where, at each step of the evolution, a new vertex attaches to an existing vertex $v$ in the current tree with probability proportional to $f$(degree(v)). We explore the effect of a change point in the system; the dynamics are initially driven by a function f until the tree reaches size $τ(n) \in (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 $τ(n) = γn$, and the quick big bang model where $τ(n) = n^γ$, for some $0 < γ< 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 non-parametric estimator for the change point $γ$. 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 associated (time) inhomogeneous continuous time branching process (CTBP). In the course of proving the above results, we develop novel mathematical techniques to analyze both homogeneous and inhomogeneous CTBPs and obtain rates of convergence for functionals of such processes, which are of independent interest.