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.