Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1805.10653 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914252236783616 |
|---|---|
| author | Janson, Svante Sen, Subhabrata Spencer, Joel |
| author_facet | Janson, Svante Sen, Subhabrata Spencer, Joel |
| contents | We study an urn process with two urns, initialized with a ball each. Balls are added sequentially, the urn being chosen independently with probability proportional to the $α^{th}$ power $(α>1)$ of the existing number of balls. We study the (rare) event that the urn compositions are balanced after the addition of $2n-2$ new balls. We derive precise asymptotics of the probability of this event by embedding the process in continuous time. Quite surprisingly, a fine control on this probability may be leveraged to derive a lower tail Large Deviation Principle (LDP) for $L = \sum_{i=1}^{n} \frac{S_i^2}{i^2}$, where $\{S_n : n \geq 0\}$ is a simple symmetric random walk started at zero. We provide an alternate proof of the LDP via coupling to Brownian motion, and subsequent derivation of the LDP for a continuous time analogue of $L$. Finally, we turn our attention back to the urn process conditioned to be balanced, and provide a functional limit law describing the trajectory of the urn process. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1805_10653 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Preferential Attachment When Stable Janson, Svante Sen, Subhabrata Spencer, Joel Probability Discrete Mathematics Combinatorics 60F10, 60F17, 60C05 We study an urn process with two urns, initialized with a ball each. Balls are added sequentially, the urn being chosen independently with probability proportional to the $α^{th}$ power $(α>1)$ of the existing number of balls. We study the (rare) event that the urn compositions are balanced after the addition of $2n-2$ new balls. We derive precise asymptotics of the probability of this event by embedding the process in continuous time. Quite surprisingly, a fine control on this probability may be leveraged to derive a lower tail Large Deviation Principle (LDP) for $L = \sum_{i=1}^{n} \frac{S_i^2}{i^2}$, where $\{S_n : n \geq 0\}$ is a simple symmetric random walk started at zero. We provide an alternate proof of the LDP via coupling to Brownian motion, and subsequent derivation of the LDP for a continuous time analogue of $L$. Finally, we turn our attention back to the urn process conditioned to be balanced, and provide a functional limit law describing the trajectory of the urn process. |
| title | Preferential Attachment When Stable |
| topic | Probability Discrete Mathematics Combinatorics 60F10, 60F17, 60C05 |
| url | https://arxiv.org/abs/1805.10653 |