An important property of Gibbs measures is the socalled “finite energy” property.
This means that there is a continuous version of the conditional probability
$\mathbb{P}({\sigma}_{0}=0{\sigma}_{\mathbb{Z}d\backslash \left\{0\right\}})$
such that
$$\begin{array}{c}\delta <\mathbb{P}({\sigma}_{0}=0{\sigma}_{\mathbb{Z}d\backslash \left\{0\right\}})<(1\delta )\end{array}$$ 
(2.6)

where
$\delta \in (0,\frac{1}{2})$
is independent of
$\sigma $
. This immediately implies the existence of
$\kappa >0$
such that for all
$V\subseteq \mathbb{Z}d$
, and all
$\eta \in \Omega $
$$\begin{array}{c}\mathbb{P}\left(\right\{\sigma :{\sigma}_{V}={\eta}_{V}\left\}\right)\le {e}^{\kappa \leftV\right}.\end{array}$$ 
(2.7)

We will use the following estimate:
LEMMA 1.
Under the assumption that
$\mathbb{P}$
is a Gibbs measure, there exist
${\epsilon}_{c}>0$
and
$K=K\left({\epsilon}_{c}\right)>0$
such that for any pattern
${A}_{n}$
and any
$\epsilon <{\epsilon}_{c}$
$$\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon})\le {e}^{K{n}^{d}}.$$

Proof.
This is an immediate consequence of the estimate ( 2.7 ) and the estimate
$$\left\right[{A}_{n}{]}^{\epsilon}\le {\sum}_{k=0}^{\epsilon {n}^{d}}\left(\genfrac{}{}{0ex}{}{{n}^{d}}{k}\right)\le {e}^{{n}^{d}I\left(\epsilon \right)}$$
with
$I\left(\epsilon \right)\downarrow 0$
if
$\epsilon \downarrow 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 selfrepeating” 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<\alpha <1,0\le \epsilon <1$
, we say that a
$n$
pattern
${A}_{n}$
is called
$(\epsilon ,\alpha )$
good if the set
$\left[An\right]\epsilon \cap {\theta}_{x}[{A}_{n}{]}^{\epsilon}$
is empty for all
$x\in {\mathbb{Z}}^{d}$
such that
$\leftx\right\le \alpha n$
. The set of all
$(\epsilon ,\alpha )$
good patterns is denoted by
${\mathcal{G}}_{n}(\epsilon ,\alpha )$
. By abuse of notation, we use the same symbol for the set of configurations
$\omega $
such that
${\omega}_{{C}_{n}}$
is
$(\epsilon ,\alpha )$
good.
For
$\epsilon =0$
and
$\alpha <1/2$
,
${\mathcal{G}}_{n}(\epsilon ,\alpha )$
coincides with the set of non badly selfrepeating 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
$\mathbb{Q}$
and a stationary and ergodic Gibbs measure
$\mathbb{P}$
, the rate distortion function
$\mathcal{\mathcal{R}}(\mathbb{Q},\mathbb{P},\epsilon )$
is defined as follows:
$$\begin{array}{cc}\mathcal{\mathcal{R}}(\mathbb{Q},\mathbb{P},\epsilon )& ={lim}_{n\to \infty}{\mathcal{\mathcal{R}}}_{n}(\mathbb{Q},\mathbb{P},\epsilon )\end{array}$$ 
(2.8)

$$\begin{array}{cc}{\mathcal{\mathcal{R}}}_{n}(\mathbb{Q},\mathbb{P},\epsilon )& ={inf}_{{J}_{n}}\frac{1}{\left{C}_{n}\right}H({\mathbb{J}}_{n}\parallel {\mathbb{Q}}_{n}\times {\mathbb{P}}_{n})\end{array}$$ 
(2.9)

$$\begin{array}{}\end{array}$$  
where the infimum taken over all joint distributions
${\mathbb{J}}_{n}$
on
$\{0,1{\}}^{{n}^{d}}\times \{0,1{\}}^{{n}^{d}}$
such that the
$\{0,1{\}}^{{n}^{d}}$
marginal of
${\mathbb{J}}_{n}$
is
${\mathbb{Q}}_{n}$
and
$$\int \frac{\Delta ({C}_{n},\omega ,\sigma )}{\left{C}_{n}\right}d{\mathbb{J}}_{n}(\omega ,\sigma )\le \epsilon .$$
$H({\mathbb{J}}_{n}\parallel {\mathbb{Q}}_{n}\times {\mathbb{P}}_{n})$
is the relative entropy between
${\mathbb{J}}_{n}$
and
${\mathbb{Q}}_{n}\times {\mathbb{P}}_{n}$
.
We have the following key result which follows from [
4]
and [
6,Theorem25]
.
PROPOSITION 1.
Let
$\mathbb{Q}$
be a stationary and ergodic measure and
$\mathbb{P}$
be a stationary and ergodic Gibbs measure. Then
$$\begin{array}{c}\mathcal{\mathcal{R}}(\mathbb{Q},\mathbb{P},\epsilon )={lim}_{n\to \infty}\frac{1}{\left{C}_{n}\right}log\mathbb{P}\left(\right[{\omega}_{{C}_{n}}{]}^{\epsilon})\mathbb{Q}\text{almostsurely}.\end{array}$$ 
(2.10)

