Iteration über Vektoren in der Reihenfolge ihrer Wahrscheinlichkeit auf kleinem Raum

Man betrachte einen dimensionalen Vektor v, wobei v i ∈ { 0 , 1 } ist . Für jedes i kennen wir p i = P ( v i = 1 ) und nehmen an, dass v i unabhängig sind. Gibt es unter Verwendung dieser Wahrscheinlichkeiten einen effizienten Weg, um binäre n- dimensionale Vektoren zu iterieren, um mit größter Wahrscheinlichkeit die geringste Wahrscheinlichkeit (mit willkürlichen Auswahlmöglichkeiten für Bindungen) zu erzielen, indem Raum-Sublinearität in der Ausgabegröße verwendet wird? $n$$v$$v_i \in \{0,1\}$$i$$p_i = P(v_i = 1)$$v_i$$n$

Nehmen wir zum Beispiel . Der wahrscheinlichste Vektor ist ( 1 , 0 , 1 ) und der am wenigsten wahrscheinliche ist { 0 , 1 , 0 } . $p = \{0.8, 0.3, 0.6\}$$(1,0,1)$$\{0,1,0\}$

Für sehr kleine könnten wir jeden der 2 n Vektoren mit seiner Wahrscheinlichkeit bezeichnen und einfach sortieren, aber dies würde natürlich immer noch keinen sublinearen Raum verwenden.$n$$2^n$

Eine enge Variante dieser Frage wurde zuvor unter /cs/24123/how-to-iterate-over-vectors-in-order-of-probability gestellt .

Das Folgende gibt einen Algorithmus an, der ungefähr Zeit und 2 n / 2 Raum verwendet.$2^n$$2^{n/2}$

Betrachten wir zunächst das Problem des Sortierens der Summen aller Teilmengen von Elementen.$n$

Betrachten Sie dieses Unterproblem: Sie haben zwei sortierte Listen mit der Länge und möchten eine sortierte Liste der paarweisen Summen der Zahlen in den Listen erstellen. Sie möchten dies in ungefähr 0 ( m 2 ) Zeit (der Ausgabegröße), aber im sublinearen Raum tun . Wir können O ( m ) Raum erreichen. Wir führen eine Prioritätswarteschlange und ziehen die Summen in aufsteigender Reihenfolge aus der Prioritätswarteschlange heraus.$m$$O(m^2)$$O(m)$

Die Listen seien und b 1 … b m , in aufsteigender Reihenfolge sortiert. Wir nehmen die m Summen a i + b 1 , i = 1 … m und stellen sie in eine Prioritätswarteschlange.$a_1 \ldots a_m$$b_1 \ldots b_m$$m$$a_i + b_1$$i = 1 \ldots m$

