A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913880080384000 |
|---|---|
| author | Du, Hang Gong, Shuyang Xu, Jiaming |
| author_facet | Du, Hang Gong, Shuyang Xu, Jiaming |
| contents | We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al.~\cite{bet2023detecting} show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change occurs at time $n-Ω(\sqrt{n})$. They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time $n-o(\sqrt{n}).$ Kaddouri et al.~\cite{kaddouri2024impossibility} make a step forward by proving the detection is impossible if the change occurs at time $n-o(n^{1/3}).$ In this paper, we resolve the conjecture affirmatively, proving that detection is indeed impossible if the change occurs at time $n-o(\sqrt{n}).$ Furthermore, we establish that estimating the changepoint with an error smaller than $o(\sqrt{n})$ is also impossible, thereby confirming that the estimator proposed in Bhamidi et al.~\cite{bhamidi2018change} is order-optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_00514 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models Du, Hang Gong, Shuyang Xu, Jiaming Probability Combinatorics Statistics Theory Primary 05C80, Secondary 68Q87 We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al.~\cite{bet2023detecting} show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change occurs at time $n-Ω(\sqrt{n})$. They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time $n-o(\sqrt{n}).$ Kaddouri et al.~\cite{kaddouri2024impossibility} make a step forward by proving the detection is impossible if the change occurs at time $n-o(n^{1/3}).$ In this paper, we resolve the conjecture affirmatively, proving that detection is indeed impossible if the change occurs at time $n-o(\sqrt{n}).$ Furthermore, we establish that estimating the changepoint with an error smaller than $o(\sqrt{n})$ is also impossible, thereby confirming that the estimator proposed in Bhamidi et al.~\cite{bhamidi2018change} is order-optimal. |
| title | A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models |
| topic | Probability Combinatorics Statistics Theory Primary 05C80, Secondary 68Q87 |
| url | https://arxiv.org/abs/2502.00514 |