title: Counting solutions from finite samplings.
abstract: We formulate the solution counting problem within the framework of the inverse Ising problem and use fast belief propagation equations to estimate the entropy whose value provides an estimate of the true one. We test this idea on both diluted models [random 2-SAT (2-satisfiability) and 3-SAT problems] and a fully connected model (binary perceptron), and show that when the constraint density is small, this estimate can be very close to the true value. The information stored by the salamander retina under the natural movie stimuli can also be estimated, and our result is consistent with that obtained by the Monte Carlo method. Of particular significance is that the sizes of other metastable states for this real neuronal network are predicted.
authors.affiliation: State Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
authors.forename: Haiping
authors.initials: H
authors.lastname: Huang
authors.forename: Haijun
authors.initials: H
authors.lastname: Zhou
mesh_terms: D019277:Entropy; D008962:Models, Theoretical; D018401:Sample Size; D013269:Stochastic Processes