×

Efficient recursion for general factorisable models. (English) Zbl 1162.62310

Summary: Let \(n\) \(S\)-valued categorical variables be jointly distributed according to a distribution known only up to an unknown normalising constant. For an unnormalised joint likelihood expressible as a product of factors, we give an algebraic recursion which can be used for computing the normalising constant and other summations. A saving in computation is achieved when each factor contains a lagged subset of the components combining in the joint distribution, with maximum computational efficiency as the subsets attain their minimum size. If each subset contains at most \(r+1\) of the n components in the joint distribution, we term this a lag-\(r\) model, whose normalising constant can be computed using a forward recursion in \(O(S^{r+1})\) computations, as opposed to \(O(S^n)\) for the direct computation. We show how a lag-r model represents a Markov random field and allows a neighbourhood structure to be related to the unnormalised joint likelihood. We illustrate the method by showing how the normalising constant of the Ising or autologistic model can be computed.

MSC:

62E10 Characterization and structure theory of statistical distributions
65C60 Computational problems in statistics (MSC2010)
62M40 Random fields; image analysis
PDFBibTeX XMLCite
Full Text: DOI