Dolna granica szacowania dla

Chciałbym wiedzieć (związany z tym drugim pytaniem ), czy dolne granice były znane z następującego problemu testowego: jeden ma dostęp do zapytania do sekwencji liczb nieujemnych i , z obietnicą, że albo lub .$a_n \geq \dots\geq a_1$$\varepsilon \in (0,1)$$\sum_{k=1}^n a_k = 1$$\sum_{k=1}^n a_k \leq 1-\varepsilon$

Ile zapytań (wyszukiwań) jest wystarczających i niezbędnych, aby (adaptacyjny) randomizowany algorytm rozróżniał te dwa przypadki, z prawdopodobieństwem co najmniej ?$2/3$

Znalazłem poprzedni post, który podaje logarytmiczną (w ) górną granicę pokrewnego problemu przybliżenia sumy i z grubsza dopasowującą dolną granicę tego problemu dla algorytmów deterministycznych; ale nie mogłem znaleźć wyniku dla konkretnego problemu, który rozważam (w szczególności algorytmów losowych).$n$

Edycja: Zgodnie z odpowiedzią poniżej, chyba powinienem był jaśniej wyrazić: w powyższym (a szczególnie w asymptotykach dla dolnej granicy), jest „główną” wielkością postrzeganą jako zbliżająca się do nieskończoności, podczas gdy jest (arbitralnie mała) stała.$n$$\varepsilon$

