Geschätzter Durchschnitt in Polynomialzeit

Sei eine Funktion. Wir wollen den Durchschnitt von f schätzen , das heißt: E [ f ( n ) ] = 2 - n ∑ x ∈ { 0 , 1 } n f ( x ) .$f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]$$f$$\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)$

NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if not, forget it!)

Sei der (randomisierte) Schätzalgorithmus. Angenommen, E hat Black-Box-Zugriff auf f . Wir bezeichnen dies mit E f .$E$$E$$f$$E^f$

Es gibt zwei Bedingungen:

1) Laufzeit des Schätzers: Es existiert ein einzelnes Polynom so dass für alle n und alle f die Laufzeit von E f ( 1 n ) durch p ( n $p(\cdot)$$n$$f$$E^f(1^n)$ .$\frac{p(n)}{\mathbb{E}[f(n)]}$

2) Schätzerpräzision mit Sicherheit :$\delta$ Es existiert ein einzelnes Polynom , so dass wir für alle n und alle f $q(\cdot)$$n$$f$mit einer Wahrscheinlichkeit von mindestensδ.${1 \over {q(n)}} < \frac{E^f(1^n)}{\mathbb{E}[f(n)]} < q(n)$$\delta$

NOTE: The confidence δ was not in the OP. The parameter δ is in (0,1), and may depend on n. For instance, it may be 1-1/2^n.

Gibt es solche Schätzer?

Hintergrund und Motivation

Ich habe meine Motivation anfangs nicht erwähnt, da sie viel Hintergrundwissen erfordert. Jedenfalls beschreibe ich es für die Enthusiasten kurz: Die Notwendigkeit für solche Schätzer ergibt sich im Zusammenhang mit "Proofs of Ability", wie im folgenden Artikel definiert:

Mihir Bellare, Oded Goldreich. Proving Computational Ability , 1992. Unveröffentlichtes Manuskript.

Insbesondere haben die Autoren am Ende von Seite 5 implizit angenommen, dass solche Schätzer existieren (Präzision wird nicht erwähnt, und die Laufzeit ist nicht genau definiert; der Kontext definiert jedoch alles klar.)

Mein erster Versuch war, " Eine Stichprobe von Samplern - Eine rechnerische Perspektive auf das Sampling " zu lesen . Es handelt sich um ein sehr ähnliches Problem, jedoch ist die definierte Fehlerwahrscheinlichkeit additiv, während unsere multiplikativ ist. (Ich habe die Zeitung nicht vollständig gelesen, vielleicht wird erwähnt, was ich irgendwo brauche.)

EDIT (gemäß Tsuyoshis Anfrage): Tatsächlich setzt die Definition von "Proofs of Computational Ability" die Existenz eines "Knowledge Extractor" voraus, dessen (erwartete) Laufzeit . Da wirE[f(n)]nicht kennen, möchten wir es schätzen; Dies darf jedoch die Laufzeit nicht wesentlich verändern: Es sollte sie in einen Polynomfaktor ändern. Die Präzisionsbedingung versucht, eine solche Anforderung zu erfassen.$p(n) \over E[f(n)]$$E[f(n)]$

EDIT: Dies löst die Version des Problems, bei der f nur 0 oder 1 ausgibt. Ich denke jedoch, dass die Lösung angepasst werden kann, damit sie für den allgemeineren Fall funktioniert.

Vielleicht habe ich die Frage falsch verstanden, aber das sieht nicht allzu schwer aus.

Anstatt den Durchschnitt zu schätzen, wollen wir die Anzahl der Einsen schätzen und diese Zahl k nennen. Es sei . Der Durchschnitt ist also k / N. Sie möchten dies innerhalb eines polynomialen multiplikativen Faktors in der Zeit O (N Polylog (N) / k) schätzen.$N = 2^n$

Ich denke, dass dies auch innerhalb eines konstanten multiplikativen Faktors getan werden kann. Nehmen wir zum Beispiel an, Sie möchten dies auf einen Faktor von 2 abschätzen. Die Ausgabe des Algorithmus liegt also zwischen k / 2 und 2k.$k'$

Ich werde einen Algorithmus skizzieren, der die entsprechende Laufzeit haben sollte. Überprüfen Sie zuerst, ob k zwischen N / 2 und N liegt. Dies ist einfach, probieren Sie einfach ein paar zufällige Werte aus und wenn Sie mehr als eine halbe 1 erhalten, dann liegt es in diesem Intervall. Sie haben also eine 2-Approximation. Wenn nicht, prüfen Sie, ob es zwischen N / 4 und N / 2 liegt. Und so weiter. Jedes Mal, wenn Sie das Intervall verkleinern, ist es kostspieliger abzuschätzen, ob k in diesem Bereich liegt. Die Kosten sind jedoch umgekehrt proportional zu der Größe des Intervalls.

Wenn Sie beispielsweise prüfen, ob k zwischen und 2 N / 2 q liegt , müssen Sie ungefähr O ( 2 q ) -Anfragen stellen. Auf jeden Fall sollten Sie nach mehrmaligem Wiederholen dieses Vorgangs das Intervall erhalten, in dem k liegt. Sagen wir k liegt zwischen N / 2 q und 2 N / 2 q . Dann ist k ungefähr N / 2 q . Also 2 $N/2^q$$2N/2^q$$O(2^q)$$N/2^q$$2N/2^q$$N/2^q$$2^q$ist über k / N. In diesem Schritt würden wir also O (k / N) Abfragen ausgeben. Für diesen Schritt sind jedoch q andere Schritte erforderlich, dies ist jedoch nur ein zusätzlicher Polylog-Faktor (N). Die Gesamtlaufzeit ist also O (N Polylog (N) / k) für eine 2-Approximation.

(Man müsste tatsächlich eine Fehlerverstärkung durchführen, um in jedem Schritt eine angemessene Präzision zu erzielen. Dies ist jedoch nur ein zusätzlicher Polylog-Faktor.)

Der Grund, warum ich in diesem mehrstufigen Prozess gerne daran denke, ist, dass er den Prozess als eine Voraussage- und Überprüfungsmaßnahme hervorhebt. Wenn dir jemand sagt, dass zwischen N / 2 q und 2 n / 2 q liegt , dann könntest du es in der versprochenen Zeit noch genauer abschätzen, wenn du diese Tatsache kennst. Wir müssen also den Schritt eliminieren, für k eine Vermutung zu erhalten . Dies erfolgt durch binäre Suche über alle möglichen Intervalle dieses Typs.$k$$N/2^q$$2n/2^q$$k$

Damit dies bei nicht-booleschen Ausgaben funktioniert, müssen Sie nur die angezeigten Werte summieren, anstatt die Anzahl der Einsen zu zählen. Ich werde versuchen, eine Referenz zu finden, um zu zeigen, dass dies konsequent funktioniert.

$f_1,f_2,\ldots$$f$$\{0,1\}^n$$k$$\sum_{i=1}^k f_i \ge M$$M$$M=polylog(n)$$M / k$

$k$$\mu$$E(f)$$k_{low}$$k_{high}$$\mu$$1 - \delta$$\sum_{i=1}^{k_{low}} f_i < M$$\sum_{i=1}^{k_{high}} f_i > M$$f_i$$k_{low} < k < k_{high}$$1-\delta$$M/k$