On Approximate Pattern Matching for a Class of Gibbs Random Fields

J.-R. Chazottes * * CPhT, CNRS-Ecole polytechnique, 91128 Palaiseau Cedex, France, jeanrene@cpht.polytechnique.fr F. Redig † † Faculteit Wiskunde en Informatica, Technische Universiteit Eindhoven, Postbus 513, 5600 MB Eindhoven, The Netherlands, f.h.j.redig@tue.nl E. Verbitskiy ‡ ‡ Philips Research, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands, evgeny.verbitskiy@philips.com

November 27, 2006

Key-words: Gibbs measures, approximate matching, exponential law, lossy data compression, law of large numbers, large deviations.

1 Introduction

In recent years there has been growing interest in a detailed probabilistic analysis of pattern matching and approximate pattern matching. For example, in information theory, motivation comes from studying performance of idealized Lempel-Ziv coding schemes. In mathematical biology, one likes to have accurate estimates for the probability that two (e.g. DNA) sequences agree in a large interval with some error-percentage.
There is also considerable interest in the analysis of occurrence of patterns in the multi-dimensional setting, e.g., in the context of video-image compression [2] , and more generally, lossy data compression [5, 6] .
In this paper we study the following problem. Fix a pattern A n   in a cubic box of size n   . Given a configuration σ   of a Gibbs random field, what is the size of the ”observation window” in which we do not necessary see exactly this pattern for the first time, but any pattern obtained by distorsion of the fixed pattern A n   ? By this we mean a pattern which contains a fixed fraction ε   of spins different from those of A n   . We are interested in the behavior of the volume of this observation window, that we call ”approximate hitting-time”, when n   grows.
Our main result (Theorem  1 ) can be phrased as follows. The distribution of the approximate hitting-time, when properly normalized, gets closer and closer to an exponential law. The normalization is the product of a certain parameter Λ n   and the probability of the set of distorted patterns [ A n ] ε   . In fact, we get a precise control of the error term which allows us to derive two corollaries for the approximate waiting-time: given a configuration η   randomly chosen from an ergodic Gibbs random field, we increase the obervation window in the random configuration σ   drawn from the given Gibbs random field until we see approximately the pattern η C n   . The first corollary implies a law of large numbers allowing to get the rate distorsion function almost-surely from this approximate waiting-time. The second corollary is related to large deviations bounds. While the law of large numbers for approximate waiting-times appears in [6] , the large deviation result is new. Moreover, the convergence in distribution to the exponential law of the rescaled approximate hitting-time is also new.
We briefly indicate the key ingredients needed to prove this exponential approximation.
First, we assume that the Gibbs random field satisfies a certain strong mixing condition (non-uniformly φ   -mixing condition). For instance, this property holds for all Markov random fields which satisfy the Dobrushin uniqueness condition. The second key ingredient is a result by Chi [4] allowing one to obtain the rate distorsion function ”à la Shannon-McMillan-Breiman”. We take advantage of our previous work [1] in which we deal with ”exact” hitting-times. The proof of the main result of the present work readily follows a large part of the proof in [1] but there is a crucial step which is different (”second moment estimate ”). Moreover, one has to restrict to ”good” patterns: if a pattern has ”too much overlap” with its translates by vectors of size of order n   , then one cannot hope to obtain an exponential distribution. These good patterns are shown to be typical in the sense that the measure of good patterns approaches one exponentially fast as n   diverges (Proposition  2 ). When we have a random field distributed according to a Bernoulli measure, the goodness assumption on patternscan be removed. In this case, we prove (Theorem 2) that for any pattern Theorem 1 applies. Surprisingly, our proof involves the strong invariance principle for simple random walks. We have no idea to provide a simpler proof.
Outline of the paper. In the next section, we set notations and definitions, and state our main theorems. In section 3, we apply the exponential approximation of the previous section to approximate waiting times for which we obtain a.s. strong approximation and large deviations results. In section 4, we give all proofs.
Acknowledgment. We thank Z. Chi for providing us his preprint [4] .

2 Set-up and main results

