A SAMPLE-PATH LARGE DEVIATION PRINCIPLE FOR DYNAMIC ERDO˝S-ReNYI RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Braunsteins, Peter; Den Hollander, Frank; Mandjes, Michel
• 署名单位: University of Amsterdam; Leiden University - Excl LUMC; Leiden University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1892
• 发表日期: 2023
• 页码: 3278-3320
• 关键词: convergent sequences; dense; LIMITS

摘要

We consider a dynamic Erdo ˝s-Renyi random graph on n vertices in which each edge switches on at rate & lambda; and switches off at rate & mu;, indepen-dently of other edges. The focus is on the analysis of the evolution of the associated empirical graphon in the limit as n & RARR; & INFIN;. Our main result is a large deviation principle (LDP) for the sample path of the empirical graphon observed until a fixed time horizon. The rate is (n), the rate function is a spe-2 cific action integral on the space of graphon trajectories. We apply the LDP to identify (i) the most likely path that starting from a constant graphon creates a graphon with an atypically large density of d-regular subgraphs, and (ii) the mostly likely path between two given graphons. It turns out that bifurcations may occur in the solutions of associated variational problems.