Oto dolne granice, które mogę pokazać. Przypuszczam, że dla ustalonego prawą dolną granicą jest , ale oczywiście mogę się mylić.Ω ( log n $\epsilon$$\Omega( \log n)$

Użyję sekwencji malejącej (dla wygody). Podstawowym mechanizmem jest dzielenie sekwencji na bloków. W tym bloku będą elementy (tj. ).i n i ∑ i n i = $L$$i$$n_i$$\sum_i n_i = n$

Poniżej chcemy, aby algorytm odniósł sukces z prawdopodobieństwem , dla niektórych parametrów .δ > $\geq 1-\delta$$\delta >0$

Pierwsza dolna granica: .$\displaystyle \Omega\left( \frac{1}{\epsilon} \log \frac{1}{\delta} \right)$

tego bloku jest elementów, więc . Ustawiamy wartość wszystkich elementów w tym bloku na , gdzie jest zmienną lub . Oczywiście całkowita suma tej sekwencji wynosi Wyobraź sobie, że każdy z prawdopodobieństwem ma wartość a w przeciwnym razie . Aby oszacować , potrzebujemy wiarygodnego oszacowanian i = 2 i - 1 L = lg n i ( $i$$n_i = 2^{i-1}$$L = \lg n$$i$X i 0 1 α = L ∑ i = 1 1 + X $(1+X_i)/(2n_iL)$$X_i$$0$$1$Xiβ10α

Teraz wyobraź sobie próbkowanie tych zmiennych losowych i niech Z 1 , … , Z m będą próbkami zmiennych. Ustawienia (zauważ, że bierzemy sumę zmiennych dopełniacza ), mamy , a nierówność Chernoffa mówi nam, że jeśli , to , a prawdopodobieństwo niepowodzenia to Aby ta ilość była mniejsza niż$m$$Z_1, \ldots, Z_m$μ = E [ Y ] = ( 1 - β ) $Y = \sum_{i=1}^m (1-X_i)$$\mu = E[Y] = (1-\beta) m$μ = 4 ϵ m P [ Y ≤ 2 ϵ m ] = P [ Y ≤ ( 1 - 1 / 2 ) μ ] ≤ $\beta =1-4\epsilon$$\mu = 4\epsilon m$δ m ≥

Kluczową obserwacją jest to, że nierówność Chernoffa jest ścisła (należy zachować ostrożność, ponieważ nie jest poprawna dla wszystkich parametrów, ale w tym przypadku jest poprawna), więc nie można tego zrobić lepiej (aż do stałych).

Druga dolna granica: .$\Omega( \log n / \log \log n)$

Ustaw ty rozmiar bloku na , gdzie to liczba bloków. Element w tym bloku ma wartość . Tak więc całkowita suma wartości w sekwencji wynosi .n i = L i L = Θ $i$$n_i = L^i$i α i = ( 1 / L ) / n i$L = \Theta( \log n / \log \log n)$$i$$\alpha_i = \Bigl(1/L\Bigr)/n_i$$1$

Teraz możemy wybrać dowolny blok, powiedzmy ty, i ustawić wszystkie wartości w tym bloku na (zamiast ). Zwiększa to udział tego bloku z do i zwiększa całkowitą masę sekwencji do (prawie) .α j - 1 = L α j α j j 1 / L 1 $j$$\alpha_{j-1} = L \alpha_j$$\alpha_j$$j$$1/L$$1$$2$

Teraz, nieformalnie, każdy randomizowany algorytm musi sprawdzić wartość w każdym z bloków. Jako taki musi odczytać przynajmniej wartości sekwencji.$L$

Aby powyższy argument był bardziej formalny, z prawdopodobieństwem , podaj pierwotną sekwencję masy jako dane wejściowe (nazywamy to pierwotnym danymi wejściowymi). W przeciwnym razie losowo wybierz blok, który ma zwiększone wartości (zmodyfikowane dane wejściowe). Oczywiście, jeśli randomizowany algorytm odczytuje mniej niż, powiedzmy, wpisy , ma prawdopodobieństwo (z grubsza) wykrycia zmodyfikowanego wejścia. Jako takie, prawdopodobieństwo, że ten algorytm zawodzi, jeśli odczytuje mniej niż pozycji, wynosi co najmniej 1 l $p=1/2$$1$1 / 8 l / 8 ( 1 - P ) ( 7 / 8 ) > 7 / 16 > 1 /$L/8$$1/8$$L/8$

PS Myślę, że uważając na parametry, pierwszą dolną granicę można poprawić do .$\Omega(1/\epsilon^2)$

Dolna granica

Konieczne są przynajmniej zapytania aby rozróżnić oba przypadki.$\Omega(1/\sqrt{\epsilon})$

Rozważ sekwencję podane przez , przy czym wybrane tak, że . W szczególności możemy wziąć .$a_1,\dots,a_n$n a 1 + ⋯ + a n = 1 n ≈ 1 / $\epsilon,2\epsilon,3\epsilon,4\epsilon,\dots$$n$$a_1+\dots+a_n = 1$$n \approx 1/\sqrt{2\epsilon}$

Teraz skonstruuj nową sekwencję poprzez modyfikację pojedynczego elementu powyższej sekwencji przez odjęcie ϵ . Innymi słowy, a ′ 1 = a 1 , a ′ 2 = a 2 itd., Z tym wyjątkiem, że a ′ i = a i - ϵ . Zauważ, że a ′ 1 + ⋯ + a ′ n = 1 - ϵ .$a'_1,\dots,a'_n$$\epsilon$$a'_1=a_1$$a'_2=a_2$$a'_i = a_i - \epsilon$$a'_1 + \dots + a'_n = 1-\epsilon$

Ile sondy trwa do odróżnienia z ' 1 , ... , ' n ? Cóż, różnią się tylko jednym elementem ($a_1,\dots,a_n$$a'_1,\dots,a'_n$Ω ( n ) n ≈ 1 / $i$ tym elementem), więc sonda potrzebuje stałego prawdopodobieństwa rozróżnienia. Teraz przypominam sobie, że ; okaże się, że potrzebne są sondy .$\Omega(n)$ Ω(1/$n \approx 1/\sqrt{2\epsilon}$$\Omega(1/\sqrt{\epsilon})$

Górna granica

Myślę, że można rozróżnić dwa przypadki za pomocą zapytań . Nie wiem czy to jest optymalne.$O(\lg(n/\epsilon) [\lg n + 1 / \epsilon^2])$

Oto jak. Podzielmy przedział w następujący sposób:$[0,1]$

$a_i$$a_i$$a_i$$[\ell,u]$$i,j$$a_i,\dots,a_j \in [\ell,u]$$O(\lg(n/\epsilon))$

Teraz oszacujemy sumę wartości w każdym zakresie. Pierwszy zakres będzie obsługiwany osobno od wszystkich pozostałych:

• $[0,0.25\epsilon/n)$$0$$m \times 0.25\epsilon/n$$m$$m \le n$$0.25 \epsilon$

• $\delta$$O(1/\delta^2)$$2 \times$$\delta = 0.25 \epsilon$

$0.25 \epsilon$$0.25 \epsilon$$\le 0.5 \epsilon$$1$$1-\epsilon$