Moreover,
$\mathcal{\mathcal{R}}$
is a convex (and hence continuous) function of
$\epsilon $
and is nonzero in some interval
$[0,{\epsilon}_{0})$
.
The property 2.10 is called the generalized asymptotic equipartition property in [6] . Throughout we will simply write
$\mathcal{\mathcal{R}}\left(\epsilon \right)$
instead of
$\mathcal{\mathcal{R}}(\mathbb{Q},\mathbb{P},\epsilon )$
.
We can now state our main result.
THEOREM 1.
Suppose that
$\mathbb{P}$
is a nonuniformly exponentially
$\phi $
mixing Gibbs measure and
$\mathbb{Q}$
is a stationary and ergodic Gibbs measure. Assume that the rate distortion function ( 2.8 ) is strictly positive in
$[0,{\epsilon}_{0})$
. Then for all
$\alpha \in (0,1)$
and
$\epsilon >0$
small enough: namely,
$$\frac{\epsilon}{\alpha}<{\epsilon}_{0},$$
there exist
${\Lambda}_{1},{\Lambda}_{2},C,c\in (0,\infty )$
, such that and for every
$t>0$
,
$n\ge 1$
, and
$\mathbb{Q}$
almost all
$\omega $
with
${\omega}_{{C}_{n}}\in {\mathcal{G}}_{n}(\epsilon ,\alpha )$
, the following estimate holds:
$$\begin{array}{c}\left\mathbb{P}\left({\mathbf{T}}_{[{\omega}_{{C}_{n}}{]}^{\epsilon}}>\frac{t}{{\Lambda}_{n}\mathbb{P}\left(\right[{\omega}_{{C}_{n}}{]}^{\epsilon})}\right){e}^{t}\right\le C{e}^{ct}{e}^{K{n}^{d}}\end{array}$$ 
(2.11)

where
${\Lambda}_{n}=\Lambda \left({\omega}_{{C}_{n}}\right)$
is such that
$$\begin{array}{c}{\Lambda}_{1}\le {\Lambda}_{n}\le {\Lambda}_{2}.\end{array}$$ 
(2.12)

Dependence of the parameters in Theorem 1 on
$\epsilon $
and
$\alpha $
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
$\epsilon =0$
. First of all, we need to restrict ourselves to special patterns, i.e.,
$(\epsilon ,\alpha )$
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}^{ct}\mathbb{P}\left(\right[{\omega}_{{C}_{n}}]{)}^{\rho}$
, where
$\rho >0$
. Of course, the factor
$\mathbb{P}\left(\right[{\omega}_{{C}_{n}}]{)}^{\rho}$
is uniformly exponentially small for Gibbs measures. This is no longer true for
$\mathbb{P}\left(\right[{\omega}_{{C}_{n}}{]}^{\epsilon})$
if
$\epsilon $
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
$\epsilon =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
$\mathbb{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 ”
${\omega}_{{C}_{n}}\in \mathcal{G}(\epsilon ,\alpha )$
”, i.e. that a pattern being
$(\epsilon ,\alpha )$
good, is a typical property.
PROPOSITION 2.
Let
$\mathbb{Q}$
be a stationary Gibbs measure. Then, if
$\alpha <1/2$
and
$\epsilon >0$
is small enough, there exists
$\nu >0$
such that for all
$n\ge 1$
$$\begin{array}{c}\mathbb{Q}\left({\mathcal{G}}_{n}\right(\epsilon ,\alpha \left)\right)>1{e}^{\nu {n}^{d}}.\end{array}$$ 
(2.13)

It turns out that if the random field has a nontrivial dependence structure, then the restriction to
$(\epsilon ,\alpha )$
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
$\mathbb{P}$
is the Bernoulli measure with
$\mathbb{P}({\sigma}_{0}=1)=1/2$
, then ( 2.11 ) holds without the restriction that
${\omega}_{{C}_{n}}$
is
$(\epsilon ,\alpha )$
good.
3 Approximate waitingtime 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 waitingtime. It was previously derived in [
6]
directly using the mixing property 2.5 .
The second one concerns large deviations of the approximate waitingtime and it is a new result. Given two configurations
$\omega ,\sigma $
, the approximate waiting time is
${\mathbf{W}}_{n}^{\epsilon}(\omega ,\sigma ):={\mathbf{T}}_{[{\omega}_{{C}_{n}}{]}^{\epsilon}}\left(\sigma \right)$
.
PROPOSITION 3.
Under the assumptions of Theorem 1 and Proposition 2 , there exists
${\gamma}_{0}>0$
such that for all
$\gamma >{\gamma}_{0}$
:
$$\begin{array}{c}\gamma logn\le log\left({\mathbf{W}}_{n}^{\epsilon}\right(\omega ,\sigma )\mathbb{P}(\left[{\omega}_{{C}_{n}}{]}^{\epsilon}\right))\le log(log{n}^{\gamma})\end{array}$$ 
(3.1)

$\mathbb{Q}\times \mathbb{P}$
eventually almost surely. In particular
$${lim}_{n\to \infty}\frac{1}{\left{C}_{n}\right}log{\mathbf{W}}_{n}^{\epsilon}(\omega ,\sigma )=\mathcal{\mathcal{R}}(\mathbb{Q},\mathbb{P},\epsilon )\mathbb{Q}\times \mathbb{P}\text{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
$\mathbb{Q}$
which are stationary and ergodic Gibbs measures, while in [
6]
$\mathbb{Q}$
is only assumed to be stationary and ergodic. On the other hand, we permit Gibbs
$\mathbb{P}$
, while in [
6]
$\mathbb{P}$
must be Bernoulli. The reason for our assumptions on
$\mathbb{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}\left\right)log\mathbb{P}\left(\right[{\omega}_{{C}_{n}}{]}^{\epsilon}\left)\right)$
, then it holds also for
$(1/{C}_{n}\left\right)log{\mathbf{W}}_{n}^{\epsilon}(\omega ,\sigma )$
. 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 (
$\alpha $
mixing) stochastic processes (
$d=1$
) with the difference that here we need to condition on
$(\epsilon ,\alpha )$
good patterns and use the Gibbs property instead of mixing.
LEMMA 2.
Let
$\mathbb{Q},\mathbb{P}$
be stationary Gibbs measures and assume that
$\alpha <1/2$
and
$0\le \epsilon <1$
. Then, for all
$q\in \mathbb{R}$
, the following function is welldefined:
$$\begin{array}{c}{\mathcal{\mathcal{E}}}_{\epsilon}\left(q\right):={\mathcal{\mathcal{E}}}_{\epsilon}(q;\mathbb{Q},\mathbb{P})={lim}_{n\to \infty}\frac{1}{\left{C}_{n}\right}log\int \mathbb{P}\left(\right[{\omega}_{{C}_{n}}{]}^{\epsilon}{)}^{q}d{\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}\left(\omega \right).\end{array}$$ 
(3.2)

