Powerlessness conjecture for late changepoint detection below the square-root scale

From papers

Consider the preferential attachment model with changepoint time τn=ncnγ\tau_n=n-cn^\gamma for c>0c>0 and γ(0,1)\gamma\in(0,1), and let Dv(n)D_v(n) denote the degree of vertex vv in the final network and GnG_n the final network snapshot. A test is powerful if its power tends to one while its type-I error tends to zero.

Powerlessness conjecture. When γ<12\gamma<\tfrac{1}{2}, all tests based on the vertex degrees {Dv(n)}v[n]\{D_v(n)\}_{v\in[n]} are powerless, and all tests based on GnG_n are powerless.

The second assertion is stronger because it rules out using higher-level information in the edge structure of GnG_n. The question is formally open; the conjecture is motivated by the fact that degree-count mean shifts are of order nγn^\gamma, below their fluctuation scale when γ<12\gamma<\tfrac{1}{2}, and by asymptotic normality results suggesting that the corresponding distributions have vanishing total variation distance.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Gianmarco Bet, Kay Bogerd, Rui M. Castro and Remco van der Hofstad, “Detecting a late changepoint in the preferential attachment model”, arXiv:2310.02603 (2023).

Solutions 0

No solutions have been posted yet.