Probabilidad Marginal de la Generación de un Árbol

Question

Corregir algunos finito gráfico $G = (V, E)$, y algunos vértice $x$.

Supongamos que generar al azar una sub-árbol de $G$ de tamaño $N$, que contiene $x$, como sigue:

1. Vamos $T_0 = \{ x \}$.

2. Para $0 < n \leqslant N$

   yo.Vamos $B_n$ el conjunto de los vecinos de $T_{n-1}$ fuera de $T_{n-1}$.

   ii.Formulario $T_n$ por

   • Ejemplo de un par de $(x_n, y_n) \in E(G) \cap \left( V (T_{n-1}) imes B_n ight)$, con una probabilidad de $q_n (x_n, y_n | T_{n-1} )$,
   • Agregar $y_n$ a $V(T_{n-1})$, y agregar $(x_n, y_n)$ a $E (T_{n-1})$.

3. Volver $T_N$.

Supongamos también que $q_n ( x_n, y_n | T_{n-1} )$ puede ser calculada fácilmente para todos $(T_{n-1}, x_n, y_n)$.Estoy interesado en forma eficiente y exactamente el cálculo de la probabilidad marginal de la generación del árbol $T_N$, dado que comenzó a crecer en $T_0 = \{ x \}$, es decir,

$$P(T_N | T_0 = \{ x \}) = \sum_{x_{1:N}, y_{1:N}} \prod_{n = 1}^N q_n (x_n, y_n | T_{n-1} ).$$

Mi pregunta es, esencialmente, si debo esperar a ser capaz de encontrar un eficiente (es decir,polinomio de tiempo) para el algoritmo de esto, y si es así, ¿qué podría ser.

Algunas ideas:

• Ingenuamente, la suma tiene exponencialmente-muchos de los términos, lo que impide tratar de evaluar la suma directa.

• Por otro lado, este problema es también altamente estructurado (árboles, la recursividad, etc.), lo que podría sugerir que algún tipo de programación dinámica sería factible.No estoy seguro exactamente de cómo acercarse a este.

• Relatedly, sé cómo calcular el imparcial, no negativo estimadores de $P(T_N | T_0 = \{ x \})$, que han razonable de propiedades de la varianza, mediante el uso de técnicas de Secuenciales de Monte Carlo / partícula de filtrado.Esto sugiere que el problema es al menos posible aproximar bien en una cantidad de tiempo razonable.

Answer 1

no. Si $ q (x_n, y_n | t_ {n-1}) $ es arbitrario: puede haber una dependencia arbitraria en $ T_ {n-1} $ - entonces esto requiere tiempo exponencial.

Considere un árbol $ t_n $ que tiene un solo nodo raíz, $ n-1 $ hojas , y un borde de la raíz a cada hoja. Hay $ 2 ^ n $ subárboles de $ t_n $ , y en particular, hay $ 2 ^ n $ valores posibles de $ t_n $ que pueden ocurrir en la expresión

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

Se puede usar un argumento de adversario simple para demostrar que la evaluación de esta expresión requiere tiempo exponencial. Supongamos que evaluamos $ q_n (x_n, x_n | t_ {n-1}) $ al consultar un oráculo con $ x_n , y_n, t_ {n-1} $ . Supongamos que hay un solo árbol $ t $ que nunca se consulta al oráculo como cualquier $ t_ {n-1} $ . Elija todo el $ q_n (\ cdots) $ valores para ser estrictamente positivos. Luego, desde $ q_n (x_n, y_n | t) $ no se preguntó durante la ejecución, podemos elegirlo después de observar la salida del algoritmo; Pero al variarlo, podemos elegir un valor que hace que la salida del algoritmo sea incorrecta (en particular, el valor de la expresión depende de $ q_n (x_n, y_n | t) $ Pero la salida del algoritmo no depende de $ q_n (x_n, y_n | t) $ , por lo que la salida del algoritmo no puede corregir). Hemos demostrado que, para producir la salida correcta, cualquier algoritmo correcto debe consultar el Oracle para todos $ 2 ^ n $ posibles subárboles de $ T_n $ . Se necesita al menos $ o (1) $ tiempo para consultar un oráculo.

En conclusión, este argumento demuestra que cualquier algoritmo correcto para computar esta expresión debe tomar $ \ omega (2 ^ n) $ tiempo.

No sé si siempre se puede hacer en $ o (2 ^ n) $ tiempo, o si quizás $ O (n!) $ El tiempo podría ser requerido.