We prove general limit theorems for sums of functions subtrees (random) binary search trees and random recursive trees. The proofs use a new version representation by Devroye, Stein's method both normal Poisson approximation together with certain couplings. As consequence, we give simple the fact that number fringe size $ k=k_n in tree or (of total n $) has an asymptotical distribution if k\rightarrow\infty $, is asymptotically k=o(\sqrt{n}) $. Furthermore, similar results k some required...

This survey studies asymptotics of random fringe trees and extended in that can be constructed as family a Crump–Mode–Jagers branching process, stopped at suitable time. includes recursive trees, preferential attachment fragmentation binary search (more generally) $m$-ary well some other classes trees. We begin with general results, mainly due to Aldous (1991) Jagers Nerman (1984). The results are applied for several particular types where the theory is developed detail. In particular, we...

We study the number of random records in a binary search tree with n vertices (or equivalently, cuttings required to eliminate tree). show that classical limit theorem for convergence sums triangular arrays infinitely divisible distributions can be used determine distribution this number. The asymptotic (normalized) or cuts is found weakly 1-stable.

Bootstrap percolation is a type of cellular automaton which has been used to model various physical phenomena, such as ferromagnetism. For each natural number $r$, the $r$-neighbour bootstrap process an update rule for vertices graph in one two states: `infected' or `healthy'. In consecutive rounds, healthy vertex with at least $r$ infected neighbours becomes itself infected. Percolation said occur if every eventually Usually, starting set chosen random, all initially independently...

We provide simplified proofs for the asymptotic distribution of number cuts required to cut down a Galton–Watson tree with critical, finite-variance offspring distribution, conditioned have total progeny $n$. Our proof is based on coupling which yields precise, nonasymptotic distributional result case uniformly random rooted labeled trees (or, equivalently, Poisson their size). approach also provides new, reversible transformation between Brownian excursion and bridge.

In this paper we study the number of random records in an arbitrary split tree (or, equivalently, cuttings required to eliminate tree). We show that a classical limit theorem for convergence sums triangular arrays infinitely divisible distributions can be used determine distribution number. After normalization are shown asymptotically weakly 1-stable. This work is generalization our earlier results binary search Holmgren (2010), which one specific case trees. Other important examples trees...

We consider the model of random trees introduced by Devroye [SIAM J. Comput. 28 (1999) 409–432]. The encompasses many important randomized algorithms and data structures. pieces (items) are stored in a fashion nodes tree. total path length (sum depths items) is natural measure efficiency algorithm/data structure. Using renewal theory, we prove convergence distribution toward characterized uniquely fixed point equation. Our result covers, using unified approach, structures such as binary...

In recent decades, analyses of hospitals evacuations have generated valuable knowledge. Unfortunately, these evacuation case studies often lack crucial details and policies that would be helpful in preparedness. The aim this study was to use a simulation model illustrate how it can aid emergency planners the development, testing, revising plans. This includes exercises at two Region Stockholm, Sweden.A scientifically validated system for "table top" used interactive training hospital medical...

Let $r\in\mathbb{N}$. In $r$-neighbour bootstrap percolation on the vertex set of a graph $G$, vertices are initially infected independently with some probability $p$. At each time step, expands by infecting all uninfected that have at least $r$ neighbours. When $p$ is close to 1, we study distribution which become infected. Given $t=t(n)=o(\log n/\log\log n)$, prove sharp threshold result for occurs $t$ in $d$-neighbour $d$-dimensional discrete torus $\mathbb{T}_{n}^{d}$. Moreover, show...

We prove limit theorems for sums of functions subtrees binary search trees and random recursive trees. In particular, we give simple new proofs the fact that number fringe size $ k=k_n in tree (of total n $) asymptotically has a Poisson distribution if k\rightarrow\infty $, is normal k=o(\sqrt{n}) $. Furthermore, similar results k with some required property P example copies certain fixed subtree T Using Cramér-Wold device, show also these numbers different converge jointly to multivariate...

