Scaling limits for exploration algorithms

2015/04/09 by Bermolen, Paola, Jonckheere, Matthieu, Sanders, Jaron
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1504.02438

Abstract

We consider an exploration algorithm where at each step, a random number of items become active while related items get explored. Given an initial number of items N growing to infinity and building on a strong homogeneity assumption, we study using scaling limits of Markovian processes statistical properties of the proportion of active nodes in time. This is a companion paper that rigorously establishes the claims and heuristics presented in [5]. [5] Jaron Sanders, Matthieu Jonckheere, and Servaas Kokkelmans. Sub-Poissonian statistics of jamming limits in Rydberg gases. 2015. To appear.

Related

• Scaling limits for the peeling process on random maps
• Scaling limits in dependent random environments: relating a random walk, a branching process and a spatial branching process
• Scaling limit and ageing for branching random walk in Pareto environment
• Scaling limits of Markov-Branching trees and applications
• Scaling limits of random graphs