For the sake of simplicity, we consider a { 0 , 1 }   -valued random field on the lattice Z d   , d ≥ 2   . The results hold for arbitrary finite alphabets as well. Configurations are denoted η , σ , ω   and collected in the set Ω = { 0 , 1 } Z d   . Ω   is provided with the Borel σ   -field, and for V ⊆ Z d   , ℱ V   denotes the σ   -algebra generated by { σ x : x ∈ V }   .
For a finite subset V ⊆ Z d   and configurations σ , η ∈ Ω   we denote by
Δ ( V , η , σ ) = ∑ x ∈ V | η x − σ x | (2.1)
the number of mismatches between σ   and η   in the volume V   , i.e., the Hamming distance between η V   and σ V   times the cardinality of V   .
We denote by C n   the cube [ 0 , n ] d ∩ Z d   . A n   -pattern is a map A n : C n → { 0 , 1 }   .
It is naturally associated to its cylinder [ A n ] = { σ ∈ Ω : σ C n = A n }   . For a pattern A n   and x ∈ Z d   we denote by θ − x A n   the pattern supported on C n + x   defined by A n ( y + x ) = A n ( y )   ( y ∈ C n   ).
For a pattern A n   we denote by [ A n ] ε   the set of configurations which ε   -match with A n   :
[ A n ] ε = { ω ∈ Ω : Δ ( C n , ω , A n ) ≤ ε | C n | } . (2.2)
The set of configurations [ A n ] ε   can also be viewed as a set of n   -patterns, and we will (with a slight abuse of notation) use the same symbol for the set of configurations and the set of n   -patterns which are restrictions of configurations in [ A n ] ε   to C n   .
DEFINITION 1. The approximate hitting time of [ A n ] ε   in a configuration σ   is defined as
T [ A n ] ε ( σ ) = min { | C k | : k > 0 , ∃ x ∈ Z d , C n + x ⊆ C k a n d θ − x σ ∈ [ A n ] ε } . (2.3)
For ε = 0   (exact matching time or occurrence time of a pattern), we obtained in [1] an exponential approximation for the law of T [ A n ] ε   under the hypotheses of non-uniform φ   -mixing and Gibbsianness of the random field. We recall here what this mixing assumption is. For m > 0   define
φ ( m ) = sup 1 | A 1 | | P ( E A 1 | E A 2 ) − P ( E A 1 ) | (2.4)
where the supremum is taken over all finite subsets A 1 , A 2   of Z d   , with d ( A 1 , A 2 ) ≥ m   ( 1   ) and E A i ∈ ℱ A i   , with P ( E A 2 ) > 0   . Note that this φ ( m )   differs from the usual φ   -mixing function since we divide by the size of the dependence set of the event E A 1   .
DEFINITION 2. A random field is non-uniformly exponentially φ   -mixing if there exist constants C 1 , C 2 > 0   such that
φ ( m ) ≤ C 1 e − C 2 m for all m > 0 . (2.5)
A typical example of a Gibbs field satisfying this assumption is the 2d-Ising model above critical temperature. In general, it is satisfied in the so-called high-temperature regime of Dobrushin uniqueness. We refer the reader to [8, 9] for more details on this and on Gibbs measures in general.
An important property of Gibbs measures is the so-called “finite energy” property.
This means that there is a continuous version of the conditional probability P ( σ 0 = 0 | σ Z d \ { 0 } )   such that
δ < P ( σ 0 = 0 | σ Z d \ { 0 } ) < ( 1 − δ ) (2.6)
where δ ∈ ( 0 , 1 2 )   is independent of σ   . This immediately implies the existence of κ > 0   such that for all V ⊆ Z d   , and all η ∈ Ω  
P ( { σ : σ V = η V } ) ≤ e − κ | V | . (2.7)
We will use the following estimate:
LEMMA 1. Under the assumption that P   is a Gibbs measure, there exist ε c > 0   and K = K ( ε c ) > 0   such that for any pattern A n   and any ε < ε c   P ( [ A n ] ε ) ≤ e − K n d .  
  • Proof. This is an immediate consequence of the estimate ( 2.7 ) and the estimate | [ A n ] ε | ≤ ∑ k = 0 ε n d ( n d k ) ≤ e n d I ( ε )   with I ( ε ) ↓ 0   if ε ↓ 0   .
