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$

reference-request randomized-algorithms property-testing

— Klemens C.
źródło

Chyba masz na myśli .

\sum_{k = 1}^{n} a_{k} \leq 1 - ε

$\sum_{k=1}^n a_k \leq 1-\varepsilon$

— RB

Rzeczywiście - naprawiłem to.

— Klemens C.

Cóż, bez kolejności zależałoby od , uważam (z próbkowaniem lub bez). „Zła” instancja (para sekwencji) byłaby na przykład sekwencją, w której wszystkie byłyby równe , z wyjątkiem jednej (arbitralnej, losowej) takiej, że jest albo równe (w pierwszej sekwencji) i (w drugiej). Bez zapytań nie można rozdzielić dwóch sekwencji ...

n

$n$

a_{k}

$a_k$

\frac{1 - ε}{n - 1}

$\frac{1-\varepsilon}{n-1}$

j

$j$

a_{j}

$a_j$

ε

$\varepsilon$

0

$0$

Ω (n)

$\Omega(n)$

— Clement C.

Zakładam, że model zapytań pozwala wybrać dla którego , czy to prawda?

k

$k$

a_{k}

$a_k$

— kodlu

Tak (możesz wybrać punkt, który chcesz „ujawnić”).

— Klemens C.

Odpowiedzi:

Oto dolne granice, które mogę pokazać. Przypuszczam, że dla ustalonego prawą dolną granicą jest , ale oczywiście mogę się mylić. $\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. ). $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 oszacowania $i$ $n_i = 2^{i-1}$ $L = \lg n$ $i$ $(1+X_i)/(2n_iL)$ $X_i$ $0$ $1$

α = \sum_{i = 1}^{L} \frac{1 + X_{i}}{2 n_{i} L} = \frac{1}{2} + \frac{1}{2 L} (\sum_{i = 1}^{L} X_{i}) .

$\alpha = \sum_{i=1}^L \frac{1+X_i}{2n_i L} = \frac{1}{2} + \frac{1}{2L}\left(\sum_{i=1}^L X_i \right).$

X_{i}

$X_i$

β

$\beta$

1

$1$

0

$0$

α

$\alpha$

β

$\beta$ . W rozdrobnionej, chcemy być w stanie odróżnić podstawę

i, powiedzmy,

β = 1 - 4 ϵ

$\beta = 1-4\epsilon$

β = 1

$\beta=1$

Teraz wyobraź sobie próbkowanie tych zmiennych losowych i niech 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$ $Y = \sum_{i=1}^m (1-X_i)$ $\mu = E[Y] = (1-\beta) m$ $\beta =1-4\epsilon$ $\mu = 4\epsilon m$

P [Y \leq 2 ϵ m] = P [Y \leq (1 - 1 / 2) μ] \leq \exp (- μ (1 / 2)^{2} / 2) = \exp (- ϵ m / 2) .

$P\left[ Y \leq 2\epsilon m \right] = P\left[ Y \leq (1-1/2) \mu \right] \leq \exp \left( -\mu (1/2)^2 / 2 \right) = \exp \left( -\epsilon m / 2 \right).$

δ

$\delta$ , potrzebujemy .

m \geq \frac{2}{ϵ} \ln \frac{1}{δ}

$\displaystyle m \geq \frac{2}{\epsilon} \ln \frac{1}{\delta}$

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 . $i$ $n_i = L^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$ $\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 $p=1/2$ $1$ $L/8$ $1/8$ $L/8$

(1 - p) (7 / 8) > 7 / 16 > 1 / 3.

$(1-p)(7/8) > 7/16 > 1/3.$

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

— Sariel Har-Peled
źródło

Dziękuję Ci za to! Mam małe pytanie dotyczące pierwszego, lb (a dokładniej możliwej kwadratowej poprawy). Ponieważ mamy tutaj problem jednostronnej obietnicy, co oznacza, że gdy tylko algorytm „zobaczy” jakąkolwiek wartość, która daje jakiekolwiek dowody, że , może on zakończyć bez konieczności dokładniejszego oszacowania : doesn oznacza to, że jest optymalny dla tej konstrukcji, ponieważ w zasadzie można oczekiwać, że wszystkie będą miały wartość 1, lub przynajmniej nie będzie frakcji ?

Ω (1 / ϵ)

$\Omega(1/\epsilon)$

β < 1

$\beta < 1$

β

$\beta$

1 / ϵ

$1/\epsilon$

X_{i}

$X_i$

ϵ

$\epsilon$

— Klemens C.

Tak. Jeśli chcesz rozróżnić tylko między 1 a 1-epsilon, to oczywiście nie możesz poprawić dolnej granicy ... Myślałem o próbie rozróżnienia innych zakresów ... s

— Sariel Har-Peled

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$ $\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, , itd., Z tym wyjątkiem, że . Zauważ, że . $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 ? Cóż, różnią się tylko jednym elementem ( $a_1,\dots,a_n$ $a'_1,\dots,a'_n$ $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)$ $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]$

[0, 1] = [0, 0.25 ϵ / n] \cup (0.25 ϵ / n, 0.5 ϵ / n] \cup (0.5 ϵ / n, ϵ / n] \cup (ϵ / n, 2 ϵ / n] \cup (2 ϵ / n, 4 ϵ / n] \cup \dots \cup (\dots, 1] .

$[0,1] = [0,0.25\epsilon/n] \cup (0.25\epsilon/n,0.5\epsilon/n] \cup (0.5\epsilon/n,\epsilon/n] \cup (\epsilon/n,2\epsilon/n] \cup (2\epsilon/n,4\epsilon/n] \cup \dots \cup (\ldots,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$

— DW
źródło

Dzięki - wygląda to interesująco (o ile mogę powiedzieć, nie jest to takie samo podejście, jak to zastosowane w artykule / dyskusji, do której prowadzi link powyżej), a ja przyjrzę się temu, co napisałeś. Jednak szukam dolnej granicy zamiast górnej granicy - tj. Ile zapytań jest potrzebnych .

— Klemens C.

(Z upływem czasu jednak przyznam „nagrodę” za odpowiedź - chociaż wciąż szukam odniesienia do dolnej granicy, jeśli gdzieś tam jest.)

— Clement C.

@ClementC., Dodałem dolną granicę, zgodnie z twoją prośbą.

— DW

Dziękuję (chociaż, jak zwykle w testowaniu nieruchomości, domyślnie rozważyłem

n

$n$

ε

$\varepsilon$