Probabilité marginale de générer un arbre

Question

Fixez un graphique fini $ g= (v, e) $ et un sommet $ x / span >.

Supposons que je génère un sous-arbre aléatoire de $ g $ de taille $ n $ , contenant $ x $ , comme suit:

1. laisse $ t_0={x \} $ .
.

2. pour 0 $

   i. Laissez $ b_n $ être l'ensemble des voisins de $ t_ {n-1} $ en dehors de $ T_ {N-1} $ .

   ii. Formulaire $ t_n $ par

   • échantillon d'une paire $ (x_n, y_n) \ in e (g) \ cap \ gauche (v (t_ {n-1}) \ fois b_n \ droite) $ < / span>, avec probabilité $ q_n (x_n, y_n | t_ {n-1}) $ ,
   • ajout $ y_n $ to $ v (t_ {n-1}) $ et ajouter $ (x_n, y_n) $ à $ e (t_ {n-1}) $ .

3. retour $ t_n $ .

Supposons aussi que $ q_n (x_n, y_n (x, y_n | t_ {n-1}) $ peut être calculé facilement pour tous $ (T_ {n-1}, x_n, y_n) $ . Je suis intéressé par le calcul efficacement et exactement la probabilité marginale de générer l'arborescence $ t_n $ , étant donné que j'ai commencé à le développer à $ T_0={x \} $ , c'est-à-dire

$$ p (t_n | t_0={x \})=sum_ {x_ {1: n}, y_ {1: n}} \ prod_ {n= produit 1} ^ n q_n (x_n, y_n | t_ {n-1}). $$

ma question est essentiellement si je devrais vous attendre à pouvoir trouver un algorithme efficace (c'est-à-dire polynôme) pour cela, et si oui, ce que cela pourrait être.

Certaines pensées:

• naïvement, la somme a de manière exponentielle-de plusieurs termes, qui empêche d'évaluer la somme directement.

• D'autre part, ce problème est également hautement structuré (arbres, récursions, etc.), ce qui pourrait suggérer qu'une sorte d'approche de programmation dynamique serait réalisable. Je ne suis pas sûr de savoir exactement comment aborder cela.

• lié, je sais calculer comment calculer des estimateurs non négatifs non négatifs de $ p (t_n | t_0=\ \ \ x \}) $ , qui avoir des propriétés de variance raisonnables, en utilisant des techniques de filtrage séquentiel de Monte Carlo / Particule. Cela suggère que le problème est au moins possible d'approcher bien dans une quantité de temps raisonnable.

Answer 1

non. Si $ q (x_n, y_n | t_ {n-1}) $ est arbitraire - il peut y avoir une dépendance arbitraire sur $ T_ {n-1} $ - alors cela nécessite une heure exponentielle.

considérer un arbre $ t_n $ comportant un seul nœud racine, $ n-1 $ feuilles et un bord de la racine à chaque feuille. Il y a 2 ^ n $ subtraités de $ t_n $ , et en particulier, il y a 2 ^ N $ valeurs possibles de $ t_n $ qui peut se produire dans l'expression

$$ \ sum_ {x, y} \ prod_ {n= 1} ^ n q_n (x_n, y_n | t_ {n-1}). $$

On peut utiliser un argument adversaire simple pour prouver que l'évaluation de cette expression nécessite une heure exponentielle. Supposons que nous évaluions $ q_n (x_n, x_n | t_ {n-1}) $ en interrogeant un oracle avec $ x_n , y_n, t_ {n-1} $ . Supposons qu'il y ait un seul arbre $ t $ qui n'est jamais interrogé à l'oracle comme n'importe quel $ t_ {n-1} $ . Choisissez la totalité de la $ Q_N (\ CDOTS) $ Valeurs pour être strictement positive. Puis depuis $ q_n (x_n, y_n | t) $ n'a pas été interrogé pendant l'exécution, nous pouvons le choisir après avoir observé la sortie de l'algorithme; Mais en faisant varier, nous pouvons choisir une valeur qui rend le problème de la sortie de l'algorithme (en particulier, la valeur de l'expression dépend de $ q_n (x_n, y_n | t) $ Mais la sortie de l'algorithme ne dépend pas de $ q_n (x_n, y_n | t) $ , de sorte que la sortie de l'algorithme ne peut pas corriger). Nous avons prouvé que, pour produire la sortie correcte, tout algorithme correct doit interroger l'oracle pour tous 2 ^ n $ sous-arbres possibles de $ T_N $ . Il faut au moins $ o (1) $ temps pour interroger un oracle.

En conclusion, cet argument prouve que tout algorithme correct pour calculer cette expression doit prendre $ \ omega (2 ^ n) $

heure.

Je ne sais pas si cela peut toujours être fait dans $ o (2 ^ n) $ temps, ou s'il peut être $ O (n!) $ peut être requis.