Contrarily to the situation for exact matching, we will need an assumption on the patterns in order to obtain an exponential law. This can be compared with the condition of not being ”badly self-repeating” needed to obtain the exponential law for the return times in [1] . As we shall see, being a ”good” pattern is a typical property.
DEFINITION 3. Given 0 < α < 1 , 0 ≤ ε < 1   , we say that a n   -pattern A n   is called ( ε , α )   -good if the set [ A n ] ε ∩ θ x [ A n ] ε   is empty for all x ∈ Z d   such that | x | ≤ α n   . The set of all ( ε , α )   -good patterns is denoted by G n ( ε , α )   . By abuse of notation, we use the same symbol for the set of configurations ω   such that ω C n   is ( ε , α )   -good.
For ε = 0   and α < 1 / 2   , G n ( ε , α )   coincides with the set of non badly self-repeating patterns in [1] , definition 5.1.
We shall need a result by Chi [4] on the rate distorsion function. We recall briefly the definition of the rate distorsion function and refer the reader to [3] for moreinformation and background and to [6] for a discussion on lossy data compression.
Given a stationary and ergodic measure Q   and a stationary and ergodic Gibbs measure P   , the rate distortion function ℛ ( Q , P , ε )   is defined as follows:
ℛ ( Q , P , ε ) = lim n → ∞ ℛ n ( Q , P , ε ) (2.8)
ℛ n ( Q , P , ε ) = inf J n 1 | C n | H ( J n ∥ Q n × P n ) (2.9)
where the infimum taken over all joint distributions J n   on { 0 , 1 } n d × { 0 , 1 } n d   such that the { 0 , 1 } n d   -marginal of J n   is Q n   and ∫ Δ ( C n , ω , σ ) | C n | d J n ( ω , σ ) ≤ ε .   H ( J n ∥ Q n × P n )   is the relative entropy between J n   and Q n × P n   .
We have the following key result which follows from [4] and [6,Theorem25] .
PROPOSITION 1. Let Q   be a stationary and ergodic measure and P   be a stationary and ergodic Gibbs measure. Then
ℛ ( Q , P , ε ) = − lim n → ∞ 1 | C n | log P ( [ ω C n ] ε ) Q − almost-surely . (2.10)
Moreover, ℛ   is a convex (and hence continuous) function of ε   and is non-zero in some interval [ 0 , ε 0 )   .
The property  2.10 is called the generalized asymptotic equipartition property in [6] . Throughout we will simply write ℛ ( ε )   instead of ℛ ( Q , P , ε )   .
We can now state our main result.
THEOREM 1. Suppose that P   is a non-uniformly exponentially φ   -mixing Gibbs measure and Q   is a stationary and ergodic Gibbs measure. Assume that the rate distortion function ( 2.8 ) is strictly positive in [ 0 , ε 0 )   . Then for all α ∈ ( 0 , 1 )   and ε > 0   small enough: namely, ε α < ε 0 ,   there exist Λ 1 , Λ 2 , C , c ∈ ( 0 , ∞ )   , such that and for every t > 0   , n ≥ 1   , and Q   -almost all ω   with ω C n ∈ G n ( ε , α )   , the following estimate holds:
| P ( T [ ω C n ] ε > t Λ n P ( [ ω C n ] ε ) ) − e − t | ≤ C e − c t e − K n d (2.11)
where Λ n = Λ ( ω C n )   is such that
Λ 1 ≤ Λ n ≤ Λ 2 . (2.12)
Dependence of the parameters in Theorem  1 on ε   and α   will be discussed after the proof, see Remark  1 .
Let us briefly comment on the difference between Theorem  1 and the one obtained in [1] for exact matching, that is the case corresponding to ε = 0   . First of all, we need to restrict ourselves to special patterns, i.e., ( ε , α )   -good patterns, whereas in [1] result applies to all patterns. Secondly, the error term that we obtain in [1] is of the form C e − c t P ( [ ω C n ] ) ρ   , where ρ > 0   . Of course, the factor P ( [ ω C n ] ) ρ   is uniformly exponentially small for Gibbs measures. This is no longer true for P ( [ ω C n ] ε )   if ε   is too large. This is precisely why we need Lemma  1 . Thirdly, a crucial step in the proof of Theorem  1 , which differs slightly from that in [1] for the case ε = 0   , involves Proposition  1 . This explains why we need to restrict to typical configurations in the sense of this result.
Let us close this set of remarks by noticing that Q   has to be a stationary and ergodic measure, but not necessarily Gibbsian. But for later use of Theorem  1 we shall also need the latter assumption, so we already impose it to state the theorem.
The following proposition shows that ” ω C n ∈ G ( ε , α )   ”, i.e. that a pattern being ( ε , α )   -good, is a typical property.
PROPOSITION 2. Let Q   be a stationary Gibbs measure. Then, if α < 1 / 2   and ε > 0   is small enough, there exists ν > 0   such that for all n ≥ 1  
Q ( G n ( ε , α ) ) > 1 − e − ν n d . (2.13)
It turns out that if the random field has a non-trivial dependence structure, then the restriction to ( ε , α )   -good patterns is unavoidable. However, in the case of a random field distributed according to a Bernoulli measure, the exponential law  2.11 holds for all approximate patterns. This is expressed by the following theorem.
THEOREM 2. If P   is the Bernoulli measure with P ( σ 0 = 1 ) = 1 / 2   , then ( 2.11 ) holds without the restriction that ω C n   is ( ε , α )   -good.

1   As usual, d ( A 1 , A 2 ) : = inf { d ( x , y ) : x ∈ A 1 , y ∈ A 2 }   and d ( x , y ) : = | | x − y | | ∞ = max 1 ≤ i ≤ d | x i − y i |   .

3 Approximate waiting-time fluctuations