(
${\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}$
denotes the measure
$\mathbb{Q}$
conditioned on the set of good patterns.)
The generalized
$q$
order Rényi entropy should be defined as
${\mathcal{\mathcal{E}}}_{\epsilon}(q)/q$
.
We now have the following theorem. By
${a}_{n}\approx {b}_{n}$
we mean that
$max\{{a}_{n}/{b}_{n},{b}_{n}/{a}_{n}\}$
is bounded from above.
THEOREM 3.
Let
$\mathbb{P}$
be a nonuniformly exponentially
$\phi $
mixing Gibbs measure and
$\mathbb{Q}$
a stationary and ergodic Gibbs measure. If
$\epsilon >0$
is small enough, then for any
${\alpha}_{0}\le \alpha <1/2$
, we have
$$\begin{array}{c}\int \int \left({\mathbf{W}}_{n}^{\epsilon}\right(\omega ,\sigma \left){)}^{q}d{\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}\right(\omega )d\mathbb{P}(\sigma )\approx \int \mathbb{P}(\left[{\omega}_{{C}_{n}}{]}^{\epsilon}{)}^{q}d{\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}\right(\omega )\text{if}q\ge 1\end{array}$$ 
(3.3)

and
$$\begin{array}{c}\int \int \left({\mathbf{W}}_{n}^{\epsilon}\right(\omega ,\sigma \left){)}^{q}d{\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}\right(\omega )d\mathbb{P}(\sigma )\approx \int \mathbb{P}(\left[{\omega}_{{C}_{n}}{]}^{\epsilon}\right)d{\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}\left(\omega \right)\text{if}q<1\end{array}$$ 
(3.4)

In particular,
$$\begin{array}{c}{lim}_{n\to \infty}\frac{1}{\left{C}_{n}\right}log\int \int \left({\mathbf{W}}_{n}^{\epsilon}\right(\omega ,\sigma \left){)}^{q}d{\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}\right(\omega )d\mathbb{P}(\sigma )=\{\begin{array}{c}{\mathcal{\mathcal{E}}}_{\epsilon}(q)\text{if}q\ge 1\\ {\mathcal{\mathcal{E}}}_{\epsilon}\left(1\right)\text{if}q<1.\\ \end{array}\end{array}$$ 
(3.5)

It follows from this theorem that Theorem 4.5.20 in [
7]
applies to large deviations of
$\left(\right(1/\left{C}_{n}\right)log{\mathbf{W}}_{n}^{\epsilon}(\eta ,\sigma ){)}_{n}$
. We do not know under which conditions the function
$q\mapsto {\mathcal{\mathcal{E}}}_{\epsilon}\left(q\right)$
is, for example, continuously differentiable for
$\epsilon $
small enough. It it were the case, we would get a large deviation principle for
$\left(\right(1/\left{C}_{n}\right)log{\mathbf{W}}_{n}^{\epsilon}(\eta ,\sigma ){)}_{n}$
with a rate function given by the Legendre transform of
${\mathcal{\mathcal{E}}}_{\epsilon}(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
$$\mathbb{P}(Z>s+tZ>t)=\mathbb{P}(Z>s)$$
or, equivalently,
$$\mathbb{P}(Z>s+t)=\mathbb{P}(Z>s)\mathbb{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}\subseteq {\mathbb{Z}}^{d}$
,
$i=1,\dots ,k$
, with equal volumes
$$\left{C}_{i}\right={\left(\frac{1}{\mathbb{P}\left({A}_{n}\right)}\right)}^{\gamma}$$
we have
$$\begin{array}{c}\mathbb{P}\left({A}_{n}{\text{does not occur in}}^{k}{\bigcup}_{i=1}{C}_{i}\right)\approx \mathbb{P}{\left({A}_{n}\text{does not occur in}{C}_{1}\right)}^{k}.\end{array}$$ 
(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}{]}^{\epsilon}$
, with
$[{A}_{n}{]}^{\epsilon}$
does not occur in volume
$V$
if any pattern
${B}_{n}\in [{A}_{n}{]}^{\epsilon}$
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 nontriviality of the parameter
${\Lambda}_{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
$\sigma $
restricted to a box that has later to be taken of size
$1/\mathbb{P}\left(\right[{A}_{n}\left]\right)$
. 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}\in {\mathcal{\mathcal{F}}}_{{C}_{n}}$
are events such that
$\mathbb{P}\left({E}_{n}\right)<{e}^{c{n}^{d}}$
for some
$c>0$
, and such that
$$\begin{array}{c}{limsup}_{n\to \infty}{\sum}_{0<\leftx\right<n}\frac{\mathbb{P}({E}_{n}\cap {\theta}_{x}{E}_{n})}{\mathbb{P}\left({E}_{n}\right)}<\infty \end{array}$$ 
(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 nontriviality 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}{]}^{\epsilon}$
, where
${A}_{n}$
is a good and typical pattern. We assume that patterns
${A}_{n}$
are such that
${\cap}_{n}{A}_{n}=\left\{\sigma \right\}$
, with
$\sigma $
chosen from the
$\mathbb{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}\in {\mathcal{G}}_{n}(\epsilon ,\alpha )$
with
$\epsilon /\alpha <{\epsilon}_{0}$
, there exists a finite
$C=C(\epsilon ,\alpha )$
such that for all
$n$
$$\begin{array}{c}{\sum}_{0<\leftx\right\le n}\frac{\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon}\cap {\theta}_{x}\left[{A}_{n}{]}^{\epsilon}\right)}{\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon})}\le C(\epsilon ,\alpha ).\end{array}$$ 
(4.3)

