Sharp Local Minimax Rates for Goodness-of-Fit Testing in Large Random Graphs, multivariate Poisson families and multinomials
We consider the identity testing problem in large inhomogeneous random graphs (also called goodness-of-fit testing problem), multivariate Poisson families and multinomials. Given a known probability distribution P and n iid samples drawn from an unknown probability distribution Q, we investigate how large ρ should be to distinguish, with high probability, the case P=Q from the case d(P,Q) ≥ρ. We answer this question in the case of a family of distances: d(P,Q) = P-Q_t for t ∈ [1,2]. Besides being locally minimax-optimal (i.e. characterizing the detection threshold associated to the known matrix P), our tests have simple expressions and are easily implementable. Our results are closely related to important and popular results in the multinomial setting, and complete them by providing the missing matching upper and lower bounds.
READ FULL TEXT