# Marginal Probability of Generating a Tree

Fix some finite graph $$G = (V, E)$$, and some vertex $$x$$.

Suppose I generate a random sub-tree of $$G$$ of size $$N$$, containing $$x$$, as follows:

1. Let $$T_0 = \{ x \}$$.
2. For $$0 < n \leqslant N$$

i. Let $$B_n$$ be the set of $$y \in V$$ such that $$y \notin V(T_{n-1})$$, and such that $$(x, y) \in E \text{ for exactly one } x \in V(T_{n-1})$$.

ii. Form $$T_n$$ by

• Selecting some $$y_n \in B_n$$ with probability $$q_n (y_n | T_{n-1} )$$,
• Adding it to $$T_{n-1}$$, and
• Adding the edge between $$y$$ and its neighbour in $$V (T_{n-1})$$.
3. Return $$T_N$$.

Suppose also that $$q_n (y_n | T_{n-1} )$$ can be computed easily for all $$(T_{n-1}, y_n)$$. I am interested in efficiently calculating the marginal probability of generating the tree $$T_N$$, given that I began growing it at $$T_0 = \{ x \}$$, i.e.

$$P(T_N | T_0 = \{ x \}) = \sum_{y_1, \cdots, y_N} \prod_{n = 1}^N q_n (y_n | T_{n-1} ).$$

My question is essentially whether I should expect to be able to find an efficient (i.e. polynomial-time) algorithm for this, and if so, what it might be.

Some thoughts:

• Naively, the sum has exponentially-many terms, which precludes trying to evaluate the sum directly.

• On the other hand, this problem is also highly-structured (trees, recursion, etc.), which might suggest that some sort of dynamic programming approach would be feasible. I’m not sure of exactly how to approach this.

• Relatedly, I know how to calculate unbiased, non-negative estimators of $$P(T_N | T_0 = \{ x \})$$, which have reasonable variance properties, by using techniques from Sequential Monte Carlo / particle filtering. This suggests that the problem is at least possible to approximate well in a reasonable amount of time.