← All problems

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

3 years old · traced to

Consider the preferential attachment model with changepoint time τn=n−cnγ\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.

References
  1. 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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.