Research Article Open Access

A Flexible, Real-Time Algorithm for Simulating Correlated Random Fields and Its Properties

Michael A. Kouritzin1, Fraser Newton1 and Biao Wu1
  • 1 University of Alberta, Canada

Abstract

Contemporary real-time problems like CAPTCHA generation and optical character recognition can be solved effectively using correlated random fields. These random fields should be produced on a graph in order that problems of any dimension and shape can be handled. However, traditional solutions are often too slow, inaccurate or both. Herein, the Quick Simulation Random Field algorithm to produce correlated random fields on general undirected graphs is introduced. It differs from prior algorithms by completing the graph and setting the unspecified covariances to zero, which facilitates analytic study. The Quick Simulation Random Field graph distribution is derived within and the following questions are studied: (1) For which marginal pmfs and covariances will this algorithm work? (2) When does the marginal property hold, where the sub-graph distribution of an algorithm-simulated field matches the distribution of the algorithm-simulated field on the subgraph? (3) When does the permutation property hold, where the vertex simulation order does not affect the joint distribution?

Journal of Mathematics and Statistics
Volume 13 No. 3, 2017, 197-208

DOI: https://doi.org/10.3844/jmssp.2017.197.208

Submitted On: 12 June 2017 Published On: 29 September 2017

How to Cite: Kouritzin, M. A., Newton, F. & Wu, B. (2017). A Flexible, Real-Time Algorithm for Simulating Correlated Random Fields and Its Properties. Journal of Mathematics and Statistics, 13(3), 197-208. https://doi.org/10.3844/jmssp.2017.197.208

  • 1,621 Views
  • 962 Downloads
  • 2 Citations

Download

Keywords

  • Simulation
  • Correlated Random Field
  • Markov Random Field
  • Graph
  • Coupling
  • Permutation Property