First of all, since
${A}_{n}\in {\mathcal{G}}_{n}(\epsilon ,\alpha )$
(see Definition 3 ), the terms corresponding to
$x$
with
$\leftx\right<\alpha n$
are equal to
$0$
. Therefore we have to estimate the sum
$$\begin{array}{c}{\sum}_{\alpha n\le \leftx\right\le n}\frac{\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon}\cap {\theta}_{x}\left[{A}_{n}{]}^{\epsilon}\right)}{\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon})}\end{array}$$ 
(4.4)

Note that for
$x$
with
$\leftx\right\ge \alpha n$
, the intersection
$({C}_{n}+x)\cap {C}_{n}$
is not very large:
$$\left\right({C}_{n}+x)\cap {C}_{n}\le (1\alpha ){n}^{d}.$$
Note also that
$\Delta (V,\omega ,{A}_{n})$
denotes the number of differences between
$\omega $
and
${A}_{n}$
in the volume
$V$
, see 2.1 . Then we can write
$$\begin{array}{c}\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon}\cap {\theta}_{x}\left[{A}_{n}{]}^{\epsilon}\right)=\mathbb{P}\left(\omega :\Delta ({C}_{n},\omega ,{A}_{n})\le \epsilon {n}^{d}\cap \Delta ({C}_{n}+x,\omega ,{\theta}_{x}{A}_{n})\le \epsilon {n}^{d}\right)\end{array}$$ 
(4.5)

where by
${\theta}_{x}{A}_{n}$
we mean
${\theta}_{x}{A}_{n}(y+x)={A}_{n}\left(y\right)$
,
$y\in {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 shorthand notations
$$\begin{array}{ccc}& & {S}_{1}=\Delta (C\backslash {C}_{x},\omega ,{A}_{n})\end{array}$$  
$$\begin{array}{ccc}& & {S}_{2}=\Delta (C\cap {C}_{x},\omega ,{A}_{n})\end{array}$$  
$$\begin{array}{ccc}& & {S}_{3}=\Delta (C\cap {C}_{x},\omega ,{\theta}_{x}{A}_{n})\end{array}$$  
$$\begin{array}{ccc}& & {S}_{4}=\Delta (C\backslash {C}_{x},\omega ,{\theta}_{x}{A}_{n}).\end{array}$$ 
(4.6)

With these notations what we have to estimate
$$\begin{array}{c}{\sum}_{\alpha n\le \leftx\right\le n}\frac{\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon}\cap {\theta}_{x}\left[{A}_{n}{]}^{\epsilon}\right)}{\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon})}={\sum}_{\alpha n\le \leftx\right\le n}\mathbb{P}({S}_{3}+{S}_{4}\le \epsilon {n}^{d}{S}_{1}+{S}_{2}\le \epsilon {n}^{d}).\end{array}$$ 
(4.7)

The following estimate is a corollary of [
4]
and a basic property of a Gibbs measures:
for any configuration
$\xi $
:
$$\begin{array}{c}\mathbb{P}\left(\right\{\omega :\Delta ({V}_{n},\omega ,\sigma )\le \epsilon \left{V}_{n}\right\left\}\right{\xi}_{{V}_{n}^{c}})\le exp(\left{V}_{n}\right\mathcal{\mathcal{R}}\left(\epsilon \right)+c\partial {V}_{n})\end{array}$$ 
(4.8)

