Probabilidade marginal de gerar uma árvore

Question

Corrija algum gráfico finito $G = (V,E)$, e algum vértice $x$.

Suponha que eu gere uma subárvore aleatória de $G$ de tamanho $N$, contendo $x$, do seguinte modo:

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

2. Para $0 < n \leqslant N$

   eu.Deixar $B_n$ seja o conjunto de vizinhos de $T_{n-1}$ fora de $T_{n-1}$.

   ii.Forma $T_n$ por

   • Experimente um par $(x_n, y_n) \in E(G) \cap \left( V (T_{n-1}) imes B_n ight)$, com probabilidade $q_n (x_n, y_n | T_{n-1} )$,
   • Adicionar $y_n$ para $V(T_{n-1})$, e adicione $(x_n, y_n)$ para $E(T_{n-1})$.

3. Retornar $T_N$.

Suponha também que $q_n ( x_n, y_n | T_{n-1} )$ pode ser calculado facilmente para todos $(T_{n-1}, x_n, y_n)$.Estou interessado em calcular com eficiência e exatidão a probabilidade marginal de gerar a árvore $T_N$, visto que comecei a cultivá-lo em $T_0=\{x\}$, ou seja

$$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} ).$$

Minha pergunta é essencialmente se devo esperar encontrar um eficiente (ou seja,algoritmo de tempo polinomial) para isso e, em caso afirmativo, o que poderia ser.

Alguns pensamentos:

• Ingenuamente, a soma tem muitos termos exponencialmente, o que impede tentar avaliar a soma diretamente.

• Por outro lado, este problema também é altamente estruturado (árvores, recursão, etc.), o que pode sugerir que algum tipo de abordagem de programação dinâmica seria viável.Não tenho certeza de exatamente como abordar isso.

• Da mesma forma, sei como calcular estimadores imparciais e não negativos de $P(T_N | T_0 = \{ x \})$, que possuem propriedades de variância razoáveis, utilizando técnicas de Monte Carlo Sequencial/filtragem de partículas.Isso sugere que é pelo menos possível aproximar bem o problema em um período de tempo razoável.

Answer 1

Não.Se $q(x_n,y_n|T_{n-1})$ é arbitrário - pode haver uma dependência arbitrária de $T_{n-1}$ - então isso requer tempo exponencial.

Considere uma árvore $T_N$ que tem um único nó raiz, $N-1$ folhas e uma borda da raiz a cada folha.Há $2^N$ subárvores de $T_N$, e em particular, existem $2^N$ possíveis valores de $T_n$ que pode ocorrer na expressão

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

Pode-se usar um argumento simples do adversário para provar que a avaliação desta expressão requer tempo exponencial.Suponha que avaliemos $q_n(x_n,x_n|T_{n-1})$ consultando um oráculo com $x_n,y_n,T_{n-1}$.Suponha que haja uma única árvore $T$ que nunca é questionado ao oráculo como qualquer $T_{n-1}$.Escolha todos os $q_n(\cdots)$ valores sejam estritamente positivos.Então desde $q_n(x_n,y_n|T)$ não foi consultado durante a execução, podemos escolhê-lo após observar a saída do algoritmo;mas variando-o, podemos escolher um valor que torne a saída do algoritmo errada (em particular, o valor da expressão depende de $q_n(x_n,y_n|T)$ mas a saída do algoritmo não depende de $q_n(x_n,y_n|T)$, então a saída do algoritmo não pode ser corrigida).Provamos que, para produzir a saída correta, qualquer algoritmo correto deve consultar o oráculo para todos $2^N$ possíveis subárvores de $T_N$.É preciso pelo menos $O(1)$ hora de consultar um oráculo.

Em conclusão, este argumento prova que qualquer algoritmo correto para calcular esta expressão deve tomar $\Ômega(2^N)$ tempo.

Não sei se isso sempre pode ser feito em $O(2^N)$ tempo, ou se talvez $O(N!)$ pode ser necessário algum tempo.