Wenn wir nun die kleinste verbleibende Summe aus der Prioritätswarteschlange ziehen, setzen wir , wenn j < m , die Summe a i + b j + 1 in die Prioritätswarteschlange. Der Raum wird von der Prioritätswarteschlange dominiert, die immer höchstens m Summen enthält. Und die Zeit ist O ( m 2 log m ) , da wir O ( log m ) für jede Prioritätswarteschlangenoperation verwenden. Dies zeigt, dass wir das Teilproblem in O ( m 2 lösen können$a_i + b_j$$j < m$$a_i + b_{j+1}$$m$$O(m^2 \log m)$$O(\log m)$ Zeit und O ( m ) Raum.$O(m^2 \log m)$$O(m)$

Um nun die Summen aller Teilmengen von Zahlen zu sortieren , verwenden wir einfach diese Unterroutine, bei der die Liste a i die Menge von Teilmengen der ersten Hälfte der Elemente ist und die Liste b i die Menge von Teilmengen ist der zweiten Hälfte der Artikel. Wir können diese Listen mit demselben Algorithmus rekursiv finden.$n$$a_i$$b_i$

Wir werden nun das ursprüngliche Problem betrachten. Sei der Satz von Koordinaten, die 0 sind , und S 1 der Satz von Koordinaten, die 1 sind . Dann ∏ i ∈ S 0 p ( v i = 0 ) ∏ i ∈ S 1 p ( v i = 1 $S_0$$0$$S_1$$1$

Das Sortieren dieser Zahlen ist dasselbe wie das Sortieren der Zahlen , daher haben wir das Problem auf das Sortieren der Summen von Teilmengen von n Elementen reduziert .$\sum_{i\in S_1}\log p(v_i=1) - \log p(v_i=0)$$n$

Wir können das im Raum (wenn uns die Laufzeit egal ist).$O(n)$

1. Für eine gegebene Zeichenkette können wir im Raum O ( n ) die Anzahl r ( x ) von Zeichenketten berechnen , die wahrscheinlicher als x sind ; das heißt, die Anzahl von x ' st p ( x $x \in \{0,1\}^n$$O(n)$$r(x)$$x$$x'$ : gehe einfach über alle x ' ∈ { 0 , 1 } n und zähle die Anzahl von x ' st$p(x') > p(x)$$x'\in \{0,1\}^n$$x'$ . Beachten Sie, dass r ( x ) die fortlaufende Nummer der Zeichenfolge x in der Ausgabe ist.$p(x') > p(x)$$r(x)$$x$
2. Für jedes können wir x mit r ( x ) = k im Raum O ( n ) finden : gehe über alle x ∈ { 0 , 1 $k$$x$$r(x) = k$$O(n)$ , für jedes x berechnen Sie r ( x ) , stoppen Sie und geben Sie x aus, wenn r ( x ) = k .$x \in \{0,1\}^n$$x$$r(x)$$x$$r(x) = k$
3. Jetzt gehe einfach alle von $k$$0$ zu , für jedes k Druck x mit r ( x ) = k .$2^n-1$$k$$x$$r(x) =k$

(Wir sollten uns auch um mögliche Bindungen kümmern, aber das ist nicht schwierig.)

Bearbeiten: Diese Antwort ist falsch. Siehe Kommentare für Details. ~ Gandaliter

Linear im Ausgabemittel . Ich denke, der offensichtliche Algorithmus verwendet nur den O ( n ) Raum, abgesehen von der Ausgabe selbst natürlich.$O(2^n)$$O(n)$

1. Nimm die Liste mit den Paaren und sortieren Sie sie nach | 0,5 - p i | größte zuerst.$(i, p_i)$$\left|0.5 - p_i\right|$

2. Definieren Sie eine doppelt rekursive Funktion, die eine Liste solcher Paare und einen teilweise gefüllten Vektor aufnimmt und den Wert von v i auf 1 setzt, wenn p i > 0,5 ist , und$v$$v_i$$1$$p_i > 0.5$andernfalls auf 0 , und rekursiv (unter Verwendung des Endes der Liste und v ) , kippt dann v i und rekursiert erneut. Wenn die Liste leer ist, wird stattdessen v ausgegeben.$0$$v$$v_i$$v$

3. Rufen Sie diese rekursive Funktion für die sortierte Liste und einen leeren Vektor auf.

Die Intuition ist, dass Sie die Werte der sichersten Elemente im Vektor zuerst festlegen (diejenigen, deren Wahrscheinlichkeiten am nächsten bei und 1 liegen ) und den Vektor auf diese Weise ausfüllen und mit denen abschließen, deren Wahrscheinlichkeiten am nächsten bei 0,5 liegen . Jeder mögliche Wert, den der gesamte Vektor annehmen könnte, wird in der Reihenfolge seiner Wahrscheinlichkeit ausgegeben.$0$$1$$0.5$

Die Laufzeit ist . Dies ist die Untergrenze, da dies die Länge der Ausgabe ist. Die Raumkomplexität ist O ( n ), weil die Sortierung nicht mehr als das erfordert, und die rekursive Länge ist die Länge des Vektors, die n ist . Ich glaube, dass dies auch die Untergrenze ist, da es für jeden Zeitschritt beim Ausführen des Algorithmus einen anderen Speicherzustand geben muss und die Zeitkomplexität O ( 2 n ) ist .$O(2^n)$$O(n)$$n$$O(2^n)$ -Zustände im Speicher sind erforderlich, um O ( 2 n ) $O(n)$$O(2^n)$Zeitschritte. Daher ist dieser Algorithmus im ungünstigsten Fall für die Komplexität optimal.