{'fraction_non_alphanumeric': 0.06786151960784313, 'fraction_numerical': 0.0156906512605042, 'mean_word_length': 3.602840451248993, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Properties of Quick Simulation Random Fields

Herein, we introduce and study a new class of discrete random fields designed for quick simulation and covariance inference under inhomogeneous condition. 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 methods. The fields are constructed directly from specified marginal probability mass functions and covariances between nearby sites. The proposition on which the construction is based establishes when and how it is possible to simplify the conditional probabilities of each site given the other sites in a manner that makes simulation quite feasible yet maintains desired marginal probabilities and covariances between sites. Special cases of these correlated fields have been deployed successfully in data authentication, object detection and image generation. The limitations that must be imposed on the covariances and marginal probabilities in order for the algorithm to work are studied. What's more, a necessary and sufficient condition that guarantees the permutation property of correlated random fields are investigated. In particular, Markov random fields as a subclass of correlated random fields are derived by a general and natural condition. Consequently, a direct and flexible single pass algorithm for simulating Markov random fields follows.


Introduction
Random fields are widely used in sciences and technologies to model spatially distributed random phenomena or objects. Within sciences, random fields are used in geophysics, astrophysics, statistical mechanics, underwater acoustics, structural biology and agriculture. Applications of random fields in technologies include TV signal processing, image processing in photography such as medical images (human brain imaging, functional magnetic resonance imaging, mammography), computer vision, web data extraction, clustering gene expression time series, natural language processing etc. Readers are referred to [1], [5], [11], [12], [13], [15], [16], [17], and [18] for those applications. Technologically, researchers of random fields have dealt either with the modeling of images (for synthesis, recognition or compression purposes) or with the resolution of various spatial inverse problems (image restoration and reconstruction, deblurring, classification, segmentation, data fusion, optical flow estimation, optical character recognition, stereo matching, finger print classification, pattern recognition, face recognition, intelligent video surveillance, sparse signal recovery, natural language processing like Chinese chunk and so on, see [4], [6], [13], [14], and [15]).
Scientists and technicians are interested in the inverse problems such as image restoration, boundary detection, tomographic reconstruction, shape detection from shading, and motion analysis. Many precisely formulated mathematical models were constructed to model certain types of random fields, and various methods and estimators have been developed to make the proposed models work in application. There are diverse needs calling for simulating random fields. For example, simulation is employed to calculate minimum mean square (MMS) and maximum posterior marginal (MPM) estimators, see [15]. Simulation can also be a potential smoothing technique. In the chapter 2 of Winkler [15], various smoothing techniques were proposed to clean "dirty" pictures. Most of these methods involve simulation. The difficult problem is how do we effectively simulate random fields. A typical simulation would involve 100,000 or more highly correlated random variables, which would certainly exceed the capacity of modern computers if one tried to simulate the whole random field directly.
Researchers frequently resort to imposing discrete Markov assumptions on their random fields to be simulated out of practical need. In this regard, the Gibbs sampler was proposed to ease this simulation difficulty. Briefly speaking, a Gibbs sampler starts with a given initial configuration (i.e. potential realization of the random field) or a configuration chosen at random from some initial distribution, and then updates its configuration site by site based on the local characteristics of the random field. Once all sites of a configuration are sequentially updated, a sweep or a pass is finished. A Gibbs sampler usually takes hundreds of sweeps to produce a configuration closely consistent with a given distribution and there are still computational and convergence issues to deal with.
In this paper, we propose a new class of discrete correlated random fields which incorporate given probability mass functions (pmfs) {π si } for all sites S = {s i } N i=1 and given covariances β si,sj between nearby sites. These fields are dsigned with efficient simulation in mind. The number of possible random configurations within a general discrete random field can be enormous and simulation is further complicated when the sites are correlated with one another. These factors can make Gibbs sampling and other Markov chain Monte Carlo simulation impractical. However, Proposition 2.1 on which our fields are based establishes a method to imbed desired covariances and marginal probabilities into a random field while maintaining simulation ease. Indeed, Proposition 2.1 is a simple means to construct some site-by-site conditional probabilities consistent with given marginal probabilities and site-to-site covariances in such a way that sampling the missing portion of a random field sequentially is very feasible. More precisely, when simulating a new site, we compute this conditional probability mass function of its state conditioned on the known portion and the previously-simulated sites. This construction establishes the sequential simulation property of our correlated random field, that is to say, we can actually construct a random field in one pass based on this algorithm, reducing the computation over the Gibbs sampler dramatically. For demonstration purposes, we discuss application of our random fields and simulation algorithm to Data Authentication, Object Detection and Image Creation.
The constraints and properties of the random fields generated by Proposition 2.1 are discussed in detail. The necessary and sufficient conditions of the regularity type are given in Proposition 5.1 when base set is a singleton. In particular, we investigate the conditions related to the marginality and permutation properties of our random fields. In the case where one wants to match the covariances between each pair of sites for S = {s i } n i=1 , the field takes the form (See Lemma 5.1) Π s1,...,sn (x s1 , ..., x sn ) (1.1) where {π si } and {π si } are two auxiliary collections of pmfs, and we study conditions onπ si ,π si , π si and β si,sj that ensure the same random field X S is constructed, regardless of site ordering. In addition, if π si ≡ π si ∀1 ≤ i ≤ n, then each pair of uncorrelated sites are actually independent. These results are given in Corllary 5.2, Proposition 5.3 and Corllary 5.3. The predominance followed from these results is to simulate true Markov random fields rather than just correlated random fields on a general site space (S, ∂). For a given (S, ∂), its neighborhood system ∂ can be extended to ∂ ′ (under ∂ ′ all sites in S are neighbors of each other) by setting those pair of sites which are not neighbors of each other have covariances 0, i.e., for each s ∈ S, if any t / ∈ ∂(s), let β s,t = 0. Herein, we develop a direct and flexible algorithm from Proposition 5.3 to generate site-order invariant Markov random fields, i.e., the simulated Markov random field does not depend on the particular site order generating it. This subclass of random fields require stronger assumptions and have nicer properties, compared to the correlated random fields generated by Proposition 2.1.
The remainder of this note is laid out as follows: Section 2 contains our notation and the statement of our main results, Proposition 2.1. Next, we explain our simulation algorithm in Section 3. In section 4, we summarize our prior applications of our simulation algorithm to image analysis. In Section 5, we explore its properties and constraints. We give the necessary and sufficient conditions of the regularity type for singleton case of A si in Proposition 5.1. We also give a necessary and sufficient condition for the permutation property of a random field in Proposition 5.2 and 5.3. An effective algorithm for generating Markov random field follows from these propositions. Section 6, the Appendix, contains our proofs of Lemma 2.1 and of Proposition 2.1.

Notation and Background
In this section, we recall some random field notation from Winkler [15], introduce new concepts, and state a proposition from which our novel random fields and algorithm follow. Let S be a finite index set of sites; and for each site s ∈ S, X s be a finite space of states at site s. For nonempty A ⊂ S, denote the space of configurations x A = (x s ) s∈A on A by X A = s∈A X s . If A = S, we abbreviate X S by X , i.e., X = s∈S X s .
Let Π denote a probability measure or distribution on X . If for every x ∈ X , Π(x) > 0, i.e., Π is a strictly positive probability measure on X , then Π is called a random field. We also call the random vector X = (X s ) s∈S on the probability space (X , Π) a random field. For a nonempty A ⊂ S, define the projection map from X onto X A as follows: The definitions of neighborhood system and Markov random field follow directly from Winkler [15]: s ∈ S} of S is any collection of subsets of S that satisfies the conditions: (i) s / ∈ ∂(s) for every s ∈ S and (ii) s ∈ ∂(t) if and only if t ∈ ∂(s). The sites t ∈ ∂(s) are called neighbors of s. Definition 2.2. The random field Π is a Markov random field with respect to the neighborhood system ∂ if for all x ∈ X , We will introduce the notions of base set and one pass simulatable respectively. These concepts rely on the following definitions and discussion. First, the neighborhood of nonempty set generalizes the neighborhood of single site: that is the neighbors of the sites in A that are not part of A themselves. For convenience, let ∂(∅) = S, i.e., the neighborhood of empty set ∅ is all sites S.
Next, we define exclusiveness, connectedness and separateness for subsets of site space S based on the neighborhood of nonempty set: In the above definition, [B 1 ∂(B 1 )] B 2 = ∅ and B 1 [B 2 ∂(B 2 )] = ∅ are equivalent, i.e., one implies the other. Separateness of a nonempty subset B implies that there exist two subsets B 1 , B 2 which are exclusive such that B = B 1 B 2 .
In some applications, e.g. image restoration and shape detection from shading, a site space S is divided into two parts: good part and bad part, or known part and unknown part. Herein, we let H ⊂ S denote the bad or unknown part, and H C ⊜ S \ H the good or known part of the site space S. For a nonempty subset H of a connected space (S, ∂), we can order its sites sequentially and associate each site with a connected set, which is a subset of the neighborhood of the site: The set A si is called the base set for site s i .
We are really interested in using a valid setup to simulate the unknown portion of a random field.
Definition 2.6. The unknown states H of a discrete random field Π are one pass or sequentially simulatable Then, by the multiplication rule one has that for any configuration x ∈ X is given: (2.1) From this configuration probability, we can find the probability of any set of sites B. When B ⊂ {s 1 , ..., s j } for some j, we need only compute the product of the first j terms and this formula can be used to compute Π(X Kolmogorov's consistency conditions consist of permutation condition and marginality condition. These conditions were applied to Kolmogorov's extension theorem to gurantee the unique existence (almost surely) of stochastic process that can degenerate to given families of random vectors. These conditions also light up those good properties that Markov random fields satisfy. For each integer 1 < n ≤ N , let M n contain n elements and G Mn be the symmetric group consisting of all permutations on M n . Then we define the consistency conditions for discrete random field as follows: and X H C be the known portion of the random field. For each 1 ≤ k ≤ n, and each M k = {i 1 , ..., i k } ⊆ {1, · · · , n} and g ∈ G M k , let Π s g(i 1 ) ,...,s g(i k ) (·|X H C = x H C ) (if it can be defined the same way as Π si 1 ,...,si k (·|X H C = x H C )) be a probability mass function on X s g(i 1 ) ,...,s g(i k ) = k u=1 X s g(iu ) . The two consistency conditions for the collection of probability mass functions {Π s g(i 1 ) ,...,s g(i k ) , · · · , n}, 1 ≤ k ≤ n} are listed as follows.
(1) permutation: (2) marginality: Note that in the above definition, it can happen that some Π s g(i 1 ) ,...,s g(i k ) (·|X H C = x H C ) are not defined. For example, for g on M n = {1, · · · , n}, the sites in H can be ordered by g as {s g(i) } n i=1 , but it may fail that s g(i) ∈ ∂(H C {s g (1) , · · · , s g(i−1) }) for some 1 ≤ i ≤ n. In such case, we do not have Π s g(1) ,...,s g(n) defined. But if Π s g(1) ,...,s g(n) is defined indeed, then the permutation property states that the random fields on H generated by the order X s1 , ..., X sn and the order X s g(1) , ..., X s g(n) are the same. So the condition for permutation property assures that X H on H can be simulated in any site order, given X H can be generated in such order. Note also permutation property is not required or recommended for some type of random fields such as discrete time series. The marginality condition ensures that random field X H1 generated directly on a proper subset H 1 ⊂ H is the same as that degenerated from X H .
When simulating X si , one has access to X H C {X s1 , ..., X si−1 }, the known sites and the sites already simulated, but need only use X As i . This reduction is the key that makes one-pass sequential simulation effective when the base sets are relatively small compared to H. We will explain how this can be done when one is just interested in simulating a field with given marginal probabilities and certain covariances. For the case H = S, since H C = ∅, the conditioning X H C = x H C disappears from (2.1) and (2.2), leading to an easier-to-assimulate means of constructing a random field. Conversely, the case H ⊂ S is advantageous for real applications.
Herein, we simulate random fields with given marginal probabilities for sites and given covariances between nearby (meaning within the base sets however they are defined) sites for a subset H of a connected space (S, ∂) with N sites. We assume a valid setup {(s i , A si )} n i=1 for H. Our algorithm constructs X H with the given marginal probabilities {π si (x si ) : x si ∈ X si } n i=1 and the given covariances between nearby sites {β si,ti : t i ∈ A si } for 1 ≤ i ≤ n. (It is assumed a priori that these marginal conditions hold within the used set of known sites (∪ n i=1 A si )\H. It is also assumed that β si,ti = β ti,si for t i ∈ A si (1 ≤ i ≤ n) since β si,ti will denote covariance between X si and X ti ). We assign conditional probabilities Π(X si = x si | X As i = x As i ), such that we maintain the desired covariances and marginal probabilities as we include the unknown sites: Proposition 2.1. Assume that (S, ∂) is a connected space of N > 2 sites, H is a subset of n ≥ 1 sites with valid setup {(s i , A si )} n i=1 and X H C is the known portion of the random field. Suppose further that {π s (x s ) : x s ∈ X s , s ∈ S} and {π s (x s ) : x s ∈ X s , s ∈ S} are two sets of pmfs. Assume that {π s (x s ) : x s ∈ X s , s ∈ S} are positive pmfs and {β si,ti : t i ∈ A si , 1 ≤ i ≤ n} are numbers such that the right hand side (RHS) of (2.3) is in [0,1] for all i. Form the conditional probabilities starting with i = 1 recursively as for each x si ∈ X si and x Then, there is a probability measure Π on X (∪ n i=1 As i )∪H consistent with (2.3) that has marginal probabilities {π si } and covariances cov(X si , X ti ) = β si,ti for all t i ∈ A si , 1 ≤ i ≤ n.
Remark 2.1. Proposition 2.1 can be used in image smoothing when H ⊂ S. For example, an image X can be smoothed in a way as follows: let H be the set of pixels with states consisting of "sharp" or undesirable values, and replace those values by simulated ones, using Proposition 2.1. H C is the portion of the picture that does not require smoothing.
Remark 2.2. The special case H = S of Proposition 2.1 deserves particular attention. When H = S, A s1 = ∅, the second term on the right hand side of (2.3) disappears since the summation is over zero terms.
Remark 2.3. In Proposition 2.1, we assumed that π s (x s ) > 0 : ∀x s ∈ X s for each s ∈ S. Note that X s can be different for each s ∈ S. For given s, if there exists a x s ∈ X s such that π s (x s ) = 0, we may deem it uninteresting and replace X s with X s \ {x s }. Therefore the positive probability mass function assumption of π s is also a convention. But forπ s andπ s , we do not need to have this assumption, i.e. the support of π s (x s ) orπ s can be a proper subset of X s .

