Estimating the Partition Function of 2-D Fields and the Capacity of Constrained Noiseless 2-D Channels

62009 IEEE Information Theory WorkshopEstimating the Partition Function of 2-D Fields andthe Capacity of Constrained Noiseless 2-DChannels Using Tree-Based Gibbs SamplingHans-Andrea Loeliger and Mehdi MolkaraieETH ZurichDept. of Information Technology & Electrical Engineering8092 Zurich,¨ SwitzerlandEmail:floeliger, molkaraig@isi.ee.ethz.ch= = = =Abstract—Tree-basedGibbssampling(proposedbyHamzeandde Freitas) is used to compute a Monte-Carlo estimate of thepartition function of factor graphs with cycles. The proposedmethod can be used, in particular, to compute the capacity ofnoiseless constrained 2-D channels.= = = =I. INTRODUCTIONLetX ;X ;:::;X be finite sets, letX be the Cartesian1 2 N4productX =X X :::X , and letf be a nonnegative1 2 N= = = =function f :X!R. We are interested in computing (exactlyor approximately) the quantityX4Z = f(x) (1)x2X= = = =1(or, equivalently, logZ) for cases whereN Fig. 1. Forney-style factor graph for Example 1. The unlabeled boxes X ;:::X are “small” sets (e.g.,jXj =jXj =::: = 2), represent factors as in (4).1 N 1 2 N is large, and f has a “useful” factorization (as will be detailedvalue 1. Letf be the indicator function of this constraint, which canbelow).be factored into factors of the formNote that14 0; if x =x = 1k ‘(x ;x ) = (4)p(x) = f(x) (2) k ‘1; else,Zis a probability mass function onX . We will also need the set with one such factor for each adjacent pair (x ;x ).k ‘The ...