Optimal detection of planted stars via a random energy model
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908837769904128 |
|---|---|
| author | Narang, Ijay Perkins, Will Wee, Timothy L. H. |
| author_facet | Narang, Ijay Perkins, Will Wee, Timothy L. H. |
| contents | We study the problem of detecting a planted star in the Erd{ő}s--R{é}nyi random graph $G(n,m)$, formulated as a hypothesis test. We determine the scaling window for critical detection in $m$ in terms of the star size, and characterize the asymptotic total variation distance between the null and alternative hypotheses in this window. In the course of the proofs we show a condensation phase transition in the likelihood ratio that closely resembles that of the random energy model from spin glass theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15585 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal detection of planted stars via a random energy model Narang, Ijay Perkins, Will Wee, Timothy L. H. Statistics Theory Information Theory Probability We study the problem of detecting a planted star in the Erd{ő}s--R{é}nyi random graph $G(n,m)$, formulated as a hypothesis test. We determine the scaling window for critical detection in $m$ in terms of the star size, and characterize the asymptotic total variation distance between the null and alternative hypotheses in this window. In the course of the proofs we show a condensation phase transition in the likelihood ratio that closely resembles that of the random energy model from spin glass theory. |
| title | Optimal detection of planted stars via a random energy model |
| topic | Statistics Theory Information Theory Probability |
| url | https://arxiv.org/abs/2602.15585 |