Remark 2.4. In general we will match covariances between a site s and sites in
This is one of the connected components in ∂(s).
Remark 2.5. By definition, connectedness is based upon the notion of neighbor, and so is the Markov property of a Markov random field. The connectedness condition of the site space S guarantees that we can use the accumulated information about the neighbor states X ti , t i ∈ A si , to generate the state X si .
A random field generated by Proposition 2.1 is a correlated random field. Indeed, one value of this proposition is the assertion that there are one-pass simulatable correlated random fields that match a given collection of marginal probabilities and covariances. What's more, we will state conditions in Section 5 that convert a correlated random field into a Markov random field. We call these one-pass simulatable correlated random fields generated by Proposition 2.1 the KNW Random Fields for ease of future reference.
Remark 2.6. Proposition 2.1 has a few interesting and important special cases: In (2.4), two auxiliary collections of pmfs are reduced to one.
There are no auxiliary collections of pmfs in (2.5).
ds , x s ∈ X s for all s ∈ S where d s is the cardinality of X s , then (2.3) has the following form Here two collections of auxiliary pmfs take same discrete uniform pmfs respectively. The simplicity in (2.6) reduces the computation of conditional probabilities. Notice theμ s andσ 2 s calculations are simplified. (4) Ifπ s (x s ) = 1 ds andπ s (x s ) = π s (x s ), ∀x s ∈ X s for all s ∈ S with d s being the cardinality of X s , then (2.3) is changed to where D As i \{ti} = ui∈As i \{ti} d ui . Here one collection of auxiliary pmfs take discrete uniform pmfs and another collection is identitical to the prescribed {π s }. (5) If we assume the sufficient condition for permutation property of a random field (see Corollary 5.2):π s (x s ) = π s (x s ), ∀x s ∈ X s for all s ∈ S, then (2.3) becomes Assume that the space of states X s for all s ∈ S is same and is denoted by . In this case, auxiliary pmfs {π s } are identically distributed, so are {π s }.
(7) If we combine the assumptions for formula (2.6) and (2.9) together, i.e., X s = X andπ s (x s ) = π s (x s ) = 1 d , x s ∈ X for all s ∈ S where d is the cardinality of X, then (2.3) takes the following simple form (2.10) is used in [10] for Captcha generation.
Insomuch as the case H = S only involves a notational change, the remainder of this note will only consider the case H = S and will not state it anymore. For example, in the appendix we will only prove Proposition 2.1 for the case H = S.  By previous discussion, we can take as well). Note that A 5 = {2, 3, 4} is a connected set with respect to the neighborhood system ∂.
Let the common space of states for each site be X = {−1, 0, 1}. To construct a probability measure Π on X = {−1, 0, 1} 5 , we use Proposition 2.1 to compute the conditional probabilities: ) as a prerequisite, using Proposition 2.1. By (2.1) and (2.2), first we compute the joint probabilities Alternatively, with the connectedness of A 5 , we can treat A 5 as S, use Proposition 2.1 again, and compute Π(X A5 = x A5 ) as follows: This later alternative method is more efficient than the former one.