The purpose of this section is to derive two consequences of Theorem  1 and Proposition  2 . The first one implies a strong law of large numbers for the approximate waiting-time. It was previously derived in [6] directly using the mixing property  2.5 .
The second one concerns large deviations of the approximate waiting-time and it is a new result. Given two configurations ω , σ   , the approximate waiting time is W n ε ( ω , σ ) : = T [ ω C n ] ε ( σ )   .
PROPOSITION 3. Under the assumptions of Theorem  1 and Proposition  2 , there exists γ 0 > 0   such that for all γ > γ 0   :
− γ log n ≤ log ( W n ε ( ω , σ ) P ( [ ω C n ] ε ) ) ≤ log ( log n γ ) (3.1)
Q × P   -eventually almost surely. In particular lim n → ∞ 1 | C n | log W n ε ( ω , σ ) = ℛ ( Q , P , ε ) Q × P − almost surely .  
With Proposition  3 we recover the results of Theorems 26 and 27 in [6] . However, there is a substantial difference in conditions on random fields. We have to restrict ourselves to measures Q   which are stationary and ergodic Gibbs measures, while in [6]  Q   is only assumed to be stationary and ergodic. On the other hand, we permit Gibbs P   , while in [6]  P   must be Bernoulli. The reason for our assumptions on Q   is that Proposition  2 is valid for Gibbs measures. We do not know if it can be extended to more general situations.
Let us also remark that by a basic result in Probability Theory, this strong approximation implies that if a central limit theorem holds for − ( 1 / | C n | ) log P ( [ ω C n ] ε ) )   , then it holds also for ( 1 / | C n | ) log W n ε ( ω , σ )   . Unfortunately, the former seems to be a difficult issue, except in the iid case. We refer the reader to [6] for some results in that direction.
We have the following (partial) large deviation results. We first need the following lemma showing that we can define the generalized conditional q   -order Rényi entropy for Gibbs random fields. This was first done in [11] for ( α   -mixing) stochastic processes ( d = 1   ) with the difference that here we need to condition on ( ε , α )   -good patterns and use the Gibbs property instead of mixing.
LEMMA 2. Let Q , P   be stationary Gibbs measures and assume that α < 1 / 2   and 0 ≤ ε < 1   . Then, for all q ∈ R   , the following function is well-defined:
ℰ ε ( q ) : = ℰ ε ( q ; Q , P ) = lim n → ∞ 1 | C n | log ∫ P ( [ ω C n ] ε ) q d Q G n ( ε , α ) ( ω ) . (3.2)
( Q G n ( ε , α )   denotes the measure Q   conditioned on the set of good patterns.)
The generalized q   -order Rényi entropy should be defined as − ℰ ε ( − q ) / q   .
We now have the following theorem. By a n ≈ b n   we mean that max { a n / b n , b n / a n }   is bounded from above.
THEOREM 3. Let P   be a non-uniformly exponentially φ   -mixing Gibbs measure and Q   a stationary and ergodic Gibbs measure. If ε > 0   is small enough, then for any α 0 ≤ α < 1 / 2   , we have
∫ ∫ ( W n ε ( ω , σ ) ) q d Q G n ( ε , α ) ( ω ) d P ( σ ) ≈ ∫ P ( [ ω C n ] ε ) − q d Q G n ( ε , α ) ( ω ) if q ≥ − 1 (3.3)
and
∫ ∫ ( W n ε ( ω , σ ) ) q d Q G n ( ε , α ) ( ω ) d P ( σ ) ≈ ∫ P ( [ ω C n ] ε ) d Q G n ( ε , α ) ( ω ) if q < − 1 (3.4)
In particular,
lim n → ∞ 1 | C n | log ∫ ∫ ( W n ε ( ω , σ ) ) q d Q G n ( ε , α ) ( ω ) d P ( σ ) = { ℰ ε ( − q ) if q ≥ − 1 ℰ ε ( 1 ) if q < − 1 . (3.5)
It follows from this theorem that Theorem 4.5.20 in [7] applies to large deviations of ( ( 1 / | C n | ) log W n ε ( η , σ ) ) n   . We do not know under which conditions the function q ↦ ℰ ε ( q )   is, for example, continuously differentiable for ε   small enough. It it were the case, we would get a large deviation principle for ( ( 1 / | C n | ) log W n ε ( η , σ ) ) n   with a rate function given by the Legendre transform of ℰ ε ( − q )   for q > − 1   .

4 Proofs

4.1 Proof of Theorem  1 

The proof of Theorem  1 is quite similar to the proof of exponential law in [1] . We describe briefly the common approach and indicate the differences. We also provide the necessary modifications of the proof.
It is well known that a random variable Z   has an exponential distribution if and only if P ( Z > s + t | Z > t ) = P ( Z > s )   or, equivalently, P ( Z > s + t ) = P ( Z > s ) P ( Z > t ) .   The basic ingredient of the proof in [1] was Lemma 4.4 (”Iteration Lemma”). This result establishes that for a pattern A n   and any finite number of cubes C i ⊆ Z d   , i = 1 , … , k   , with equal volumes | C i | = ( 1 P ( A n ) ) γ   we have
P ( A n does not occur in k ⋃ i = 1 C i ) ≈ P ( A n does not occur in C 1 ) k . (4.1)
In [1] we also observed that the Iteration Lemma remains valid if a pattern A n   is replaced by the event [ A n ] ε   , with [ A n ] ε   does not occur in volume V   if any pattern B n ∈ [ A n ] ε   does not occur in volume V   .
Another important ingredient of the proof is the control of the parameter of the exponential distribution. Lemma 4.3 (”The parameter”) in [1] concerns non-triviality of the parameter Λ n   , that is, the fact that it is neither null nor infinite. To prove Lemma 4.3, we established a uniform second moment estimate for the number of occurrences of a pattern A n   in a configuration σ   restricted to a box that has later to be taken of size 1 / P ( [ A n ] )   . It is the proof of this second moment estimate that we have to modify completely. In remark 4.1 in [1] , we noticed that if E n ∈ ℱ C n   are events such that P ( E n ) < e − c n d   for some c > 0   , and such that
limsup n → ∞ ∑ 0 < | x | < n P ( E n ∩ θ x E n ) P ( E n ) < ∞ (4.2)
then this implies, together with the mixing property  2.5 and the Gibbs property  2.7 , that the desired uniform second moment estimate holds. In turn, this implies the non-triviality of the parameter  2.12 (Lemma 4.3 in [1] ). Thus, we turn to prove  4.2 when the event E n   is [ A n ] ε   , where A n   is a good and typical pattern. We assume that patterns A n   are such that ∩ n A n = { σ }   , with σ   chosen from the Q   -measure one set of Proposition  1 and such that A n   is good in the sense of Definition  3 .
We have to show for patterns A n ∈ G n ( ε , α )   with ε / α < ε 0   , there exists a finite C = C ( ε , α )   such that for all n  
∑ 0 < | x | ≤ n P ( [ A n ] ε ∩ θ x [ A n ] ε ) P ( [ A n ] ε ) ≤ C ( ε , α ) . (4.3)
First of all, since A n ∈ G n ( ε , α )   (see Definition  3 ), the terms corresponding to x   with | x | < α n   are equal to 0   . Therefore we have to estimate the sum
∑ α n ≤ | x | ≤ n P ( [ A n ] ε ∩ θ x [ A n ] ε ) P ( [ A n ] ε ) (4.4)
Note that for x   with | x | ≥ α n   , the intersection ( C n + x ) ∩ C n   is not very large:
| ( C n + x ) ∩ C n | ≤ ( 1 − α ) n d .   Note also that Δ ( V , ω , A n )   denotes the number of differences between ω   and A n   in the volume V   , see  2.1 . Then we can write
P ( [ A n ] ε ∩ θ x [ A n ] ε ) = P ( ω : Δ ( C n , ω , A n ) ≤ ε n d ∩ Δ ( C n + x , ω , θ − x A n ) ≤ ε n d ) (4.5)
where by θ − x A n   we mean θ − x A n ( y + x ) = A n ( y )   , y ∈ C n   . For the sake of convenience, we simply write C   for C n   and C x   for C n + x   in the course of this proof. We also introduce the short-hand notations
S 1 = Δ ( C \ C x , ω , A n )
S 2 = Δ ( C ∩ C x , ω , A n )
S 3 = Δ ( C ∩ C x , ω , θ − x A n )
S 4 = Δ ( C \ C x , ω , θ − x A n ) . (4.6)
With these notations what we have to estimate
∑ α n ≤ | x | ≤ n P ( [ A n ] ε ∩ θ x [ A n ] ε ) P ( [ A n ] ε ) = ∑ α n ≤ | x | ≤ n P ( S 3 + S 4 ≤ ε n d | S 1 + S 2 ≤ ε n d ) . (4.7)
The following estimate is a corollary of [4] and a basic property of a Gibbs measures:
for any configuration ξ   :
P ( { ω : Δ ( V n , ω , σ ) ≤ ε | V n | } | ξ V n c ) ≤ exp ( − | V n | ℛ ( ε ) + c | ∂ V n | ) (4.8)
Indeed, the unconditioned statement is proved in [4] , and conditioning can at most introduce a term of order exp ( c | ∂ V n | )   .
We proceed as follows
P ( ( S 1 + S 2 ) ≤ ε n d ∩ ( S 3 + S 4 ) ≤ ε n d )
≤ P ( ( S 1 + S 2 ) ≤ ε n d ∩ S 4 ≤ ε n d )
≤ sup ξ P ( S 4 ≤ ε n d | ξ Z d \ ( C x \ C ) ) P ( [ A n ] ε )
≤ exp ( − α n d ℛ ( ε α ) + c n d − 1 ) P ( [ A n ] ε ) .
Therefore ∑ α n ≤ | x | ≤ n P ( [ A n ] ε ∩ θ x [ A n ] ε ) P ( [ A n ] ε ) ≤ n d exp ( − α n d ℛ ( ε α ) + c n d − 1 ) = : C n ( ε , α ) .   Taking into account that ε / α < ε 0   , and hence ℛ ( ε / α ) > 0   , we conclude that C n ( ε , α ) → 0   as n → ∞   , and hence C ( ε , α ) = sup n C n ( ε , α )   is finite. This finishes the proof.
REMARK 1. The parameters of Theorem  1 depend on the choice of ε   and α   . The most interesting is the dependence of Λ 1   and Λ 2   . TheParameter Lemma of [1] in fact shows that a uniform choice Λ 2 = 2   suffices. A more interesting question is whether we can give a uniform bound on Λ 1   for a large set of ε   and α   . The present modification of the second moment estimate together with the rest of Lemma 4.3 in [1] , which remains unchanged, gives that for some c   , dependent on ε   alone, the following choice of Λ 1 = Λ 1 ( ε , α )   will suffice Λ 1 = 1 c + C ( ε , α ) .   The rate distortion function ℛ   is a monotonically decreasing function.
Hence, for a fixed ε > 0   , α ℛ ( ε α )   is a monotonically increasing function of α   , and finally, C ( ε , α )   is monotonically decreasing in α   . Therefore, if ε < ε 0   , then for all α > α 0 : = 0.99 ε ε 0   Λ 1 ( ε , α ) ≥ Λ 1 ( ε , α 0 ) > 0 .   Therefore, for a fixed ε > 0   we obtain a uniform (in α   ) bound on the parameter Λ 1   .

4.2 Proof of Proposition  2 

For ε = 0   we know that most patterns are ( 0 , α )   -good for any α < 1   . Indeed, it is proved in [1] (lemma 5.3) that Q ( G n ( ε , α ) ) ≥ 1 − e − κ ′ n d   , for some κ ′ > 0   .
Let us now argue that for small ε   this is still the case. Suppose α < 1 / 2   , that is, we are going to consider vectors x ∈ Z d   such that | x | ≤ n 2   . An element A   of [ A n ] ε ∩ θ x [ A n ] ε   satisfies
∑ y ∈ C x ∩ C | A ( y ) − A ( y − x ) | ≤ 2 ε n d . (4.9)
(Recall that C = C n   and C x = C n + x   . This implies that there exists a set V n ⊆ C   and a disjoint translate V n + z ⊆ C   such that | V n | > ( 1 / 2 ) d n d   such that θ − z A V n + z   matches with error fraction 2 d + 1 ε   with A V n   , this can be made as small as e − ν n d   , for some ν > 0   , for ε   sufficiently small uniformly in A V n   by Lemma  1 . Therefore we obtain that
Q ( G ( ε , α 0 ) ) > 1 − e − ν n d (4.10)
for all α < 1 / 2   and ε   small enough.

4.3 Proof of Theorem  2 

We consider the case d = 1   only, because the case d ≥ 2   is completely analogous.
Start with the particular pattern A n = 0 ⋯ 0   that we simply denote by 0 n   . The difficulty with this ”bad pattern” comes from the fact that the second moment estimate does not apply, because ( 4.2 ) fails. Therefore, we have to prove by other means that there exists δ > 0   such that for all n ∈ N   ,
δ < P ( T [ 0 n ] ε > 1 P ( [ 0 n ] ε ) ) < 1 − δ (4.11)
which would imply the non-triviality of the parameter Λ n   . We will first show that there exists a sequence k n ↑ ∞   such that
δ < P ( T [ 0 n ] ε > k n ) < 1 − δ . (4.12)
It will then follow easily from the Bernoulli character of P   that k n   does not depend on the choice of the pattern, i.e., ( 4.12 ) holds with the same k n   for any pattern A n   . Then we can apply Theorem  1 for good patterns, and obtain k n = 1 / P ( [ A n ] ε ) = 1 / P ( [ 0 n ] ε )   .
We have the following identities:
P ( T [ 0 n ] ε ≤ k n ) = P ( k n min k = 0 ∑ i = k k + n ω i ≤ n ε )
= P ( k n max k = 0 ∑ i = k k + n ( 1 − 2 ω i ) ≥ ( 1 − 2 ε ) n )
= P ( k n max k = 0 ( S k + n − S k ) ≥ ( 1 − 2 ε ) n ) (4.13)
where S n   is the position of a simple random walk on Z   (with S 0 = 0   ) after n   steps.
By Theorem 7.23 in [12] , together with the strong invariance principle [12] p. 53, we have
k n max k = 0 ( S k + n − S k ) = a log k n + b log log k n + c + o ( 1 ) + X (4.14)
where X   is a random variable with a Gumbel distribution. Therefore, if we choose k n   such that
( 1 − 2 ε ) n = a log k n + b log log k n + c + o ( 1 ) (4.15)
then ( 4.12 ) holds.
If we now choose any other pattern A n   , then under P   , S n = 2 ∑ i = 0 n ( 1 / 2 − σ i − A n ( i ) )   is again distributed as a simple random walk, so we find the same k n   , which completes the proof of the theorem.

4.4 Proof of Proposition  3 

By using Theorem  1 we immediately get Q × P { ( ω , σ ) : log ( W n ε ( ω , σ ) P ( [ ω C n ] ε ) ) > log t } =   ∫ d Q ( ω ) P { σ : log ( T [ ω C n ] ε ( σ ) P ( [ ω C n ] ε ) ) > log t } ≤ e − Λ 1 t + C e − K n d + ∑ A n ∈ G n c ( ε , α ) Q ( [ A n ] ) .   Now we choose t = t n = log ( n γ )   with γ > 0   such that Λ 1 γ > 1   . This makes the first term in the rhs summable in n   . The last one equals the Q   -measure of the complement of G n ( ε , α )   , which is less than e − ν n d   by Proposition  2 . We thus get the upper bound in  3.1 by an application of the Borel-Cantelli Lemma. Now we turn to prove the lower bound in  3.1 . Proceeding as before, we get Q × P { ( ω , σ ) : log ( W n ε ( ω , σ ) P ( [ ω C n ] ε ) ) ≤ log t } ≤   1 − e − Λ 2 t + C e − K n d + ∑ A n ∈ G n c ( ε , α ) Q ( [ A n ] ) ≤   Λ 2 t + C e − K n d + e − ν n d .   We have used Theorem  1 and Proposition  2 . We now choose t = t n = n − γ   , with γ > 1   , to get a summable upper bound in n   for the above probability. An application of Borel-Cantelli Lemma gives the desired result and the proof of the proposition is complete.

4.5 Proof of Lemma  2 

We only consider the case q > 0   leaving the (very similar) proof for the case q < 0   to the reader. Let S □   be the system of all rectangular boxes of the form V = Z d ∩ d ∏ k = 1 [ m k , n k ] with m k , n k ∈ Z , m k ≤ n k .   Before proceeding, we have to extend definition  3 somewhat. We will denote by G V ( ε , α )   the set of good patterns supported on V ∈ S □   . We shall need Proposition  2 which remains valid if one replaces G n ( ε , α )   with G V ( ε , α )   and n   by | V |   in  2.13 .
We are going to prove that the function a : S □ → ( − ∞ , + ∞ )   defined as a ( V ) : = − log ∫ P q ( [ σ V ] ε ) d Q G V ∪ V ′ ( ε , α ) ( σ )   satisfies a ( V ∪ V ′ ) ≤ a ( V ) + a ( V ′ ) + C | ∂ ( V ∪ V ′ ) |   for all V , V ′ ∈ S □   such that V ∪ V ′ ∈ S □   and V ∩ V ′ = ∅   , where C   is a constant (depends on q   ), and where ∂ V   denotes the boundary of V   . Of course, | ∂ ( V ∪ V ′ ) |   is a surface order correction. If such a property holds (together with a ( V + x ) = a ( V )   , for all x ∈ Z d   , V ∈ S □   which is obvious by stationarity of the measure), then a generalised sub-additive lemma, obtained as a combination of a lemma found in [8] and another one given in [7] , will guarantee that lim n → ∞ a ( C n ) | C n |   exists, as we wish. For all q ∈ R   , V , V ′ ∈ S □   such that V ∪ V ′ ∈ S □   and V ∩ V ′ = ∅   , we have the following:
P q ( [ σ V ∪ V ′ ] ε ) = ( ∑ ω V ∪ V ′ ∈ [ σ V ∪ V ′ ] ε P ( [ ω V ∪ V ′ ] ) ) q ≥   e K 1 | ∂ ( V ∪ V ′ ) | ( ∑ ω V ∪ V ′ ∈ [ σ V ∪ V ′ ] ε P ( [ ω V ] ) P ( ω V ′ ] ) ) q ≥   e K 2 | ∂ ( V ∪ V ′ ) | ( ∑ ω V ∈ [ σ V ] ε P ( [ ω V ] ) ) q ( ∑ ω V ′ ∈ [ ω V ′ ] ε P ( ω V ′ ] ) ) q =   e K 2 | ∂ ( V ∪ V ′ ) | P q ( [ σ V ∪ V ′ ] ε ) P q ( [ σ V ∪ V ′ ] ε )   where K 1 , K 2   are constants. The first inequality follows from the Gibbs property and the second one is a simple consequence of the Hamming distance property. To complete the proof we again use the Gibbs property to get ∫ P q ( [ σ V ∪ V ′ ] ε ) d Q G V ∪ V ′ ( ε , α ) ( σ ) = ∑ ω V ∪ V ′ ∈ { 0 , 1 } V ∪ V ′ P q ( [ ω V ∪ V ′ ] ε ) Q G V ∪ V ′ ( ε , α ) ( [ ω V ∪ V ′ ] ) ≥   Q ( G V ∪ V ′ ( ε , α ) ) e K 3 | ∂ ( V ∪ V ′ ) | ×   ∑ ω V ∈ { 0 , 1 } V P q ( [ ω V ] ε ) Q G V ∪ V ′ ( ε , α ) ( [ ω V ] ) × ∑ ω V ′ ∈ { 0 , 1 } V ′ P q ( [ ω V ′ ] ε ) Q G V ∪ V ′ ( ε , α ) ( [ ω V ′ ] ) ≥   1 2 e K 3 | ∂ ( V ∪ V ′ ) | ∫ P q ( [ σ V ] ε ) d Q G V ( ε , α ) ( σ ) × ∫ P q ( [ σ V ′ ] ε ) d Q G V ′ ( ε , α ) ( σ )   where K 3   is a constant. The second inequality is the consequence of Proposition  2 if | V ∪ V ′ |   is large enough. The lemma is proved.

