Untergrenze bei der Schätzung von

11

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 ε ( 0 , 1 ) mit dem Versprechen, dass entweder n k = 1 a k = 1 oder n k = 1 a k1 - ε .ana1ε(0,1)k=1nak=1k=1nak1ε

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ε

Clement C.
quelle
Ich denke du meinst . k=1nak1ε
RB
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 a k gleich 1 - ε sindnak , mit Ausnahme von einem (willkürlichen, zufälligen)j,so dassajentweder gleichε(in der ersten Sequenz) und0(in der zweiten) ist. OhneΩ(n)Abfragen können die beiden Sequenzen nicht voneinander getrennt werden ...1εn1jajε0Ω(n)
Clement C.
Ich gehe davon aus, dass Sie mit dem Abfragemodell das auswählen können, für das Sie ein k abfragen. Ist das richtig? kak
Kodlu
Ja (Sie können wählen, welchen Punkt Sie "offenlegen" möchten).
Clement C.

Antworten:

5

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

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

Im Folgenden möchten wir, dass der Algorithmus mit einer Wahrscheinlichkeit für einige Parameter δ > 0 erfolgreich ist .1δδ>0

Erste Untergrenze: .Ω(1ϵlog1δ)

Der te Block hat n i = 2 i - 1 Elemente, also L = lg n . Wir setzen den Wert aller Elemente im i- ten Block auf ( 1 + X i ) / ( 2 n i L ) , wobei X i eine Variable ist, die entweder 0 oder 1 ist . Die Gesamtsumme dieser Sequenz ist eindeutig α = L i = 1 1 + X.ini=2i1L=lgni(1+Xi)/(2niL)Xi01 Stellen Sie sich vor, Sie wählen jedesXimit der Wahrscheinlichkeitβ aus, dass esandernfalls1und0 ist. Umαabzuschätzen, benötigen wir eine zuverlässige Schätzung vonβ. Insbesondere wollen wir in der Lage sein, die Baseβ=1-4ϵund beispielsweiseβ=1 zu unterscheiden.

α=i=1L1+Xi2niL=12+12L(i=1LXi).
Xiβ10αββ=14ϵβ=1

Stellen Sie sich nun vor, Sie nehmen dieser Zufallsvariablen ab und lassen Z 1 , , Z ϵ , dann μ = 4 ϵ m , und die Ausfallwahrscheinlichkeit ist P [ Y 2 ϵ m ] = P [m die abgetasteten Variablen sein. Einstellungen Y = m i = 1 ( 1 - X i ) (beachten Sie, dass wir die Summe derKomplementvariablen nehmen), wir haben μ = E [ Y ] = ( 1 - β ) m , und die Chernoff-Ungleichung sagt uns dass, wenn β = 1 - 4Z1,,ZmY=i=1m(1Xi)μ=E[Y]=(1β)mβ=14ϵμ=4ϵm Um diese Menge kleiner als zu machen

P[Y2ϵm]=P[Y(11/2)μ]exp(μ(1/2)2/2)=exp(ϵm/2).
, wir brauchen m 2δ .m2ϵln1δ

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: .Ω(logn/loglogn)

Stellen Sie das i te Blockgröße auf , wobei L =ni=Li die Anzahl der Blöcke ist. Ein Element im i- ten Block hat den Wert α i = ( 1 / L ) / n i . Die Gesamtsumme der Werte in der Sequenz ist also 1 .L=Θ(logn/loglogn)iαi=(1/L)/ni1

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

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 1 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, L / 8 Einträge, hat es Wahrscheinlichkeit (etwa) 1 / 8 zu erfassenein modifiziertes Eingangs. Daherbeträgtdie Wahrscheinlichkeit, dass dieser Algorithmus fehlschlägt, wenn er weniger als L / 8 Einträgeliest,mindestens ( 1 - p ) ( 7 /p=1/21L/81/8L/8

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

PS Ich denke, wenn man die Parameter vorsichtiger betrachtet, kann die erste Untergrenze auf verbessert werden .Ω(1/ϵ2)

Sariel Har-Peled
quelle
Danke dafür! Ich habe eine kleine Frage zum ersten, Ω(1/ϵ)β<1β1/ϵXiϵ
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
4

Untergrenze

Ω(1/ϵ)

Betrachten Sie die durch gegebene Folge a1,,anϵ,2ϵ,3ϵ,4ϵ,na1++an=1n1/2ϵ

Konstruieren Sie nun eine neue Sequenz indem Sie ein einzelnes Element der obigen Sequenz durch Subtrahieren von ϵ modifizieren . Mit anderen Worten, a ' 1 = a 1 , a ' 2 = a 2 usw., außer dass a ' ia1,,anϵa1=a1a2=a2ai=aiϵa1++an=1ϵ

a1,,ana1,,aniΩ(n)n1/2ϵΩ(1/ϵ)

Obere Grenze

O(lg(n/ϵ)[lgn+1/ϵ2])

[0,1]

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

aiaiai[,u]i,jai,,aj[,u]O(lg(n/ϵ))

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

  • [0,0.25ϵ/n)0m×0.25ϵ/nmmn0.25ϵ

  • Für jeden anderen Bereich können wir die Summe der Werte in diesem Bereich auf einen relativen Fehler beschränken δO(1/δ2)2×δ=0.25ϵ

Der Fehler in der Summe der Schätzungen für alle außer dem ersten Bereich beträgt höchstens 0.25ϵ0.25ϵ0.5ϵ11ϵ

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.
2
@ClementC., Ich habe gemäß Ihrer Anfrage eine Untergrenze hinzugefügt.
DW
Vielen Dank (obwohl ich gemäß dem üblichen Fokus beim Testen von Eigenschaften implizit darüber nachgedacht habe nε
Clement C.