Generating junction trees of decomopsable graphs with the Christmas tree algorithm

The junction tree representation provides an attractive structural property for organizing a decomposable graph. In this study, we present a novel stochastic algorithm which we call the Christmas tree algorithm for building of junction trees sequentially by adding one node at a time to the underlying decomposable graph. The algorithm has two important theoretical properties. Firstly, every junction tree and hence every decomposable graph have positive probability of being generated. Secondly, the transition probability from one tree to another has a tractable expression. These two properties, along with the reversed version of the proposed algorithm are key ingredients in the construction of a sequential Monte Carlo sampling scheme for approximating distributions over decomposable graphs, see Olsson et al. [2016]. As an illustrating example, we specify a distribution over the space of junction trees and estimate of the number of decomposable graph through the normalizing constant.QC 20170915