4.6 Proof of Theorem  3 

Since the proof of this theorem is very similar to that of Theorem 2.7 in [1] , we only sketch it to indicate the little differences between them.
The starting point is of course to write ∫ ∫ ( W n ε ( ω , σ ) ) q d Q G n ( ε , α ) ( ω ) d P ( σ ) = ∫ d Q G n ( ε , α ) ( ω ) ∫ T [ ω C n ] ε q ( σ ) d P ( σ ) .   Then we can mimic the proof of Theorem 2.7 in [1] by using Theorem  1 and the analog of lemma 4.3 in [1] , which holds true when T [ ω C n ]   is replaced by T [ ω C n ] ε   , provided that ω C n   be a ( ε , α )   -good pattern (see the beginning of the proof of Theorem  1 ), and ω   be Q   -typical in the sense of Proposition  1 . Notice that we integrate with respect to the conditional measure Q G n ( ε , α )   which takes care of these two properties.
References

  1. M. Abadi, J.-R. Chazottes F. Redig and E. Verbitskiy, Exponential distribution for the occurrence of rare patterns in Gibsian random fields, Commun. Math. Phys. 246 no. 2 (2004), 269–294.
  2. M. Alzina, W. Szpankowski and A. Grama, 2d-pattern matching, image and video-compression: theory, algorithms and experiments, IEEE Transactions on Image Processing 11 no. 3, (2002), 318-331.
  3. T. Berger, Rate Distorsion Theory: A Mathematical Basis for Data Compression. Englewood Cliffs, NJ: Prentice-Hall, 1971.
  4. Z. Chi, Conditional large deviation principle for finite state Gibbs random fields. Preprint (2002).
  5. A. Dembo, I. Kontoyiannis, The asymptotics of waiting times between stationary processes, allowing distortion, Ann. Appl. Probab. 9 (1999), no. 2, 413–429.
  6. A. Dembo, I. Kontoyiannis, Source coding, large deviations, and approximate matching, IEEE Trans. Inform. Th. 48 no. 6 (2002), 1590–1615.
  7. A. Dembo, O. Zeitouni, Large deviations techniques and applications. Second edition. Applications of Mathematics (New York) 38. Springer-Verlag, New York, 1998.
  8. H.-O. Georgii. Gibbs Measures and Phase Transitions. Walter de Gruyter & Co., Berlin, 1988.
  9. X. Guyon. Random Fields on a Network. Modeling, Statistics and Applications, Springer Verlag, New York, Berlin, 1995.
  10. I. Kontoyiannis, Pattern matching and lossy data compression on random fields, IEEE Trans. Inform. Th. 49 no. 4 (2003), 1047–1051.
  11. T. Luczak, W. Szpankowski, A suboptimal lossy data compression based on approximate pattern matching, IEEE Trans. Inform. Th. 43 no. 5 (1997), 1439–1451.
  12. P. Révész, Random Walks in Random and Non-Random Environments, World Scientific, Singapore, New Jersey, London, Hong Kong, (1990).