4
Dolna granica dla testowania bliskości w normie ?
Zastanawiałem się, czy istnieje jakakolwiek dolna granica (pod względem złożoności próby) znana z następującego problemu: Biorąc pod uwagę przykładowy dostęp do wyroczni do dwóch nieznanych dystrybucji , D_2 w \ {1, \ dots, n \} , test (whp) czyD1D1D_1D2D2D_2{1,…,n}{1,…,n}\{1,\dots,n\} D1=D2D1=D2D_1=D_2 lub d2(D1,D2)=∥D1−D2∥2=∑ni=1(D1(i)−D2(i))2−−−−−−−−−−−−−−−−−−√≥ϵd2(D1,D2)=‖D1−D2‖2=∑i=1n(D1(i)−D2(i))2≥ϵ\operatorname{d_2}(D_1,D_2)=\lVert D_1-D_2\rVert_2 = \sqrt{\sum_{i=1}^n\left(D_1(i)-D_2(i)\right)^2} \geq \epsilon Batu i in. …