Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2407.19027 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909270212083712 |
|---|---|
| author | de Carvalho, Gustavo O. Machado, Fábio P. |
| author_facet | de Carvalho, Gustavo O. Machado, Fábio P. |
| contents | We consider a system of interacting random walks known as the frog model. Let $\mathcal{K}_n=(\mathcal{V}_n,\mathcal{E}_n)$ be the complete graph with $n$ vertices and $o\in\mathcal{V}_n$ be a special vertex called the root. Initially, $1+η_o$ active particles are placed at the root and $η_v$ inactive particles are placed at each other vertex $v\in\mathcal{V}_n\setminus\{o\}$, where $\{η_v\}_{v\in \mathcal{V}_n}$ are i.i.d. random variables. At each instant of time, each active particle may die with probability $1-p$. Every active particle performs a simple random walk on $\mathcal{K}_n$ until the moment it dies, activating all inactive particles it hits along its path. Let $V_\infty(\mathcal{K}_n,p)$ be the total number of visited vertices by some active particle up to the end of the process, after all active particles have died. In this paper, we show that $V_\infty(\mathcal{K}_n,p_n)\geq (1-ε)n$ with high probability for any fixed $ε>0$ whenever $p_n\rightarrow 1$. Furthermore, we establish the critical growth rate of $p_n$ so that all vertices are visited. Specifically, we show that if $p_n=1-\fracα{\log n}$, then $V_\infty(\mathcal{K}_n,p_n)=n$ with high probability whenever $0<α<E(η)$ and $V_\infty(\mathcal{K}_n,p_n)<n$ with high probability whenever $α>E(η)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_19027 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Critical Conditions for the Coverage of Complete Graphs with the Frog Model de Carvalho, Gustavo O. Machado, Fábio P. Probability 60K35, 05C81 We consider a system of interacting random walks known as the frog model. Let $\mathcal{K}_n=(\mathcal{V}_n,\mathcal{E}_n)$ be the complete graph with $n$ vertices and $o\in\mathcal{V}_n$ be a special vertex called the root. Initially, $1+η_o$ active particles are placed at the root and $η_v$ inactive particles are placed at each other vertex $v\in\mathcal{V}_n\setminus\{o\}$, where $\{η_v\}_{v\in \mathcal{V}_n}$ are i.i.d. random variables. At each instant of time, each active particle may die with probability $1-p$. Every active particle performs a simple random walk on $\mathcal{K}_n$ until the moment it dies, activating all inactive particles it hits along its path. Let $V_\infty(\mathcal{K}_n,p)$ be the total number of visited vertices by some active particle up to the end of the process, after all active particles have died. In this paper, we show that $V_\infty(\mathcal{K}_n,p_n)\geq (1-ε)n$ with high probability for any fixed $ε>0$ whenever $p_n\rightarrow 1$. Furthermore, we establish the critical growth rate of $p_n$ so that all vertices are visited. Specifically, we show that if $p_n=1-\fracα{\log n}$, then $V_\infty(\mathcal{K}_n,p_n)=n$ with high probability whenever $0<α<E(η)$ and $V_\infty(\mathcal{K}_n,p_n)<n$ with high probability whenever $α>E(η)$. |
| title | Critical Conditions for the Coverage of Complete Graphs with the Frog Model |
| topic | Probability 60K35, 05C81 |
| url | https://arxiv.org/abs/2407.19027 |