Chernoff bounds for branching random walks
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917232982884352 |
|---|---|
| author | Liu, Changqing |
| author_facet | Liu, Changqing |
| contents | Concentration inequalities, which have proved very useful in a variety of fields, provide fairly tight bounds on large deviation probabilities while central limit theorem (CLT) describes the asymptotic distribution around the mean (at the $\sqrt{n}$ scale). Harris (1963) conjectured that for a supercritical branching random walk (BRW) of i.i.d offspring and i.i.d displacements, positions of individuals in $nth$ generation approach to Gaussian distribution -- central limit theorem. This conjecture was later proved by Stam (1966) and Kaplan \& Asmussen (1976). Refinements and extensions followed. However, to the best of our knowledge, there is no corresponding existing work on concentration inequalities for BRWs. In this note, we propose a new definition of BRW, providing a more general framework. Owing to this definition, a Chernoff-type (subgaussian) bound for BRWs follows directly from the Chernoff bound for random walk. The relation between RW (random walk) and BRW is discussed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1604_00056 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Chernoff bounds for branching random walks Liu, Changqing Probability Concentration inequalities, which have proved very useful in a variety of fields, provide fairly tight bounds on large deviation probabilities while central limit theorem (CLT) describes the asymptotic distribution around the mean (at the $\sqrt{n}$ scale). Harris (1963) conjectured that for a supercritical branching random walk (BRW) of i.i.d offspring and i.i.d displacements, positions of individuals in $nth$ generation approach to Gaussian distribution -- central limit theorem. This conjecture was later proved by Stam (1966) and Kaplan \& Asmussen (1976). Refinements and extensions followed. However, to the best of our knowledge, there is no corresponding existing work on concentration inequalities for BRWs. In this note, we propose a new definition of BRW, providing a more general framework. Owing to this definition, a Chernoff-type (subgaussian) bound for BRWs follows directly from the Chernoff bound for random walk. The relation between RW (random walk) and BRW is discussed. |
| title | Chernoff bounds for branching random walks |
| topic | Probability |
| url | https://arxiv.org/abs/1604.00056 |