Untergrenze bei der Schätzung von

Ich würde gerne wissen (im Zusammenhang mit dieser anderen Frage ), ob Untergrenzen für das folgende Testproblem bekannt waren: Man erhält Abfragezugriff auf eine Folge nicht negativer Zahlen und mit dem Versprechen, dass entweder oder . $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$

Wie viele Abfragen (Lookups) sind ausreichend und notwendig für einen (adaptiven) randomisierten Algorithmus zwischen den beiden Fällen zu unterscheiden, mit einer Wahrscheinlichkeit von mindestens ? $2/3$

Ich habe einen früheren Beitrag gefunden , der eine logarithmische (in ) Obergrenze für das verwandte Problem der Approximation der Summe und eine ungefähr übereinstimmende Untergrenze für dieses Problem für deterministische Algorithmen angibt. Ich konnte jedoch kein Ergebnis für das spezifische Problem finden, das ich in Betracht ziehe (insbesondere randomisierte Algorithmen). $n$

Bearbeiten: Nach der Antwort unten hätte ich klarer sein sollen: In der obigen (und insbesondere in der Asymptotik für die Untergrenze) ist die "Haupt" -Größe, die als unendlich angesehen wird, während eine (willkürlich kleine) ist ) konstant. $n$ $\varepsilon$

reference-request randomized-algorithms property-testing Clement C.
quelle

Ich denke du meinst

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

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

In der Tat - behoben.

Clement C.

Nun, ohne die Reihenfolge wäre eine Abhängigkeit von

notwendig, denke ich (mit oder ohne Stichprobe). Eine "schlechte" Instanz (ein Paar von Sequenzen) wäre zum Beispiel eine Sequenz, bei der alle

gleich

n

$n$

a_{k}

$a_k$

, mit Ausnahme von einem (willkürlichen, zufälligen)

so dass

entweder gleich

(in der ersten Sequenz) und

(in der zweiten) ist. Ohne

Abfragen können die beiden Sequenzen nicht voneinander getrennt werden ...

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

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

j

$j$

a_{j}

$a_j$

ε

$\varepsilon$

0

$0$

Ω (n)

$\Omega(n)$

Clement C.

Ich gehe davon aus, dass Sie mit dem Abfragemodell das

auswählen können, für das Sie

abfragen.

das richtig?

k

$k$

a_{k}

$a_k$

Kodlu

Ja (Sie können wählen, welchen Punkt Sie "offenlegen" möchten).

Clement C.

Antworten:

Hier sind die unteren Grenzen, die ich zeigen kann. Ich vermute, dass für ein festes die rechte Untergrenze , aber natürlich könnte ich mich irren. $\epsilon$ $\Omega( \log n)$

Ich werde eine abnehmende Sequenz verwenden (nur der Einfachheit halber). Der grundlegende Mechanismus besteht darin, die Sequenz in Blöcke zu unterteilen. Im ten Block gibt es Elemente (dh ). $L$ $i$ $n_i$ $\sum_i n_i = n$

Im Folgenden möchten wir, dass der Algorithmus mit einer Wahrscheinlichkeit für einige Parameter . $\geq 1-\delta$ $\delta >0$

Erste Untergrenze: . $\displaystyle \Omega\left( \frac{1}{\epsilon} \log \frac{1}{\delta} \right)$

Der te Block hat Elemente, also . Wir setzen den Wert aller Elemente im ten Block auf , wobei eine Variable ist, die entweder oder . Die Gesamtsumme dieser Sequenz ist eindeutig $i$ $n_i = 2^{i-1}$ $L = \lg n$ $i$ $(1+X_i)/(2n_iL)$ $X_i$ $0$ $1$ Stellen Sie sich vor, Sie wählen jedesmit der Wahrscheinlichkeit, dass esandernfallsund. Umabzuschätzen, benötigen wir eine zuverlässige Schätzung von. Insbesondere wollen wir in der Lage sein, die Baseund beispielsweise.

α = \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$

β = 1 - 4 ϵ

$\beta = 1-4\epsilon$

β = 1

$\beta=1$

Stellen Sie sich nun vor, Sie nehmen dieser Zufallsvariablen ab und lassen , dann , und die Ausfallwahrscheinlichkeit ist $m$ die abgetasteten Variablen sein. Einstellungen (beachten Sie, dass wir die Summe derKomplementvariablen nehmen), wir haben , und die Chernoff-Ungleichung sagt uns dass, wenn $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$ Um diese Menge kleiner als zu machen

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).$

, wir brauchen

δ

$\delta$

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

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

Die wichtigste Beobachtung ist, dass die Chernoff-Ungleichung eng ist (man muss vorsichtig sein, da sie nicht für alle Parameter korrekt ist, aber in diesem Fall korrekt), sodass Sie (bis zu Konstanten) nichts Besseres tun können.