We study protected nodes in $m-$ary search trees, by putting them context of generalized Pólya urns. show that the number two-protected (the are neither leaves nor parents leaves) a random ternary tree is asymptotically normal. The methods apply principle to trees with larger $m$ as well, although size matrices used calculations grow rapidly $m$; we conjecture method yields an normal distribution for all $m \leq 26$. one-protected nodes, and their complement, i.e., leaves, easier analyze. By...

We investigate characteristics of random split trees introduced by Devroye [SIAM J Comput 28, 409-432, 1998]; include e.g., binary search trees, $m$-ary quadtrees, median $(2k+1)$-trees, simplex tries and digital trees. More precisely: use renewal theory in the studies this to prove several results about A tree cardinality n is constructed distributing balls (which often represent data) a subset nodes an infinite tree. One our main relation between deterministic number N. In 1998] there...

We study fringe subtrees of random $m$-ary search trees and preferential attachment trees, by putting them in the context generalised Pólya urns. In particular we show that for with $ m\leq 26 linear number are isomorphic to an arbitrary fixed tree T converges a normal distribution; more generally, also prove multivariate distribution results vectors such numbers different subtrees. Furthermore, protected nodes $m\leq 26$ has asymptotically distribution.

Nous considérons les boucles et arêtes multiples dans le modèle de configuration lorsque la taille du graphe tend vers l'infini. L'intérêt ces variables aléatoires est dû au fait que configuration, conditionné à simplicité, un aléatoire uniforme avec des degrés prescrits. La simplicité correspond l'absence multiples. montrons nombre converge en loi deux indépendantes qui suivent lois Poisson moment d'ordre 2 empirique converge. fournissons aussi estimations distances variation totale entre...

Emergency department charge nurses are expected to oversee the quality of patient care, direct work, and allocation resources. The nurse is unit's frontline leader, he/she must have proper leadership training support carry out duties effectively. This study explores how perceive their role in managing daily work major incidents at emergency department.A qualitative based on focus group discussions using a semi-structured interview. Participants were 12 from four Swedish departments.For data...

We define the (random) $k$-cut number of a rooted graph to model difficulty destruction resilient network. The process is as cut Meir and Moon [21] except now node must be $k$ times before it destroyed. first order terms expectation variance $\mathcal{X} _{n}$, path length $n$, are proved. also show that after rescaling, converges in distribution limit $\mathcal{B} _{k}$, which has complicated representation. paper then briefly discusses some trees general graphs. conclude by analytic...

We study the number of random records in an arbitrary split tree (or equivalently, cuttings required to eliminate tree). show that a classical limit theorem for convergence sums triangular arrays infinitely divisible distributions can be used determine distribution this number. After normalization are shown asymptotically weakly 1-stable. This work is generalization our earlier results binary search tree, which one specific case trees. Other important examples trees include $m$-ary trees,...

Majority bootstrap percolation on a graph $G$ is an epidemic process defined in the following manner. Firstly, initially infected set of vertices selected. Then step by that have at least half its neighbours become infected. We say occurs if eventually all infected.In this paper we provide sharp bounds for critical size majority Erdős-Rényi random $G(n,p)$. This answers open question Janson, Luczak, Turova and Vallier (2012). Our results obtained $p=c\log(n)/n$ are close to Balogh, Bollobás...

In our previous work, we introduced the random $k$-cut number for rooted graphs. this paper, show that distribution of in complete binary trees size $n$, after rescaling, is asymptotically a periodic function $\lg n - \lg n$. Thus there are different limit distributions subsequences, where these limits similar to weakly 1-stable distributions. This generalizes result case $k = 1$, i.e., traditional cutting model, by Janson.

We consider two types of random networks grown in blocks. Hooking are from a set graphs as blocks, each with labelled vertex called hook. At step the growth network, latch is chosen hooking network and copy one blocks attached by fusing its hook latch. Bipolar directed single source sink. an arc replaced Using P\'olya urns, we prove normal limit laws for degree distributions both networks. extend previous results allowing more than block studying arbitrarily large degrees.