Concentration Inequalities for Branching Random Walks

Abstract

Motivated by phase transition problems in CSPs, we prove a more general concentration inequality that retains classical sub-Gaussian tails under a mild global linear-growth condition $|S_n|<Cn$, relaxing the bounded-increment assumption to finite exponential moments and requiring neither independence nor the martingale property. We further extend it to branching random walks (BRWs), obtaining the first concentration inequality for BRWs.

Corrected errors and revised title and abstract. 31 pages. 1 figure