Remark 2.7. Example 2.2 shows how to use the connectedness assumption on
si is the largest subset of ∂(s i ) containing A si such that the covariances between X si and X ti ( In the following diagram, those neighbors with matched covariances are connected by thick edges, and the covariance between X 1 and X 4 are not matched: Herein we can prescribe {β s,t : t ∈ ∂(s), s ∈ S} such that the random field X constructed by Proposition 2.1 satisfies cov(X s , X t ) = β s,t for any pair of neighbors s, t ∈ S (without reference to the sets A s ).
As introduced in Section 1, random fields have typical applications in two-dimensional space (e.g. Xray imaging) and three-dimensional space (e.g. human brain imaging and mammography). Herein, we present an example of two-dimensional site space and two types of its natural neighborhood systems. The three-dimensional analogue can be formulated accrodingly.
ℓ is the radius of neighborhood system ∂ ℓ on S defined as follows: for each (i, j) ∈ S, Therefore, (S, ∂ ℓ ) is a connected space. There are M N pixels in S, and we enumerate these pixels in the following sequence: be the points in S within the square distance ℓ from (i, j) that are either to the left or directly above of (i, j). The restriction to {s 1 , s 2 , ..., s (j−1)M+i−1 } ensures that only the previously simulated pixels that are to the left or directly above of (i, j) are used to generate the next pixel (i, j). One can verify that (2.12) It can also be shown that ∂ ℓ ((i, j)) {s 1 , s 2 , ..., s (j−1)M+i−1 } contains only one connected component, i.e., A ℓ (i,j) . Example 2.3 shows that the abstract connected site space (S, ∂) can have natural instances from real applications. The sequence of pixels enumerated above satisfies that s k ∈ ∂({s 1 , ..., [10] defined the same site space S as that in Example 2.3, but replaced the square distance with Euclidean distance and ℓ ∈ R + is not necessarily an integer. When ℓ ≥ √ 2, the base set A ℓ (i,j) can still be defined by (2.11) albeit (2.12) does not hold.
The neighborhood of each s i consist of 4 nodes which are connected to s i by a dashed edge as illustrated by the following graph. It can be verified that the neighborhood ∂(s i ) of each s i as a subset of S is connected. For example, Remark 2.9. Example 2.4 shows that the condition that the neighborhood of each site is connected cannot imply ∂(s i ) {s j , 1 ≤ j ≤ i − 1} is connected for all 2 ≤ i ≤ N . In fact, for abstract space (S, ∂), it is difficult to find simple condition to guarantee that A si = ∂(s i ) {s j , 1 ≤ j ≤ i − 1}, ∀2 ≤ i ≤ N . But fortunate enough, Example 2.3 illustrated that for many real random field applications, there exist natural neighborhood systems which have good properties and can satisfy our purpose very well.

Novel Algorithm for Simulating Random Fields
Let (S, ∂) be a connected space of sites, with valid setup Based on Proposition 2.1, we have a novel algorithm for simulating X with state space X , given marginal probabilities {π si (x si ) : x si ∈ X si } N i=1 and given covariances of nearby sites {β si,ti : t i ∈ A si }, for 2 ≤ i ≤ N .
Do for i = 1, . . . , N : (1) Base on Definition 2.6, compute for all chosen combinations of x s1 , ..., x si−1 . Here we choose x s1 , ..., x si−1 as follows: for each 1 ≤ k ≤ i − 1, if s k ∈ A si , we use the simulated x s k ; otherwise, we enumerate x s k ∈ X s k . (2) Take marginal to get Π(X As i = x As i ): (3) Based on Π(X As i = x As i ), compute Π( X si = x j si X As i = x As i ) for 1 ≤ j ≤ d i , using (2.3).
(4) Generate a [0, 1]-uniform random variable U . For the given U , there exists unique 1 ≤ j ≤ d i such that Then set X si = x j si . For notational convenience, we supress superscript j and use x si to indicate the simulated value x j si of X si .
Remark 3.1. There exists an alternative, more efficient way of computing Π(X As i = x As i ): View A si as S, and let {(t j , B tj )} ni j=1 be a valid setup for A si , where n i is the number of sites in A si . Now, compute Π(X As i = x As i ) as follows: In Example 2.2, we illustrated how to compute Π(X A5 = x A5 ) by treating A 5 as S.

Summary of Applications of Novel Algorithm
In this section, we summarize our prior applications of simulation algorithm of Section 3 to image generation, data authentication and target recognition.
4.1. Application to Image Generation. Generating KNW-CAPTCHAs is an application of our simulation algorithm to image analysis. CAPTCHA is the acronym for "Completely Automated Public Turing test to tell Computers and Hummans Apart" (see [2]) and is widely used to prevent online resources intended for humans from abuse by automated agents. CAPTCHAs often appear to be images of characters or digits designed easy to read by humans and difficult to crack by computer programs. Kouritzin, Newton and Wu [10] proposed a novel method for generating a type of CAPTCHAs named "KNW-CAPTCHAs" through random field simulation stated in Section 3 with common pixel state space X = {1, −1} = {black, white}. Roughly speaking, KNW-CAPTCHAs are generated by specifying proper pixel marginal probabilities and pixel-pixel covariances of alphabets and embedding these quantities into KNW conditional probabilities -formula (2.10). One predominance of this method is that these random field CAPTCHAs can be simulated in real time, yet another is significant resistance of these CAPTCHAs to attack. More details on this application can be found in [10]. With the algorithm in Section 3 and the alternative algorithm for generating Markov random field at the end of Section 5, we are also able to generate many variants of KNW-CAPTCHAs.

Data Authentication Application.
Data authentication is classifying data as true or fabricated and has been used in fraud detection and verification of data samples including financial data [7]. Detecting fake coin flip sequence was an application of our simulation algorithm to data authentication, see Kouritzin et al [8] where site space S = {1, 2, ..., N } consists of time units and coin state space is X = {1, −1} = {head, tail}. In [8], a filtering method was applied to simplified fraud-detection problem, classifying coin flip sequences as either "faked" (i.e., generated by a person) or "real" (i.e., generated by perfect flipping of a true coin). A true coin flip sequence has the expected head counts approximating 1 2 of total flips. For this reason, a faker that deviates from expected behaviour in one time period has to be compensated by later deviating from the expected behaviour in an opposite way such that deviant behaviour averages out. Consequently, marginal probabilities and pair-wise covariances between each flip and the flips that preceded in time were used to describe faker's behaviours. It followed that simulating fake coin flip sequences in real time became a fundamental step of solving the simplified fraud-detection problem. The much simpler but preceded version of the algorithm in Section 3 was developed to simulate the faked coin flip sequences which are just specific random fields on the set S with state pace X = {head, tail}.

Target Recognition Application.
Analogue of simulation algorithm in Section 3 was also applied to target recognition by Kouritzin, Luo, Newton and Wu [9]. Kouritzin et al considered an imaginary detection problem of hidden targets such as rocket launchers in random forest. The rocket lauchers sit still in forest, and a surveillance aircraft or unmanned vehicle equipped with an electro-optic camera is flying over the forest to capture the forest with hiden target rocket launchers. The camera cannot penetrate through the foliage, and the foliage blocks the latent ground objects from detection. However, the camera can observe partial images of the ground through the gaps among the leaves. The forest is random in the sense that the foliage coverage is encoded with a binary representation (i.e., foliage and no foliage), and is correlated in adjacent regions. Similarly, the ground is a mixture of the grass and soil, and its color is randomly either green or brown with some type of correlation structure. The rocket launchers are camouflaged with the colors of grass (green) and soil (brown) and have another type of correlation structure. The information from within the forest called the observations, can be easily obtained from stored historical overhead pictures and analyzed pixel by pixel for each small area. As the captcha generation, simulation algorithm similar to that in Section 3 was used to generate the image of random forest, ground and hidden targets. The weight functions used by the SERP (selectively resampling particle) filter [3] resort to Proposition 2.7 of [9], which is a specific vector version of Proposition 2.1.

Algorithm Properties and Constraints
An effective algorithm that can generate random fields is related to two properties: regularity and consistency. Regularity means that the right hand side of (2.3) is within [0,1]. Consistency means the permutation and marginality properties. In this section, we explore the constraints that can guarantee these properties. The outline of this section is as follows. First, we give the necessary and sufficient conditions of the regularity type for singleton case of A si in Proposition 5.1. Second, we consider conditions for permutation and marginality properties for A ⊆ S where sites in A are neighbors of each other. For random field X A , there are no conditions needed for the marginality property, and there exists a necessary and sufficient condition presented in Proposition 5.2 and 5.3 for the permutation property. Third, for an arbitrary site space (S, ∂), the neighborhood system ∂ is extended to ∂ ′ such that each pair of sites are neighbors of each other under ∂ ′ , i.e., for each site s ∈ S, let ∂ ′ (s) = S \ {s}. Furthermore, the covariances between each site s ∈ S and sites outside of ∂(s) are assumed to be zero. Based on these assumptions, we propose an alternative algorithm that can generate a true Markov random field with the remarkable property of consistency.
We first determine the conditions of regularity type, i.e., the constraints for {β si,ti : t i ∈ A si } N i=1 of Proposition 2.1 that cause it to produce a value in [0, 1]. A theoretical constraint relating a particular β si,ti to the given marginal probabilities {π si (x si ) : x si ∈ X si } and {π ti (x ti ) : x ti ∈ X ti } is given in the following proposition. .
By (5.2), there is no constraint on β s,t when x s = µπ s or x t = µπ t . Therefore, β s,t being consistent with a proper right hand side of (2.3) is equivalent to, for all x s ∈ X s , x s = µπ s , and x t ∈ X t , x t = µπ t . From (5.3), (5.1) follows.
In the Appendix, we will prove that By multiplying both sides of (5.4) by σ 2 πs σ 2 π t πs(xs)πt(xt) , for any x s ∈ X s , x t ∈ X t , we can verify that The inequalities in (5.6) are actually tight. If for x s ∈ X s and x t ∈ X t , Then, by (5.5), we have Therefore, by (5.2) and (5.6), (5.1) is exactly the constraint required for β s,t to be a valid covariance.
Secondly, we consider the case when A s is not a singleton. For this case, we assume that cov(X s , X t ) = β s for every t ∈ A s , i.e., the state X s on the site s has same covariance with each state in A s . A simple necessary condition on β s is given in the following corollary.
Corollary 5.1. Assume that cov(X s , X t ) = β s for each t ∈ A s . Then, a necessary condition on β s for .
Proof. For each t ∈ A s , we get a condition on β s by applying Proposition 5.1 to A s,t = {t}. (5.7) follows by combining all these conditions into one. This is also the reason that (5.7) is only necessary, not sufficient for (2.3) to be in [0,1].
Assume that A = {s i : 1 ≤ i ≤ n} ⊆ S where sites in A are neighbors of each other under ∂, we denote the joint probability mass function of X s1 , ...,X sn by Π s1,...,sn (x s1 , ..., x sn ) which by formula (2.3) satisfies: We have the following lemma giving the closed form of Π s1,...,sn (x s1 , ..., x sn ): Lemma 5.1. Based on the assumptions on A, the joint probability mass function of X s1 , ..., X sn is Π s1,...,sn (x s1 , ..., x sn ) Proof. Repeated use of (5.8) followed by (5.9) yields Π s1,...,sn (x s1 , ..., x sn ) = Π s1,...,sn−1 (x s1 , ..., x sn−1 )π sn (x sn ) +π π si (x si ). (5.11) Remark 5.1. Our KNW quick simulation random field X A on A satisfies the marginality condition defined in Definition 2.7. This can be proved by formula (5.10) and the facts that Therefore, there are no derived conditions on β si,sj (1 ≤ i = j ≤ n) and π si (1 ≤ i ≤ n) for X A to satisfy the marginality condition. Next, we determine conditions of permutation type. Assume that s, t ∈ S are neighbors of each other. We have by (2.3) and the multiplication rule that for x s ∈ X s , x t ∈ X t . Hence, Π t,s (x t , x s ) = Π s,t (x s , x t ), i.e., when we compute the joint probability of two simulated random variables X s , X t , the order of simulating X s and X t does not matter. It means that the specific form of (2.3) guarantees the permutation property of any two random variables with their sites being neighbors. This is a very desirable property of formula (2.3) when the site space S is one-dimensional, e.g., S ⊂ N. When there are n ≥ 3 sites which are neighbors of each other, we have a necessary and sufficient condition for permutation property given by Propposition 5.2 below. First, we introduce some notations and preliminary results. For each 1 ≤ i ≤ n and 1 ≤ u i ≤ d i , let In the proof of Propposition 5.2, if we use x si , omitting u i for x ui si , then we do the same thing forz ui si , i.e., we usez si . For any duple 1 ≤ i = j ≤ n, let ρ si,sj = β si,sj σπ s i σπ s j = σ πs i σ πs j σπ s i σπ s j ρ si,sj . (5.14) Note thatz ui si is the weighted standardization of the element x ui si by the weightπ si (x ui si ) andρ si,sj is an adjusted correlation coefficient of X si and X sj . Without loss of generality, we assume that ρ s1,s2 = 0 and ρ s1,sn = 0, i.e.,ρ s1,s2 = 0 andρ s1,sn = 0. We introduce d (= n i=1 d i ) variables y ui si and denote d componentsŷ For each triple 1 ≤ i, j, k ≤ n (i, j and k are distinct integers) and 1 ≤ u i ≤ d i , 1 ≤ u j ≤ d j and 1 ≤ u k ≤ d k , we formulate equations in y as follows: The coefficient matrix of the equations (5.17) is 18) for each given triple i, j and k.
(5.27) (5.24) and (5.27) together lead to the permutation property of the joint distribution of X s1 , ..., X sn . Before we discuss the solution space of the linear equations of blockwise Canonical form (5.17), we point out its trivial solution 0 where 0 is the d-mensional zero vector. This 0 implies a simple albeit special condition on the permutation property of X s1 , ..., X sn . Corollary 5.2. Assume n ≥ 3 and A = {s i : 1 ≤ i ≤ n} ⊆ S with all sites in A being neighbors of each other under ∂. Then, a sufficient condition for the permutation property of the joint distribution of X s1 , ..., X sn is thatπ si (·) ≡ π si (·) for 1 ≤ i ≤ n.
We make a very loose assumption that no distribution in {π s } s∈S , {π s } s∈S and {π s } s∈S is degenerate, i.e., being the distribution of a constant random variable. Now we discuss the structure of the solution space of the linear equations of (5.17). The solution space of (5.17) is the null space of the canonical form matrix in (5.18). This space depends on the value of n and the correlation structure among X s1 , ..., X sn , i.e. ρ si,sj (1 ≤ i < j ≤ n). We deal with the case n = 3 and the case n ≥ 4 separately.
When n = 3, i, j and k essentially have only one combination, e.g., i = 1, j = 2 and k = 3. Based on the assumption above, there exists at least one 1 ≤ǔ 1 ≤ d 1 such thatzǔ 1 s1 = 0. It follows that (5.17) has solutions: where yǔ 1 s1 is a free variable. It means that the solution space of (5.17) is one-dimensional. When n ≥ 4, it becomes more complicated. First, we define the correlation multiplication equalities.
Definition 5.1. Correlation multiplication equalities are ρ si,sj ρ s k ,s l = ρ si,s l ρ sj ,s k = ρ si,s k ρ sj ,s l (5.29) for each quadruple 1 ≤ i, j, k, l ≤ n where i, j, k and l are distinct integers. In Example 5.1, we will construct a random field whose nearby correlations indeed satisfy the correlation multiplication equalities (5.29).
For each quadruple 1 ≤ i, j, k, l ≤ n with i, j, k, l being distinct, we may consider the triples (i, j, k), (i, j, l), (i, k, l) and (j, k, l) and apply the n = 3 case to each of them. Each of the four groups of equations of blockwise canonical form has solutions formally similar to (5.28), that is to say, we can solve where yǔ 1 s1 is a free variable. It means that for the case n ≥ 4, when the conditions (5.29) are satisfied, the solution space of (5.17) is also one-dimensional.
To summarize, when n = 3, (5.17) has nonzero solutions expressed by (5.28). When n ≥ 4, (5.17) also has nonzero solutions formulated in (5.30), given the correlation multiplication equalities conditions (5.29) are satisfied. The conditions (5.29) themselves are not simple though. We need to further our investigation on the conditions that can guarantee the existence of (5.29).
Proof. By Corollary 5.2, we only need to prove the statement if X sn is uncorrelated with each X sj (1 ≤ j ≤ n − 1), then X sn is independent of {X sj } n−1 j=1 . This statement follows immediately by using formula (5.10) for the cases n and n − 1 respectively.
Even if (X s1 , X s2 ) T and (X s3 , X s4 ) T are uncorrelated, (X s1 , X s2 ) T and (X s3 , X s4 ) T are not necessarily independent. But Corollary 5.3 does provide us a way to producing a true Markov random field with the remarkable properties of marginality and permutation. Recall the concept of connected space (S, ∂) in Section 2. We extend the neighborhood system ∂ to ∂ ′ as follows: for each site s ∈ S, let ∂ ′ (s) = S \ {s} and β s,t = 0, ∀t ∈ ∂ ′ (s) \ ∂(s) = S \ (∂(s) {s}). What's more, for each site s ∈ S, because X s is uncorrelated with {X t : t ∈ S \ (∂(s) {s})}, X s is independent of {X t : t ∈ S \ (∂(s) {s})} by Corollary 5.3. Now, let's return to the original neighborhood system ∂. The previous conclusion infers that the state of each s ∈ S depends only on states of its neighbors t ∈ ∂(s), regardless of rest of the states. This exactly matches the definition of Markov random field in Definition 2.2.
Before we state an alternative algorithm to generate our KNW Markov random field with those good properties of marginality and permutation, we update formula (2.3) with the sufficient condition for permutation, i.e.,π s (·) ≡ π s (·) (s ∈ S). For any ordered sequence {s i } N i=1 of sites in S, it follows by formula (2.3) and Corollary 5.3 that where A si = ∂(s i ) {s 1 , ..., s i−1 }. Now we propose the alternative algorithm to generate the KNW Markov random field with the desired marginality and permutation properties on S: Do for i = 1, . . . , N : (1) Choose arbitrary site s ∈ S \{s 1 , ..., s i−1 } and denote it by s i . Then, let A si = ∂(s i ) {s 1 , ..., s i−1 }, and compute Π(X As i = x As i ) by treating A si as S and recursively repeating all the steps listed here. (2) Based on Π(X As i = x As i ), we compute Π( X si = x ui si X As i = x As i ) for 1 ≤ u i ≤ d i , using (5.34).
We use x si to indicate the simulated value x j si from X si .
Remark 5.3. Note that in the generation of random field X S on (S, ∂), we made the extra assumption that for each site s ∈ S, β s,t = 0, ∀t ∈ S \ (∂(s) {s}). The gain is the simplicity of the new algorithm compared to the algorithm in Section 3 and the desirable properties of marginality and permutation. This extra condition is actually necessary for generating a Markov random field, since state of each site on a Markov random field has to be independent of states outside of its neighborhood so as to be uncorrelated with them. Note also that S = {s i } N i=1 is not prescribed, but dynamically chosen. Here we took the great advantage of permutation which guarantees that our simulated Markov random field does not depend on how we order sites in S. This alternative algorithm behaves in Gibbs sampler manner because every time it simulates state on a new site, it uses as much information as possible from simulated states in its neighborhood. But it is not Gibbs sampler algorithm, because this algorithm also simulates a Markov random field within one-pass.
Note also that in the above algorithm, Π(X As i = x As i ) is computed through treating A si as S and recursively repeating all the steps in the algorithm, not through the multiplication rule employed in the algorithm of Section 3. The reason is that the sites in A si may not be neighbors of each other, if we use the multiplication rule, the Markov property to be established will be broken. Since there is no such concern as the Makrov property for the algorithm in Section 3, multiplication rule can be applied there. Genearally speaking, S is big and neighborhoods are small, the method of computing Π(X As i = x As i ) in this alternative algorithm is much more efficient than that using multiplication rule.

The Appendix
Proof of Lemma 2.1. First, we prove that we can enumerate the sites within H in a sequence {s i } n i=1 such that s i ∈ ∂(H C {s 1 , ..., s i−1 }) for 1 ≤ i ≤ n. Because H is nonempty, H C is a proper subset of S. If H = S, ∂(H C ) = ∂(∅) = S, then we pick up arbitrary s 1 ∈ ∂(H C ) = S. Otherwise, H is a proper subset of S, so H C = ∅. Because S is connected, ∂(H C ) = ∅, we choose arbitrary s 1 ∈ ∂(H C ). Assume that for some 1 ≤ j < n we have {s i } j i=1 such that s i ∈ ∂(H C {s 1 , ..., s i−1 }) for i = 1, ..., j. Then, we have s i / ∈ H C {s 1 , ..., s i−1 } for i = 1, ..., j, which implies that s i (i = 1, ..., j) are j different sites within H.
Because 1 ≤ j < n and H consists of n sites, H C {s 1 , ..., s j } is a nonempty proper subset of S. Since S is connected, ∂(H C {s 1 , ..., s j }) = ∅, we can find some arbitrary s j+1 ∈ ∂(H C {s 1 , ..., s j }). By induction, the statement is proved. By the above construction, for each 1 ≤ i ≤ n, s i ∈ ∂ For a given nonempty A ⊂ S, we now present one way of choosing a nonempty connected component B ⊆ A. We start B with the empty set (B = ∅). We select an arbitrary site t 1 ∈ A, and append t 1 to B (B = {t 1 }). If ∂(B) A = ∅, that is to say, B has no neighbors within A, then we stop and B is finalized (B = {t 1 }). If ∂(B) A = ∅, then we pick up a site t 2 ∈ ∂(B) A, a neighbor of B within A, and append t 2 to B (B = {t 1 , t 2 }). If ∂(B) A = ∅, we stop and B is finalized (B = {t 1 , t 2 }). We repeat this procedure and add more and more neighbors of B within A to B. Because A is finite, the procedure must be stopped for some 1 ≤ k ≤ |A| where |A| is the size of A, then B is finalized (B = {t 1 , t 2 , ..., t k }). By the construction of B, t j ∈ ∂({t 1 , ..., t j−1 }) for 2 ≤ j ≤ k, so B is nonempty and connected.
If B = A, the claim in the second paragraph is proved. Otherwise, let B 1 = B. Then A \ B 1 = ∅, B 1 and A \ B 1 are exclusive. Then we can replace A in the third paragraph with A \ B 1 and repeat the procedure there. Since the orginal A only has finite sites, there exist some m ≥ 1 for A, such that we can repeat the procedure in the third paragraph m times to find out those m connected components of A Proof of Proposition 2.1. It is clear by (2.3) that for i = 1, X s1 has probability distribution π s1 (·), since A s1 = ∅. We next to prove that for 2 ≤ i ≤ N , X si has probability distribution π si (·), and for any t i ∈ A si , cov(X si , X ti ) = β si,ti . To ease notation, we suppress the subscript i. For x s ∈ X s , by (2.3), one has that Π(X s = x s ) = xA s ∈XA s Π( X s = x s | X As = x As )Π(X As = x As ) = π s (x s ) +π s (x s )(x s − µπ s ) σ 2 πs t∈As xA s ∈XA s u∈As\{t}π u (x u ) · β s,tπt (x t )(x t − µπ t ) σ 2 πt = π s (x s ) +π s (x s )(x s − µπ s ) σ 2 πs t∈As β s,t x As\{t} ∈X As \{t} u∈As\{t}π u (x u ) · xt∈Xtπ t (x t )(x t − µπ t ) σ 2 πt = π s (x s ), (6.1) where the third equality follows from the equality xA s ∈XA s = x As \{t} ∈X As \{t} xt∈Xt and interchanging the order of summations, and the fourth equality holds, because for fixed t ∈ A s , xt∈Xtπ t (x t )(x t − µπ t ) = µπ t − µπ t = 0. Now fix t ∈ A s , we prove cov(X s , X t ) = β s,t . We compute the joint probability mass function of X s and X t . For x s ∈ X s , x t ∈ X t , we have that by (2.3) again Π(X s = x s , X t = x t ) = x As \{t} ∈X As \{t} Π(X s = x s |X t = x t , X As\{t} = x As\{t} ) × Π(X t = x t , X As\{t} = x As\{t} ) = π s (x s ) x As \{t} ∈X As \{t} since Π(X t = x t , X As\{t} = x As\{t} ) = Π(X As = x As ) for t ∈ A s . Therefore, πs u∈As\{t} x As\{t} ∈X As \{t} v∈As\{u}π v (x v ) · β s,uπu (x u )(x u − µπ u ) σ 2 πu = π s (x s )π t (x t ) +π s (x s )(x s − µπ s )β s,tπt (x t )(x t − µπ t ) σ 2 πs σ 2 πt (6.3) where the third equality follows from arguments similar to those in (6.1), in particular: x As \{t,u} ∈X As \{t,u} (x s − µπ s )(x t − µπ t )π s (x s )π t (x t ) (6.5) It follows that cov(X s , X t ) = cov(X s − µπ s , X t − µπ t ) = β s,t (6.6) Remark 6.1. Note that (5.4) follows by (6.3) and (6.6).