The broken sample problem revisited: Proof of a conjecture by Bai-Hsing and high-dimensional extensions

We revisit the classical broken sample problem: Two samples of i.i.d. data points X=₁,⋯, Xₙ\ and Y=₁,⋯,Yₘ\ are observed without correspondence with m≤ n. Under the null hypothesis, X and Y are independent. Under the alternative hypothesis, Y is correlated with a random subsample of X, in the sense that (Xπ(i),Yᵢ)'s are drawn independently from some bivariate distribution for some latent injection π:[m] → [n]. Originally introduced by DeGroot, Feder, and Goel (1971) to model matching records in census data, this problem has recently gained renewed interest due to its applications in data de-anonymization, data integration, and target tracking. Despite extensive research over the past decades, determining the precise detection threshold has remained an open problem even for equal sample sizes ($m=n$). Assuming m and n grow proportionally, we show that the sharp threshold is given by a spectral and an L₂ condition of the likelihood ratio operator, resolving a conjecture of Bai and Hsing (2005) in the positive. These results are extended to high dimensions and settle the sharp detection thresholds for Gaussian and Bernoulli models.