Indeed, the unconditioned statement is proved in [
4]
, and conditioning can at most introduce a term of order
$exp\left(c\right\partial {V}_{n}\left\right)$
.
We proceed as follows
$$\begin{array}{cc}\mathbb{P}(({S}_{1}+{S}_{2})& \le \epsilon {n}^{d}\cap ({S}_{3}+{S}_{4})\le \epsilon {n}^{d})\end{array}$$  
$$\begin{array}{cc}& \le \mathbb{P}\left(({S}_{1}+{S}_{2})\le \epsilon {n}^{d}\cap {S}_{4}\le \epsilon {n}^{d}\right)\end{array}$$  
$$\begin{array}{cc}& \le {sup}_{\xi}\mathbb{P}({S}_{4}\le \epsilon {n}^{d}{\xi}_{{\mathbb{Z}}^{d}\backslash ({C}_{x}\backslash C)})\mathbb{P}(\left[{A}_{n}{]}^{\epsilon}\right)\end{array}$$  
$$\begin{array}{cc}& \le exp\left(\alpha {n}^{d}\mathcal{\mathcal{R}}\left(\frac{\epsilon}{\alpha}\right)+c{n}^{d1}\right)\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon}).\end{array}$$  
Therefore
$${\sum}_{\alpha n\le \leftx\right\le n}\frac{\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon}\cap {\theta}_{x}\left[{A}_{n}{]}^{\epsilon}\right)}{\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon})}\le {n}^{d}exp\left(\alpha {n}^{d}\mathcal{\mathcal{R}}\left(\frac{\epsilon}{\alpha}\right)+c{n}^{d1}\right)=:{C}_{n}(\epsilon ,\alpha ).$$
Taking into account that
$\epsilon /\alpha <{\epsilon}_{0}$
, and hence
$\mathcal{\mathcal{R}}(\epsilon /\alpha )>0$
, we conclude that
${C}_{n}(\epsilon ,\alpha )\to 0$
as
$n\to \infty $
, and hence
$$C(\epsilon ,\alpha )={sup}_{n}{C}_{n}(\epsilon ,\alpha )$$
is finite. This finishes the proof.
REMARK 1.
The parameters of Theorem 1 depend on the choice of
$\epsilon $
and
$\alpha $
. The most interesting is the dependence of
${\Lambda}_{1}$
and
${\Lambda}_{2}$
. TheParameter Lemma of [
1]
in fact shows that a uniform choice
${\Lambda}_{2}=2$
suffices. A more interesting question is whether we can give a uniform bound on
${\Lambda}_{1}$
for a large set of
$\epsilon $
and
$\alpha $
. 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
$\epsilon $
alone, the following choice of
${\Lambda}_{1}={\Lambda}_{1}(\epsilon ,\alpha )$
will suffice
$${\Lambda}_{1}=\frac{1}{c+C(\epsilon ,\alpha )}.$$
The rate distortion function
$\mathcal{\mathcal{R}}$
is a monotonically decreasing function.
Hence, for a fixed
$\epsilon >0$
,
$\alpha \mathcal{\mathcal{R}}\left(\frac{\epsilon}{\alpha}\right)$
is a monotonically increasing function of
$\alpha $
, and finally,
$C(\epsilon ,\alpha )$
is monotonically decreasing in
$\alpha $
. Therefore, if
$\epsilon <{\epsilon}_{0}$
, then for all
$\alpha >{\alpha}_{0}:=0.99\frac{\epsilon}{{\epsilon}_{0}}$
$${\Lambda}_{1}(\epsilon ,\alpha )\ge {\Lambda}_{1}(\epsilon ,{\alpha}_{0})>0.$$
Therefore, for a fixed
$\epsilon >0$
we obtain a uniform (in
$\alpha $
) bound on the parameter
${\Lambda}_{1}$
.
4.2 Proof of Proposition 2
For
$\epsilon =0$
we know that most patterns are
$(0,\alpha )$
good for any
$\alpha <1$
. Indeed, it is proved in [
1]
(lemma 5.3) that
$\mathbb{Q}\left({\mathcal{G}}_{n}\right(\epsilon ,\alpha \left)\right)\ge 1{e}^{{\kappa}^{\prime}{n}^{d}}$
, for some
${\kappa}^{\prime}>0$
.
Let us now argue that for small
$\epsilon $
this is still the case. Suppose
$\alpha <1/2$
, that is, we are going to consider vectors
$x\in {\mathbb{Z}}^{d}$
such that
$\leftx\right\le \frac{n}{2}$
. An element
$A$
of
$[{A}_{n}{]}^{\epsilon}\cap {\theta}_{x}[{A}_{n}{]}^{\epsilon}$
satisfies
$$\begin{array}{c}{\sum}_{y\in {C}_{x}\cap C}\leftA\right(y)A(yx\left)\right\le 2\epsilon {n}^{d}.\end{array}$$ 
(4.9)

