A graph theoretic approach to simulation and classification

A new class of discrete random fields designed for quick simulation and covariance inference under inhomogeneous conditions is introduced and studied. Simulation of these correlated fields can be done in a single pass instead of relying on multi-pass convergent methods like the Gibbs Sampler or other Markov chain Monte Carlo algorithms. The fields are constructed directly from an undirected graph with specified marginal probability mass functions and covariances between nearby vertices in a manner that makes simulation quite feasible yet maintains the desired properties. Special cases of these correlated fields have been deployed successfully in data authentication, object detection and CAPTCHA11An acronym for “Completely Automated Public Turing test to tell Computers and Humans Apart” that is widely used to protect online resources from abuse by automated agents. generation. Further applications in maximum likelihood estimation and classification such as optical character recognition are now given within.