Zweite Untergrenze: . $\Omega( \log n / \log \log n)$

Stellen Sie das $i$ te Blockgröße auf , wobei $n_i = L^i$ die Anzahl der Blöcke ist. Ein Element im ten Block hat den Wert . Die Gesamtsumme der Werte in der Sequenz ist also . $L = \Theta( \log n / \log \log n)$ $i$ $\alpha_i = \Bigl(1/L\Bigr)/n_i$ $1$

Nun könnten wir uns entscheiden, einen beliebigen Block auszuwählen, sagen wir den ten, und alle Werte in seinem Block auf (anstelle von ) setzen. Dies erhöht den Beitrag des ten Blocks von auf und erhöht die Gesamtmasse der Sequenz auf (fast) . $j$ $\alpha_{j-1} = L \alpha_j$ $\alpha_j$ $j$ $1/L$ $1$ $2$

Informell muss nun jeder zufällige Algorithmus den Wert in jedem der Blöcke überprüfen. Als solches muss es mindestens Werte der Sequenz lesen . $L$

Um das obige Argument mit Wahrscheinlichkeit formeller zu machen , der ursprünglichen Reihenfolge der Masse gibt als Eingang (verweisen wir auf diesem als OriginalEingang). Andernfalls wählen Sie zufällig den Block mit den erhöhten Werten aus (modifizierte Eingabe). Klar, wenn der randomisierten Algorithmus liest weniger als, sagen wir, Einträge, hat es Wahrscheinlichkeit (etwa) zu erfassenein modifiziertes Eingangs. Daherbeträgtdie Wahrscheinlichkeit, dass dieser Algorithmus fehlschlägt, wenn er weniger als Einträgeliest,mindestens $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 Ich denke, wenn man die Parameter vorsichtiger betrachtet, kann die erste Untergrenze auf verbessert werden . $\Omega(1/\epsilon^2)$

Sariel Har-Peled
quelle

Danke dafür! Ich habe eine kleine Frage zum ersten,

Ω (1 / ϵ)

$\Omega(1/\epsilon)$

β < 1

$\beta < 1$

β

$\beta$

1 / ϵ

$1/\epsilon$

X_{i}

$X_i$

ϵ

$\epsilon$

Ja. Wenn Sie nur zwischen 1 und 1-Epsilon unterscheiden möchten, können Sie natürlich die Untergrenze nicht verbessern ... Ich habe darüber nachgedacht, andere Bereiche zu unterscheiden ... s

Sariel Har-Peled

Untergrenze

$\Omega(1/\sqrt{\epsilon})$

Betrachten Sie die durch gegebene Folge $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}$

Konstruieren Sie nun eine neue Sequenz indem Sie ein einzelnes Element der obigen Sequenz durch Subtrahieren von modifizieren . Mit anderen Worten, , usw., außer dass $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$

$a_1,\dots,a_n$ $a'_1,\dots,a'_n$ $i$ $\Omega(n)$ $n \approx 1/\sqrt{2\epsilon}$ $\Omega(1/\sqrt{\epsilon})$

Obere Grenze

$O(\lg(n/\epsilon) [\lg n + 1 / \epsilon^2])$

$[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))$

Jetzt schätzen wir die Summe der Werte in jedem Bereich. Der erste Bereich wird getrennt von allen anderen behandelt:

$[0,0.25\epsilon/n)$ $0$ $m \times 0.25\epsilon/n$ $m$ $m \le n$ $0.25 \epsilon$
Für jeden anderen Bereich können wir die Summe der Werte in diesem Bereich auf einen relativen Fehler beschränken $\delta$ $O(1/\delta^2)$ $2 \times$ $\delta = 0.25 \epsilon$

Der Fehler in der Summe der Schätzungen für alle außer dem ersten Bereich beträgt höchstens $0.25 \epsilon$ $0.25 \epsilon$ $\le 0.5 \epsilon$ $1$ $1-\epsilon$

DW
quelle

Danke - das sieht interessant aus (soweit ich das beurteilen kann, ist es nicht der gleiche Ansatz wie in dem oben verlinkten Papier / der Diskussion), und ich werde mir genauer ansehen, was Sie geschrieben haben. Ich suche jedoch eher eine Untergrenze als eine Obergrenze - dh wie viele Abfragen erforderlich sind .

Clement C.

(Da die Zeit abgelaufen ist, vergebe ich der Antwort trotzdem das "Kopfgeld" - obwohl ich immer noch nach einer Referenz für eine Untergrenze suche, falls es dort oben irgendwo eine gibt.)

Clement C.

@ClementC., Ich habe gemäß Ihrer Anfrage eine Untergrenze hinzugefügt.

Vielen Dank (obwohl ich gemäß dem üblichen Fokus beim Testen von Eigenschaften implizit darüber nachgedacht habe

n

$n$

ε

$\varepsilon$

Clement C.