(Recall that
$C={C}_{n}$
and
${C}_{x}={C}_{n}+x$
. This implies that there exists a set
${V}_{n}\subseteq C$
and a disjoint translate
${V}_{n}+z\subseteq C$
such that
$\left{V}_{n}\right>(1/2{)}^{d}{n}^{d}$
such that
${\theta}_{z}{A}_{{V}_{n}+z}$
matches with error fraction
${2}^{d+1}\epsilon $
with
${A}_{{V}_{n}}$
, this can be made as small as
${e}^{\nu {n}^{d}}$
, for some
$\nu >0$
, for
$\epsilon $
sufficiently small uniformly in
${A}_{{V}_{n}}$
by Lemma 1 . Therefore we obtain that
$$\begin{array}{c}\mathbb{Q}(\mathcal{G}(\epsilon ,{\alpha}_{0}\left)\right)>1{e}^{\nu {n}^{d}}\end{array}$$ 
(4.10)

for all
$\alpha <1/2$
and
$\epsilon $
small enough.
4.3 Proof of Theorem 2
We consider the case
$d=1$
only, because the case
$d\ge 2$
is completely analogous.
Start with the particular pattern
${A}_{n}=0\cdots 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
$\delta >0$
such that for all
$n\in \mathbb{N}$
,
$$\begin{array}{c}\delta <\mathbb{P}\left({\mathbf{T}}_{[{0}_{n}{]}^{\epsilon}}>\frac{1}{\mathbb{P}\left(\right[{0}_{n}{]}^{\epsilon})}\right)<1\delta \end{array}$$ 
(4.11)

which would imply the nontriviality of the parameter
${\Lambda}_{n}$
. We will first show that there exists a sequence
${k}_{n}\uparrow \infty $
such that
$$\begin{array}{c}\delta <\mathbb{P}\left({\mathbf{T}}_{[{0}_{n}{]}^{\epsilon}}>{k}_{n}\right)<1\delta .\end{array}$$ 
(4.12)

It will then follow easily from the Bernoulli character of
$\mathbb{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/\mathbb{P}\left(\right[{A}_{n}{]}^{\epsilon})=1/\mathbb{P}(\left[{0}_{n}{]}^{\epsilon}\right)$
.
We have the following identities:
$$\begin{array}{ccc}\mathbb{P}({\mathbf{T}}_{[{0}_{n}{]}^{\epsilon}}\le {k}_{n})& =& \mathbb{P}\left({}^{{k}_{n}}{min}_{k=0}{\sum}_{i=k}^{k+n}{\omega}_{i}\le n\epsilon \right)\end{array}$$  
$$\begin{array}{ccc}& =& \mathbb{P}\left({}^{{k}_{n}}{max}_{k=0}{\sum}_{i=k}^{k+n}(12{\omega}_{i})\ge (12\epsilon )n\right)\end{array}$$  
$$\begin{array}{ccc}& =& \mathbb{P}\left({}^{{k}_{n}}{max}_{k=0}({S}_{k+n}{S}_{k})\ge (12\epsilon )n\right)\end{array}$$ 
(4.13)

where
${S}_{n}$
is the position of a simple random walk on
$\mathbb{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
$$\begin{array}{c}{}^{{k}_{n}}{max}_{k=0}({S}_{k+n}{S}_{k})=alog{k}_{n}+bloglog{k}_{n}+c+o\left(1\right)+X\end{array}$$ 
(4.14)

where
$X$
is a random variable with a Gumbel distribution. Therefore, if we choose
${k}_{n}$
such that
$$\begin{array}{c}(12\epsilon )n=alog{k}_{n}+bloglog{k}_{n}+c+o\left(1\right)\end{array}$$ 
(4.15)

then ( 4.12 ) holds.
If we now choose any other pattern
${A}_{n}$
, then under
$\mathbb{P}$
,
${S}_{n}=2{\sum}_{i=0}^{n}(1/2{\sigma}_{i}{A}_{n}(i\left)\right)$
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
$$\mathbb{Q}\times \mathbb{P}\left\{(\omega ,\sigma ):log\left({\mathbf{W}}_{n}^{\epsilon}(\omega ,\sigma )\mathbb{P}\left(\right[{\omega}_{{C}_{n}}{]}^{\epsilon})\right)>logt\right\}=$$
$$\int d\mathbb{Q}\left(\omega \right)\mathbb{P}\left\{\sigma :log\left({\mathbf{T}}_{[{\omega}_{{C}_{n}}{]}^{\epsilon}}\left(\sigma \right)\mathbb{P}\left(\right[{\omega}_{{C}_{n}}{]}^{\epsilon})\right)>logt\right\}\le {e}^{{\Lambda}_{1}t}+C{e}^{K{n}^{d}}+{\sum}_{{A}_{n}\in {\mathcal{G}}_{n}^{c}(\epsilon ,\alpha )}\mathbb{Q}\left(\right[{A}_{n}\left]\right).$$
Now we choose
$t={t}_{n}=log\left({n}^{\gamma}\right)$
with
$\gamma >0$
such that
${\Lambda}_{1}\gamma >1$
. This makes the first term in the rhs summable in
$n$
. The last one equals the
$\mathbb{Q}$
measure of the complement of
${\mathcal{G}}_{n}(\epsilon ,\alpha )$
, which is less than
${e}^{\nu {n}^{d}}$
by Proposition 2 . We thus get the upper bound in 3.1 by an application of the BorelCantelli Lemma. Now we turn to prove the lower bound in 3.1 . Proceeding as before, we get
$$\mathbb{Q}\times \mathbb{P}\left\{(\omega ,\sigma ):log\left({\mathbf{W}}_{n}^{\epsilon}(\omega ,\sigma )\mathbb{P}\left(\right[{\omega}_{{C}_{n}}{]}^{\epsilon})\right)\le logt\right\}\le $$
$$1{e}^{{\Lambda}_{2}t}+C{e}^{K{n}^{d}}+{\sum}_{{A}_{n}\in {\mathcal{G}}_{n}^{c}(\epsilon ,\alpha )}\mathbb{Q}\left(\right[{A}_{n}\left]\right)\le $$
$${\Lambda}_{2}t+C{e}^{K{n}^{d}}+{e}^{\nu {n}^{d}}.$$
We have used Theorem 1 and Proposition 2 . We now choose
$t={t}_{n}={n}^{\gamma}$
, with
$\gamma >1$
, to get a summable upper bound in
$n$
for the above probability. An application of BorelCantelli 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
${\mathcal{S}}_{\square}$
be the system of all rectangular boxes of the form
$$V={\mathbb{Z}}^{d}{\cap}^{d}{\prod}_{k=1}[{m}_{k},{n}_{k}]\text{with}{m}_{k},{n}_{k}\in \mathbb{Z},{m}_{k}\le {n}_{k}.$$
Before proceeding, we have to extend definition 3 somewhat. We will denote by
${\mathcal{G}}_{V}(\epsilon ,\alpha )$
the set of good patterns supported on
$V\in {\mathcal{S}}_{\square}$
. We shall need Proposition 2 which remains valid if one replaces
${\mathcal{G}}_{n}(\epsilon ,\alpha )$
with
${\mathcal{G}}_{V}(\epsilon ,\alpha )$
and
$n$
by
$\leftV\right$
in 2.13 .
We are going to prove that the function
$a:{\mathcal{S}}_{\square}\to (\infty ,+\infty )$
defined as
$$a\left(V\right):=log\int {\mathbb{P}}^{q}\left(\right[{\sigma}_{V}{]}^{\epsilon}\left)d{\mathbb{Q}}_{{\mathcal{G}}_{V\cup {V}^{\prime}}(\epsilon ,\alpha )}\right(\sigma )$$
satisfies
$$a(V\cup {V}^{\prime})\le a\left(V\right)+a\left({V}^{\prime}\right)+C\partial (V\cup {V}^{\prime}\left)\right$$
for all
$V,{V}^{\prime}\in {\mathcal{S}}_{\square}$
such that
$V\cup {V}^{\prime}\in {\mathcal{S}}_{\square}$
and
$V\cap {V}^{\prime}=\mathbb{\varnothing}$
, where
$C$
is a constant (depends on
$q$
), and where
$\partial V$
denotes the boundary of
$V$
. Of course,
$\partial (V\cup {V}^{\prime}\left)\right$
is a surface order correction. If such a property holds (together with
$a(V+x)=a\left(V\right)$
, for all
$x\in {\mathbb{Z}}^{d}$
,
$V\in {\mathcal{S}}_{\square}$
which is obvious by stationarity of the measure), then a generalised subadditive lemma, obtained as a combination of a lemma found in [
8]
and another one given in [
7]
, will guarantee that
$${lim}_{n\to \infty}\frac{a\left({C}_{n}\right)}{\left{C}_{n}\right}$$
exists, as we wish. For all
$q\in \mathbb{R}$
,
$V,{V}^{\prime}\in {\mathcal{S}}_{\square}$
such that
$V\cup {V}^{\prime}\in {\mathcal{S}}_{\square}$
and
$V\cap {V}^{\prime}=\mathbb{\varnothing}$
, we have the following:
$${\mathbb{P}}^{q}\left(\right[{\sigma}_{V\cup {V}^{\prime}}{]}^{\epsilon})={\left({\sum}_{{\omega}_{V\cup {V}^{\prime}}\in [{\sigma}_{V\cup {V}^{\prime}}{]}^{\epsilon}}\mathbb{P}\left(\right[{\omega}_{V\cup {V}^{\prime}}\left]\right)\right)}^{q}\ge $$
$${e}^{{K}_{1}\partial (V\cup {V}^{\prime}\left)\right}{\left({\sum}_{{\omega}_{V\cup {V}^{\prime}}\in [{\sigma}_{V\cup {V}^{\prime}}{]}^{\epsilon}}\mathbb{P}\left(\right[{\omega}_{V}\left]\right)\mathbb{P}\left({\omega}_{{V}^{\prime}}\right])\right)}^{q}\ge $$
$${e}^{{K}_{2}\partial (V\cup {V}^{\prime}\left)\right}{\left({\sum}_{{\omega}_{V}\in [{\sigma}_{V}{]}^{\epsilon}}\mathbb{P}\left(\right[{\omega}_{V}\left]\right)\right)}^{q}{\left({\sum}_{{\omega}_{{V}^{\prime}}\in [{\omega}_{{V}^{\prime}}{]}^{\epsilon}}\mathbb{P}\left({\omega}_{{V}^{\prime}}\right])\right)}^{q}=$$
$${e}^{{K}_{2}\partial (V\cup {V}^{\prime}\left)\right}{\mathbb{P}}^{q}\left(\right[{\sigma}_{V\cup {V}^{\prime}}{]}^{\epsilon}\left){\mathbb{P}}^{q}\right(\left[{\sigma}_{V\cup {V}^{\prime}}{]}^{\epsilon}\right)$$
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
$$\int {\mathbb{P}}^{q}\left(\right[{\sigma}_{V\cup {V}^{\prime}}{]}^{\epsilon}\left)d{\mathbb{Q}}_{{\mathcal{G}}_{V\cup {V}^{\prime}}(\epsilon ,\alpha )}\right(\sigma )={\sum}_{{\omega}_{V\cup {V}^{\prime}}\in \{0,1{\}}^{V\cup {V}^{\prime}}}{\mathbb{P}}^{q}(\left[{\omega}_{V\cup {V}^{\prime}}{]}^{\epsilon}\right){\mathbb{Q}}_{{\mathcal{G}}_{V\cup {V}^{\prime}}(\epsilon ,\alpha )}\left(\right[{\omega}_{V\cup {V}^{\prime}}\left]\right)\ge $$
$$\mathbb{Q}\left({\mathcal{G}}_{V\cup {V}^{\prime}}\right(\epsilon ,\alpha \left)\right){e}^{{K}_{3}\partial (V\cup {V}^{\prime}\left)\right}\times $$
$${\sum}_{{\omega}_{V}\in \{0,1{\}}^{V}}{\mathbb{P}}^{q}\left(\right[{\omega}_{V}{]}^{\epsilon}\left){\mathbb{Q}}_{{\mathcal{G}}_{V\cup {V}^{\prime}}(\epsilon ,\alpha )}\right(\left[{\omega}_{V}\right])\times {\sum}_{{\omega}_{{V}^{\prime}}\in \{0,1{\}}^{{V}^{\prime}}}{\mathbb{P}}^{q}(\left[{\omega}_{{V}^{\prime}}{]}^{\epsilon}\right){\mathbb{Q}}_{{\mathcal{G}}_{V\cup {V}^{\prime}}(\epsilon ,\alpha )}\left(\right[{\omega}_{{V}^{\prime}}\left]\right)\ge $$
$$\frac{1}{2}{e}^{{K}_{3}\partial (V\cup {V}^{\prime}\left)\right}\int {\mathbb{P}}^{q}\left(\right[{\sigma}_{V}{]}^{\epsilon}\left)d{\mathbb{Q}}_{{\mathcal{G}}_{V}(\epsilon ,\alpha )}\right(\sigma )\times \int {\mathbb{P}}^{q}(\left[{\sigma}_{{V}^{\prime}}{]}^{\epsilon}\right)d{\mathbb{Q}}_{{\mathcal{G}}_{{V}^{\prime}}(\epsilon ,\alpha )}\left(\sigma \right)$$
where
${K}_{3}$
is a constant. The second inequality is the consequence of Proposition 2 if
$V\cup {V}^{\prime}$
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
$$\int \int \left({\mathbf{W}}_{n}^{\epsilon}\right(\omega ,\sigma \left){)}^{q}d{\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}\right(\omega )d\mathbb{P}(\sigma )=\int d{\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}(\omega )\int {\mathbf{T}}_{[{\omega}_{{C}_{n}}{]}^{\epsilon}}^{q}(\sigma )d\mathbb{P}(\sigma ).$$
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
${\mathbf{T}}_{\left[{\omega}_{{C}_{n}}\right]}$
is replaced by
${\mathbf{T}}_{[{\omega}_{{C}_{n}}{]}^{\epsilon}}$
, provided that
${\omega}_{{C}_{n}}$
be a
$(\epsilon ,\alpha )$
good pattern (see the beginning of the proof of Theorem 1 ), and
$\omega $
be
$\mathbb{Q}$
typical in the sense of Proposition 1 . Notice that we integrate with respect to the conditional measure
${\mathbb{Q}}_{{\mathcal{G}}_{n}(\epsilon ,\alpha )}$
which takes care of these two properties.
References

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.

M. Alzina, W. Szpankowski and A. Grama, 2dpattern matching, image and videocompression: theory, algorithms and experiments, IEEE Transactions on Image Processing 11 no. 3, (2002), 318331.

T. Berger, Rate Distorsion Theory: A Mathematical Basis for Data Compression. Englewood Cliffs, NJ: PrenticeHall, 1971.

Z. Chi, Conditional large deviation principle for finite state Gibbs random fields. Preprint (2002).

A. Dembo, I. Kontoyiannis, The asymptotics of waiting times between stationary processes, allowing distortion, Ann. Appl. Probab. 9 (1999), no. 2, 413–429.

A. Dembo, I. Kontoyiannis, Source coding, large deviations, and approximate matching, IEEE Trans. Inform. Th. 48 no. 6 (2002), 1590–1615.

A. Dembo, O. Zeitouni, Large deviations techniques and applications. Second edition. Applications of Mathematics (New York) 38. SpringerVerlag, New York, 1998.

H.O. Georgii. Gibbs Measures and Phase Transitions. Walter de Gruyter & Co., Berlin, 1988.

X. Guyon. Random Fields on a Network. Modeling, Statistics and Applications, Springer Verlag, New York, Berlin, 1995.

I. Kontoyiannis, Pattern matching and lossy data compression on random fields, IEEE Trans. Inform. Th. 49 no. 4 (2003), 1047–1051.

T. Luczak, W. Szpankowski, A suboptimal lossy data compression based on approximate pattern matching, IEEE Trans. Inform. Th. 43 no. 5 (1997), 1439–1451.

P. Révész, Random Walks in Random and NonRandom Environments, World Scientific, Singapore, New Jersey, London, Hong Kong, (1990).