Comment itérer sur des vecteurs par ordre de probabilité dans un petit espace

Considérons un vecteur dimensionnel v où v i ∈ { 0 , 1 } . Pour chaque i, nous connaissons p i = P ( v i = 1 ) et supposons que les v i sont indépendants. En utilisant ces probabilités, existe-t-il un moyen efficace d'itérer sur des vecteurs binaires de dimension n dans l'ordre du plus probable au moins probable (avec des choix arbitraires pour les liens) en utilisant l'espace sublinéaire dans la taille de sortie? $n$$v$$v_i \in \{0,1\}$$i$$p_i = P(v_i = 1)$$v_i$$n$

Prenons par exemple . Le vecteur le plus probable est ( 1 , 0 , 1 ) et le moins probable est { 0 , 1 , 0 } . $p = \{0.8, 0.3, 0.6\}$$(1,0,1)$$\{0,1,0\}$

Pour un très petit, nous pourrions étiqueter chacun des 2 n vecteurs avec sa probabilité et simplement trier, mais cela n'utiliserait bien sûr pas encore l'espace sublinéaire.$n$$2^n$

Une variante proche de cette question a déjà été posée sur /cs/24123/how-to-iterate-over-vectors-in-order-of-probability .

Ce qui suit donne un algorithme qui utilise environ temps et 2 n / 2 espace.$2^n$$2^{n/2}$

Examinons d'abord le problème du tri des sommes de tous les sous-ensembles de éléments.$n$

Considérez ce sous-problème: vous avez deux listes triées de longueur , et vous souhaitez créer une liste triée des sommes par paire des nombres dans les listes. Vous souhaitez le faire dans un temps d'environ O ( m 2 ) (la taille de sortie), mais dans un espace sublinéaire. Nous pouvons atteindre un espace O ( m ) . Nous gardons une file d'attente prioritaire et retirons les sommes de la file d'attente prioritaire dans l'ordre croissant.$m$$O(m^2)$$O(m)$

Soit les listes et b 1 … b m , triées par ordre croissant. Nous prenons les m sommes a i + b 1 , i = 1 … m , et les mettons dans une file d'attente prioritaire.$a_1 \ldots a_m$$b_1 \ldots b_m$$m$$a_i + b_1$$i = 1 \ldots m$

Maintenant, lorsque nous tirons la plus petite somme restante de la file d'attente prioritaire, si j < m nous mettons alors la somme a i + b j + 1 dans la file d'attente prioritaire. L'espace est dominé par la file d'attente prioritaire, qui contient toujours au plus m sommes. Et le temps est O ( m 2 log m ) , puisque nous utilisons O ( log m ) pour chaque opération de file d'attente prioritaire. Cela montre que nous pouvons faire le sous-problème en O ( m $a_i + b_j$$j < m$$a_i + b_{j+1}$$m$$O(m^2 \log m)$$O(\log m)$ temps et O ( m ) espace.$O(m^2 \log m)$$O(m)$

Maintenant, pour trier les sommes de tous les sous-ensembles de nombres, nous utilisons simplement ce sous-programme où la liste a i est l'ensemble des sommes des sous-ensembles de la première moitié des éléments, et la liste b i est l'ensemble des sommes des sous-ensembles de la seconde moitié des articles. On peut retrouver ces listes récursivement avec le même algorithme.$n$$a_i$$b_i$

Nous allons maintenant considérer le problème d'origine. Soit l'ensemble des coordonnées qui sont 0 et S 1 l'ensemble des coordonnées 1 . Alors ∏ i ∈ S 0 p ( v i = 0 ) ∏ i ∈ S 1 p ( v i = 1 $S_0$$0$$S_1$$1$

$$\begin{eqnarray*}\prod_{i \in S_0} p(v_i=0) \prod_{i \in S_1} p(v_i=1) &=& \prod_{1\leq i \leq n} p(v_i=0) \prod_{i \in S_1} \frac{p(v_i=1)}{p(v_i=0)} \\ &=& \prod_{1\leq i \leq n} p(v_i=0) \exp\,\left(\sum_{i \in S_1} \log \frac{p(v_i=1)}{p(v_i = 0)}\right).\end{eqnarray*}$$

Le tri de ces nombres revient à trier les nombres , nous avons donc réduit le problème du tri des sommes des sous-ensembles de n éléments.$\sum_{i\in S_1}\log p(v_i=1) - \log p(v_i=0)$$n$

$O(n)$

1. $x \in \{0,1\}^n$$O(n)$$r(x)$$x$$x'$$p(x') > p(x)$$x'\in \{0,1\}^n$$x'$$p(x') > p(x)$$r(x)$$x$
2. $k$$x$$r(x) = k$$O(n)$$x \in \{0,1\}^n$$x$$r(x)$$x$$r(x) = k$
3. $k$$0$$2^n-1$$k$$x$$r(x) =k$

(Nous devons également nous occuper des liens possibles, mais ce n'est pas difficile.)

Modifier: cette réponse est incorrecte. Voir les commentaires pour plus de détails. ~ gandaliter

$O(2^n)$$O(n)$

1. $(i, p_i)$$\left|0.5 - p_i\right|$

2. $v$$v_i$$1$$p_i > 0.5$$0$$v$$v_i$$v$

3. Appelez cette fonction récursive sur la liste triée et un vecteur vide.

$0$$1$$0.5$

$O(2^n)$$O(n)$$n$$O(2^n)$$O(n)$$O(2^n)$pas de temps. Par conséquent, cet algorithme est optimal dans le pire des cas.