Covering a graph with independent walks
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915583637848064 |
|---|---|
| author | Hermon, Jonathan Sousi, Perla |
| author_facet | Hermon, Jonathan Sousi, Perla |
| contents | Let $P$ be an irreducible and reversible transition matrix on a finite state space $V$ with invariant distribution $π$. We let $k$ chains start by choosing independent locations distributed according to $π$ and then they evolve independently according to $P$. Let $τ_{\mathrm{cov}}(k)$ be the first time that every vertex of $V$ has been visited at least once by at least one chain and let $t_{\rm{cov}}(k)=\mathbb{E}[τ_{\mathrm{cov}}(k)]$ with $t_{\rm{cov}}=t_{\rm{cov}}(1)$. We prove that $t_{\rm{cov}}(k)\lesssim t_{\rm{cov}}/k$. When $k\leq t_{\mathrm{cov}}/t_{\rm{rel}}$, where $t_{\rm{rel}}$ is the inverse of the spectral gap, we show that this bound is sharp. For $k\leq t_{\mathrm{cov}}/t_{\rm{mix}}$ with $t_{\rm{mix}}$ the total variation mixing time of $(P+I)/2$ we prove that $k \cdot \max_{x_1,\ldots,x_k}\mathbb{E}_{x_1,\ldots,x_k}[τ_{\rm{cov}}(k)] \asymp t_{\rm{cov}}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_00665 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Covering a graph with independent walks Hermon, Jonathan Sousi, Perla Probability 60J10, 60J27 Let $P$ be an irreducible and reversible transition matrix on a finite state space $V$ with invariant distribution $π$. We let $k$ chains start by choosing independent locations distributed according to $π$ and then they evolve independently according to $P$. Let $τ_{\mathrm{cov}}(k)$ be the first time that every vertex of $V$ has been visited at least once by at least one chain and let $t_{\rm{cov}}(k)=\mathbb{E}[τ_{\mathrm{cov}}(k)]$ with $t_{\rm{cov}}=t_{\rm{cov}}(1)$. We prove that $t_{\rm{cov}}(k)\lesssim t_{\rm{cov}}/k$. When $k\leq t_{\mathrm{cov}}/t_{\rm{rel}}$, where $t_{\rm{rel}}$ is the inverse of the spectral gap, we show that this bound is sharp. For $k\leq t_{\mathrm{cov}}/t_{\rm{mix}}$ with $t_{\rm{mix}}$ the total variation mixing time of $(P+I)/2$ we prove that $k \cdot \max_{x_1,\ldots,x_k}\mathbb{E}_{x_1,\ldots,x_k}[τ_{\rm{cov}}(k)] \asymp t_{\rm{cov}}$. |
| title | Covering a graph with independent walks |
| topic | Probability 60J10, 60J27 |
| url | https://arxiv.org/abs/2104.00665 |