Czy istnieją właściwości dystrybucji „maksymalnie” trudne do przetestowania?

Algorytm testowania dystrybucji dla właściwości dystrybucji P (która jest tylko pewnym podzbiorem wszystkich dystrybucji w ciągu [n]) ma dostęp do próbek zgodnie z pewną dystrybucją D i jest zobowiązany do podjęcia decyzji (whp), czy lub d ( D , P ) > ϵ ( d tutaj jest zwykle odległością ℓ 1 ). Najczęstszą miarą złożoności jest liczba próbek używanych przez algorytm.$D\in P$$d(D,P)>\epsilon$$d$$\ell_1$

Teraz w standardowych testach właściwości, w których masz dostęp do zapytania do jakiegoś obiektu, liniowa dolna granica złożoności zapytania jest oczywiście najsilniejszą dolną granicą, ponieważ zapytań ujawniłoby cały obiekt. Czy dotyczy to również testów dystrybucji?$n$

O ile rozumiem, „trywialna” górna granica dla testowania właściwości rozkładów to --- według granic Chernoffa, to wystarczy „zapisać” rozkład D, który jest zbliżony do D w ℓ 1 odległość, a następnie możemy po prostu sprawdzić, czy są jakieś dystrybucje blisko do D”, które są w P (może to zająć nieskończony czas, ale to nie ma znaczenia dla próbki złożoności).$O(n^2\log n)$$\ell_1$

• Czy istnieje lepszy „trywialny” test dla wszystkich właściwości dystrybucji?
• Czy są jakieś właściwości rozkładu, dla których, jak wiemy, próbkowane dolne granice są silniejsze niż liniowe?

Przepraszam, że odkryłem ten post - jest dość stary, ale pomyślałem, że otrzymanie odpowiedzi może nie być tak złym pomysłem.

$\ell_1$$\frac{\varepsilon}{2}$$p'$$\mathcal{P}_n$$\frac{\varepsilon}{2}$$\hat{p}$$O\big(\frac{n\log n}{\varepsilon^2}\big)$$n$$\varepsilon$$O(\frac{n}{\varepsilon^2})$

$O(\frac{n}{\varepsilon^2})$$n$$\varepsilon$$n$

$1/10$$\Theta_\varepsilon(\frac{n}{\log n})$

(Pamiętaj, że jest to trochę „oszustwo” w tym sensie, że właściwość jest po prostu sposobem na postawienie tolerancyjnego pytania testowego i oznaczenie go jako testowanie właściwości ad hoc ).

$k$$k$$k=n/10$$\Omega(\frac{n}{\log n})$$\frac{n}{100}$