High resolution coding of point processes and the Boolean model [original]

High resolution coding of point processes and the

Boolean model

vorgelegt von

Diplom-Mathematiker

Christian Vormoor

aus G¨ottingen

Von der Fakult¨at II - Mathematik und Naturwissenschaften

der Technischen Universit¨at Berlin

zur Erlangung des akademischen Grades

Doktor der Naturwissenschaften

Dr.rer.nat.

genehmigte Dissertation

Promotionsausschuss:

Vorsitzender: Prof. Dr. rer. nat. Michael E. Pohst

Berichter/Gutachter: Prof. Dr. rer. nat. Michael Scheutzow

Berichter/Gutachter: Prof. Dr. rer. nat. Klaus Ritter

Tag der wissenschaftlichen Aussprache: 12. Januar 2007

Berlin 2007

D 83

Abstract

The thesis High resolution coding of point processes and the Boolean model is a

contribution to the field of coding theory, with a special focus on the problem

of quantization, entropy constrained coding and random coding. We provide an

asymptotic upper bound for the quantization error of point processes on bounded

metric spaces with finite upper Minkowski-dimension. Therefore we consider the

point process conditioned upon the number of points and construct specific code-

books for these conditional processes. Via the cardinality of these codebooks we

get a relation between the quantization error and the given rate. As a special

case, we establish upper and lower bounds for the quantization error asymptotics

of a stationary Poisson point process on a compact subset of Rdunder Hausdorff-

distance. For the lower bound we use the relation between the quantization error

and the so called small ball probabilities. Furthermore we compute an asymptotic

upper bound of the entropy constrained error and compare the results with the

Gaussian case.

In the case of one dimension we introduce a D([0, a],{w1, . . . , wq})-valued random

element induced by a point process on the compact interval [0, a]⊂Rsatisfying

a certain growth condition and provide an asymptotic upper bound of the quan-

tization error under L1-distance. For a D([0,1],{0,1})-valued random element

induced by a stationary Poisson point process on [0,1] we give asymptotic upper

and lower bounds of the quantization error and compare these to the asymptotics

of the random coding error and the entropy constrained error.

We further discuss the Boolean model, where a random set is constructed as the

Minkowski sum of the points of a Poisson point process and a given random set,

e.g. a ball with random radius. For an asymptotic upper bound of the quantiza-

tion error under Hausdorff-distance we consider the corresponding Poisson point

process conditioned upon the number of points in a compact set. We use one

part of the given rate to code the number and the position of these points and

the rest of the rate to code the random compact sets. For the lower bound we use

again the relation between the quantization error and the small ball probabilities.

Therewith we provide asymptotic upper and lower bounds for the quantization

error under Hausdorff-distance and compare these with the asymptotics of the

quantization error of the Boolean model under the L1-distance.

Zusammenfassung

Die Arbeit High resolution coding of point processes and the Boolean model be-

sch¨aftigt sich mit der Kodierungstheorie, wobei ein besonderes Augenmerk auf

das Problem der Quantisierung, der Entropie beschr¨ankten Kodierung und der

zuf¨alligen Kodierung gelegt wird. Wir berechnen unter anderem asymptotische

obere Schranken des Quantisierungsfehlers eines Punkt Prozesses, dessen Ver-

teilung der Punktanzahl eine bestimmte Wachstumsbedingung erf¨ullt, auf einem

beschr¨ankten metrischen Raum mit endlicher oberer Minkowski-Dimension. Dazu

betrachten wir den Prozess bedingt auf die Anzahl seiner Punkte und konstruieren

f¨ur diese bedingten Prozesse spezielle Kodeb¨ucher. Mit Hilfe der M¨achtigkeit der

Kodeb¨ucher erhalten wir Beziehungen zwischen dem Fehler und der vorgegebenen

Rate. Insbesondere geben wir obere und untere Schranken f¨ur die Asymptotik des

Quantisierungsfehlers eines station¨aren Poisson Punkt Prozesses auf einer kom-

pakten Teilmenge des Rdunter Hausdorff-Abstand an. F¨ur die untere Schranke

benutzen wir den Zusammenhang zwischen dem Quantisierungsfehler und der

Wahrscheinlichkeit kleiner ε-Umgebungen um gegebene beliebige Kodebuchele-

mente. Ausserdem berechnen wir die Asymptotik des Entropie beschr¨ankten

Fehlers und vergleichen die Ergebnisse mit dem Gaußschen Fall.

Im eindimensionalen Fall f¨uhren wir ein D([0, a],{w1, . . . , wq})-wertiges Zufallse-

lement ein, dessen Spr¨unge durch einen Punkt Prozess auf dem kompakten Inter-

vall [0, a]⊂Rerzeugt werden, der eine bestimmte Wachstumsbedingung erf¨ullt.

F¨ur dieses berechnen wir eine obere asymptotische Schranke des Quantisierungs-

fehlers unter L1-Abstand. F¨ur ein D([0,1],{0,1})-wertiges Zufallselement, dessen

Spr¨unge durch einen station¨aren Poisson Punkt Prozess auf [0,1] erzeugt werden,

geben wir asymptotische obere und untere Schranken des Quantisierungsfehlers

an und vergleichen diese mit der Asymptotik des zuf¨alligen Kodierungsfehlers

und der des Entropie beschr¨ankten Fehlers.

Außerdem betrachten wir das Boolesche Modell, bei dem eine zuf¨allige Menge

durch die Minkowski-Summe der Punkte eines Poisson Punkt Prozesses und einer

gegebenen zuf¨alligen kompakten Menge, zum Beispiel ein Ball mit zuf¨alligem

Radius, konstruiert wird. F¨ur eine asymptotische obere Schranke des Quan-

tisierungsfehlers unter Hausdorff-Abstand betrachten wir erneut den zugrunde-

liegenden Punkt Prozess bedingt auf die Anzahl der Punkte in der kompak-

ten Menge. Wir benutzen einen Teil der zur Verf¨ugung stehenden Rate f¨ur die

Kodierung dieser Punkte und den restlichen Teil f¨ur die Kodierung der zuf¨alligen

kompakten Mengen, die zu den Poisson Punkten addiert werden. F¨ur die un-

tere Schranke benutzen wir wieder den Zusammenhang zwischen dem Quan-

tisierungsfehler und der Wahrscheinlichkeit kleiner ε-Umgebungen um gegebene

beliebige Kodebuchelemente. Damit erhalten wir obere und untere asymptotische

Schranken f¨ur den Quantisierungsfehler des Booleschen Modells unter Hausdorff-

Abstand und vergleichen diese mit der Asymptotik des Quantisierungsfehlers

unter L1-Abstand.

iii

Contents

Introduction vii

1 Preliminaries 1

1.1 Codingtheory............................. 1

1.2 Notation................................ 4

2 Jump processes, alternating renewal processes and the L1-dis-

tance 7

2.1 Definition and basic properties . . . . . . . . . . . . . . . . . . . . 7

2.2 Ajumpprocess ............................ 12

2.3 Deterministic coding of the alternating Poisson renewal process

under L1-distance........................... 26

2.4 Random coding of the alternating Poisson renewal process under

L1-distance .............................. 29

2.5 The entropy constrained coding of the alternating Poisson renewal

process under L1-distance ...................... 39

3 Point processes and the Hausdorff distance 45

3.1 Definition and basic properties . . . . . . . . . . . . . . . . . . . . 45

3.2 The quantization error of a point process in a bounded metric space 47

3.3 The quantization error of the Poisson point process under Haus-

dorffdistance ............................. 58

3.4 The entropy constrained error of the Poisson point process under

Hausdorffdistance .......................... 63

4 The Boolean model 65

4.1 Definition and basic properties . . . . . . . . . . . . . . . . . . . . 65

4.2 The quantization error of the Boolean model under Hausdorff dis-

tortion in one dimension . . . . . . . . . . . . . . . . . . . . . . . 69

4.3 The quantization error of the Boolean model under Hausdorff dis-

tortion................................. 78

4.4 The quantization error of the Boolean model under L1-distance . 99

5 Open problems 103

5.1 Coding alternating renewal processes . . . . . . . . . . . . . . . . 103

5.2 Coding point processes in bounded metric spaces . . . . . . . . . 103

5.3 Coding the Boolean model . . . . . . . . . . . . . . . . . . . . . . 104

A Appendix 105

A.1 A small ball inequality . . . . . . . . . . . . . . . . . . . . . . . . 105

Introduction

The present work is a contribution to the field of coding theory, with a special

focus on the problem of quantization. The aim is to send a random signal from a

source to a user via a given channel. One speaks of lossless source coding when-

ever it is possible to reconstruct the original signal perfectly. Else, there will be a

discrepancy between the original and the reconstruction: in this case one speaks

of lossy source coding, and we shall assume that this difference is measured by

a distortion measure. Usually, this inaccuracy is due to some constraints on the

capacity of the channel. In such a case, it becomes necessary to measure the

information one can transmit; as explained in the sequel, we shall be using four

different ways of measuring this information. A good introduction to the funda-

mentals of information theory can be found in Cover and Thomas [6] or in Gersho

and Gray [22].

From a mathematical standpoint, the problem is modeled using a separable Ba-

nach space (E, k.k) and a Borel measurable random element X. The main aim

of the present work is to give asymptotic upper and lower bounds for the mini-

mization problem

inf(E[kX−ˆ

Xks])1

s(1)

with s∈(0,∞), where the infimum is taken over a set of random elements ˆ

the received signals or reconstructions, which has an information constraint pa-

rameterized by n∈N.

Let us present the four different ways in which we shall be measuring the infor-

mation. The first one uses a set of deterministic subsets of E, whose cardinality

is bounded by n. In this case, we call (1) the quantization error of order sof X,

denoted by D(q),s(log n|X, k.k).

Another way of measuring the information is to use a codebook having random

elements, with a cardinality again bounded from above by n. In such a case, (1) is

called the random coding error of order sand is denoted by D(R),s(log n|X, k.k).

The third kind of constraint uses a bound on the entropy of the codebook ele-

ments, giving rise to D(e),s(log n|X, k.k) the entropy constrained error of order

s. The fourth kind of constraint uses the so called Shannon mutual informa-

tion of the original signal respective to the codebook element, which results in

Ds(log n|X, k.k) the Shannon distortion rate function. The first and the last two

vii

kinds of constraints were proposed by Kolmogorov in 1965 [31].

However, the leading pioneering figure of modern information theory is most cer-

tainly C.E. Shannon, who contributed fundamental reference works such as [40],

[41] and [37] in the 1940s, [42] in the 1950s and e.g. [38] in the 1970s, together

with his collaborators Oliver and Pierce. They introduced the idea of measur-

ing the complexity of a given signal through its entropy, and defined the mutual

information of two random elements via their conditional entropy.

Known results

An overview of the history of quantization and rate distortion theory was given

by Berger and Gray in 1998 ([2]), such an overview may also be found in [29].

In the 1960s, Zador issued several articles on this theme. Among other things,

he gave results for the asymptotic high-rate behavior of the entropy constrained

vector quantization (see [44] and [45]), which were generalized by Gray et al. (see

[30]).

Recent years saw a renewed interest for the topic, which resulted in a great

number of research publications from e.g. Graf, Luschgy, Pag`es, Dereich et al.

Dembo and Kontoyiannis studied in 2001 the convergence of the compression

ratio of a memoryless source, which is compressed using a variable length fixed-

distortion code (see[12]). In 2002 they presented a development of parts of rate-

distortion theory and pattern-matching algorithms for lossy data compression,

centered around a lossy version of the asymptotic equipartition property (AEP)

which relies on recent results of large deviation theory (see [13]).

Some of the main results for quantization error of continuous random variables

in a finite dimensional space are given in Bucklew and Wise [5] and in Graf

and Luschgy [23]. One of the essential contributions of [23] is to establish that

the asymptotics of the quantization error are related to the asymptotics of the

quantization error of a uniform distribution on the unit cube: let Ybe a Rd-valued

random vector with E[kYks+ε]<∞for some ε > 0. Denote the distribution of

Yby ν. Then it follows

lim

n→∞ns

d¡D(q),s(log n|Y, k.k)¢s=Qs([0,1]d)°

dνa

dλ(d)°

°d/(d+s)

where dνa

dλ(d)is the Radon-Nikodym density of the absolutely continuous part of ν

with respect to the Lebesgue measure λ(d)on Rdand k.kpdenotes the Lp-norm

induced by the probability measure Pon the set of real-valued random variables.

Qs([0,1]d) denotes a constant depending on the quantization error of order sof

the uniform distribution on [0,1]d.

The more general case of the quantization error in an infinite-dimensional Banach

space was treated by Fehringer in 2001 [21], by Dereich in 2003 (see [14] and

[15]), and by Dereich et al. in 2003 [16]. In these references, upper and lower

viii

bounds are given for the quantization error appearing in the reconstruction of a

centered Gaussian random element on a separable, infinite-dimensional Banach

space. Thereby, the asymptotics of the quantization problem are related to some

small ball probabilities: let µbe a centered Gaussian measure on a separable

Banach space (E, k.k). Define the small ball function ϕof the measure µas

ϕ(ε) = −log µ(B(0, ε)),

where B(b, ε) denotes the closed ball with center band radius ε. Under the

assumption that x7→ ϕ(1/x) is regularly varying at infinity with index a > 0

Dereich et al. stated in [16]

ϕ−1(log n).D(q),s(log n|µ, k.k)≤D(R),s(log n|µ, k.k).21+1/aϕ−1(log n),

the notation f(x).g(x), x →a, signifying that for any sequence (xk)k∈Nin R

with lim

k→∞xk=a, one has lim sup

k→∞

f(xk)

g(xk)≤1.

Moreover we write f(x)∼g(x), x →a, if f(x).g(x) and g(x).f(x), x →a.

In this case we call the functions fand g(strongly) asymptotically equivalent.

Moreover, fand gare called weakly asymptotically equivalent if there exists

C∈R+such that f(x).Cg(x) and g(x).Cf(x) as x→a. In this case we

write f(x)≈g(x) as x→a.

Recall that x7→ ϕ(1/x) is regularly varying at infinity with index a > 0 if there

exists a function Lwhich is slowly varying at infinity such that

ϕ(ε) = ε−aLµ1

ε¶, ε > 0,

and that the function L:]0,∞[→]0,∞[ is called slowly varying at infinity if

lim

t→∞

L(st)

L(t)= 1 for each s > 0 (see Bingham et al. [4]).

Furthermore, Dereich gave in his dissertation [14] asymptotic upper and lower

bounds for the distortion rate function via the small ball function: suppose that

ϕ−1(log n)≈ϕ−1(2 log n) as n→ ∞.Then, for any s≥1,

ϕ−1(log n).Ds(log n|µ, k.k)≤D(R),s(log n|µ, k.k).ϕ−1µlog n

2¶

as n→ ∞.

Interestingly, in this case the asymptotics of the quantization error and of the

random coding error are related to the distortion rate function.

Furthermore, Dereich stated in his dissertation results for the quantization prob-

lem of a centered Gaussian random measure µon a separable real Hilbert space

(H, h·,·i). Under the assumption that µhas infinite dimensional support denote

the sequence of eigenvalues of the covariance operator of µby {λk}k∈N. If this

sequence satisfies

lim

k→∞

log log(1/λk)

k= 0

he gave for the distortion rate function, the quantization error and the entropy

constrained error the following relation: for any s∈(0,∞) it follows

D(q),s(log n|µ, k.k)∼D2(log n|µ, k.k),(2)

as n→ ∞. And for any s∈(0,∞) it follows

D(e),s(log n|µ, k.k)∼Ds(log n|µ, k.k)∼D2(log n|µ, k.k),(3)

as n→ ∞ (see [14]).

In 2005 Dereich and Scheutzow gave results for the quantization and the entropy

coding of the fractional Brownian motion for the supremum and Lp[0,1]-norm

distortions (see [17]): Let H∈(0,1) and let W= (Wt)t≥0denote fractional

Brownian motion with Hurst index H. Denote by C([0, a]), a > 0,the space of

real-valued functions on the interval [0, a]. Furthermore denote by D([0, a]) the

space of right continuous functions with left limits (RCLL) on [0, a]. Both spaces

are endowed with the supremum norm k.k[0,a]. Let (Lp[0, a],k.kLp[0,a]) denote the

standard Lp-space of real-valued functions defined on [0, a]. Let Eand ˆ

Edenote

measurable spaces, and let d:E×ˆ

E→[0,∞) be a product measurable function.

Define the quantization error of the original Wby

D(q),s(log n|W, E, ˆ

E, d) := inf

πkd(W, π(W))ks,

where the infimum is taken over all measurable functions π:E→ˆ

Ewith discrete

image that has quantization rate log n > 0.

The entropy constrained error is defined by

D(e),s(log n|W, E, ˆ

E, d) := inf

πkd(W, π(W))ks,

where the infimum is taken over all measurable functions π:E→ˆ

Ewith discrete

image that has entropy rate log n > 0.

Choose as original space E=C([0,∞)). In the case where ˆ

E=D([0,1]) and

d(f, g) = kf−gk[0,1] Dereich and Scheutzow state in [17] that there exists a

constant κ=κ(H)∈(0,∞) such that for all s1∈(0,∞] and s2∈(0,∞),

lim

n→∞(log n)HD(e),s1(log n|W, E, ˆ

E, d) = lim

n→∞(log n)HD(q),s2(log n|W, E, ˆ

E, d) = κ.

(4)

In the case where ˆ

E=Lp[0,1] and d(f, g) = kf−gkLp[0,1] for some p≥1 it

follows that for every p≥1 there exists a constant κ=κ(H, p)∈(0,∞) such

that for all s∈(0,∞),

lim

n→∞(log n)HD(e),s(log n|W, E, ˆ

E, d) = lim

n→∞(log n)HD(q),s(log n|W, E, ˆ

E, d) = κ.

(5)

They showed that for the supremum norm-based distortion, all moments and

both information constraints lead to the same asymptotic approximation qual-

ity. For the Lp[0,1] norm-based distortions both information constraints lead to

the same asymptotic approximation quality, too. In particular, quantization is

asymptotically just as efficient as entropy coding.

Another approach to the quantization error problem is studied by Creutzig in his

doctoral dissertation ([8]), who established that the quantization error is related

to an approximation quantity called average Kolmogorov width. In 2006 Dereich

et al. studied in [19] the relation between quantization and numerical integration

of Lipschitz functionals on a Banach space by means of deterministic and ran-

domized (Monte Carlo) algorithms. In the course of that they determined the

asymptotic behavior of quantization numbers and Kolmogorov widths for diffu-

sion processes.

Further generalizations of the quantization problem and entropy constrained cod-

ing of Gaussian measures are studied by Graf and Luschgy. In [25], the exact

rates of convergence of the quantization error are derived for absolutely continu-

ous distributions and for self-similar distributions, and the rates of convergence

are related to the Hausdorff dimension of the distribution of the original signal.

The case of self-similar probabilities, corresponding to an iterated function sys-

tem of contracting similitudes, is treated in [26]. In this article, the authors gave

properties of the quantization dimension, which is studied in detail by Zhu [47]

in his doctoral dissertation. The sharp asymptotics for the entropy constrained

L2-quantization errors of Gaussian measures on a Hilbert space, in particular for

Gaussian processes, is derived by Graf and Luschgy in [27].

In 2003 Graf, Luschgy and Pag`es established a complete relationship between

upper and lower bounds of the quantization error and small ball probabilities

(see [24]). In 2006 they investigated the quantization problem for Radon random

vectors in Banach spaces, studied the existence of optimal quantizers and derived

their stationarity (see [28]).

Luschgy and Pag`es worked in 2002 on the quantization problem for random

vectors in an infinite-dimensional Hilbert space and in particular, for stochastic

processes (Xt)t∈[0,1] viewed as L2([0,1], dt)-valued random vectors. For Gaussian

vectors and the L2-error, they presented detailed results for stationary and opti-

mal quantizers and established a precise link between the rate problem and the

Shannon-Kolmogorov entropy of X. This yields the exact rate of convergence

to zero of the minimal L2-quantization error under rather general conditions on

the eigenvalues of the covariance operator (see [34]). In [35] Luschgy and Pag`es

investigated the functional quantization problem for one-dimensional Brownian

diffusions on [0, T]. They proposed several methods to construct some rate-

optimal quantizers and extended the results to d-dimensional diffusions when the

diffusion coefficient is the inverse of a gradient function.

In 2004 and 2006 Delattre, Graf, Luschgy and Pag`es considered the minimiza-

tion problem inf E[V(kX−ˆ

Xk)], where Vis a nondecreasing function. Under

certain conditions on V, they derived the precise asymptotics of the quantization

error for nonsingular distributions (see [10]) and for self-similar distributions (see

[11]), and gave the asymptotic performance of optimal quantizers using weighted

empirical measures.

Another generalization of the problem of quantization error asymptotics for a

Rd-valued random vector Xwith distribution µis given in Dereich and Vormoor

[18], where the quantity (E[kX−ˆ

Xks])1

s, which is to be minimized, is replaced

kX−ˆ

Xkϑ:= inf nt≥0 : Eϑ ³kX−ˆ

t´≤1o.

The norm k.kϑis called an Orlicz norm. Thereby the function ϑ: (0,∞)→(0,∞)

is monotonically increasing, left continuous with lim

t→0ϑ(t) = 0. Defining by

δ(n|X, ϑ) := inf

|range ˆ

X|≤n

kX−ˆ

Xkϑ

the quantization error under ϑone says that the quantization error problem is

studied under Orlicz norm distortion. The main result is the following: assume

that there exists a function Wwith E[W(kXk)] <∞and that Wsatisfies

a certain growth condition which depends on the function ϑ. If additionally

µa(Rd) supt≥1ϑ(t)>1 there exists a constant 0 < I < ∞such that

lim

n→∞n1/dδ(n|X, ϑ) = I1/d.

Alternating renewal processes, point processes

and the Boolean model

In this thesis we consider the quantization error of point processes on bounded

metric spaces and of alternating renewal processes induced by a point process

on [0, a]⊂R,a > 0, a compact interval. As a special case, we establish upper

and lower bounds for the quantization error asymptotics of a stationary Poisson

point process on a compact subset of Rd, and compare these to the asymp-

totics of the entropy constrained error. We further consider the Boolean model,

where a random set is constructed as the Minkowski sum of the points of a Pois-

son point process and a given random set, e.g. a ball with random radius. We

study the quantization error under two sorts of distances, the L1-distance and

the Hausdorff-distance.

In the first chapter we describe the basics of coding theory and give some nota-

tions and definitions corresponding to the several ways of measuring information

and the corresponding error functions.

In Chapter 2, we introduce simple point processes in Rdfor d≥1. Let (E, dE)

be an arbitrary metric space. Furthermore let q∈Nwith 2 ≤q < ∞and

xii

w1, . . . , wq∈Ewith wi6=wjfor i6=jand w:= maxi,j=1,...,q dE(wi, wj)<∞.

We define a jump process Yas a D([0, a],{w1, . . . , wq})-valued random element,

where D([0, a],{w1, . . . , wq}) denotes the Skorohod-space, the set of all RCLL

functions from [0, a] to {w1, . . . , wq}. The number and position of the jumps are

given by a simple point process Ψ on the interval [0, a] satisfying the following

growth condition. Defining for every B⊂[0, a] the number of the points of Ψ in

Bas NΨ(B) := ](Ψ ∩B) it satisfies: there exists a constant c∈R+such that

P[NΨ([0, a]) = k]≤ck·e−klog k,for all k∈N.

In Figure 1 we give a sketch of a realization of Y.

0 a

Figure 1: A jump process on [0, a]

We can interpret this kind of process firstly as a sound signal with finite number

of different notes, or alternatively as a picture with finite number of different

colors without combination colors.

For two D([0, a], E)-valued processes Yand Z, we define the L1-distance as

ρE

a(Y, Z) := Za

dE(Yt, Zt)dt,

the Lebesgue measure of the parts of the interval [0, a], where Yand Zare

in different states weigthed with the distance of the states in E. With these

preliminaries, we compute an asymptotic upper bound for the s-th moment of

the quantization error of Y. Denoting the quantization error of order sfor rate

n∈Nunder ρE

a-distance as D(q),s(log n|Y, ρE

a), the main theorem of this section

yields

D(q),s(log n|Y, ρE

a)≤e−(1+o(1))·√2

slog nlog log nas n→ ∞,

xiii

where odenotes the Landau symbol.

Furthermore, we introduce a special alternating renewal process Xas a

D([0, a],{0,1})-valued random element. The waiting times of Xare described by

independent identically exponential-λ-distributed random variables with λ > 0.

This means that the number and positions of the renewals are described by a sta-

tionary Poisson point process Φ on [0, a] with parameter λ. We call this process

Xan alternating Poisson renewal process. Moreover, we give asymptotic upper

and lower bounds for the quantization error of order sof Xunder L1-distance on

[0, a], denoted by ρa, that are stated in the following

D(q),s(log n|X, ρa) = e−(1+o(1))·√2

slog nlog log n, n → ∞.

For the lower bound we use the relation between the quantization problem and

small ball probabilities which is explained in [14], [15] or [16].

In the following sections we consider the random coding error and the entropy

coding error of the process X. For the entropy constrained error of order s, we

obtain the following upper bound:

there is a constant C(λ, s), depending only on λand ssuch that

D(e),s(log n|X, ρ1).eC(λ,s)·n−1

λas n→ ∞.

Let us remark that the asymptotic approximation bounds of the quantization

and the entropy constrained errors of the alternating renewal process Xunder

L1-norm distortion behave differently in contrast to the Gaussian case (see Equa-

tions (2) and (3)). Furthermore, it is interesting to observe that the asymptotic

upper bound of the quantization error depends on the s-th moment of the dis-

tortion while the asymptotic bound for the entropy constrained error is the same

for every s∈R+. On the other hand the asymptotics of the quantization error

do not depend on λ, the intensity of Φ, but the asymptotic upper estimate of the

entropy constrained error does.

This brings a contrast to the Gaussian case, where for the supremum norm-based

distortion, both information constraints lead to the same asymptotic approxi-

mation quality (see Equation (4)). For the Lp[0,1] norm-based distortions, both

information constraints lead again to the same asymptotic approximation quality

(see Equation (5)). In particular, quantization is asymptotically just as efficient

as entropy coding. This was shown by Dereich and Scheutzow in [17].

In the third chapter we turn to a more general subject. We introduce a simple

point process on an arbitrary metric space (E, dE). To compare two arbitrary

subsets of Ewe define the Hausdorff distance for A, B ⊂Eas

dH(A, B) := max ½sup

a∈A

d(a, B),sup

b∈B

d(b, A)¾,where d(A, B) := inf

b∈B

a∈A

dE(a, b).

xiv

Moreover, for a bounded metric space (E, dE) we define the upper Minkowski

dimension to be

dimME:= lim sup

ε→0

log M(E, ε)

log(1/ε).

Here, M(E, ε) denotes the smallest number of ε-balls needed to cover E.

M(E, ε) = min (j≥1 : there exist x1, . . . , xj∈Ewith E⊂

[

i=1

Bε(xi)),

where Bε(x) := {y∈E:dE(x, y)< ε}is the open ball around xof radius ε.

On a bounded metric space (E, dE) with upper Minkowski dimension dimM(E) =:

d < ∞, we introduce a special simple point process Υ, for which the total number

of the points in Ehas a distribution satisfying

P[](Υ ∩E) = k]≤ck·e−klog kfor all k≥1

with c∈R+constant. We give an asymptotic upper bound for the quantization

error of order srelative to this process Υ:

D(q),s(log n|Υ, dH)≤e−(1+o(1))·(2

sd ·log n·log log n)1

2, n → ∞.

Using this, we prove asymptotic upper and lower bounds for the quantization

error of order sof a stationary Poisson point process Φ on a compact cube

C:= [−l, l]d⊂Rd,l > 0, namely

D(q),s(log n|Φ, dH) = e−(1+o(1))·(2

sd ·log n·log log n)1

2, n → ∞.

Again, we consider in the following section the entropy constrained error of order

sand give an asymptotic upper bound for Φ on C:= [−l, l]d

D(e),s(log n|Φ, dH).√d·µ1

λ¶1/d

·n−1

d·λ·(2l)d, n → ∞.

This time, one may notice that the quantization error asymptotics do not depend

on the intensity of Φ or on λ(d)(C), the Lebesgue measure of the cube C, but on

s, while the entropy constrained error asymptotics do not depend on sbut on λ

and on λ(d)(C).

In Chapter 4, we come to a more general situation, that of the so called Boolean

model, denoted by Ξ. Let Kdbe the system of compact subsets of Rdand B(Kd)

the corresponding σ-field. The Boolean model is composed of the Minkowski

sum of a stationary Poisson point process Φ = {x1, x2, . . .}in Rd, the so called

germs, and a sequence of independent identically distributed random compact sets

Y1, Y2, . . . (here we deal with a ball with random radius) which are independent

of Φ, the so called grains. Let Y1satisfy

E£λ(d)(Y1+K)¤<∞for all compact K.

The Boolean model is defined as follows: Given the germs xiand the grains

Yias above a Boolean model is defined as a measurable map Ξ : (Ω,F, P )→

(Kd,B(Kd)) with

Ξ := ∞

[

i=1{xi+Yi}.

In Figure 2 we give a sketch of a realization of Ξ for the case d= 2 in the unit

square. Furthermore, Y0is a ball with random bounded radius.

(1,0) (1,1)

(0,1)(0,0)

Figure 2: The Boolean model with bounded balls

This construct is useful to model quite complicated compact sets in Rdwith

irregular boundaries. If the intensity λof Φ is small relative to the size of the

grains, then primary grains will not often overlap and hence, Ξ will consist mainly

of separated particles. A typical example of such systems is the set of nodular

graphite particles in cast iron. A random sparse configuration of plants may also

yield such a pattern over an area covered by vegetation.

With increasing λ, the number of overlaps increases. Simple examples of such

occurrences in nature are pores in cheese or areas of weeds in fields.

We differentiate between the cases d= 1 and d > 1. In the case of one dimension

and balls with random but bounded radii, the balls turn into intervals, so that

we can compare the Boolean model on the interval [0,1] with a D([0,1],{0,1})-

valued random element as considered in Section 2.3. As a consequence, we obtain

xvi

the following asymptotics for the quantization error of order s∈R+of Ξ:

D(q),s(log n|Ξ, dH) = e−(1+o(1))√2

s·log nlog log nas n→ ∞.

This corresponds to the asymptotics of the quantization error of order sof the

stationary Poisson point process in dimension one.

In the case d > 1 we obtain the following asymptotic upper bound for the quan-

tization error of order scorresponding to the Boolean model on a compact cube,

where the germs consist of a stationary Poisson point process and the grains of

balls with random but bounded radius:

D(q),s(log n|Ξ, dH)≤e−(1+o(1))q2

s(d+1) ·log nlog log nas n→ ∞.

In the case where the grains consist of compact sets that can be included in

a certain way by balls with independent identically distributed radii we get an

asymptotic lower bound for the quantization error of order sof the Boolean model

D(q),s(log n|Ξ, dH)≥e−(1+o(1))√2

sd ·log nlog log nas n→ ∞.

The asymptotics of the upper bound are the same as the asymptotics of the

quantization error of a (d+ 1)-dimensional Poisson point process. The reason

for this lies in the construction of the codebook: we use a codebook that first

codes a d-dimensional Poisson point process and uses more rate to code the radii

of the balls. Hence, intuitively we have ddimensions for the point process and

one dimension for the radii. But as the lower bound yields in the case d= 1 the

right asymptotics, we conjecture that this yields the right asymptotics as well in

the case d > 1. Heuristically, this may be understood by considering the overlaps

of the Boolean model. If the radii are quite large with high probability, we have

many overlaps in the Boolean model (e.g. some balls may be entirely contained

in other balls), and we need not code all points of the Poisson point process. If

the radii are that small that we do not have any overlaps, the Boolean model is

very close to the d-dimensional Poisson point process, and thus the quantization

error asymptotics may be equal.

In the last section of this chapter, we discuss the quantization error of the d-

dimensional Boolean model under ρ(d), the L1-distance on Rd. Although the

Hausdorff distance and the L1-distance are not equivalent, we obtain the same

asymptotic upper bound for the quantization error of a special Boolean model

on a compact cube with bounded grains, namely

D(q),s(log n|Ξ, ρ(d))≤e−(1+o(1))q2

s(d+1) ·log nlog log nas n→ ∞.

Finally, Chapter 5 discusses open problems.

xvii

Acknowledgment

Foremost, I thank my advisor Prof. Dr. Michael Scheutzow for introducing me to

an interesting area of probability theory and for his continual support throughout

my work on this thesis. I want to thank Prof. Dr. Klaus Ritter for accepting the

task of being the co-examiner of this thesis.

Furthermore, I thank my colleagues and friends Steffen Dereich, Andreij Depper-

schmidt, Georgi Dimitroff, Anne Gundel, Torben Edelhoff, Felix Esche, Matthias

an der Heiden, Anton Klimovskiy, Silke Meiner, Stephan Sturm, Michel Sortais,

Stefan Weber and Wiebke Wittm¨uß for fruitful discussions and helpful advice

and for generating the pleasant working environment at Technische Universit¨at

Berlin I have enjoyed so much over the years.

Financial support by the Deutsche Forschungsgemeinschaft through the Gra-

duiertenkolleg ”Stochastic Processes and Probabilistic Analysis” is gratefully ac-

knowledged.

xviii

Chapter 1

Preliminaries

1.1 Coding theory

The basic problem of coding theory consists in transmitting a message from a

source to an user. The fundamental choice of communication is whether the

message is reproduced either exactly or approximately. We will discuss the ap-

proximation approach and evaluate its fidelity.

The coding problem consists of

•a polish space (E, d), called the source alphabet,

•a probability distribution µon the Borel sets of E, called the source distri-

bution,

•a Borel measurable function ρ:E×E→[0,∞) with

–ρ(x, y) = ρ(y, x)∀x, y ∈E

–ρ(x, y)≥0∀x, y ∈Eand ρ(x, y) = 0 ⇔x=y,

called distortion measure.

Notice that ρis not necessarily a metric, because the triangle inequality need not

hold. Let (Ω,F, P) be the underlying probability space and X: Ω →Ebe a

µ-distributed random element (hereafter abbreviated by r.e.) on E, the original

data signal. Let ˆ

X: Ω →Ebe a random element on Ewhich is called the

received signal. The distortion between Xand ˆ

Xis modeled by ρ(X, ˆ

X).

As we have a capacity constraint of the channel we use for transmitting the signal,

it is important to measure the quantity of “information” we can transmit. We

measure this information by the following quantities: One possibility is admitting

a finite number of deterministic received signals, called the codebook.

Definition 1.1.1 For s∈R+we define the quantization error of order sof a

source (µ, ρ)in terms of the rate n∈Nas follows

D(q),s(log n|µ, ρ) := 

inf

C⊂E,|C|≤n



Z

min

y∈Cρ(x, y)sµ(dx)







Here C6=∅is called a codebook that is associated with a quantizer which associates

Xwith an optimal replication ˆ

Xin C. Sometimes we write D(q),s(log n|X, ρ)

instead of D(q),s(log n|µ, ρ)and for the case where s= 1 we use the notation

D(q)(log n|µ, ρ) := D(q),1(log n|µ, ρ).

One method of generalizing the quantization error is to use instead of a deter-

ministic codebook a codebook consisting of independent µ-distributed random

variables.

Definition 1.1.2 Let {Yj}j∈Nbe a sequence of independent µ-distributed random

elements which are independent of the original X. Denote for s∈R+and n∈N

D(R),s(log n|µ, ρ) = ³E[ min

j∈{1,...,n}ρ(X, Yj)s]´1

the average coding error when using the random sequence {Yj}j∈Nas codebook

elements. Again we use for the case where s= 1 the notation D(R)(log n|µ, ρ).

Another way of measuring the information is the entropy of ˆ

Definition 1.1.3 For a random element ˆ

X: Ω →Ewith countable range define

H(ˆ

X) := −X

x∈supp( ˆ

P(ˆ

X=x) log P(ˆ

X=x)

the entropy of ˆ

Entropy can be seen as a measure of “uncertainty” or “randomness” of a random

phenomenon. For a given probability distribution µthe entropy Hmeasures

how much freedom one is given to select an event, or how difficult to predict the

outcome.

Definition 1.1.4 We define the distortion under entropy constrained coding of

order s∈R+for rate log n > 0by

D(e),s(log n|µ, ρ)

:= ³inf nE[ρ(X, ˆ

X)s] : (X, ˆ

X)r.e. in E2,L(X) = µ, H(ˆ

X)≤log no´1

Analogously we define D(e)(log n|µ, ρ) := D(e),1(log n|µ, ρ).

D(e),s(log n|µ, ρ) is the minimal distortion that arises under the constraint that

the “uncertainty” of the replication ˆ

Xis smaller than log n≥0.

The fourth sort of constraining the capacity is the mutual information between

Xand ˆ

Definition 1.1.5 For any Borel probability measures ξand νon a Polish space

let

H(ξ||ν) := ½Rlog ¡dξ

dν ¢dν, if ξ¿ν

∞,else

the relative entropy of ξwith respect to ν.

The relative entropy measures the distance between two distributions. H(ξ||ν)

is a measure of the inefficiency of assuming that the distribution is νif the

true distribution is ξ. Note that it is not a true distance, because it is neither

symmetric nor does it satisfy the triangle inequality.

Definition 1.1.6 For two random elements Xand ˆ

Xon Ewith joint distribu-

tion P(X, ˆ

X)and marginal distributions PXand Pˆ

Xwe define the mutual informa-

tion I(X, ˆ

X)as the relative entropy of the joint distribution with respect to the

product distribution PXPˆ

I(X, ˆ

X) := H³P(X, ˆ

X)||PXPˆ

X´.

The mutual information measures the amount of information that one random

element contains about another random element. It describes the reduction of

uncertainty of one element due to the knowledge of the other.

Definition 1.1.7 For n > 1the Shannon distortion rate function of order s∈

R+is defined by

D(s)(log n|µ, ρ)

:= ³inf nE[ρ(X, ˆ

X)s] : (X, ˆ

X)r.e. in E2,L(X) = µ, I(X, ˆ

X)≤log no´1

with the convention D(log n|µ, ρ) := D(1)(log n|µ, ρ).

D(log n|µ, ρ) is the minimum distortion attainable by sending mutual information

not greater than log n. It is the main object used by Shannon in his works

1948 (see [40]) and 1959 ([42]). He considered the problem of reconstructing an

original Xon the basis of the information received via a channel with restricted

capacity. One of his main results is that the distortion rate function gives the

asymptotically best achievable accuracy between the original and its replication

in the latter problem.

Remark 1.1.8 Due to the fact that for any discrete replication ˆ

H(ˆ

X)≤log |supp( ˆ

X)|

and

I(X, ˆ

X)≤H(ˆ

X),

the coding quantities are ordered as follows

D(log n|µ, ρ)≤D(e)(log n|µ, ρ)≤D(q)(log n|µ, ρ), n ∈N.

1.2 Notation

Let f, g be two nonnegative real-valued functions on R. For a∈R∪{∞}∪{−∞}

we write

f(x).g(x), x →a,

if and only if for any sequence (xk)k∈Nin Rwith lim

k→∞xk=ait follows that

lim sup

k→∞

f(xk)

g(xk)≤1.

Moreover we write

f(x)&g(x), x →a, if g(x).f(x), x →a,

and

f(x)∼g(x), x →a, if f(x).g(x) and f(x)&g(x), x →a.

In this case we call the functions fand g(strongly) asymptotically equivalent.

Moreover, fand gare called weakly asymptotically equivalent if there exists

C∈R+such that f(x).Cg(x) and g(x).Cf(x) as x→a. In this case we

write f(x)≈g(x) as x→a.

Let f, g be two positive real-valued functions on R. For a∈R∪{∞} ∪{−∞}

we write the Landau symbols

f(x) = O(g(x)), x →a,

if and only if for any sequence (xk)k∈Nin Rwith lim

k→∞xk=athere exist M > 0

and k0∈Nsuch that for all k > k0

f(xk)< M ·g(xk),

and

f(x) = o(g(x)), x →a,

if and only if for any sequence (xk)k∈Nin Rwith lim

k→∞xk=ait follows that

lim

k→∞

f(xk)

g(xk)= 0.

Denote the Lebesgue measure in Rdby λ(d)and let bxc:= max{j∈N0|j≤x}

and dxe:= min{j∈N0|j≥x}for x∈R+.

During the whole work we will use the following proposition.

Proposition 1.2.1 There exist constants 0< c1≤1≤c2<∞such that for all

x∈Rwith x≥1it follows

c1·√x·³x

e´x≤Γ(x+ 1) ≤c2·√x·³x

e´x.

Proof: From Theorem 8.22 (Stirling’s formula) in Rudin [39] we conclude that

lim

x→∞

Γ(x+ 1)

√2πx ·¡x

e¢x= 1.

Hence, for every ε > 0 there exists x0≥1 such that for all x > x0we have

(1 −ε)·√2π·√x·³x

e´x≤Γ(x+ 1) ≤(1 + ε)·√2π·√x·³x

e´x.

The functions Γ(x+ 1) and f(x) := √2πx ·¡x

e¢xare continuous and strictly

monotonically increasing on [1,∞). Therefore we have Γ(x+ 1) ≥1 and f(x)≥

√2π·e−1for all x≥1. Thus

g(x) := Γ(x+ 1)

√2πx ·¡x

e¢x

is continuous for all x≥1. For all x≤x0it follows

Γ(2)

√2πx0·¡x0

e¢x0≤g(x)≤Γ(x0+ 1)

√2π·e−1.

Hence, gis continuous and strictly positive on [1, x0] and there exist constants

0< c1≤1≤c2<∞such that for all x∈Rwith x≥1 it follows

c1·√x·³x

e´x≤Γ(x+ 1) ≤c2·√x·³x

e´x.

Chapter 2

Jump processes, alternating

renewal processes and the

L1-distance

2.1 Definition and basic properties

One of the original signals we are going to code will be the Poisson point process.

In this section we introduce point processes, in particular the Poisson point pro-

cess and give some properties. Furthermore we define two jump processes whose

jumps are related to a special point process and to the Poisson point process on

R, respectively. Moreover, we introduce the distortion measure, which is defined

via the L1-norm. We follow the definition of point processes from Stoyan et al.

[43].

For δ > 0, a ∈Rddenote the open ball in Rdwith center aand radius δby

Bδ(a). Denote the system of the bounded Borel sets by Bb(Rd). A simple point

process is defined as a random element in a measurable space (G, G), where Gis

the family of all locally finite subsets ϕ, of Rd. Each ϕin Gcan be regarded as

a closed subset of Rd. An element ϕof Gcan also be regarded as a measure on

Rdso that Nϕ(B) is the number of points of ϕin B. The σ-field Gis defined as

the smallest σ-field on Gto make measurable all mappings ϕ→Nϕ(B) (for B

an arbitrary bounded Borel set).

Definition 2.1.1 A simple point process is defined as a random element Φin a

measurable space (G, G), i.e. Φ : (Ω,F, P)→(G, G)is measurable.

We denote the intensity measure of Φby

Λ(B) := E[NΦ(B)], B ∈Bb(Rd).

It is the expected number of points of Φin B.

Stationarity of a point process Φ means that Φ and the shifted process Φx:= Φ+x

for all x∈Rdhave the same distribution.

Remark 2.1.2 If Φ is stationary then Λ is of the form

Λ(B) = λ·λ(d)(B),0≤λ≤ ∞.

λis called the intensity of the point process (see Stoyan et al. [43], Section 4.1).

Choosing Bto have measure 1 shows that λmay be interpreted as the mean

number of points of Φ per unit volume. We shall always assume that 0 < λ < ∞.

Definition 2.1.3 A stationary Poisson point process with parameter λ > 0is

defined as a point process Φon (G, G)with the following properties:

•The number of points in pairwise disjoint sets B1, . . . , Bn∈Bb(Rd), i.e. the

random variables NΦ(B1), . . . , NΦ(Bn)are independent for all n= 1,2, . . ..

•The number of points NΦ(B)in B∈Bb(Rd)is Poisson distributed with

parameter λ·λ(d)(B), i.e.

P(NΦ(B) = m) = (λ·λ(d)(B))m

m!exp(−λ·λ(d)(B)).

Remark 2.1.4 If it is known that exactly npoints of Φ are in B∈Bb(Rd) then

the position of the points is uniformly distributed in B(see Daley and Vere-Jones

[9], page 21).

Let (E, dE) be an arbitrary metric space. For a∈R+the Skorohod-space

D([0, a], E) is the set of all right continuous functions with left limits (RCLL)

from [0, a] to E. We denote by B(D([0, a], E)) the smallest σ-field containing

all finite dimensional cylinder sets of the form

C:= {f∈ D([0, a], E);(f(t1), . . . , f(td)) ∈A},

where ti∈[0, a], i = 1, . . . , d and A∈B¡Ed¢where B¡Ed¢denotes the system

of Borel-sets in Ed.

Remark 2.1.5 In Chapter 3 of [3] Billingsley showed that for E=Rthe space

D([0, a], E) is metrizable by the Skorohod metric in such a way that D([0, a], E)

is a complete and separable metric space and that B(D([0, a], E)) is the smallest

σ-field containing all open sets.

Let q∈Nsatisfy 2 ≤q < ∞and let w1, . . . , wq∈Ewith wi6=wjfor i6=jand

w:= maxi,j=1,...,q dE(wi, wj)<∞. Let D([0, a],{w1, , . . . , wq})⊂ D([0, a], E)

denote the Skorohod-space of the RCLL mappings from [0, a] to {w1, , . . . , wq}

and B(D([0, a],{w1,,...,wq})) the corresponding σ-field.

Define

G[0,a]:= {φ⊂[0, a] : ](φ)<∞},

and G[0,a]as the smallest σ-field on G[0,a]to make all mappings φ→Nφ(B)

measurable for all bounded Borel sets B.

We define a jump process which lives on the time interval [0, a]. The distribution

of the number of the jumps has to satisfy a certain growth condition.

Definition 2.1.6 Let a∈R+. Let Ybe a D([0, a],{w1,,...,wq})-valued random

element that satisfies the following condition: The number and the position of the

jumps are described by a simple point process Ψon ¡G[0,a],G[0,a]¢that satisfies

P[NΨ([0, a]) = k]≤ck·e−klog kfor all k≥1

with c≥1constant. Denote by ψthe distribution of Ψ. We call this random

element Yajump process.

Now we define a special alternating renewal process with fixed starting distribu-

tion and corresponding to a Poisson point process.

Definition 2.1.7 Let Xbe a D([0, a],{0,1})-valued random element that satis-

fies the following conditions

•P[X0= 1] = P[X0= 0] = 1

•The number and the position of the jumps are described by a stationary

Poisson point process ΦXon ¡G[0,a],G[0,a]¢with parameter λ > 0. Denote

by µXthe distribution of ΦX.

We call this random element Xan alternating Poisson renewal process.

The process jumps between zero and one, so we can think of it as a sound signal

that is either high or low. The number and the position of the jumps are described

by a Poisson point process ΦXon the interval [0, a]. We define a random variable

NΦXthat is Poisson distributed with intensity λto characterize the distribution

of the number of jumps. The waiting times of Xin state zero or state one

respectively can be described by a sequence of exponential-λ-distributed random

variables (T1, T2, . . .), i.e.

P(Ti≤t) = 1 −e−λt with i= 1,2, . . . and t∈[0, a].

Denote by Si, i = 1, . . . the position of the i-th jump, i.e. Si=

k=1

Tk.

The definition of this process corresponds to the definition of a renewal process

with exponentially distributed waiting times (see Alsmeyer [1] or Cox [7]), but

normally the renewal process jumps at every renewal upwards, our process alter-

nates between jumping upwards and downwards.

Now we are going to define three distortion measures, one for jump processes, one

for alternating jump processes and one for random elements of the form (X0,ΦX).

Definition 2.1.8 For two D([0, a], E)-valued maps Zand Ydefine the distor-

tion measure ρE

a:D([0, a], E)×D([0, a], E)→[0,∞)by

ρE

a(Z, Y ) := Za

dE(Zs, Ys)ds.

Remark 2.1.9 For two D([0, a],{w1,,...,wq})-valued maps ˜

Yand ˜

Zclearly it

holds the upper bound

ρE

a(˜

Z, ˜

Y)≤w·a.

Consider now two D([0, a],{0,1})-valued random elements, i.e. two alternating

jump processes Yand Z. Denote the point process corresponding to Zby ΦZ

and the point process corresponding to Yby ΦY. Via Z0and ΦZthe stochastic

process Zis uniquely determined.

The next definition introduces a special case of the definition above with E=R,

dE(., .) = dR(., .) with dR(x, y) = |x−y|for all x, y ∈R,q= 2, w1= 0 and

w2= 1:

Definition 2.1.10 For two D([0, a],{0,1})-valued random elements Zand Y

define the distortion measure ρa:D([0, a],{0,1})×D([0, a],{0,1})→[0, a]by

ρa(Z, Y ) := kZ−YkL1([0,a],λ(1)):= Za

0|Zs−Ys|ds.

In the following we write k.kL1instead of k.kL1([0,a],λ(1))and in the case a= 1 we

write ρ(., .)instead of ρ1(., .).

With the preliminaries above we define the distortion measure between (Z0,ΦZ)

and (Y0,ΦY) as follows: we consider all points of ΦZand ΦY, order them and

express the distortion measure via Z0,Y0and ΦZ,ΦY.

Remark 2.1.11 For the case that Yhas dY∈Njumps and Zhas dZ∈N

jumps we denote the position of the jumps by 0 < SY

1< . . . < SY

dY≤aand

0< SZ

1< . . . < SZ

dZ≤arespectively. Now let

S1:= SZ

S2:= SZ

SdZ:= SZ

dZ,

SdZ+1 := SY

SdZ+2 := SY

SdZ+dY:= SY

and

A1:= min

j∈{1,...,dZ+dY}{˜

Sj}.

Without loss of generality let A1=˜

Si1with i1∈ {1, . . . , dZ+dY}. Let

A2:= min

j∈{1,...,dZ+dY}\{i1}{˜

Sj}.

Without loss of generality let A2=˜

Si2with i2∈ {1, . . . , dZ+dY}\{i1}. Let

A3:= min

j∈{1,...,dZ+dY}\{i1,i2}{˜

Sj}

AdY+dZ:= min{˜

Sj:j∈ {1, . . . , dZ+dY}\{i1, i2, . . . idY+dZ−1}}.

Then we have

0< A1≤A2≤. . . ≤AdY+dZ≤a.

Definition 2.1.12 With the preliminaries above and with

i=1 |A2i−A2i−1|:= 0

we define ˜ρ[0,a]:G[0,a]×G[0,a]→[0, a]

˜ρ[0,a](ΦZ,ΦY) := ∞

dZ=0

∞

dY=0

1{ΦZ([0,a])=dZ,ΦY([0,a])=dY}

·



1{dZ+dYeven}·

dZ+dY

i=1 |A2i−A2i−1|

+1{dZ+dYodd}·





dZ+dY−1

i=1 |A2i−A2i−1|+|a−AdZ+dY|









and ρ[0,a]:¡{0,1}×G[0,a]¢×¡{0,1}×G[0,a]¢→[0, a]with

ρ[0,a]((Z0,ΦZ),(Y0,ΦY)) := 1{Z0=Y0}·˜ρ[0,a](ΦZ,ΦY)

+1{Z06=Y0}·(a−˜ρ[0,a](ΦZ,ΦY)).

Lemma 2.1.13 With these definitions we have

kZ−YkL1=ρ[0,a]((Z0,ΦZ),(Y0,ΦY)).

Hence, it suffices to code (X0,ΦX)instead of X.

Remark 2.1.14 As ρa(., .) defines a metric on D([0, a],{0,1}), by ρ[0,a](., .) is

defined a metric on ¡{0,1}×G[0,a]¢and thus ˜ρ[0,a](., .) is a metric on G[0,a].

2.2 A jump process

In this section we consider the jump process from Definition 2.1.6 which lives on

the time interval [0, a] with a∈R+. The distribution of the number of the jumps

satisfies a growth condition. For this process we give an asymptotic upper bound

of the quantization error.

Theorem 2.2.1 Let s, a ∈R+and E={w1, . . . , wq}. Let Ybe a jump pro-

cess as stated in Definition 2.1.6. Denote the distribution of Yby ν. Let ψ

denote the distribution of the corresponding point process Ψ. Then we have for

the quantization error the following asymptotic upper bound

D(q),s(log n|Y, ρE

a)≤e−(1+o(1))·(2

slog n·log log n)1

2as n→ ∞.

Proof:

The proof is outlined as follows: first we split the distribution νof Yinto a

sum of several distributions. Then we deduce an upper bound for the sum by

constructing concrete codebooks for each of the summands.

Define NΨ(a) := ](Ψ ∩[0, a]). Let Yk:= Y|{NΨ(a)=k}and νkbe the distribution of

Yk. We split the distribution of Yvia

ν=∞

k=0

P[NΨ(a) = k]·νk.

Let Ψk:= Ψ|{NΨ(a)=k}and ψkbe the distribution of Ψk. Analogously we split the

distribution of Ψ via

ψ=∞

k=0

P[NΨ(a) = k]·ψk,

where Ψ0=∅almost surely.

Following the reasoning in Graf and Luschgy [23] we estimate the quantization

error of Yby the sum of the quantization errors of the Yk.

Let (nk)k∈N0be a sequence such that for all 0 ≤k≤4·q2slog n

log log nand for nlarge

enough it holds that nk≥1 and

∞

k=0

nk≤n.

For 0 ≤k≤4·q2slog n

log log nlet Ckbe an arbitrary codebook for νkwith |Ck| ≤ nk.

Let C:= b4·q2slog n

log log nc

k=0

Ck. For k > 4·q2slog n

log log nwe code the case of kjumps with

the codebook C0.

We estimate the quantization error of Yin the following way. Since Cis a

codebook for νwith |C| ≤ n, we deduce

(D(q),s(log n|ν , ρE

a))s

≤Zmin

y∈C(ρE

a(x, y))sdν(x)

=∞

k=0

P[NΨ(a) = k]·Zmin

y∈C(ρE

a(x, y))sdνk(x)

≤

b4·q2slog n

log log nc

k=0

P[NΨ(a) = k]·Zmin

y∈Ck

(ρE

a(x, y))sdνk(x)

+∞

k=b4·q2slog n

log log nc+1

P[NΨ(a) = k]·Zmin

y∈C0

(ρE

a(x, y))sdνk(x).(2.1)

Now we are going to construct the specific codebooks Ckwe are going to use for

the upper bound.

Without loss of generality assume e−1n≥q. In the case of no jumps we define

n0:= qand C0:= {ˆy(1)

0,...,ˆy(q)

0}with ˆy(i)

0(t) = wifor all t∈[0, a], i= 1, . . . , q as

the codebook for ν0. Hence, we can transmit and reconstruct the signal exactly

with only qelements in the codebook C0and it follows

Zmin

y∈C0

(ρE

a(x, y))sdν0(x) = 0 for n0=q. (2.2)

For the case where 1 ≤k≤4·q2slog n

log log nwe first construct codebooks for the point

process Ψkand therewith we introduce codebooks for Yk.

Let

Γ(k)

a:= {(x1, . . . , xk)∈[0, a]k: 0 < x1< x2< . . . < xk≤a}

and

∆(k)

a:= {(x1, . . . , xk)∈Rd:xi>0,∀i= 1, . . . , k and

i=1

xi≤a}.

Consider a realization of Ψkand denote the points in [0, a] by 0 < s1< s2<

. . . < sk≤a. Thus (s1, s2, . . . , sk)∈Γ(k)

a. Then using the bijective map

T: Γ(k)

a→∆(k)













7→ 











:= 





s2−s1

sk−sk−1







(2.3)

yields the tuple

(t1, t2, . . . , tk)∈∆(k)

Let

δ:= a·³jq−1

k·(q−1)−1·e−1

k·(k!)−1

k·n1

kk´−1.(2.4)

We show that for all 1 ≤k≤4·q2slog n

log log nand for nlarge enough it holds a

δ≥1

and this is valid if

q−1·(q−1)−k·e−1·(k!)−1·n≥1.

Using Proposition 1.2.1 yields

q−1·(q−1)−k·e−1·(k!)−1·n≥q−1·(q−1)−k·e−1·(c2·√k·kk)−1·n.

Thus there exists ˜c≤1 such that for all 1 ≤k≤4·q2slog n

log log nwe have

q−1·(q−1)−k·e−1·(k!)−1·n

≥˜ck·k−k·n

≥exp ³4·q2slog n

log log n·log ˜c−4·q2slog n

log log nlog ³4·q2slog n

log log n´+ log n´

= exp ³4·q2slog n

log log n·log ˜c−2√2slog nlog log n´

·exp ³−4·q2slog n

log log nlog ³4·q2s

log log n´+ log n´

−→ ∞ as n→ ∞.

Hence, for all 1 ≤k≤4·q2slog n

log log nand for nlarge enough we have

δ≥1 (2.5)

and therefore a

δ∈N.

We cover the simplex ∆(k)

awith small k−dimensional cubes with side length δ.

To cover the simplex we need

n(1)

k:= (a

δ, k = 1,

mk−1=1 Pmk−1

mk−2=1 ...Pm2

m1=1 m1, k ≥2,

small cubes. Since for all k≥1 it holds ∆(k)

a⊆[0, a]kand we need ¡a

δ¢ksmall

cubes to cover [0, a]kit follows

k!·³a

δ´k≤n(1)

k≤³a

δ´k,for all k≥1.(2.6)

Denote the small cubes by K(k),j

δ,j= 1 . . . , n(1)

k. We put in the center of each

small cube a coding point, denoted by (ˆ

t(j)

1, . . . , ˆ

t(j)

k), j = 1, . . . , n(1)

k. Our code-

book on the simplex is defined as the set of the center points of these small cubes.

Hence, we define the codebook for ψkby

Ck:= {(ˆs(j)

1, . . . , ˆs(j)

k) := T−1¡(ˆ

t(j)

1, . . . , ˆ

t(j)

k)¢:j= 1, . . . , n(1)

k}.

Now we define the codebook Ckfor Yk.

Ck:= {ˆy: [0, a]→ {w1, . . . , wq}: ˆys∈ {w1, . . . , wq}, s ∈[0,ˆs(j)

1[,

ˆys∈ {w1, . . . , wq}\{ˆyˆs(j)

i−}, s ∈[ˆs(j)

i,ˆs(j)

i+1[, i = 1, . . . , k −1,

ˆys∈ {w1, . . . , wq}\{ˆyˆs(j)

k−}, s ∈[ˆs(j)

k, a], j = 1, . . . , nk}

with ˆyt−:= lim

s%tˆys. Hence, |Ck|=n(1)

k·q·(q−1)k.

The cardinality of Ckis the rate we use for this case and thus we define

nk:= n(1)

k·q·(q−1)kfor all 1 ≤k≤4·s2slog n

log log n.

Since a

δ≥1 (see equation (2.5)) we have n(1)

k≥1 and therefore for nlarge enough

nk≥1 for all 1 ≤k≤4·s2slog n

log log n.(2.7)

Furthermore for k > 4·q2slog n

log log nwe define nk:= 0. With equation (2.6) and the

definition of δfollows

nk=n(1)

k·q·(q−1)k

≤³a

δ´k·q·(q−1)k

=³jq−1

k·(q−1)−1·e−1

k·(k!)−1

k·n1

kk´k·q·(q−1)k

≤e−1·1

k!·n, for all 1 ≤k≤4·s2slog n

log log n,

and, hence,

∞

k=0

nk≤q+

b4·q2slog n

log log nc

k=1

e−1·1

k!·n

≤∞

k=0

e−1·1

k!·n

=n. (2.8)

Now we give an upper bound of the error on the simplex ∆(k)

a. Let h∈ {1, . . . , n(1)

be fixed. For the case the original tuple (t1, . . . , tk) is in the small cube K(k),h

our coding point (ˆ

t(h)

1, . . . , ˆ

t(h)

k) is in the middle of this cube with side length δ.

Hence,

|ti−ˆ

t(h)

i| ≤ δ

2,for all i= 1, . . . , k, h = 1, . . . , n(1)

k.(2.9)

By construction we have ˆs(h)

i=Pi

j=1 ˆ

t(h)

jfor all i= 1, . . . , k, h = 1, . . . , n(1)

This leads with (2.9) to

h=1

1{(t1,...,tk)∈K(k),h

δ}·

i=1 |si−ˆs(h)

h=1

1{(t1,...,tk)∈K(k),h

δ}·

i=1 ¯¯¯¯¯

j=1

tj−

j=1

t(h)

j¯¯¯¯¯

≤

h=1

1{(t1,...,tk)∈K(k),h

δ}·

i=1

j=1 |tj−ˆ

t(h)

≤

i=1

j=1

i=1

i·δ

=k·(k+ 1) ·δ

4(2.10)

Consider a given realization ykof Ykwith jumps (s1, . . . , sk). Let (ˆs(h)

1, . . . , ˆs(h)

k) be

the corresponding codebook element for the jumps out of Ckwith h∈ {1, . . . , n(1)

k}.

For the realization of the jump process we choose the codebook element ˆy(m)

kout

of Ckthat satisfies (ˆy(m)

k)0= (yk)0and (ˆy(m)

k)ˆs(h)

i= (yk)sifor all i= 1, . . . , k and

m∈ {1, . . . , |Ck|}.

Clearly it holds

min

ˆyk∈Ck

ρE

a(yk,ˆyk)≤ρE

a(yk,ˆy(m)

≤w·λ(1)¡{t∈[0, a] : (ˆy(m)

k)t6= (yk)t}¢

and

{t∈[0, a] : (ˆy(m)

k)t6= (yk)t} ⊂

[

i=1 hmin{si,ˆs(h)

i},max{si,ˆs(h)

i}i

Therewith and with equation (2.10) we can deduce

min

ˆyk∈Ck

ρE

a(yk,ˆyk)≤w·

h=1

1{(t1,...,tk)∈K(k),h

δ}·

i=1 |si−ˆs(h)

≤w·k·(k+ 1) ·δ

and therefore for s∈R+

min

ˆyk∈Ck¡ρE

a(yk,ˆyk)¢s≤µw·k·(k+ 1) ·δ

4¶s

.(2.11)

Thus, with the definition of δ(see (2.4)) we deduce

Zmin

y∈Ck

(ρE

a(x, y))sdνk(x)

≤µw·k(k+ 1)

4¶s

·as·³jq−1

k·(q−1)−1·e−1

k·(k!)−1

k·n1

kk´−s

∼µw·a·k(k+ 1) ·(q−1)

4¶s

·qs

k·es

k·(k!)s

k·n−s

kas n→ ∞

uniformly in k∈ {1,...,b4·q2slog n

log log nc}.

Let C:= b4·q2slog n

log log nc

k=0 Ck. Due to equation (2.8) Cis a codebook for Ywith |C| ≤ n.

With equations (2.1) and (2.2) and with the growth condition satisfied by Y, it

follows for large nthat

(D(q),s(log n|Y, ρE

a))s

≤

b4·q2slog n

log log nc

k=1

ck·e−klog kZmin

y∈Ck

(ρE

a(x, y))sdνk(x)

+∞

k=b4·q2slog n

log log nc+1

ck·e−klog k·Zmin

y∈C0

(ρE

a(x, y))sdνk(x)

b4·q2slog n

log log nc

k=1

ck·e−klog k·µw·a·(q−1) ·k(k+ 1)

4¶s

·µ1

qe ·1

k!·n¶−s

+∞

k=b4·q2slog n

log log nc+1

ck·e−klog k·Zmin

y∈C0

(ρE

a(x, y))sdνk(x) (2.12)

For all n∈Nwe introduce the function

fn:R+→R+

k7→ ck·(k(k+ 1))s·µ1

q·e−11

Γ(k+ 1)¶−s

·e−klog k·n−s

From Proposition 1.2.1 we know there exists a constant c2≥1 such that c2·√k·

¡k

e¢k≥Γ(k+ 1) and therefore

fn(k)≤fn(k)

:= c

2·ks

2k·ks·e−s·ck·(k(k+ 1))s·³1

q·e−1´−s

k·e−klog k·n−s

From equation (2.12) and with the definition of fnwe split the sum and get for

large n

(D(q),s(log n|Y, ρE

a))s

b4q2slog n

log log nc

k=1 µaw(q−1)

4¶s

·fn(k)

+∞

k=b4q2slog n

log log nc+1

ck·e−klog k·Zmin

y∈C0

(ρE

a(x, y))sdνk(x)

=bcc

k=1 µaw(q−1)

4¶s

·fn(k) +

2q2slog n

log log nc

k=bcc+1 µaw(q−1)

4¶s

·fn(k)

b4·q2slog n

log log nc

k=b1

2q2slog n

log log nc+1 µaw(q−1)

4¶s

·fn(k)

+∞

k=b4·q2slog n

log log nc+1

ck·e−klog k·Zmin

y∈C0

(ρE

a(x, y))sdνk(x).(2.13)

We assert that the sum is of order

(D(q),s(log n|Y, ρE

a))s≤e−(1+o(1))·√2slog nlog log n, n → ∞.

To prove this we will discuss each part of the sum and start with the first one.

Part 1: We consider the case where 1 ≤k≤c. Define

α1(c, c2) := c·log c+slog c2+slog √c+ log((qe)s)−s

+2slog c+slog(c+ 1).

For these kwe consider

fn(k)

e−√2slog nlog log n

= exp ³p2slog nlog log n+k(log c−log k) + s

k(log c2+ log √k)´

·exp µ1

klog((qe)s)+2slog k−s+slog(k+ 1) −s

klog n¶

≤exp ³p2 log nlog log n+c·log c+slog c2+slog √c´

·exp ³log((qe)s)+2slog c−s+slog(c+ 1) −s

clog n´

= exp ³p2slog nlog log n−s

clog n+α1(c, c2)´

−→ 0 as n→ ∞.

which yields

Pbcc

k=1 ³aw(q−1)

4´s·fn(k)

e−√2slog nlog log n

=bcc

k=1 µaw(q−1)

4¶s

·fn(k)

e−√2 log nlog log n

≤ bcc·µaw(q−1)

4¶s

·exp ³p2slog nlog log n−s

clog n+α1(c, c2)´

−→ 0, n → ∞.

Hence,

bcc

k=1 µaw(q−1)

4¶s

·fn(k) = o(e−√2slog nlog log n), n → ∞.(2.14)

Part 2: In the second part of the sum klies between cand 1

2q2slog n

log log n. It is easy

to see that

α2(c, c2, n) := s

c³log c2+1

4log slog n

2 log log n´+1

clog((qe)s) + 2s·log ³1

2q2slog n

log log n´

−s+slog ³1

2q2slog n

log log n+ 1´

=o³−p2slog nlog log n´, n → ∞.

Therewith we can give an upper bound

fn(k)≤exp µs

cµlog c2+ log r1

2q2slog n

log log n¶+1

clog((qe)s)¶

·exp ³2slog ³1

2q2slog n

log log n´−s+slog ³1

2q2slog n

log log n+ 1´´

·exp ¡−√2slog nlog log n¢

= exp ³α2(c, c2, n)−p2slog nlog log n´

and hence,

2q2slog n

log log nc

k=bcc+1 µaw(q−1)

4¶s

·fn(k)

≤³aw(q−1)

4´s·exp ³log ³1

2q2slog n

log log n´+α2(c, c2, n)−√2slog nlog log n´.

Since

log ³1

2q2slog n

log log n´+α2(c, c2, n)−p2slog nlog log n

∼ −p2slog nlog log nas n→ ∞,

we get

2q2slog n

log log nc

k=bcc+1 µaw(q−1)

4¶s

·fn(k)≤e−(1+o(1))·√2slog nlog log n(2.15)

as n→ ∞.

Part 3: For the third part of the sum we first prove the following assertion: for

I:= {1, . . . , b4·q2slog n

log log nc−b1

2q2slog n

log log nc} we define

li:= b1

2q2slog n

log log nc+i

bq2slog n

log log nc

and

kli:= li·bs2slog n

log log nc, i ∈I.

We assert

log fn(kli)≤ −(1 + o(1))√2slog nlog log n, n → ∞, i ∈I.

To prove this we use the fact that

α3(c, c2, n) := 8 ·q2slog n

log log nlog c−1

2·q2slog n

log log n·log µ1

2·µ√2s−√(log log n)/log n

√log log n¶¶

+8 ·log ³8·³q2slog n

log log n−1´´

2·³q2slog n

log log n−1´·³log c2+1

2log ³8·q2slog n

log log n´´

2·³q2slog n

log log n−1´log((qe)s)+2slog ³8·q2slog n

log log n´−s

+slog ³8·q2slog n

log log n+ 1´

=o(p2slog nlog log n), n → ∞.

Without loss of generality assume q2slog n

log log n≥2. Therewith we deduce

li≤b4·q2slog n

log log nc

bq2slog n

log log nc≤4·q2slog n

log log n

q2slog n

log log n−1≤8 for all i∈I

and

li≥b1

2q2slog n

log log nc+ 1

bq2slog n

log log nc≥

2·q2slog n

log log n

q2slog n

log log n

2for all i∈I.

We consider log fn(kli)). As c≥1 we have log c≥0. Using the fact that for all

b∈R+it holds 1

2b+1

2b≥1 we get

log fn(kli)) ≤li·q2slog n

log log nlog c−li·³q2slog n

log log n−1´log ³li·³q2slog n

log log n−1´´

li·³q2slog n

log log n−1´·³log c2+1

2log ³li·q2slog n

log log n´´

li·³q2slog n

log log n−1´log((qe)s)+2slog ³li·q2slog n

log log n´−s

+slog ³li·q2slog n

log log n+ 1´−s

li·q2slog n

log log n

log n

=−(1

2li+1

2li)√2slog nlog log n+li·q2slog n

log log nlog c

−li·q2slog n

log log n·log µli·µ√2s−√(log log n)/log n

√log log n¶¶

+li·log ³li·³q2slog n

log log n−1´´

li·³q2slog n

log log n−1´·³log c2+1

2log ³li·q2slog n

log log n´´

li·³q2slog n

log log n−1´log((qe)s)+2slog ³li·q2slog n

log log n´−s

+slog ³li·q2slog n

log log n+ 1´

≤ −√2slog nlog log n+ 8 ·q2slog n

log log nlog c

−1

2·q2slog n

log log n·log µ1

2·µ√2s−√(log log n)/log n

√log log n¶¶

+8 ·log ³8·³q2slog n

log log n−1´´

2·³q2slog n

log log n−1´·³log c2+1

2log ³8·q2slog n

log log n´´

2·³q2slog n

log log n−1´log((qe)s)+2slog ³8·q2slog n

log log n´−s

+slog ³8·q2slog n

log log n+ 1´

=−√2slog nlog log n+α3(c, c2, n).

Using this in the third part of the sum yields

b4q2slog n

log log nc

k=b1

2q2slog n

log log nc+1 µaw(q−1)

4¶s

·fn(k)

≤

b4q2slog n

log log nc

k=b1

2q2slog n

log log nc+1 µaw(q−1)

4¶s

·exp(−√2slog nlog log n+α3(c, c2, n))

≤³aw(q−1)

4´s·4q2slog n

log log n·exp(−√2slog nlog log n+α3(c, c2, n))

=³aw(q−1)

4´s·exp ³log ¡4q2slog n

log log n¢−√2slog nlog log n+α3(c, c2, n)´

and since

log ¡4q2slog n

log log n¢−√2slog nlog log n+α3(c, c2, n)

∼ −√2slog nlog log nas n→ ∞

we get for large n

b4q2slog n

log log nc

k=b1

2q2slog n

log log nc+1 µaw(q−1)

4¶s

·fn(k)≤e−(1+o(1))√2slog nlog log n.(2.16)

Part 4: We consider the last part of the sum, where k > 4·q2slog n

log log n. We code

the case of kjumps with one of the n0codebook elements of C0, denoted by

Y(1)

0, . . . , ˜

Y(n0)

Due to Remark 2.1.9 we estimate the distortion between these codebook elements

and Ykby

Zmin

i=1,...,n0

(ρE

a(˜

Y(i)

0, x))sdνk(x)≤(aw)s.

Therefore we estimate the fourth part of the sum

∞

k=b4·q2slog n

log log nc+1

ck·e−klog k·Zmin

Y∈C0

(ρE

a(x, ˆ

Y))sdνk(x)

≤∞

k=b4·q2slog n

log log nc+1

ck·e−klog k·(aw)s.

Define

g(k) := ek·(log c−log k).

Consider

g(b4·q2slog n

log log nc+ 1)

e−√2slog nlog log n≤exp ¡√2slog nlog log n¢

·exp ³4·q2slog n

log log n³log c−log ³4·q2slog n

log log n´´´

= exp ¡−√2slog nlog log n¢

·exp ³4·q2slog n

log log n³log c−log ³4·q2s

log log n´´´

−→ 0 as n→ ∞.

Therefore g(b4·q2slog n

log log nc+ 1) = o(e−√2slog nlog log n) as n→ ∞.

For 4 ·q2slog n

log log n< k consider now

g(k+ 1)

g(k)=c·kk

(k+ 1)k+1

=c·µk

k+ 1¶k

·1

k+ 1

≤c·1

k+ 1

≤c·1

4·q2slog n

log log n+ 1

−→ 0, n → ∞.

Thus there exists a ˜n > 0 such that for all n > ˜nand k > 4·q2slog n

log log nwe have

g(k+ 1)

g(k)<1

Hence, for n > ˜nit holds

∞

k=b4·q2slog n

log log nc+1

g(k)

≤gÃb4·s2slog n

log log nc+ 1!·∞

k=b4·q2slog n

log log nc+1 µ1

2¶k−b4·q2slog n

log log nc−1

= 2 ·g(b4·q2slog n

log log nc+ 1)

=o(e−√2slog nlog log n), n → ∞.(2.17)

Combining now equations (2.13), (2.14), (2.15), (2.16) and (2.17) yields

(D(q),s(log n|Y, ρE

a))s≤e−(1+o(1))·√2slog nlog log nas n→ ∞

and thus

D(q),s(log n|Y, ρE

a)≤e−(1+o(1))·√2

slog nlog log nas n→ ∞.

In the following we consider the question whether the quantization error asymp-

totics will get better, if D([0, a], E)-valued codebook elements are admitted in-

stead of D([0, a],{w1, . . . , wq})-valued. That this is not the case is shown by the

following lemma.

Lemma 2.2.2 Let (E, dE)be a metric space and ˜

E⊆Emeasurable. Let Ybe

a˜

E-valued random element. Let C={f1, . . . , fn} ⊂ Ebe an arbitrary codebook

with n∈Nelements. Then there exists a codebook ˜

C={g1, . . . , gn}with n

elements which are taken from ˜

E, such that

Ehmin

g∈˜

dE(Y, g)i≤2·Ehmin

f∈C dE(Y, f)i.

Proof:

Consider an arbitrary ˜

E-valued random element Yand an arbitrary codebook

C={f1, . . . , fn}with n∈Nelements which are taken from E. Let (Ai)i=1,...,n

be a measurable partition of Esatisfying

dE(g, fi) = min

j=1,...,n dE(g, fj) for all g∈Ai

for i= 1, . . . , n, the so called Voronoi-regions (see Graf and Luschgy [23]). Let

Pi(.) := P(.|Ai).In the definition of the quantization error we consider

Ehmin

j=1,...,n dE(Y, fj)|Y∈Aii=E[dE(Y, fi)|Y∈Ai]

=EPi[dE(Y, fi)].

Assume that EPi[dE(Y, fi)] = κiwith κi∈R+constant. Then there exists gi∈˜

such that dE(fi, gi)≤κiand P[Y=gi]>0.Thus it follows

EPi[dE(Y, gi)] ≤EPi[dE(Y, fi)] + dE(fi, gi)

≤2·EPi[dE(Y, fi)].

This is valid for all i= 1, . . . , n. If we define the codebook ˜

C:= {g1, . . . , gn}we

can deduce

Ehmin

g∈˜

dE(Y, g)i≤2·Ehmin

f∈C dE(Y, f)i.

2.3 Deterministic coding of the alternating Pois-

son renewal process under L1-distance

In this section we deal with an alternating renewal process induced by a Poisson

point process and give upper and lower bounds for the asymptotics of the quan-

tization error.

Consider a D([0, a],{0,1})-valued random element Xas stated in Definition

2.1.7. The aim is to give asymptotically upper and lower bounds for the quanti-

zation error of Xwith rate n∈Nwith respect to the distortion measure ρafrom

Definition 2.1.10.

Theorem 2.3.1 Let a, s ∈R+. Let Xbe an alternating Poisson renewal process

as stated in Definition 2.1.7. Let µXdenote the distribution of the corresponding

Poisson point process ΦXwith intensity λ > 0. Then we have for the quantization

error the following estimate

D(q),s(log n|X, ρa) = e−(1+o(1))·(2

slog n·log log n)1

2, n → ∞.

Proof:

We split the proof into two parts, one for the upper and one for the lower bound.

We start with the upper bound.

We use Theorem 2.2.1. Hence, we have to prove, that Xsatisfies the conditions

of the theorem. By definition Xis a D([0, a],{0,1})-valued process which means

we can apply the results we got for the D([0, a],{w1, . . . , wq})-valued random

element using E=R,dE(., .) = dR(., .) with dR(x, y) = |x−y|for all x, y ∈R,

q= 2, w1= 0 and w2= 1. It remains to show, that the Poisson point process

ΦXsatisfies the condition

P[](ΦX∩[0, a]) = k]≤ck·e−klog kfor all k≥1

with c∈R+constant.

By definition of ΦXwe estimate with Proposition 1.2.1

P[](ΦX∩[0, a]) = k] = e−λa ·(λa)k

k!(2.18)

≤(λa)k

c1·√k·(k

e)k(2.19)

≤1

c1·(λae)k·e−klog k(2.20)

≤µλae

c1¶k

·e−klog k.(2.21)

Thus the growth condition is fulfilled, too. And we can apply Theorem 2.2.1 with

q= 2, w1= 0 and w2= 1 and it follows

D(q),s(log n|X, ρa)≤e−(1+o(1))·(2

slog n·log log n)1

2, n → ∞.(2.22)

Now we proceed with the lower bound.

Let

ε:= a

lq2slog n

log log nm.

Hence, a

ε∈N. We split the interval [0, a] into small intervals with length εand

denote them by ˜

I1, . . . , ˜

ε. Put in the center of every interval ˜

Iia smaller interval

Ii,i= 1, . . . , a

ε, with length ε

2. Consider the event Athat X0= 0 and every Ii

contains one of the points of the Poisson point process ΦX, i.e. the jumps of X,

and that [0, a]\(∪a

i=1Ii) contains no point. Now we give for small εthe probability

that this event Aoccurs.

P[A] = P[X0= 0] ·Ph

i=1 ³{NΦX(Ii) = 1}}´∩{NΦX([0, a]\(

[

i=1

Ii)) = 0}i

2·

i=1 ³e−λ·ε

2·λ·ε

2´·e−λ(a−a

ε·ε

2·e−λa ·³λ

2´a

ε·εa

ε.(2.23)

Let XA:= X|Abe the alternating Poisson renewal process Xconditioned upon

Aand let µX

Abe the distribution of XA. Denote the jumps of XAby {x1, . . . , xa

ε}

where xj∈Ij. Let

δ:= µsε

a+sε¶sε

·³ε

4´s·n−sε

Hence, δ1

s<ε

4. Consider an arbitrary codebook with nelements ˆ

X1, . . . , ˆ

Xn,

where the ˆ

Xj, j = 1, . . . , n, are taken from D([0, a],{0,1}). As

P[ρa(XA,ˆ

Xj)s< δ] = P[ρa(XA,ˆ

Xj)< δ1

we estimate the probability that the original signal XAand a codebook element

Xjhave a distance less than δ1

s. Due to Proposition A.1.1 we have

P[ρa(XA,ˆ

Xj)< δ1

s]≤³4δ1/s

ε´a/ε for all j= 1, . . . , n.

Using this we can estimate the quantization error of XAdepending on εand δas

follows

¡D(q),s(log n|XA, ρa)¢s≥δ·inf

Ccodebook Ã1−µX

AÃn

[

j=1

Bδ1

s(ˆ

Xj)!!

≥δ·inf

Ccodebook Ã1−

i=1

P[ρa(XA,ˆ

Xj)< δ1

s]!

≥δ·µ1−n·³4δ1/s

ε´a/ε¶.

Using the definition of δ=¡sε

a+sε¢sε

a·¡ε

4¢s·n−sε

ayields

¡D(q),s(log n|XA, ρa)¢s≥µsε

a+sε¶sε

·³ε

4´s·n−sε

a·µa

a+sε¶.

Weighting this estimate with the probability of Ayields combined with equation

(2.23) a lower bound for the quantization error

¡D(q),s(log n|X, ρa)¢s

≥P[A]·¡D(q),s(log n|XA, ρa)¢s

≥1

2·e−λa ·³λa

2´a

ε·³ε

a´a

ε·µsε

a+sε¶sε

·³ε

4´s·n−sε

a·µa

a+sε¶

= exp ³−log 2 −λa +a

εlog(λa

2)−a

εlog(a

ε) + sε

alog ¡sε

1+sε

a¢´

·exp ³slog(ε

4)−sε

alog n+ log ¡1

1+sε

a¢´.

With the definition of ε=a

lq2slog n

log log nmwe deduce

¡D(q),s(log n|X, ρa)¢s

≥exp ³−log 2 −λa +q2slog n

log log n·log(λa

2)−³q2slog n

log log n+ 1´log ³q2slog n

log log n+ 1´´

·exp µsµ1

q2slog n

log log n+1 ¶log µs

q2slog n

log log n+1+s¶+slog µa

4(q2slog n

log log n+1) ¶¶

·exp µ−sqlog log n

2slog nlog n+ log µ1

1+sqlog log n

2slog n¶¶

= exp µ−log 2 −λa +q2slog n

log log n·log(λa

2)−q2slog n

log log n·log µ√2s+qlog log n

log n

√log log n¶¶

·exp µ−log ³q2slog n

log log n+ 1´+sµ1

q2slog n

log log n+1 ¶log µs

q2slog n

log log n+1+s¶¶

·exp µslog µa

4(q2slog n

log log n+1) ¶+ log µ1

1+sqlog log n

2slog n¶¶

·exp ¡−√2slog nlog log n¢

= exp ¡−(1 + o(1)) ·√2slog nlog log n¢as n→ ∞,

and therefore

D(q),s(log n|X, ρa)≥exp ³−(1 + o(1)) ·q2

s·log nlog log n´(2.24)

as n→ ∞. Combining estimates (2.22) and (2.24) yields

D(q),s(log n|X, ρa) = exp ³−(1 + o(1)) ·¡2

slog n·log log n¢1

2´as n→ ∞.

2.4 Random coding of the alternating Poisson

renewal process under L1-distance

In this section we compute an upper bound for the random quantization error.

Theorem 2.4.1 Let Xbe a D([0,1],{0,1})-valued process as stated in Defini-

tion 2.1.7 whose jumps are generated by a Poisson point process ΦXwith intensity

λ. Let µdenote the distribution of Xand µXthe distribution of ΦX. Then we

have

D(R)(log n|X, ρ1)≤e−(1+o(1))·(2 log n·log log n)1

2as n→ ∞.

Proof:

As in the proof of the quantization error we consider the distribution µof Xand

decompose it as follows

µ=∞

k=0

e−λλk

k!·µk,

where µkdenotes the distribution of Xconditioned upon kjumps in [0,1].

Let n∈Nand denote by {Y(1), . . . , Y (n)}a sequence of D([0,1],{0,1})-valued,

independent µ-distributed random elements.

Therewith we can write D(R)(r|X, ρ1) as

D(R)(log n|X, ρ1)

=E[ min

j∈{1,...,n}kX−Y(j)kL1]

=∞

k=0

e−λλk

k!Z Z1

P[ min

j∈{1,...,n}kxk−Y(j)kL1≥ε]dε dµk(xk)

=∞

k=0

e−λλk

k!Z Z1

P[kxk−Y(1)kL1≥ε, . . . , kxk−Y(n)kL1≥ε]dε dµk(xk)

=∞

k=0

e−λλk

k!Z Z1

j=1

P[kxk−Y(j)kL1≥ε]dε dµk(xk)

=∞

k=0

e−λλk

k!Z Z1

0¡P[kxk−Y(1)kL1≥ε]¢ndε dµk(xk).(2.25)

Now we estimate the inner integral.

The deterministic realization xk, k = 1,2, . . . , has kjumps. The codebook

element Y(1) is µ-distributed. Denote by ΦY(1) the corresponding Poisson point

process. Let 0 < εk≤1. Then we estimate

P¡kxk−Y(1)kL1≥ε¢ndε =Zεk

P¡kxk−Y(1)kL1≥ε¢ndε

+Z1

εk

P¡kxk−Y(1)kL1≥ε¢ndε

≤εk+¡1−P¡kxk−Y(1)kL1< εk¢¢n

Consider P¡kxk−Y(1)kL1< εk¢. Denote the jumps of the realization xkby s1<

. . . < sk. We construct a diluted version of the set {s1, . . . , sk}as follows: starting

from the left we remove the first pair (sj, sj+1) that satisfies |sj+1 −sj| ≤ εk/k or

the first point that satisfies |1−sj| ≤ εk/k. Repeating this procedure until every

remaining point has a distance more than εk/k to his neighbor points or to the

point 1 leads to a new set {˜s1, . . . , ˜s˜

k}with ˜

k≤kand |˜sj+1 −˜sj|> εk/k for all

j= 1, . . . , ˜

k−1 and |1−sj|> εk/k for all j= 1, . . . , ˜

k. Consider the case where

k≥1. Let Abe the event, that Y(1)

0= (xk)0and Y(1) has exactly one jump inside

each interval [˜sj,˜sj+εk/k] for all j= 1, . . . , ˜

k. Thus A⊂ {kxk−Y(1)k< εk}and

P£kxk−Y(1)kL1< εk¤≥P[A]

≥1

2·e−λ·λ˜

k!·˜

k!·³εk

k´˜

≥1

2·e−λ·λ˜

k·³εk

k´k.

In the case where the diluted version has no jump we have

P£kxk−Y(1)kL1< εk¤≥1

2·e−λ.

Since εk≤1 and ˜

k= 0 we estimate

P£kxk−Y(1)kL1< εk¤≥1

2·e−λ

≥1

2·e−λ·λ˜

k·³εk

k´k.

Let ˜

λ:= min{1, λ}which leads to λ˜

k≥˜

λk. Hence,

P¡kxk−Y(1)kL1≥ε¢ndε ≤εk+¡1−P¡kxk−Y(1)kL1< εk¢¢n

≤εk+µ1−1

2·e−λ·˜

λk·³εk

k´k¶

Let αk:= 2

keλkk·˜

λ−kand εk:= ¡αk·log n

n¢1

k∧1. Hence,

P(kxk−Y(1)kL1≥ε)ndε

≤³¡αk·log n

n¢1

k∧1´+³³1−e−λ·˜

λk

kk·αk·log n

2n´n∨0´

≤µαk·log n

n¶1

+en·³−e−λ·˜

λk

kk·αk·log n

2n´

=µαk·log n

n¶1

+n−e−λ·˜

λk

kk·αk

and thus

Z Z1

P¡kxk−Y(1)kL1≥ε¢ndε dµk(xk)

≤Ãµαk·log n

n¶1

+n−e−λ·˜

λk

kk·αk

2·!Zdµk(xk)

=µαk·log n

n¶1

+n−e−λ·˜

λk

kk·αk

For the case where the realization x0of the original signal is constant, we will

have a positive distortion if every element of the codebook has at least one jump

or if (Y(i))06= (x0)0with i∈ {1, . . . , n}. Denote the realization of Y(i)by y(i).

Then kx0−y(i)kL1≤1 for all i= 1, . . . n. The probability that this event occurs

is e−λ·(1 −e−λ

2)n. Thus we estimate the random quantization error in equation

(2.25) as follows

D(R)(log n|X, ρ1)≤e−λ·(1 −e−λ

2)n

+∞

k=1

e−λλk

k!·µ¡αk·log n

n¢1

k+n−e−λ·˜

λk

kk·αk

2¶

Using e−λ<1 for λ > 0 and with the definition of αkfollows

D(R)(log n|X, ρ1)≤(1 −e−λ

2)n+∞

k=1

e−λλk

k!·¡2

keλ¢1

k·k·˜

λ−1·¡log n

n¢1

+∞

k=1

e−λλk

k!·n−1

k.(2.26)

We consider the first part of the estimate and assert

(1 −e−λ

2)n≤o(e−√2 log nlog log n) as n→ ∞.

Since λ > 0 it follows log(1 −e−λ

2)<0 and therefore

(1 −e−λ

2)n

e−√2 log nlog log n= exp ³n·log(1 −e−λ

2) + √2 log nlog log n´

→0 as n→ ∞.

Thus

(1 −e−λ

2)n≤o(e−√2 log nlog log n) as n→ ∞.(2.27)

Now we consider the first sum in estimate (2.26).

For all n∈Nwe introduce the function

˜γn:R+→R+

k7→ e−λ

λ·λk

Γ(k+ 1) ·µ2eλ

k¶1

·k·µlog n

n¶1

Using Proposition 1.2.1 we estimate

˜γn(k)≤e−λ

λλk·(c1·√k·¡k

e¢k)−1·³2eλ

k´1

k·k·¡log n

n¢1

For all k≥1 it follows k1

2≤2kand therefore

e−λ

λλk·c−1

1·ek·µ2eλ

k¶1

·k1

2≤e−λ(λe)k·2eλ

λc1·k1

≤(2λe)k·2

λc1

and hence,

˜γn(k)≤γn(k)

:= (2λe)k·2

λc1·k−k·µlog n

n¶1

.(2.28)

From equation (2.26) and with the definition of ˜γnand γnwe split the sum and

get

∞

k=1

e−λ

λ·λk

k!·µ2

keλ¶1

·k·µlog n

n¶1

≤∞

k=1

γn(k)

=b2λec

k=1

γn(k) +

2q2 log n

log log nc

k=b2λec+1

γn(k) +

b2·q2 log n

log log nc

k=b1

2q2 log n

log log nc+1

γn(k)

blog n

log log nc

k=b2·q2 log n

log log nc+1

γn(k) + ∞

k=blog n

log log nc+1

γn(k).(2.29)

We assert ∞

k=1

γn(k)≤e−(1+o(1))·(2 log n·log log n)1

2as n→ ∞.

To prove this we discuss the five parts and start with the first one.

Part 1: In the first part of the sum we have 1 ≤k≤2λe. Therewith we give an

upper bound for γn

γn(k) = exp ³k(log(2λe)−log k) + log( 2

λc1) + 1

k·log log n−1

klog n´

≤exp ³log(2λe) + log( 2

λc1) + log log n−1

2λe log n´.

Thus it follows

Pb2λec

k=1 γn(k)

e−√2 log n·log log n≤exp ³log(2λe) + log( 2

λc1) + log log n´

·exp µ−1

2λe log n+p2 log n·log log n¶

→0 as n→ ∞.

Hence,

b2λec

k=1

γn(k) = o³e−√2 log n·log log n´as n→ ∞.(2.30)

Part 2: In the second part of the sum klies between 2λe and 1

2q2 log n

log log n. There-

with we estimate

γn(k) = exp ³k(log(2λe)−log k) + log( 2

λc1) + 1

k·log log n−1

klog n´

≤exp ³log( 2

λc1) + 1

2λe log log n−√2 log nlog log n´.

and hence,

2q2 log n

log log nc

k=b2λec+1

γn(k)≤exp ³log(1

2q2 log n

log log n) + log( 2

λc1)´

·exp ¡1

2λe log log n−√2 log nlog log n¢.

Since

log(1

2q2 log n

log log n) + 1

2q2 log n

log log n·log(2λe) + log( 2

λc1) + 1

2λe log log n−√2 log nlog log n

∼ −(2 log nlog log n)1

2as n→ ∞,

we get

2qlog n

log log nc

k=1

γn(k)≤e−(1+o(1))√2 log nlog log nas n→ ∞.(2.31)

Part 3: For the third part of the sum we first prove the following assertion: for

I:= {1, . . . , b2·q2 log n

log log nc−b1

2q2 log n

log log nc} we define

li:= b1

2q2 log n

log log nc+i

bq2 log n

log log nc

and

kli:= li·bs2 log n

log log nc, i ∈I,

and deduce

log γn(kli)≤ −(1 + o(1))√2 log nlog log n, n → ∞, i ∈I.

To prove this we consider

β1(˜

λc1, λ, n) := 4 ·q2 log n

log log n·log(2λe) + log( 2

λc1)

+4 ·log(4 ·(q2 log n

log log n−1)) + 2

(q2 log n

log log n−1) log log n

−1

2·q2 log n

log log n·log(1

2·(√2−√(log log n)/log n

√log log n))

=o(−p2 log nlog log n), n → ∞ for all i∈I.

Without loss of generality assume q2 log n

log log n≥2. Therewith we can deduce

li≤b2·q2 log n

log log nc

bq2 log n

log log nc≤2·q2 log n

log log n

q2 log n

log log n−1≤4 for all i∈I

and

li≥b1

2q2 log n

log log nc+ 1

bq2 log n

log log nc≥

2·q2 log n

log log n

q2 log n

log log n

2for all i∈I.

Now consider log γn(kli). Using the fact that for all c∈Rit holds 1

2c+1

2c≥1 we

get

log γn(kli)≤li·q2 log n

log log n·log(2λe) + log( 2

λc1)

−li·³q2 log n

log log n−1´log ³li·³q2 log n

log log n−1´´

li·³q2 log n

log log n−1´·log log n−1

li·q2 log n

log log n

log n

=−(1

2li+1

2li)√2 log nlog log n+li·q2 log n

log log n·log(2λe) + log( 2

λc1)

+li·log(li·(q2 log n

log log n−1)) + 1

li·(q2 log n

log log n−1) log log n

−li·q2 log n

log log n·log(li·(√2−√(log log n)/log n

√log log n))

≤ −1·√2 log nlog log n+ 4 ·q2 log n

log log n·log(2λe) + log( 2

λc1)

+4 ·log(4 ·(q2 log n

log log n−1)) + 2

(q2 log n

log log n−1) log log n

−1

2·q2 log n

log log n·log(1

2·(√2−√(log log n)/log n

√log log n))

=−√2 log nlog log n+β1(˜

λc1, λ, n),for all i∈I.

Hence,

log γn(kli)≤ −(1 + o(1))p2 log nlog log nas n→ ∞ for all i∈I.

Using this in the third part of the sum yields for large n

b2q2 log n

log log nc

k=b1

2q2 log n

log log nc+1

γn(k)≤3

2q2 log n

log log n·exp(log γn(k))

= exp ³log ¡3

2qlog n

log log n¢+ log γn(k)´

= exp(−(1 + o(1))p2 log nlog log n).(2.32)

Part 4: In the fourth part of the sum we have 2q2 log n

log log n≤k≤log n

log log n. There-

with we estimate

γn(k) = exp ³k(log(2λe)−log k) + log( 2

λc1) + 1

k·log log n−1

klog n´

≤exp ³2q2 log n

log log n·³log(2λe)−log ³2q2 log n

log log n´´+ log( 2

λc1)´

·exp ³+1

2qlog log n

2 log n·log log n−log log n´

= exp ³2q2 log n

log log n·³log(2λe)−log ³2q2

log log n´´+ log( 2

λc1)´

·exp ³+1

2qlog log n

2 log n·log log n−log log n−√2 log nlog log n´

= exp ³−(1 + o(1))p2 log nlog log n´as n→ ∞.

Hence, we can estimate the fourth part of the sum

blog n

log log nc

k=b2q2 log n

log log nc+1

γn(k)

≤exp ³log( log n

log log n) + log γn(k)´

= exp ³−(1 + o(1))p2 log nlog log n´as n→ ∞.(2.33)

Part 5: We consider the last part of the sum. For k→ ∞ the term ¡log n

n¢1

increases monotonically to one for n > 1, hence, we can give an upper bound for

this part of the sum

∞

k=blog n

log log nc+1

γn(k)≤∞

k=blog n

log log nc+1

(2λe)k·2

λc1·k−k.

Define h(k) := (2λe)k·2

λc1·k−kand consider

h(blog n

log log nc+ 1)

e−√2 log nlog log n

≤exp ³log n

log log n(log(2λe)−log( log n

log log n)) + log( 2

λc1) + √2 log nlog log n´

−→ 0 as n→ ∞.

Thus, h(log n

log log n)≤o(e−√2 log nlog log n) as n→ ∞. Consider now for log n

log log n< k

h(k+ 1)

h(k)=2λe

k+ 1 ·³k

k+ 1´k

≤2λe

k+ 1

≤2λe

log n

log log n

−→ 0 as n→ ∞.

Hence, there exists a n0>0 such that for all n > n0and k > log n

log log nwe have

h(k+ 1)

h(k)<1

Therefore,

∞

k=blog n

log log nc+1

γn(k)≤∞

k=blog n

log log nc+1

h(k)

≤h(blog n

log log nc+ 1) ·∞

k=blog n

log log nc+1 ¡1

2¢k−b log n

log log nc−1

= 2 ·h(blog n

log log nc+ 1)

=o(e−√2 log nlog log n), n → ∞.(2.34)

Combining now equations (2.29), (2.30), (2.31), (2.32), (2.33) and (2.34) yields

∞

k=1

e−λ

λk

k!·¡2

keλ¢1

k·k·¡log n

n¢1

≤∞

k=1

γn(k)

≤e−(1+o(1))·(2 log ·log log n)1

2as n→ ∞.(2.35)

We consider now the second sum in equation (2.26) and assert

∞

k=1

e−λλk

k!·n−1

k≤e−(1+o(1))·(2 log ·log log n)1

2as n→ ∞.

To prove this we introduce the function

ˆγn:R+→R+

k7→ e−λ·λk

Γ(k+ 1) ·µ1

n¶1

Without loss of generality assume n≥e. This yields 1/n ≤(log n)/n. Using

Proposition 1.2.1 we can estimate

ˆγn(k)≤e−λλk·(c1·√k·¡k

e¢k)−1¡1

n¢1

≤1

c1·(λe)k·k−k·¡1

n¢1

≤1

c1·(2λe)k·k−k·¡log n

n¢1

=˜

2·γn(k)

with γn(k) defined in (2.28). Due to equation (2.35) we get

∞

k=1

e−λλk

k!·n−1

k≤∞

k=1

2·γn(k)

≤e−(1+o(1))·(2 log ·log log n)1

2as n→ ∞.(2.36)

Combining now equations (2.26), (2.27), (2.35) and (2.36) yields

D(R)(log n|X, ρ1)≤e−(1+o(1))·(2 log ·log log n)1

2as n→ ∞.

2.5 The entropy constrained coding of the al-

ternating Poisson renewal process under L1-

distance

Theorem 2.5.1 Let s∈R+. Let Xbe a D([0,1],{0,1})-valued process as stated

in Definition 2.1.7. Let µXbe the distribution of the corresponding Poisson point

process ΦXwith intensity λ > 0. Let

C(λ, s) := 1

λ·µlog 2 + λ−λlog λ+∞

k=2

e−λλk

k!log(k!)

+λ

s·log µ∞

k=0

e−λλk

k!·³k(k+1)

4´s¶¶.

Then we have for the entropy constrained error the following asymptotic upper

bound

D(e),s(log n|X, ρ1).eC(λ,s)·n−1

λas n→ ∞.

Proof:

The proof is outlined as follows: similarly to the proof of the upper bound for the

quantization error we construct a codebook by splitting the distribution µinto a

sum of distributions µkand create for each of the µka random codebook. For this

codebook we estimate the expected error and compute the entropy. Comparing

this with the rate log nyields an upper bound for the entropy constrained error.

Due to Lemma 2.1.13 it suffices to code (X0,ΦX) instead of X. Let Nt:=

NΦX([0, t]) be the number of jumps of Xin [0, t]. Let (ΦX)k:= ΦX|{N1=k}be the

process ΦXconditioned upon ΦXhas kpoints in [0,1]. Let µX

kbe the distribution

of (ΦX)k. We decompose µXinto

µX=∞

k=0

e−λλk

k!·µX

Due to Remark 2.1.4 µX

kis a product distribution of kuniform distributions on

[0,1]. µX

0describes the case of no jumps and we set µX

0(∅) = 1.

Recall the definitions

Γ(k):= Γ(k)

1={(x1, . . . , xk)∈[0,1]k: 0 < x1< x2< . . . < xk<1}

and

∆(k):= ∆(k)

1={(x1, . . . , xk)∈Rd:xi>0,∀i= 1, . . . , k and

i=1

xi<1}.

We identify µX

kwith a uniform distribution U(∆(k)) on the simplex ∆(k)in the

following way. By Remark 2.1.4 µX

kis a product distribution of pairwise indepen-

dent uniform distributions on [0,1]. Denote by ˜

S1, . . . , ˜

Skthe points. Hence, the

unordered tuple ( ˜

S1, . . . , ˜

Sk) is uniformly distributed on [0,1]k. By sorting the

tuple we get an ordered tuple (S1, . . . , Sk) that is uniformly distributed on Γ(k).

Using the bijective and measure preserving map Tdefined in (2.3) with a= 1 we

get the tuple (T1, . . . , Tk) that is uniformly distributed on ∆(k).

Let

C(λ, s) := 1

λ·µlog 2 + λ−λlog λ+∞

k=2

e−λλk

k!log(k!)

+λ

s·log µ∞

k=0

e−λλk

k!·³k(k+1)

4´s¶¶.

and

δ:= Ã$e−C(λ,s)·n1

λ·µ∞

k=0

e−λλk

k!·³k(k+1)

4´s¶1

s%!−1

.(2.37)

Hence, for nlarge enough we have 1

δ∈N. We cover the simplex ∆(k)with small

k−dimensional cubes with side-length δ. Denote the number of the cubes we

need to cover ∆(k)by jk. Hence,

jk=

lk−1=1

lk−1

lk−2=1

...

l1=1

Denote the small cubes by K(k),m

δ,m= 1, . . . , jkand the number of the cubes

that are completely inside ∆(k)by j(1)

k. Hence,

j(1)

δ−1

lk−1=1

lk−1

lk−2=1

...

l1=1

l1.

Denote the number of the cubes that are not completely inside ∆(k)by j(2)

Hence,

j(2)

k=jk−j(1)

lk−2=1

lk−2

lk−3=1

...

l1=1

l1.

Therefore we have

U(∆(k))hK(k),m

δi=(k!·δk, m = 1, . . . , j(1)

δk, m =j(1)

k+ 1, . . . , jk

and, hence,

U(∆(k))hK(k),m

δi≥δkfor all m= 1, . . . , jk.(2.38)

Denote the center of the cube K(k),m

δby (ˆ

t(m)

1, . . . , ˆ

t(m)

k) for m= 1, . . . , jk. We

introduce the random codebook. Let ˆ

Xbe a D([0,1],{0,1})-valued process with

starting point ˆ

X0and jump variable ˆ

Φˆ

Xwith

X0:= X0

and ˆ

Φˆ

X:= ∞

k=0

1{N1=k}

m=1

T−1³(ˆ

t(m)

1, . . . ˆ

t(m)

k)´·1nT(ΦX∩[0,1])∈K(k),m

δo.

Denote by X|{N1=k}the original signal Xunder the condition Xhas exactly

kjumps. Consider a realization xkof X|{N1=k}and denote the corresponding

realization of (ΦX)kby φk. Denote the corresponging realizations of the random

codebook defined above by ˆxkand ˆ

φk. Analogously to the proof of the upper

bound for the quantization error (see equation (2.10)) we estimate the distortion

of φkand ˆ

φk

˜ρ[0,1](φk,ˆ

φk)≤k·(k+ 1) ·δ

As ˆ

X0=X0this yields by Lemma 2.1.13

kxk−ˆxkkL1≤k·(k+ 1) ·δ

and, hence, for s∈R+

kxk−ˆxkks

L1≤µk·(k+ 1) ·δ

4¶s

Hence, we deduce

E·µZ1

0|Xt−ˆ

Xt|dt¶s¸=∞

k=0

P[N1=k]·E·µZ1

0|Xt−ˆ

Xt|dt¶s

|N1=k¸

≤∞

k=0

e−λ·λk

k!·µk(k+ 1)

4¶s

·δs.(2.39)

In the following we compute the entropy of ˆ

Xand show that it is smaller or equal

to log n.

Let

Φˆ

X|{N1=k}:=

m=1

T−1³(ˆ

t(m)

1, . . . ˆ

t(m)

k)´·1nT(ΦX∩[0,1])∈K(k),m

δo

be the random element of the jumps of the codebook element under the condition

N1=k. Then we have

H[ˆ

X] = H[ˆ

X0] + H[N1] + H[Φ ˆ

X|N1]

=H[ˆ

X0] + H[N1] + ∞

k=0

P[N1=k]·H[Φ ˆ

X|N1=k]

=H[ˆ

X0] + H[N1] + ∞

k=0

e−λλk

k!·H[Φ ˆ

X|N1=k]

We compute the terms of the sum. It is easily seen that H[ˆ

X0] = log 2. Further-

H[N1] = −∞

k=0

e−λλk

k!·log ³e−λλk

k!´

=λ−λlog λ+∞

k=2

e−λλk

k!log(k!)

Now with equation (2.38) follows

H[Φ ˆ

X|N1=k] = −

m=1

U(∆(k))hK(k),m

δi·log ³U(∆(k))hK(k),m

δi´

≥ −

m=1

U(∆(k))hK(k),m

δi·log ¡δk¢

= log Ãµ1

δ¶k!·

m=1

U(∆(k))hK(k),m

δi

=k·log µ1

δ¶.

Therefore we have

H[ˆ

X] = H[ˆ

X0] + H[N1] + ∞

k=0

e−λλk

k!·H[Φ ˆ

X|N1=k]

≤log 2 + λ−λlog λ+∞

k=2

e−λλk

k!log(k!) + ∞

k=1

e−λλk

k!·k·log µ1

δ¶.

Thus with the definition of δand C(λ, s) we estimate

H[ˆ

X]≤log 2 + λ−λlog λ+∞

k=2

e−λλk

k!log(k!) + ∞

k=1

e−λλk

k!·k·log µ1

δ¶

= log 2 + λ−λlog λ+∞

k=2

e−λλk

k!log(k!) + λ·log µ1

δ¶

≤log 2 + λ−λlog λ+∞

k=2

e−λλk

k!log(k!)

−λ·C(λ, s) + log n+λ

slog Ã∞

k=0

e−λλk

k!·µk(k+ 1)

4¶s!

= log n.

By construction of the codebook, equation (2.39) and the definition of δwe have

(D(e),s(log n|X, ρ1))s

≤∞

k=0

e−λ·λk

k!·³k(k+1)

4´s·δs

=∞

k=0

e−λ·λk

k!·³k(k+1)

4´s·Ã$e−C(λ,s)·n1

λ·µ∞

k=0

e−λλk

k!·³k(k+1)

4´s¶1

s%!−s

∼esC(λ,s)·n−s

λas n→ ∞

and hence,

D(e),s(log n|X, ρ1).eC(λ,s)·n−1

λas n→ ∞.

We compare the asymptotic bounds of the quantization error and the entropy

constrained error of the alternating Poisson renewal process with the asymptotics

of the fractional Brownian motion. The results for the quantization and the

entropy coding of the fractional Brownian motion for the supremum and Lp[0,1]

norm distortions are given by Dereich and Scheutzow in [17]. We repeat Theorem

1.1 and Theorem 1.3 of [17].

Let H∈(0,1) and let W= (Wt)t≥0denote fractional Brownian motion with

Hurst index H. Denote by C[0, a], a > 0,and by D[0, a] the space of real-

valued functions on the interval [0, a] and the space of RCLL functions on [0, a],

respectively. Both spaces are endowed with the supremum norm k.k[0,a]. Let

(Lp[0, a],k.kLp[0,a]) denote the standard Lp-space of real-valued functions defined

on [0, a]. Furthermore, k.kq, q ∈(0,∞] denotes the Lq-norm induced by the

probability measure Pon the set of real-valued random variables. Let Eand ˆ

denote measurable spaces, and let d:E×ˆ

E→[0,∞) be a product measurable

function. Define the quantization error of an original Yby

D(q)(log n|Y, E, ˆ

E, d, q) := inf

πkd(Y, π(Y))kq,

where the infimum is taken over all measurable functions π:E→ˆ

Ewith discrete

image that has quantization rate log n > 0.

The entropy constrained error is defined by

D(e)(log n|Y, E, ˆ

E, d, q) := inf

πkd(Y, π(Y))kq,

where the infimum is taken over all measurable functions π:E→ˆ

Ewith discrete

image that has entropy rate log n > 0.

Choose as original Y=Wand as original space E=C[0,∞). First treat the

case where ˆ

E=D[0,1] and d(f, g) = kf−gk[0,1]. Then Theorem 1.1 of Dereich

and Scheutzow [17] states

Theorem 2.5.2 There exists a constant κ=κ(H)∈(0,∞)such that for all

q1∈(0,∞]and q2∈(0,∞),

lim

n→∞(log n)HD(e)(log n|W, q1) = lim

n→∞(log n)HD(q)(log n|W, q2) = κ.

In the case where ˆ

E=Lp[0,1] and d(f, g) = kf−gkLp[0,1] for some p≥1 Theorem

1.3 of [17] yields

Theorem 2.5.3 For every p≥1there exists a constant κ=κ(H, p)∈(0,∞)

such that for all q∈(0,∞),

lim

n→∞(log n)HD(e)(log n|W, q) = lim

n→∞(log n)HD(q)(log n|W, q) = κ.

They showed that for the supremum norm-based distortion, all moments and

both information constraints lead to the same asymptotic approximation qual-

ity. For the Lp[0,1] norm-based distortions both information constraints lead to

the same asymptotic approximation quality, too. In particular, quantization is

asymptotically just as efficient as entropy coding.

In our case comparing the results of Theorem 2.5.1 and Theorem 2.3.1 shows that

the asymptotic bounds of the quantization and the entropy constrained error of

the renewal process under L1norm distortion are different. Furthermore it is

interesting that the asymptotic upper bound of the quantization error depends

on the s-th moment of the distortion while the asymptotic bound for the entropy

constrained error is the same for every s∈R+.

Chapter 3

Point processes and the

Hausdorff distance

3.1 Definition and basic properties

In the previous chapter we gave upper and lower bounds for the quantization

error of an alternating renewal process related to a Poisson point process in di-

mension one under L1-norm. In this chapter we deal with a more general subject,

the d-dimensional simple point processes which will be defined in the next section

and a d-dimensional Poisson point process as stated in Definition 2.1.3.

To compare two sets in Rd, we need a convenient distance. We define the Haus-

dorff distance for an arbitrary metric space (E, dE) and for (Rd, dRd).

Definition 3.1.1 Let (E, dE)be an arbitrary metric space. Let A, B ⊂Ebe two

arbitrary sets. The Hausdorff-distance of Aand Bis defined as

dH(A, B) := max ½sup

a∈A

d(a, B),sup

b∈B

d(b, A)¾,

where

d(A, B) := inf

b∈B

a∈A

dE(a, b).

For the special case of the empty set, we define dH(∅,∅) := 0 and dH(∅, A) := ∞

for A6=∅.

Definition 3.1.2 In the case E:= Rdwe denote for x:= (x1, . . . , xd)∈Rdthe

absolute value as follows

|x|:= v

i=1

We define the Hausdorff distance on Rdas stated in the above definition with

dE(a, b) = dRd(a, b) := |a−b|.

Remark 3.1.3 If Aand Bare unbounded subsets of Rd, the Hausdorff distance

may be infinite. Denoting by Kc(Rd) the set of non-empty compact subsets of

Rd, the space (Kc(Rd), dH(., .)) is a complete separable metric space (see Li et al.

[33], Theorems 1.1.2 and 1.1.3).

We define the L1-distance in Rdas follows

Definition 3.1.4 Let A, B ⊂Rdtwo arbitrary sets. Denote by

1A(x) = ½1, x ∈A,

0, x 6∈ A

the indicator function of A. Therewith define

ρ(d)(A, B) := k1A−1BkL1:= ZRd|1A(x)−1B(x)|dx

=λ(d)(A4B).

Which kind of distance one prefers depends on the intention: in case one is

interested in the exact volume of the set, where Aand Bdo not intersect, the

L1distance is the right one. If one is more interested in the gap between Aand

every part of B, the Hausdorff-distance yields the desired quantity.

Remark 3.1.5 The two distances are not equivalent which will be argued via

an example. For a∈Narbitrary let

A1:= {x= (x1, . . . , xd)|xi∈(Z∩[0, a]), i = 1, . . . , d}

and B1:= {x= (x1, . . . , xd)|xi∈(Z∩[−a, 0]), i = 1, . . . , d}.

Hence

dH(A1, B1) = √d·aand ρ(d)(A1, B1) = 0.

On the other hand for ε > 0 we define εZ:= {ε·j|j∈Z}. For a∈Nlet

A2:= {x= (x1, . . . , xd)|xi∈(εZ∩[0, a]), i = 1, . . . , d}

and B2:= [0, a]d.

Therefore

dH(A2, B2) = √d

2·εand ρ(d)(A2, B2) = ad.

3.2 The quantization error of a point process in

a bounded metric space

In the following section we will consider a bounded metric space that satisfies

some dimension conditions. Therefore we recall some definitions of Mattila [36].

Let (E, dE) be a bounded metric space. Here bounded means that the diameter

of Eis finite. The example we have in mind is a bounded subset of Rm.

Definition 3.2.1 For 0<ε<∞let M(E, ε)be the smallest number of ε-balls

needed to cover E.

M(E, ε) = min (j≥1 : there exist x1, . . . , xj∈Ewith E⊂

[

i=1

Bε(xi)),

where Bε(x) := {y∈E:dE(x, y)< ε}is the open ball around xof radius ε.

With this definition we introduce the so called Minkowski dimension.

Definition 3.2.2 For a bounded metric space we define the lower Minkowski

dimension as

dimME:= lim inf

ε→0

log M(E, ε)

log(1/ε),

and the upper Minkowski dimension as

dimME:= lim sup

ε→0

log M(E, ε)

log(1/ε).

We always have dimME≤dimME, but equality need not hold. If it holds we

write

dimME= dimME= dimME.

Remark 3.2.3 The upper and lower Minkowski dimension are also introduced

as the upper and lower box counting dimension (see Falconer, [20]).

Consider now a bounded metric space (E, dE) with d:= dimME < ∞.

A simple point process is defined as a random element in a measurable space

(˜

G, ˜

G), where ˜

Gis the family of all finite subsets ϕof E. Each ϕin ˜

Gcan be

regarded as a closed subset of E. An element ϕof ˜

Gcan also be regarded as a

measure on Eso that Nϕ(B) is the number of points of ϕin B. The σ-field ˜

Gis

defined as the smallest σ-field on ˜

Gto make all mappings ϕ→Nϕ(B) measurable

for all bounded Borel sets B.

Definition 3.2.4 A simple point process is defined as a random element Φin a

measurable space (˜

G, ˜

G), i.e. Φ : (Ω,F, P)→(˜

G, ˜

G)is measurable.

We now define the special point process we are going to give an asymptotic upper

bound for the quantization error.

Definition 3.2.5 Let Υbe a simple point process on (˜

G, ˜

G), that satisfies

P[](Υ) = k]≤ck·e−klog kfor all k≥1

with c∈R+constant. Denote the distribution of Υby υ.

Theorem 3.2.6 Let (E, dE)be a bounded metric space with d:= dimME < ∞.

Let s∈R+and denote the Hausdorff distance defined in 3.1.1 by dH. Let Υbe

a point process as stated in Definition 3.2.5. Let υdenote the distribution of Υ.

Then we have for the quantization error the following asymptotic upper bound

D(q),s(log n|Υ, dH)≤e−(1+o(1))·(2

sd ·log n·log log n)1

2, n → ∞.

Proof:

The proof is outlined as follows: first we split the distribution υof Υ into a sum

of several distributions. By constructing concrete codebooks we give for each

of them an upper estimate and therewith deduce an upper bound for the whole

sum.

Recall the definition NΥ(B) = ](Υ ∩B) for all B⊆E. Let Υk:= Υ|{NΥ(E)=k}

and υkbe the the distribution of Υk. We split the distribution of Υ via

υ=∞

k=0

P[NΥ(E) = k]·υk.

By definition of d= dimMEwe have the following:

lim sup

ε→0

log M(E, ε)

log(1/ε)=d,

and thus, for all δ > 0 there exists ε1>0 such that for all ε≤ε1we have

log M(E, ε)≤(d+δ)·log(1/ε),

and hence,

M(E, ε)≤ε−(d+δ).(3.1)

Let δ > 0 and let (nk)k∈N0be a sequence such that for all 0 ≤k≤4·q2slog n

(d+δ) log log n

it holds that nk≥1 and ∞

k=0

nk≤n

for nlarge enough. For 0 ≤k≤4q2slog n

(d+δ) log log nlet Ckbe an arbitrary codebook

for υkwith |Ck| ≤ nk. Let C:= b4q2slog n

(d+δ) log log nc

k=0

Ck. For k > 4·q2slog n

(d+δ) log log nwe

code the case of kpoints with one of the n1codebook elements of C1. Since Cis

a codebook for υwith |C| ≤ n, we can deduce

(D(q),s(log n|Υ, dH))s

≤Zmin

y∈C(dH(x, y))sdυ(x)

=∞

k=0

P[NΥ(E) = k]·Zmin

y∈C(dH(x, y))sdυk(x)

≤

b4q2slog n

(d+δ) log log nc

k=0

P[NΥ(E) = k]·Zmin

y∈Ck

(dH(x, y))sdυk(x)

+∞

k=b4q2slog n

(d+δ) log log nc+1

P[NΥ(E) = k]·Zmin

y∈C1

(dH(x, y))sdυk(x).(3.2)

Now we are going to construct the codebooks Ckwe use for the estimate.

Without loss of generality assume e−1·n≥1 and define n0:= 1. In the case

where the realization of Υ has no point we define C0:= {∅} as the codebook for

υ0. Hence,

Zmin

y∈C0

(dH(x, y))sdυ0(x) = 0 for n0= 1.(3.3)

Consider the case where 1 ≤k≤4q2slog n

(d+δ) log log nand let

εk,n := e1

k(d+δ)·(k!) 1

k(d+δ)·n−1

k(d+δ).

Without loss of generality assume nto be large enough such that equation (3.1)

is satisfied. Denote the smallest number of εk,n-balls needed to cover Eby M:=

M(E, εk,n) and let ˆ

M:= ˆ

M(E, εk,n, δ) := ε−(d+δ)

k,n . For nlarge enough we have

that εk,n is small uniformly for all 1 ≤k≤4q2slog n

(d+δ) log log n. Hence, due to equation

(3.1) for large nwe have

M≤ˆ

M. (3.4)

Denote the M ε-balls by ˆ

B1, . . . , ˆ

BMand their centers by ˆx1, . . . , ˆxM. Let I:=

{ˆx1, . . . , ˆxM}. As the original signal has exactly kpoints we have to allocate k

or less than kcoding points in the centers of the Mballs to get a distortion less

than εk,n. We define the codebook Ckfor the point process as the set of all these

allocations

Ck:= {ˆy⊂I:|ˆy|=i, i = 1, . . . , k},

which yields

|Ck|=

i=1 µM

i¶.

We define the rate we are going to use for this case by

nk:= |Ck|.

It is easy to verify, that for all 1 ≤k≤4q2slog n

(d+δ) log log nand ˆ

M≥2 it holds

1≤nk≤Mk≤ˆ

Mk(3.5)

due to equation (3.4). For k > 4·q2slog n

(d+δ) log log nwe define nk:= 0. Due to

equations (3.5) and the definitions of ˆ

Mand of εn,k it follows for large n

∞

k=0

nk≤1 +

b4·q2slog n

(d+δ) log log nc

k=1

≤1 +

b4·q2slog n

(d+δ) log log nc

k=1

e−1·1

k!·n

≤∞

k=0

e−1·1

k!·n

≤n.

By construction of Ckwe get for a given realization φkof Υk

min

ˆy∈Ck

dH(ˆy, φk)≤εn,k.

Combining this with the definition of εn,k yields for all δ > 0 and for 1 ≤k≤

4q2slog n

(d+δ) log log n

Zmin

ˆy∈Ck

(dH(x, ˆy))sdυk(x).µ1

e−1·1

k!·n¶s

k(d+δ)

, n → ∞,(3.6)

uniformly for all 1 ≤k≤4q2slog n

(d+δ) log log n.

Consider the case where k > 4·q2slog n

(d+δ) log log n. We have nk= 0. As Eis bounded

by assumption there exists b∈R+such that

sup

x,y∈E

dH(x, y)≤b.

Therewith we can estimate the distortion we make using the codebook C1by

Zmin

y∈C1

(dH(x, y))sdυk(x)≤bs.(3.7)

Combining equations (3.2), (3.3),(3.6) and (3.7) yields for all δ > 0

(D(q),s(log n|Υ, dH))s.

b4·q2slog n

(d+δ) log log nc

k=1

P[NΥ(E) = k]·µ1

e−1·1

k!·n¶s

k(d+δ)

+∞

k=b4·q2slog n

(d+δ) log log nc+1

P[NΥ(E) = k]·bs

≤

b4·q2slog n

(d+δ) log log nc

k=1

ck·e−klog k·µ1

e−1·1

k!·n¶s

k(d+δ)

+∞

k=b4·q2slog n

(d+δ) log log nc+1

ck·e−klog k·bs(3.8)

as n→ ∞.

For all n∈Nwe introduce the function

fn:R+→R+

k7→ ck·µe−11

Γ(k+ 1)¶−s

k(d+δ)

·e−klog k·n−s

k(d+δ).

From Proposition 1.2.1 we know there exists a constant c2such that c2·√k·¡k

e¢k≥

Γ(k+ 1) and therefore

fn(k)≤fn(k)

:= c

k(d+δ)

2·ks

2k(d+δ)·ks

d+δ·e−s

d+δ·ck·es

k(d+δ)·e−klog k·n−s

k(d+δ).

From equation (3.8) and with the definition of fnwe split the sum and get for

all δ > 0

(D(q),s(log n|Υ, dH))s

b4·q2slog n

(d+δ) log log nc

k=1

fn(k) + ∞

k=b4·q2slog n

(d+δ) log log nc+1

ck·e−klog k·bs

=bcc

k=1

fn(k) +

2q2slog n

(d+δ) log log nc

k=bcc+1

fn(k)

b4·q2slog n

(d+δ) log log nc

k=b1

2q2slog n

(d+δ) log log nc+1

fn(k)

+∞

k=b4·q2slog n

(d+δ) log log nc+1

ck·e−klog k·bs, n → ∞.(3.9)

We assert that for all δ > 0 the sum is of order

(D(q),s(log n|Υ, dH))s≤e−(1+o(1))·√2s

d+δlog nlog log n, n → ∞.

To prove this we estimate each part of the sum and start with the first one.

Part 1: We consider the case where 1 ≤k≤c. Define

α1(c, c2, d, δ) := c·log c+s

d+δlog c2+s

d+δlog √c+s

d+δlog c.

For these kwe consider

fn(k)

e−√2s

d+δlog nlog log n

= exp ³q2s

d+δlog nlog log n+k(log c−log k) + s

d+δlog k´

·exp ³s

k(d+δ)(log c2+ log √k) + s

k(d+δ)−s

d+δ−s

k(d+δ)log n´

≤exp ¡√2 log nlog log n+c·log c+s

d+δlog c2+s

d+δlog √c¢

·exp ³s

d+δ+s

d+δlog c−s

d+δ−s

c(d+δ)log n´

= exp ³q2s

d+δlog nlog log n−s

c(d+δ)log n+α1(c, c2, d, δ)´

−→ 0, n → ∞,

which yields for all δ > 0

Pbcc

k=1 fn(k)

e−√2s

d+δlog nlog log n

=bcc

k=1

fn(k)

eq−2 log n

d+δlog log n

≤ bcc·exp ³q2s

d+δlog nlog log n−s

c(d+δ)log n+α1(c, c2, d, δ)´

−→ 0, n → ∞.

Hence, for all δ > 0 we have

bcc

k=1

fn(k) = o³e−√2s

d+δlog nlog log n´as n→ ∞.(3.10)

Part 2: In the second part of the sum klies between cand 1

2q2slog n

(d+δ) log log n.

Clearly for all δ > 0 it holds that

α2(c, c2, d, δ, n)

:= s

c(d+δ)³log c2+1

2log 1

2q2slog n

(d+δ) log log n´+s

c(d+δ)+s

d+δlog c−s

d+δ

=o³−q2s

d+δlog nlog log n´, n → ∞.

Therewith we estimate

fn(k)≤exp ³s

c(d+δ)³log c2+1

2log 1

2q2slog n

(d+δ) log log n´´

·exp ³s

c(d+δ)+s

d+δlog c−s

d+δ−q2s

d+δlog nlog log n´

= exp ³α2(c, c2, d, δ, n)−q2s

d+δlog nlog log n´

and hence,

2q2slog n

(d+δ) log log nc

k=bcc+1

fn(k)

≤exp ³log ³1

2q2slog n

(d+δ) log log n´+α2(c, c2, d, δ, n)−q2s

d+δlog nlog log n´.

Since

log ³1

2q2slog n

(d+δ) log log n´+α2(c, c2, d, δ, n)−q2s

d+δlog nlog log n

∼ −q2s

d+δlog nlog log nas n→ ∞,

for all δ > 0 we get

2q2slog n

(d+δ) log log nc

k=bcc+1

fn(k)≤e−(1+o(1))·√2s

d+δlog nlog log n, n → ∞.(3.11)

Part 3: For the third part of the sum we first prove the following assertion: for

I:= {1, . . . , b4·q2slog n

(d+δ) log log nc−b1

2q2slog n

(d+δ) log log nc} we define

li:= b1

2q2slog n

(d+δ) log log nc+i

bq2slog n

(d+δ) log log nc

and

kli:= li·bs2slog n

(d+δ) log log nc, i ∈I.

For all δ > 0 we assert

log fn(kli)≤ −(1 + o(1))q2s

d+δlog nlog log n, n → ∞, i ∈I.

To prove this we consider

α3(c,c2, d, δ, n)

:= 8 ·q2slog n

(d+δ) log log nlog c+ 8 ·log ³8·³q2slog n

(d+δ) log log n−1´´

−1

2·q2slog n

(d+δ) log log n·log µ1

2·µ√2slog n−√(d+δ) log log n

√(d+δ) log nlog log n¶¶

2(d+δ)·³q2slog n

(d+δ) log log n−1´·³log c2+1

2log ³8·q2slog n

(d+δ) log log n´+ 1´

d+δlog ³8·q2slog n

(d+δ) log log n´−s

d+δ

=o(−q2s

d+δlog nlog log n), n → ∞,for all δ > 0.

Without loss of generality assume q2slog n

(d+δ) log log n≥2. Therewith for all i∈Iwe

can deduce

li≤b4·q2slog n

(d+δ) log log nc

bq2slog n

(d+δ) log log nc≤4·q2slog n

(d+δ) log log n

q2slog n

(d+δ) log log n−1≤8(3.12)

and

li≥b1

2q2slog n

d(1+δ) log log nc+ 1

bq2slog n

(d+δ) log log nc≥

2·q2slog n

(d+δ) log log n

q2slog n

(d+δ) log log n

2.(3.13)

We consider log fn(kli) and use the fact that for all b∈Rit is 1

2b+1

2b≥1. Hence,

log fn(kli)≤li·q2slog n

(d+δ) log log nlog c

−li·³q2slog n

(d+δ) log log n−1´log ³li·³q2slog n

(d+δ) log log n−1´´

(d+δ)li·³q2slog n

(d+δ) log log n−1´·³log c2+1

2log ³li·q2slog n

(d+δ) log log n´´

(d+δ)li·³q2slog n

(d+δ) log log n−1´+s

d+δlog ³li·q2slog n

(d+δ) log log n´−s

d+δ

−slog n

(d+δ)li·q2slog n

(d+δ) log log n

=−(1

2li+1

2li)q2s

d+δlog nlog log n+li·q2slog n

(d+δ) log log nlog c

−li·q2slog n

(d+δ) log log n·log µli·µ√2slog n−√(d+δ) log log n

√d(1+δ) log nlog log n¶¶

+li·log ³li·³q2slog n

(d+δ) log log n−1´´

d(1+δ)li·³q2slog n

(d+δ) log log n−1´·³log c2+1

2log ³li·q2slog n

(d+δ) log log n´´

(d+δ)li·³q2slog n

(d+δ) log log n−1´+s

d+δlog ³li·q2slog n

(d+δ) log log n´−s

d+δ

≤ −q2s

d+δlog nlog log n+ 8 ·q2slog n

(d+δ) log log nlog c

−1

2·q2slog n

(d+δ) log log n·log µ1

2·µ√2slog n−√(d+δ) log log n

√(d+δ) log nlog log n¶¶

+8 ·log ³8·³q2slog n

(d+δ) log log n−1´´

2(d+δ)·³q2slog n

(d+δ) log log n−1´·³log c2+1

2log ³8·q2slog n

(d+δ) log log n´+ 1´

d+δlog ³8·q2slog n

(d+δ) log log n´−s

d+δ

=−q2s

d+δlog nlog log n+α3(c, c2, d, δ, n).

Using this in the third part of the sum yields

b4q2slog n

(d+δ) log log nc

k=b1

2q2slog n

(d+δ) log log nc+1

fn(k)

≤

b4q2slog n

(d+δ) log log nc

k=b1

2q2slog n

(d+δ) log log nc+1

exp ³−q2s

d+δlog nlog log n+α3(c, c2, d, δ, n)´

≤exp ³log ¡4q2slog n

(d+δ) log log n¢−q2s

d+δlog nlog log n+α3(c, c2, d, δ, n)´

and since

log ¡4q2slog n

(d+δ) log log n¢−q2s

d+δlog nlog log n+α3(c, c2, d, δ, n)

∼ −q2s

d+δlog nlog log n

as n→ ∞, for all δ > 0 we get

b4q2slog n

(d+δ) log log nc

k=b1

2q2slog n

(d+δ) log log nc+1

fn(k)≤e−(1+o(1))√2s

d+δlog nlog log n, n → ∞.(3.14)

Part 4: We consider the last part of the sum, where k > 4·q2slog n

(d+δ) log log n. Define

g(k) := ek·(log c−log k).

Consider

g(b4·q2slog n

(d+δ) log log nc+ 1)

e−√2s

d+δlog nlog log n

≤exp ³q2s

d+δlog nlog log n´

·exp ³4·q2slog n

(d+δ) log log n³log c−log ³4·q2slog n

(d+δ) log log n´´´

= exp ³−q2s

d+δlog nlog log n´

·exp ³4·q2slog n

(d+δ) log log n³log c−log ³4·q2s

(d+δ) log log n´´´

−→ 0 as n→ ∞.

Therefore for all δ > 0 we have g¡b4·q2slog n

(d+δ) log log nc+ 1¢=o¡e−√2s

d+δlog nlog log n¢

as n→ ∞.

Consider now for 4 ·q2slog n

(d+δ) log log n< k

g(k+ 1)

g(k)=c·kk

(k+ 1)k+1

=c·µk

k+ 1¶k

·1

k+ 1

≤c·1

k+ 1

≤c·1

4·q2slog n

(d+δ) log log n+ 1

−→ 0, n → ∞.

Thus there exists a ˜n > 0 such that for all n > ˜n, for all δ > 0 and k >

4·q2slog n

(d+δ) log log nwe have

g(k+ 1)

g(k)<1

Hence, for n > ˜nand for all δ > 0 this yields

∞

k=b4·q2slog n

(d+δ) log log nc+1

g(k)

≤g³j4·q2slog n

(d+δ) log log nk+ 1´·∞

k=b4·q2slog n

(d+δ) log log nc+1 ¡1

2¢k−b4·q2slog n

(d+δ) log log nc−1

= 2 ·g(b4·q2slog n

(d+δ) log log nc+ 1)

=o(e−√2s

d+δlog nlog log n), n → ∞.(3.15)

Combining now equations (3.9), (3.10), (3.11), (3.14) and (3.15) yields for all

δ > 0

(D(q),s(log n|Υ, dH))s≤e−(1+o(1))·√2s

d+δlog nlog log n, n → ∞

log((D(q),s(log n|Υ,dH))s)

√log nlog log n.−q2s

d+δas n→ ∞

for all δ > 0. With δ→0 it follows

log((D(q),s(log n|Υ,dH))s)

√log nlog log n.−q2s

das n→ ∞

which leads to

(D(q),s(log n|Υ, dH))s≤e−(1+o(1))·√2s

dlog nlog log n, n → ∞

and thus

D(q),s(log n|Υ, dH)≤e−(1+o(1))·√2

sd log nlog log n, n → ∞.

3.3 The quantization error of the Poisson point

process under Hausdorff distance

In the following section we give upper and lower bounds for the asymptotics of

the quantization error of a Poisson point process on a compact cube in Rd.

Theorem 3.3.1 Let s∈R+. Consider for l∈R+the Poisson point process Φ

from Definition 2.1.3 on the cube C:= [−l, l]d⊂Rd. Denote the distribution of

Φby µ. Denoting by dHthe Hausdorff distance on Rdfrom Definition 3.1.2 we

have

D(q),s(log n|Φ, dH) = exp Ã−(1 + o(1))r2

d·s·log nlog log n!, n → ∞.

Proof.

First we use Theorem 3.2.6 to prove the upper bound. By assumption (C, ρ) with

ρ(a, b) := |a−b|is a bounded metric space with diam(C)≤√d·2l. We show

that dimM(C) = d. Denote the uniform distribution on the cube Cby UC, i.e.

the density is defined by uC(x) := 1

(2l)d·1C(x) for all x∈Rd. Therewith follows

0< UC(C) = UC(Rd) = 1 <∞

and there is δ0>0 such that for all x∈Cand 0 < δ ≤δ0

2d·πd/2

Γ(d

2+ 1)(2l)d·δd≤UC(Bδ(x)) ≤πd/2

Γ(d

2+ 1)(2l)d·δd.

Due to Theorem 5.7 in Mattila [36] the Minkowski dimension of Cequals dand

hence, dimM(C) = dimM(C) = d.

Analogously to equation (2.18) it follows, that the Poisson point process Φ satis-

fies the condition

P[](Φ ∩C) = k]≤ck·e−klog kfor all k≥1

with c∈R+constant.

Hence, we can apply Theorem 3.2.6 and it follows

D(q),s(log n|Φ, dH)≤exp ³−(1 + o(1))q2

ds ·log nlog log n´(3.16)

as n→ ∞.

Now we proceed with the lower bound.

Let

ε:= 2l·Ã&µ2slog n

dlog log n¶1

2d'!−1

Hence, 2l

ε∈N. We split the cube C= [−l, l]dinto small ε-cubes ˜

C1, . . . , ˜

C(2l

ε)d.

Put in every cube ˜

Cia smaller cube Ci,i= 1, . . . , (2l

ε)d, with side length 4ε

Consider the event Athat inside every small cube Ciis exactly one of the points

of the Poisson point process Φ and C\(∪(2l

ε)d

i=1 Ci) contains no point. In Figure

3.1 we give a sketch for the case l=1

2,d= 2 and ε=1

(−1

2,−1

(−1

2,1

2,−1

oε

Figure 3.1: The Poisson point process conditioned A

Now we give for small εthe probability that this event Aoccurs.

P[A] = Ph

(2l

ε)d

i=1 ³{Φ(Ci) = 1}}´∩{Φ(C\(

(2l

ε)d

[

i=1

Ci)) = 0}i

(2l

ε)d

i=1 ³e−λ·(4ε

5)d·λ·(4ε

5)d´·e−λ((2l)d−(2l

ε)d·(4ε

5)d)

=e−λ(2l)d·λ(2l

ε)d·³4ε

5´(2l)dd

εd.(3.17)

Denote by ΦAthe Poisson point process Φ under the condition that Aoccurs and

by µAthe distribution of ΦA. Denote the points of ΦAby {x1, . . . , x(2l

ε)d}where

xj∈Cj. Let

δ:= εs

5s·³n·³d

sεd+ 1´´−sεd

(2l)dd.

Thus for nlarge enough we have δ1

s<ε

10. Consider an arbitrary codebook with n

elements ˆ

Φ1, . . . , ˆ

Φn, where the ˆ

Φi, i = 1, . . . , n, are arbitrary subsets of [−l, l]d.

P[dH(ΦA,ˆ

Φi)s< δ] = P[dH(ΦA,ˆ

Φi)< δ1

we estimate the probability that the original signal ΦAand a codebook element

Φihave a Hausdorff distance less than δ1

Case 1: If there exists j∈ {1, . . . , (2l

ε)d}such that ˜

Cj∩ˆ

Φi=∅, then

dH(ΦA,ˆ

Φi)>ε

10 > δ1

because Cj∩ΦA6=∅. Hence,

P[dH(ΦA,ˆ

Φi)< δ1

s] = 0.

Case 2: For every j∈ {1, . . . , (2l

ε)d}we have ˜

Cj∩ˆ

Φi6=∅.

For jfixed denote Mij := Cj∩ˆ

Φi. Assume diam(Mij)>2δ1

s. Then again we

have

dH(ΦA,ˆ

Φi)> δ1

because ΦA∩Cj={xj}consists in only one point. Thus

P[dH(ΦA,ˆ

Φi)< δ1

s] = 0.

If diam(Mij)≤2δ1

sthere is a cube Kij with side length 2δ1

ssuch that Mij ⊂Kij.

As ΦA∩Cj={xj}is uniformly distributed in Cjwe can deduce

P[dH({xj}, Mij)< δ 1

s]≤P[dH({xj}, Kij)< δ1

≤(4δ1

s)d

5ε)d,for all j= 1, . . . , ¡2l

ε¢d.

Thus for all i= 1, . . . , n it follows

P[dH(ΦA,ˆ

Φi)< δ1

s]≤Ph

(2l

ε)d

j=1 {dH({xj}, Mij)< δ 1

s}i

(2l

ε)d

j=1

P[dH({xj}, Mij)< δ 1

=³5dδd

εd´(2l

ε)d

.(3.18)

Using this we can estimate the quantization error depending on εand δby

¡D(q),s(log n|ΦA, dH)¢s≥δ·inf

Ccodebook on CÃ1−µAÃn

[

i=1

Bδ1

s(ˆ

Φi)!!

≥δ·inf

Ccodebook on CÃ1−

i=1

P[dH(ΦA,ˆ

Φi)< δ1

s]!

≥δ·µ1−n·³5d

εd·δd

s´(2l

ε)d¶.

With the definition of δ=εs

5s·(n·(d

sεd+ 1))−sεd

(2l)ddit follows

¡D(q),s(log n|ΦA, dH)¢s≥εs

5s·µn·µd+sεd

sεd¶¶−sεd

(2l)dd·d

d+sεd.

Weighting this estimate with the probability of Ayields combined with equation

(3.17) a lower bound for the quantization error

¡D(q),s(log n|Φ, dH)¢s≥P[A]·¡D(q),s(log n|ΦA, dH)¢s

≥e−λ·λ(2l

ε)d·³4ε

5´(2l)dd

εd·εs

·µn·µd+sεd

sεd¶¶−sεd

(2l)dd·d

d+sεd.

For simplicity denote α(λ, s) := −λ−slog 5. Hence,

¡D(q),s(log n|Φ, dH)¢s≥exp ¡α(λ, s)+(2l

ε)d·¡log λ+dlog ¡4

5¢¢+slog(ε)¢

·exp ³−(2l)d

εdlog ¡1

εd¢−sεd

(2l)ddlog n´

·exp ³−sεd

(2l)ddlog ³d+sεd

sεd´+ log ³d

d+sεd´´.

With the definition of ε= 2l·µ»³2slog n

dlog log n´1

2d¼¶−1

∼2l·³dlog log n

2slog n´1

2das n→ ∞

it holds for large nthat

¡D(q),s( log n|Φ, dH)¢s

&exp µα(λ, s) + ³2slog n

dlog log n´1

2·¡log λ+dlog ¡4

5¢¢¶

·exp µslog µ2l·³dlog log n

2slog n´1

2d¶¶

·exp µ−³2slog n

dlog log n´1

2·log µ(2l)−d·³2slog n

dlog log n´1

2¶¶

·exp Ã−s

d³dlog log n

2slog n´1

2·log n+ log Ãd

d+s(2l)d(dlog log n

2 log n)1

2!!

·exp Ã−s

d³dlog log n

2slog n´1

2log Ãd+s(2l)d(dlog log n

2 log n)1

s(2l)d(dlog log n

2 log n)1

2!!

= exp µα(λ, s) + ³2slog n

dlog log n´1

2·¡log λ+dlog ¡4

5¢¢¶

·exp µslog µ2l·³dlog log n

2slog n´1

2d¶¶

·exp µ−³2slog n

dlog log n´1

2·log µ(2l)−d·µ√2s+√dlog log n/ log n

√dlog log n¶¶¶

·exp µ−log µ(2l)−d·³2slog n

dlog log n´1

2¶¶

·exp Ã−¡2s

dlog n·log log n¢1

2+ log Ãd

d+s(2l)d(dlog log n

2 log n)1

2!!

·exp Ã−s

d³dlog log n

2slog n´1

2log Ãd+s(2l)d(dlog log n

2 log n)1

s(2l)d(dlog log n

2 log n)1

2!!.

Hence,

D(q),s(log n|Φ, dH)

&exp µ1

sα(λ, s) + ³2 log n

ds log log n´1

2·¡log λ+dlog ¡4

5¢¢¶

·exp µlog µ2l·³dlog log n

2slog n´1

2d¶¶

·exp µ−1

s³2slog n

dlog log n´1

2·log µ(2l)−d·µ√2s+√dlog log n/ log n

√dlog log n¶¶¶

·exp µ−1

slog µ(2l)−d·³2slog n

dlog log n´1

2¶¶

·exp Ã−¡2

ds log n·log log n¢1

2+1

slog Ãd

d+s(2l)d(dlog log n

2 log n)1

2!!

·exp Ã−1

d³dlog log n

2slog n´1

2log Ãd+s(2l)d(dlog log n

2 log n)1

s(2l)d(dlog log n

2 log n)1

2!!

= exp µ−(1 + o(1)) ·³2

ds log n·log log n´1

2¶, n → ∞.

Together with equation (3.16) this proves the assertion.

3.4 The entropy constrained error of the Pois-

son point process under Hausdorff distance

As in the previous section we consider for b∈R+a stationary Poisson point

process Φ = {x1, x2, . . .}with intensity λ > 0 from Definition 2.1.3 in the cube

C:= [−b, b]d⊂Rd. We give an asymptotic upper bound for the entropy con-

strained error of order s∈R+.

Theorem 3.4.1

D(e),s(log n|Φ, dH).√d·µ1

λ¶1/d

·n−1

d·λ·(2b)d, n → ∞.

Proof.

During the proof we will use the following: for all λ > 0 it holds that

lim

ε→0−¡1−e−λεd¢log ¡1−e−λεd¢+λεd·e−λεd

−λεdlog(λεd)= 1.

Thus for all δ1>0 there is ε1>0 such that for all ε < ε1we have

−¡1−e−λεd¢log ¡1−e−λεd¢+λεd·e−λεd≤(1 + δ1)·λεdlog( 1

λεd).(3.19)

Now we construct a specific codebook and appoint the rate for this codebook.

Let δ1>0 and

ε:= 2b·³j2b·λ1

d·n

d(1+δ1)·λ·(2b)dk´−1

Without loss of generality assume nto be large enough such that we have 2b

ε∈N

and such that equation (3.19) is satisfied. We divide the cube [−b, b]dinto small

cubes with side length ε. To fill the big cube we need (2b

ε)dsmall cubes, say

K1, . . . K(2b

ε)d. Denote the center of the small cube Kiby ˆxifor all i= 1, . . . , (2b

ε)d.

We put in the center of a small cube a coding point if at least one of the original

points is inside this small cube. Define the codebook

X(Φ) :=

(2b

ε)d

[

i=1 {ˆxi|NΦ(Ki)≥1}.

We appoint the likelihood that at least one point of the original signal is inside

one small cube Ki

pi:= P(NΦ(Ki)≥1)

= 1 −e−λ·λ(d)(Ki)

= 1 −exp ¡−λ·εd¢, i = 1,...,³2b

ε´d.

We compute the entropy of this codebook and show that it is smaller or equal to

log n. Due to equation (3.19) it follows

H[ˆ

X(Φ)] =

(2b

ε)d

i=1

(−pilog pi−(1 −pi) log(1 −pi))

=³2b

ε´d·(−p1log p1−(1 −p1) log(1 −p1))

=³2b

ε´d·³−¡1−e−λεd¢log ¡1−e−λεd¢+λεd·e−λεd´

≤(1 + δ1)·(2b)d·λlog ¡1

λεd¢.

With the definition of εthis leads to

H[ˆ

X(Φ)] ≤(1 + δ1)·(2b)d·λlog ¡1

λεd¢

≤(1 + δ1)·(2b)d·λlog ¡n

(1+δ1)λ(2b)d¢

= log n.

Let φbe a realization of Φ. By construction of the codebook the distortion is

bounded by

³dH(φ, ˆ

X(φ))´s≤(√d·ε)s

and with the definition of εwe deduce

(D(e),s(log n|Φ, dH))s≤µ√d·2b·³j2b·λ1

d·n

d(1+δ1)·λ·(2b)dk´−1¶s

∼Ã√d·µ1

λ¶1/d

·n−1

d(1+δ1)·λ·(2b)d!s

, n → ∞,

and with δ1→0

(D(e),s(log n|Φ, dH))s.Ã√d·µ1

λ¶1/d

·n−1

d·λ·(2b)d!s

, n → ∞,

and thus

D(e),s(log n|Φ, dH).√d·µ1

λ¶1/d

·n−1

d·λ·(2b)d, n → ∞.

Chapter 4

The Boolean model

4.1 Definition and basic properties

In the previous chapter we considered the quantization error of point processes

in dimension d≥1, especially of the Poisson point process. In this chapter we

deal with a more general subject, the so called d-dimensional Boolean model.

For this we follow the definition of Stoyan, Kendall and Mecke (see [43]). For

d∈Nlet Kdbe the system of all compact subsets of Rd. Hence, (Kd, dH) is also

a complete separable metric space. The corresponding open subsets generate a

σ-field on Kd, the Borel-σ-field B(Kd). A random compact set Yis defined as a

measurable map Y: (Ω,F, P)→(Kd,B(Kd)).

Definition 4.1.1 The basis of the Boolean model is a stationary Poisson point

process Φ = {x1, x2, . . .}in Rdwith intensity λ, the so-called germs. Let Y1, Y2, . . .

be a sequence of independent identically distributed random compact sets in Rd

which are independent of Φ, the so-called grains. Let Y1satisfy

E£λ(d)(Y1+K)¤<∞for all compact K. (4.1)

The Boolean model is defined as follows: Given the germs xiand the grains

Yias above a Boolean model is defined as a measurable map Ξ : (Ω,F, P)→

(Kd,B(Kd)) with

Ξ := ∞

[

i=1{xi+Yi}.

We say Ξis a Boolean model with primary grain Y1.

Remark 4.1.2 The technical condition (4.1) ensures that only finitely many of

the grains xi+Yihave a nonempty intersection with any given compact set. Thus,

in particular, it ensures that the property of being a closed set is inherited by Ξ

from the primary grains.

From the stationarity of the Poisson point process Φ of germs and the identical

distribution of the primary grains it follows that the Boolean model defined above

is stationary, i.e. its distribution is translation-invariant. We give two examples

for application of the Boolean model. In the first place, it is a natural model

for sparse systems of particles distributed at random. Here, the sparse nature

of the system is modeled by a low value of the intensity λof the Poisson point

process Φ. If λis small relative to the size of the grains then primary grains

will not often overlap and hence, Ξ will consist mainly of separate particles. A

typical example of such systems is the set of nodular graphite particles in cast

iron. A random sparse pattern of plants may also yield such a pattern in an area

covered by vegetation. With increasing λthe number of overlaps increases. E.g.

this happens with pores in cheese or areas of weeds in fields.

Remark 4.1.3 The grains of the Boolean model are not required to be connected

sets. For example, they may be sets of discrete points. In such a case the Boolean

model is a point process, more precisely, a Neymann-Scott point process (see

Stoyan et al. [43], Section 5.3).

Our main object in this section will be a special form of the Boolean model

defined as follows.

Definition 4.1.4 Let Φ = {x1, x2, . . .}be a stationary Poisson point process in

Rd,d≥1, with intensity λ. Let (Yi)i∈N, be a sequence of independent identically

distributed random compact sets in Rd, which satisfies the following: There is a

ball with center 0, denoted by B(i)(0), such that Yi⊆B(i)(0) and diam(Yi) =

diam(B(i)(0)). Denote the Radius of B(i)(0) by Ri. Assume that the Riare

independent identically distributed and denote the distribution function of the Ri

by F. Moreover assume that there exists a constant κ∈R+such that the Ri

satisfy P(Ri< t) = F(t)∼κ·tas t→0and E[Rd

i]<∞for all i∈N. We

define a special Boolean model as

Ξ := ∞

[

i=1{xi+Yi}.

We denote by ξthe law of Ξ.

Now we define a specialization of the Boolean model given above, where the

grains are balls with random radii.

Definition 4.1.5 Let Φ = {x1, x2, . . .}be a stationary Poisson point process in

Rd,d≥1, with intensity λ. Let ˆ

Yi, i ∈N, be balls in Rdwith random radii

Ri, i ∈N, where the Riare i.i.d on the interval [0,∞)with density ffor all

i∈N, where fis continuous in 0with f(0) >0. Let E[Rd

1]<∞. We define a

special Boolean model as

Ξ := ∞

[

i=1{xi+ˆ

Yi}.

We denote by ˇ

ξthe law of ˇ

Ξ.

We will mainly consider the Boolean model on a compact subset of Rd. The case

where the whole set is completely overlapped by one ball is trivial. The following

lemma guarantees that this does not happen almost surely on the set [−1

2,1

2]d.

Lemma 4.1.6 Consider the Boolean model from Definition 4.1.5. Let F(t) :=

0f(x)dx and E[Rd

1]<∞. Let Adenote the event that the cube [−1

2,1

2]dis not

completely covered by the balls of the Boolean model. Then we have

P[A]≥³e−λ·lim

b→∞

lim

δ→0Pb/δ

j=0((2δ(j+1))d−(2δj)d)·(1−F(δj))´

>0.

Proof.

Define for j∈Nand δ > 0

Vδj := [−(j+ 1)δ, (j+ 1)δ]d\[−jδ, jδ]d.

As the sets Vδj and Vδ˜

jare disjoint for j6=˜

jwith j, ˜

j∈N, and the radii Rm,

m∈N, are independent of each other and of Φ we can deduce

P[A]

≥lim

b→∞ lim

δ→0Ph{Φ([δ, δ]d) = 0}∩

b/δ

j=1 ³{Φ(Vδj) = 0}∪¡∪∞

i=1 ¡{Φ(Vδj) = i}∩(∩i

m=1{Rm≤jδ})¢¢´i

= lim

b→∞ lim

δ→0

b/δ

j=0 ³∞

i=0

e−λ((2δ(j+1))d−(2δj)d)·(λ((2δ(j+ 1))d−(2δj)d))i

i!·¡F(δj)¢i´

= lim

b→∞ lim

δ→0

b/δ

j=0

e−λ·((2δ(j+1))d−(2δj)d)·(1−F(δj))

= exp ³−λ2d·lim

b→∞ lim

δ→0

b/δ

j=0

δd((j+ 1)d−jd)·(1 −F(δj))´.

And this does not vanish if and only if

lim

b→∞ lim

δ→0

b/δ

j=0

δd((j+ 1)d−jd)·(1 −F(δj)) <∞.

Since Fis the distribution function of R1this is equivalent to E[Rd

1]<∞.

Remark 4.1.7 This result can be generalized to arbitrary compact sets that

contain the origin.

We introduce now another special form of the Boolean model which differs from

the last definition in the boundedness of the Ri,i∈N, which describe the radii.

Definition 4.1.8 Let b > 0,λ > 0and Φ = {x1, x2, . . .}be a stationary Poisson

point process in Rd,d≥1, with intensity λ. Let ˜

Yi, i ∈N, be balls in Rdwith

random radii Ri, i ∈N, where the Riare i.i.d on the interval [0,∞)with density

ffor all i∈N. Let fbe continuous in 0with f(0) >0and f(x)=0for all

x > b. We define another special Boolean model as

Ξ(b):= ∞

[

i=1{xi+˜

Yi}.

We denote by ξthe law of Ξ.

4.2 The quantization error of the Boolean model

under Hausdorff distortion in one dimension

In the following section we consider the Boolean model from Definition 4.1.5 in

the case where d= 1. In one dimension the balls of the Boolean model are

actually intervals. This is a special case, because the union of two intervals with

non-empty intersection is again an interval. In higher dimension this does not

remain valid for balls generally.

Theorem 4.2.1 Consider the Boolean model from Definition 4.1.5 for the case

d= 1 on the interval [0,1] ⊂R. Denoting the Hausdorff-distance by dHwe have

for every s∈R+

D(q),s(log n|ˇ

Ξ, dH) = exp µ−(1 + o(1))q2

s·log nlog log n¶as n→ ∞.

Proof.

Here we prove just the upper bound and refer for the lower bound to Theorem

4.3.3, where an asymptotic lower bound for the d-dimensional Boolean model on

a compact cube is given.

The outline of the proof is as follows. First we study some properties of the

one-dimensional Boolean model. Then we construct a concrete codebook and

compute the distortion for this codebook.

For the upper bound it is sufficient to code (instead of the points of Φ and the

radii of the intervals) just the starting and ending points of the intervals. The

advantage of this method lies in the lower complexity, e.g. for two overlapping

intervals where none of them is a subset of the other we have to code just two

points (the starting point of the left interval and the ending point of the right

interval) instead of four points (the two points of Φ and the two radii). We call

these points the visible starting and ending points of the Boolean model. These

visible points form a random point process on Rwhich we denote by Ψ and its

distribution by ψ. Denote for all t≥0 the number of the visible starting and

ending points of the Boolean model in the interval [0, t] by NΨ(t).

We denote the area that is covered by ˇ

Ξ as a sequence of ”green” intervals where

the length of the i-th interval is modeled by a random variable Gi. The remaining

area will be interpreted as a sequence of ”white” intervals, denoted by ˜

Wiand

their length by Wi. Hence, we can interpret the process as an alternating jump

process that changes between white and green. We define

S2k:=

i=1

(Wi+Gi) =

i=1

Wi+

i=1

and

S2k+1 :=

k+1

i=1

Wi+

i=1

if the process starts with a white area and analogously for the other case. Let

Ξk:= ˇ

Ξ|{NΨ(1)=k}and let ˇ

ξkbe the distribution of ˇ

Ξk. Therewith we split the

distribution of ˇ

Ξ on the interval [0,1] via

ξ=∞

k=0

P[NΨ(1) = k]·ˇ

ξk.

Analogously let Ψk:= Ψk|{NΨ(1)=k}and ψkbe the distribution of Ψk. We split

the distribution of Ψ via

ψ=∞

k=0

P[NΨ(1) = k]·ψk.

Now we give bounds for the number of points we are going to code. We interpret

the Boolean model ˇ

Ξ as a marked Poisson point process

(Ψ, m) = {(x1, m1),(x2, m2), . . .},

where the mark describes the radius of the corresponding interval. We consider

the measurepreserving translation ˜

T:R2→R2with ˜

T((a, b)) = (a−b, b). Hence,

this translated marked point process ˜

T((Ψ, m)) can be interpreted as a Boolean

model where the germs xjare the starting points of the corresponding grain

intervals with length 2mj. Assume ti∈R+to be the starting point of a white

interval Wi, and since fis the density of the random radius it follows

P[Wi≥z|Wistarts in ti] = exp ³−λZti+z

tiZ∞

f(r)dr dλ(1)(x)´

= exp ³−λZti+z

dλ(1)(x)·Z∞

f(r)dr´

=e−λz.

Denote the starting point of the i-th white interval by Ti. Let A:= {Wi≥z}

and for η > 0 let (tη

l)l∈N0be a partition of [0,∞) with |tη

l+1 −tη

l|=η. Let

A(ti, a) := {there is no jump in [ti, ti+a)}and

Aη:= [

l∈N0{Ti∈[tη

l, tη

l+1)}∩ ˆ

A(tη

l+1, z).

Hence, Aη%Aas η→0. Therewith we deduce

P[Wi≥z] = lim

η→0P[Aη]

= lim

η→0X

l∈N0

P[ˆ

A(tη

l+1, z)] ·P[Ti∈[tη

l, tη

l+1)|ˆ

A(tη

l+1, z)]

=e−λz ·lim

η→0X

l∈N0

P[Ti∈[tη

l, tη

l+1)|ˆ

A(tη

l+1, z)]

=e−λz ·lim

η→0Ph[

l∈N0{Ti∈[tη

l, tη

l+1)|ˆ

A(tη

l+1, z)]

=e−λz.

To show that the (Wi)i∈Nare independent we show the independence of a pair

Wi, Wjwith j > i. The proofs for the other combinations follow analogously. Let

A:= {Wi≥a1, Wj≥a2}and for η > 0 let (tη

l)l∈N0be a partition of [0,∞) with

|tη

l+1 −tη

l|=η. Let

Aη:= [

l,m∈N0,

l+1+a1

η<m ¡{Ti∈[tη

l, tη

l+1), Tj∈[tη

m, tη

m+1)}∩ ˆ

A(tη

l+1, a1)∩ˆ

A(tη

m+1, a2)¢.

Hence, ˜

Aη%˜

Aas η→0. Therewith we deduce

P[Wi≥a1, Wj≥a2]

= lim

η→0P[˜

Aη]

= lim

η→0X

l,m∈N0,

l+1+a1

η<m

P[ˆ

A(tη

l+1, a1)∩ˆ

A(tη

m+1, a2)]

·P[Ti∈[tη

l, tη

l+1), Tj∈[tη

m, tη

m+1)|ˆ

A(tη

l+1, a1)∩ˆ

A(tη

m+1, a2)]

=e−λ(a1+a2)·

·lim

η→0X

l,m∈N0,

l+1+a1

η<m

P[Ti∈[tη

l, tη

l+1), Tj∈[tη

m, tη

m+1)|ˆ

A(tη

l+1, a1)∩ˆ

A(tη

m+1, a2)]

=e−λ(a1+a2)·

·lim

η→0Ph[

l,m∈N0,

l+1+a1

η<m ¡{Ti∈[tη

l, tη

l+1), Tj∈[tη

m, tη

m+1)}| ˆ

A(tη

l+1, a1)∩ˆ

A(tη

m+1, a2)¢i

=e−λ(a1+a2)

=P[Wi≥a1]·P[Wj≥a2].

Using this and the exponential Tchebycheff inequality we get for t > 0 and θ > 0

the estimate

Ph1

i=1

Wi≤1i≤eθ·E[e−θ

tPk

i=1 Wi]

=ek·log(E[e−θ

tW1])+θ

Define ΛW1(θ) := log(E[e−θ

tW1]) = log(R∞

0λ·e−λs ·e−θ

tsds). We deduce

ΛW1(θ) = log(Z∞

λ·e−λs ·e−θ

tsds)

= log ³λ

λ+θ/t´.

Hence,

Ph1

i=1

Wi≤1i≤ek·log(λ

λ+θ/t )+θ

and with θ=k

Phk

i=1

Wi≤ti≤eklog(λt

λt+k)+k

=e−klog k+k¡1+log(λt)−log( λt

k+1)¢

≤e−klog k+k(1+log(λt)).(4.2)

Consider now the G1, . . . Gk. As before we interpret the Boolean model ˇ

Ξ as

a marked Poisson point process (Ψ, m) = {(x1, m1),(x2, m2), . . .}and translate

it via ˜

T:R2→R2with ˜

T((a, b)) = (a−b, b). Hence, this translated marked

point process can be interpreted as a Boolean model where the germs xjare

the starting points of the corresponding grain intervals with length 2mj. Denote

these translated green intervals by ˆ

G1, . . . , ˆ

Gk. Assume that the green interval ˆ

starts in the point xˆ

1of the Poisson point process and denote the corresponding

random radius by Rˆ

1. Hence, we estimate for small a∈R+

P[Gi≤a] = P[ˆ

Gi≤a]

≤P[2Rˆ

1≤a]

= 2 Za

f(x)dx

∼2·f(0) ·a, for all i= 1, . . . , k.

Hence, for all ε > 0 there exists aε>0 such that for all a≤aεwe have

P[Gi≤a]≤(1 + ε)·2·f(0) ·a.

Let ε:= 1. Since P[Gi≤a]≤1 for all a∈[a1,1] there exists a constant

c:= max{1

a1,4·f(0),1} ≥ 1 such that

P[Gi≤a]≤c·a, for all 0 ≤a≤1, i = 1, . . . , k. (4.3)

For an upper estimate we use again the exponential Tchebycheff inequality which

yields for t > 0 and θ > 0

P[1

i=1

Gi≤1] ≤eθ·E[e−θ

tPk

i=1 Gi]

=ek·log(E[e−θ

tG1])+θ

Define ΛG1(θ) := log(E[e−θ

tG1]) = log(R∞

t·e−θ

ts·P[G1≤s]ds). Using estimate

(4.3) we deduce

ΛG1(θ) = log ³Z1

t·e−θ

ts·P[G1≤s]ds +Z∞

t·e−θ

ts·P[G1≤s]ds´

≤log ³Z1

t·e−θ

ts·c·s ds +Z∞

t·e−θ

tsds´

= log ³−ce−θ

t−ct

θe−θ

t+ct

θ+e−θ

t´

= log ³(1 −c−ct

θ)·e−θ

t+ct

θ´.

Hence,

Ph1

i=1

Gi≤1i≤ek·log((1−c−ct

θ)·e−θ

t+ct

θ)+θ,

and with θ=kthis yields

Phk

i=1

Gi≤ti≤eklog((1−c−ct

k)k·e−k

t+ct)−klog k+k

≤eklog(−(c−1)k·e−k

t+ct)−klog k+k

≤e−klog k+klog(ct)+k(4.4)

as c≥1. Hence, we gave upper bounds for the number of ending points of the

white intervals and of the green intervals in the interval [0,1]. From now on we

assume that the process starts with a white interval. We distinguish between two

cases. First we consider the case where we have an even number of color changes.

Using equations (4.2) and (4.4) we conclude

P[NΨ(1) = 2k] = P[S2k≤1] −P[S2k+1 ≤1]

≤P[S2k≤1]

=Phk

i=1

Wi+Gi≤1i

≤Phk

i=1

Wi≤1i·Phk

i=1

Gi≤1i

≤e−klog k+k(1+log λ)·e−klog k+klog c+k

=e−2klog(2k)·ek(2 log 2+2+log λ+log c)

≤e−2klog(2k)·¡e2 log 2+2+log λ+log c¢2k.

Analogously we get for an odd number of color changes

P[NΨ(1) = 2k+ 1]

=P[S2k+1 ≤1] −P[S2k+2 ≤1]

≤P[S2k+1 ≤1]

=Phk+1

i=1

Wi+

i=1

Gi≤1i

≤Phk+1

i=1

Wi≤1i·Phk

i=1

Gi≤1i

≤e−(k+1) log(k+1)+(k+1)(1+log λ)·e−klog k+klog c+k

=e−(2k+1) log(2k+1)+(k+1)(1+log λ)+klog( 4k2+4k+1

k2+k)+log( 2k+1

k+1 )+klog c+k

≤e−(2k+1) log(2k+1) ·e(k+1)(1+log λ)+klog( 9

2)+log(2)+klog c+k

≤e−(2k+1) log(2k+1) ·³e1+log λ+log( 9

2)+log 2+log c+1´2k+1 .

Define

γ:= max{e2 log 2+2+log λ+log c, e1+log λ+log( 9

2)+log 2+log c+1}.

This yields

P[NΨ(1) = k]≤γk·e−klog kfor all k≥1.(4.5)

Thus we got an upper bound for the distribution of the number of interval ending

points in [0,1].

Now we are going to construct the codebook with nelements which we will use

to code the model. Analogously to the proof of Theorem 2.3.1 in Section 2.3 we

consider a sequence (nk)k∈N0such that for all 0 ≤k≤4·q2 log n

log log nit holds nk≥1

for nlarge enough and ∞

k=0

nk≤n,

where kdenotes the number of color changes in the interval [0,1]. For 0 ≤k≤

4·q2 log n

log log nlet Ckbe an arbitrary codebook for ˇ

ξkwith |Ck| ≤ nk. Therewith we

get analogously to equation (2.1)

(D(q),s( log n|ˇ

ξ, dH))s

≤

b4·q2 log n

log log nc

k=0

P[NΨ(1) = k]·Zmin

y∈Ck

(dH(x, y))sdˇ

ξk(x)

+∞

k=b4·q2 log n

log log nc+1

P[NΨ(1) = k]·Zmin

y∈C0

(dH(x, y))sdˇ

ξk(x) (4.6)

Consider the case where 0 is inside a white area, i.e. 0 6∈ ˇ

Ξ. We construct the

codebook for ˇ

ξksimilar to the codebook we used for the point process in Section

2.2. Nevertheless, as we here consider the Hausdorff-distance instead of the L1-

distance we have to make some modifications.

Recall the definitions

Γ(k):= {(x1, . . . , xk)∈[0,1]k: 0 < x1< x2< . . . < xk≤1}

and

∆(k):= {(x1, . . . , xk)∈Rd:xi>0,for all i= 1, . . . , k and

i=1

xi≤1}.

Consider a realization ykof ˇ

Ξkand denote the visible points of this realization in

[0,1] by 0 < s1< s2< . . . < sk≤1. Thus (s1, s2, . . . , sk)∈Γ(k). Using the map

Tdefined by (2.3) for a= 1 yields a tuple

T¡(s1, s2, . . . , sk)¢= (t1, t2, . . . , tk)∈∆(k).

Let

δ:= ³j2−1

k·e−1

k·(k!)−1

k·n1

kk´−1.(4.7)

Analogously to equation (2.5) we deduce 1

δ≥1 and, hence, 1

δ∈N. As in the

proof of Theorem 2.2.1 we cover the k-dimensional simplex ∆(k)with small cubes

with side length δ. As before we need

n(1)

k=(1

δ, k = 1,

mk−1=1 Pmk−1

mk−2=1 . . . Pm2

m1=1 m1, k ≥2,

cubes to cover the simplex, and get analogously to equation (2.6) with a= 1 the

relation

n(1)

k≤µ1

δ¶k

,for all k≥1.(4.8)

Denote the small cubes by K(k),j

δ,j= 1 . . . , n(1)

k. In the center of each small cube

we put a coding point (ˆ

t(j)

1, . . . , ˆ

t(j)

k), j= 1, . . . , n(1)

k. The codebook consists of

the union of all these center points. It is composed in such a way that

min

l=1,...,n(1)

k|ti−ˆ

t(l)

i| ≤ δ

2for all i= 1, . . . , k (4.9)

Let

(ˆs(j)

1,...,ˆs(j)

k) := T−1³(ˆ

t(j)

1, . . . ˆ

t(j)

k)´, j = 1, . . . , n(1)

Now we define the codebook for the case where 0 6∈ ˇ

Ξ via

Ξ(j),w

k:= ({b∈R|b∈Sk/2

i=1[ˆs(j)

2i−1,ˆs(j)

2i]}keven,

{b∈R|b∈Sk−1/2

i=1 [ˆs(j)

2i−1,ˆs(j)

2i]∪[ˆs2k+1,1]}kodd.

for j= 1, . . . , n(1)

kand

Ξw

k:= {ˆ

Ξ(j),w

k, j = 1, . . . , n(1)

k}.

Hence, we can estimate the minimal Hausdorff-distance between ykand the ele-

ments of ˆ

Ξw

kusing equation (4.9)

min

ˆyk∈ˆ

Ξw

dH(yk,ˆyk)≤

n(1)

j=1

1nT((s1,...,sk))∈K(k),j

δo·max

i∈{1,...,k}|ˆsi−si|

≤k·

n(1)

j=1

1nT((s1,...,sk))∈K(k),j

δo·max

i∈{1,...,k}|ˆ

t(j)

i−ti|

≤k·δ

2.(4.10)

For the case where 0 ∈ˇ

Ξ we get analogous results if we use the codebook defined

Ξg

k:= {[0,1] \ˆ

Ξ(j),w

k, j = 1, . . . , n(1)

k}.

Define the codebook for ˇ

Ξkby

Ξ0:= {∅,[0,1]}and ˆ

Ξk:= ˆ

Ξw

k∪ˆ

Ξg

kfor 1 ≤k≤4·s2 log n

log log n.

Without loss of generality assume e−1·1

k!·n≥2. If we define n0:= 2, nk:=

|ˆ

Ξk|= 2 ·n(1)

kfor all 1 ≤k≤4·q2 log n

log log nand nk:= 0 for k > 4·q2 log n

log log nwe get

analogously to equation (2.8) with a= 1 and q= 2

∞

k=0

nk≤n.

The definition of δand equation (4.10) yield for s∈R+

Zmin

y∈ˆ

Ξk

(dH(x, y))sdˇ

ξk(x)≤µk

2·³j2−1

k·e−1

k·(k!)−1

k·n1

kk´−1¶s

∼µk

2¶s

·2s

k·es

k·(k!)s

k·n−s

kas n→ ∞

uniformly for all 1 ≤k≤4·q2 log n

log log n. For the case where k > 4·q2 log n

log log nwe use

the codebook ˆ

Ξ0and get

Zmin

y∈ˆ

Ξ0

(dH(x, y))sdˇ

ξk(x)≤1.

Combining these estimates with equation (4.6) yields

(D(q),s(log n|ˇ

ξ, dH))s.

b4·q2 log n

log log nc

k=0

P[NΨ(1) = k]·µk

2¶s

·2s

k·es

k·(k!)s

k·n−s

+∞

k=b4·q2 log n

log log nc+1

P[NΨ(1) = k] as n→ ∞.

In the proof of Theorem 2.2.1 we got the same upper bound sum for the quanti-

zation error of a jump process in Rwith a= 1 and q= 2 (see equation (2.12))

besides the factor kinstead of k(k+ 1). As this factor is not important for the

asymptotics of the sum, we can determine the asymptotics of the whole sum

following exactly the way there which yields

(D(q),s(log n|ˇ

ξ, dH))s≤e−(1+o(1))·(2s·log n·log log n)1

2as n→ ∞

and, hence,

D(q),s(log n|ˇ

ξ, dH)≤e−(1+o(1))·(2

s·log n·log log n)1

2as n→ ∞.

4.3 The quantization error of the Boolean model

under Hausdorff distortion

In this section we give an upper bound for the quantization error of the Boolean

model as specified in Definition 4.1.8 and a lower bound for the quantization error

of the Boolean model as specified in Definition 4.1.5 both in the special case where

C= [−1

2,1

2]d. As the radii of the balls Riare distributed on the interval [0,∞),

every ball of the Boolean model might have a nonempty intersection with the

compact set C.

Lemma 4.3.1 1.) Consider the Boolean model from Definition 4.1.5 on Rd. Let

F(t) := Rt

0f(x)dx and E[Rd

1]<∞.

For l > 0, l ∈R,let Abe the event that all balls of the Boolean model with

center outside the cube [−l, l]dhave an empty intersection with the compact cube

[−1

2,1

2]d. Then we have

P[A]≥exp ³−λ2d·

i=1 µd

i¶Z∞

sd−i·(1 −F(s)) ds´

−→ 1for l→ ∞.

2.) Consider the Boolean model from Definition 4.1.4 on Rd. For l > 0, l ∈R,

let ˜

Abe the event that all grains of the Boolean model with corresponding germ

outside the cube [−l, l]dhave an empty intersection with the cube [−l, l]d. Then

we have

P[˜

≥exp ³−λ2d·lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

((l+ (j+ 1)δ)d−(l+jδ)d)·P[F1>2jδ])´

=: c(λ, l, d)

with 0< c(λ, l, d)≤1for all λ, l ∈R+and d∈N.

Proof.

1.) Let δ > 0 and j, ˜

j∈N. Define

Vjδ := [−l−(j+ 1)δ, l + (j+ 1)δ]d\[−l−jδ, l +jδ]d

and

h(l, j, δ) := λ(d)(Vjδ) = 2d·((l+ (j+ 1)δ)d−(l+jδ)d).

As the sets Vjδ and V˜

jδ are disjoint for j6=˜

j, j, ˜

j∈N, and the Rmare independent

of each other and of Φ we can deduce that

P[A]

≥lim

a→∞ lim

δ→0Phb(a−l)/δc

j=0 ³{Φ(Vjδ) = 0}∪

∪¡∪∞

i=1 ¡{Φ(Vjδ) = i}∩(∩i

m=1{Rm≤l+jδ})¢¢´i

= lim

a→∞ lim

δ→0

b(a−l)/δc

j=0 ³e−λh(l,j,δ)+³∞

i=1 ¡e−λh(l,j,δ)·(λh(l, j, δ))i

i!·

m=1

F(l+jδ)¢´´

= lim

a→∞ lim

δ→0

b(a−l)/δc

j=0 ³∞

i=0 ¡e−λh(l,j,δ)·(λh(l, j, δ)F(l+jδ))i

i!¢´

= lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

e−λ2d·((l+(j+1)δ)d−(l+jδ)d)·(1−F(l+jδ))

= exp ³−λ2d·lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

((l+ (j+ 1)δ)d−(l+jδ)d)·(1 −F(l+jδ))´

Consider the sum

b(a−l)/δc

j=0

((l+ (j+ 1)δ)d−(l+jδ)d)·(1 −F(l+jδ))

=b(a−l)/δc

j=0 ·(l+jδ)d+d·(l+jδ)d−1δ+µd

2¶(l+jδ)d−2δ2+. . .

. . . +δd−(l+jδ)d¤·(1 −F(l+jδ))

=b(a−l)/δc

j=0 ·d·(l+jδ)d−1δ+µd

2¶(l+jδ)d−2δ2+. . . +δd¸·(1 −F(l+jδ))

=b(a−l)/δc

j=0

d·(l+jδ)d−1δ·(1 −F(l+jδ)) + . . .

. . . +b(a−l)/δc

j=0

δd·(1 −F(l+jδ)).(4.11)

We analyze the limits of the sums.

d·lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

δ·(l+jδ)d−1(1 −F(l+jδ))

=d·lim

a→∞Za−l

(l+s)d−1·(1 −F(l+s)) ds

=d·lim

a→∞Za

sd−1·(1 −F(s)) ds

=d·Z∞

sd−1·(1 −F(s)) ds

<∞for all l > 0

since Fis the distribution function of the Riand E[Rd

1]<∞.

Without loss of generality let δ < 1. Thus the second sum can be estimated

µd

2¶·lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

δ2·(l+jδ)d−2(1 −F(l+jδ))

≤µd

2¶·lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

δ·(l+jδ)d−2(1 −F(l+jδ))

=µd

2¶·lim

a→∞Za

sd−2·(1 −F(s)) ds

=µd

2¶·Z∞

sd−2·(1 −F(s)) ds

<∞for all l > 0.

We get analogous results for the other sums in equation (4.11) and hence,

P[A]≥exp ³−λ2d·

i=1 µd

i¶Z∞

sd−i·(1 −F(s)) ds´.

Since all the integrals are finite due to E[Rd

1]<∞we get for every i= 1, . . . , d

lim

l→∞Z∞

sd−i·(1 −F(s)) ds = 0,

and the first part is proved.

2.) Analogously to the first part it follows that

P[˜

A]≥exp ³−λ2d·lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

((l+ (j+ 1)δ)d−(l+jδ)d)·(1 −F(jδ))´

We will show now that

lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

((l+ (j+ 1)δ)d−(l+jδ)d)·(1 −F(jδ))´<∞for all l∈R+

because then the second part will be proved. As in equation (4.11) we get

b(a−l)/δc

j=0

((l+ (j+ 1)δ)d−(l+jδ)d)·(1 −F(jδ))

=b(a−l)/δc

j=0

d·(l+jδ)d−1δ·(1 −F(jδ)) + . . . +b(a−l)/δc

j=0

δd·(1 −F(jδ)).

Again we have to analyze the limits of the sums.

d·lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

δ·(l+jδ)d−1(1 −F(jδ))

=d·lim

a→∞Za−l

(l+s)d−1·(1 −F(s)) ds

=d·lim

a→∞Za−l

ld−1·(1 −F(s)) ds +...

. . . +d·lim

a→∞Za−l

sd−1·(1 −F(s)) ds

=d·ld−1·E[R1] + . . . +d·1

d·E[Rd

<∞for all l > 0.

We get analogous results for the other sums. Thus

0≤lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

((l+ (j+ 1)δ)d−(l+jδ)d)·(1 −F(jδ)) <∞

and hence, with

c(λ, l, d) := exp ³−λ2d·lim

a→∞ lim

δ→0

b(a−l)/δc

j=0

((l+ (j+ 1)δ)d−(l+jδ)d)·(1 −F(jδ))´

it follows

0< c(λ, l, d)≤1

and the assertion is proved.

Now we give an upper bound for the quantization error of the Boolean model in

the case where the radii are bounded by b > 0.

Theorem 4.3.2 Consider the Boolean model from Definition 4.1.8 on the com-

pact cube [−1

2,1

2]d. For b > 0and s > 0we have

D(q),s(log n|Ξ(b), dH)≤exp Ã−(1 + o(1))s2

s(d+ 1) ·log nlog log n!

as n→ ∞.

Proof:

Let b > 0. As the radii take values in the interval [0, b] every point of the

corresponding Poisson point process in the cube [−b, b]dmay have influence on

the cube [−1

2,1

2]d. Therefore we will construct a codebook whose elements will

be composed of points in [−b, b]d(to code the Poisson point process) and values

in Rto code the radii of the balls. We decompose the distribution ξ(b)of Ξ(b)by

decomposing the distribution µof the corresponding Poisson point process Φ. As

in Section 2.3 we split µinto

µ=∞

k=0

e−λ·(2b)d·(λ·(2b)d)k

k!·µk,

where µ0(∅) := 1 and µkis the distribution of Φk:= Φ|{NΦ([−b,b]d)=k}. Note

that µkis a product distribution of kuniform distributions on [−b, b]dfor k≥

1. Let Ξ(b)

k:= Ξ(b)|{NΦ([−b,b]d)=k}be the Boolean model on [−1

2,1

2]dthat has

exactly kpoints of the corresponding Poisson point process in [−b, b]d. Denote

the distribution of Ξ(b)

kby ξ(b)

Consider a sequence (nk)k∈N0such that for all 0 ≤k≤4·q2slog n

(d+1) log log nit holds

nk≥1 and ∞

k=0

nk≤n.

For 0 ≤k≤4·q2slog n

(d+1) log log nlet Ckbe an arbitrary codebook for ξ(b)

kwith

|Ck| ≤ nk. Let C:= b4·q2slog n

(d+1) log log nc

k=0

Ck. Since Cis a codebook for ξ(b)with

|C| ≤ nwe deduce analogously to equation (2.1)

(D(q),s( log n|Ξ(b), dH))s

≤

b4·q2slog n

(d+1) log log nc

k=0

e−λ·(2b)d(λ·(2b)d)k

k!·Zmin

y∈Ck

dH(x, y)sdξ(b)

k(x)

+∞

k=b4·q2slog n

(d+1) log log nc+1

e−λ·(2b)d(λ·(2b)d)k

k!·Zmin

y∈C0∪C1

dH(x, y)sdξ(b)

k(x)

(4.12)

Without loss of generality assume e−1·n≥1. In the case where k= 0 we have

no point in [−b, b]d. Thus we define ˆ

C0:= {∅}, which leads to

(D(q),s(log n0|Ξ(b)

0, dH))s= 0 for n0= 1.(4.13)

Now we construct a specific codebook, say ˆ

Ck, for Ξ(b)

kfor 1 ≤k≤4·q2slog n

(d+1) log log n.

It will be composed of kballs with center in [−b, b]d. These balls are specified by

the position of the centers and the length of the radii. We use one part of the

codebook to code Φk, the point process in [−b, b]dwith exactly kpoints, and the

remaining part is used for the R1, . . . , Rk, the radii of the balls in the Boolean

model.

Consider a realization y(b)

kof Ξ(b)

k. Denote the germs of this realization by φkand

the radii of the grains by r1, . . . , rk. Let

δ:= 2b·³j(2b)1

d+1 ·(√d+ 1)−1

d+1 ·e−1

k(d+1) ·(k!)−1

k(d+1) ·n1

k(d+1) k´−1.(4.14)

Analogously to equation (2.5) it can be shown that for all 1 ≤k≤4·q2slog n

(d+1) log log n

and for nlarge enough we have 2b

δ≥1 and, hence, 2b

δ∈N. We divide the cube

[−b, b]dinto small cubes with side length δ. To fill the big cube we need (2b/δ)d

small cubes, denoted by K1, . . . , K(2b

δ)d. Denote the center of Kjby ˆxjfor all

j= 1, . . . , (2b/δ)d. Let I:= {ˆx1, . . . , ˆx(2b

δ)d}. We put a coding point in the center

of a small cube if at least one of the original points is inside this small cube. We

define the codebook for this part

CΦ

k:= {ˆ

φ⊂I:|ˆ

φ|=i, i = 1, . . . , k}.

Thus we allocate kor, if two or more original points are in one small cube, less

than kcoding points to (2b/δ)dcubes. Hence, we need

n(1)

k:= |ˆ

CΦ

k|=

i=1 µ(2b

δ)d

i¶

codebook elements, denoted by ˆ

φ(1)

k, . . . , ˆ

φ(n(1)

k. It is easy to verify that for all

δ≥2 and k≥1 it holds

1≤n(1)

k≤³2b

δ´dk.(4.15)

With this codebook the Hausdorff distance between the realization φkand the

coding points is smaller than (√dδ)/2

min

i=1,...,n(1)

dH(φk,ˆ

φ(i)

k)≤√d

2·δ. (4.16)

To code also the radii we need more coding points. As we are only interested

in the length of the radii inside [−1

2,1

2]d, we need one point to code if the ball

is completely outside the cube and use √d/δ points to mark the ending of the

radius inside the cube. For this we divide the interval [0,√d] into small intervals

with length δand put in the middle of each small interval a coding point. As we

do this for each of the kpoints we need for this part the rate

n(2)

k:= ³√d

δ+ 1´k,

which satisfies

1≤n(2)

k≤³√d+ 1

δ´k.(4.17)

Denote these radii codebook elements by ˆr(1)

k, . . . , ˆr(n(2))

k. Let k1≤kand assume

that r1, . . . , rk1are the radii of all original balls that end inside the cube [−1

2,1

2]d.

Then it follows

min

j=1,...,n(2)

dH(rm,ˆr(j)

k)≤δ

2for all m= 1, . . . , k1.(4.18)

Now we define the codebook for Ξ(b)

Ck:= {ˆ

φ(i)

k+Bˆr(j)

k(0) : i= 1, . . . , n(1)

k, j = 1, . . . , n(2)

k}.(4.19)

We code each ball of the original signal by a ball whose center is less than (√dδ)/2

away from the original center and whose radius differs for less than δ/2 from the

original radius. Thus, with equations (4.16) and (4.18) we deduce

min

ˆyk∈ˆ

dH(y(b)

k,ˆyk)≤√d+ 1

2·δ

and hence, for s > 0 it follows

min

ˆyk∈ˆ

dH(y(b)

k,ˆyk)s≤(√d+ 1)s

2s·δs.(4.20)

Thus we need a total rate of nk:= |ˆ

Ck|=n(1)

k·n(2)

kfor ξ(b)

kto get Hausdorff

distortion less than √d+1

2δfor 1 ≤k≤4·q2slog n

(d+1) log log n. For k > 4·q2slog n

(d+1) log log n

let nk:= 0.

Now we show that with these definitions it holds that P∞

k=0 nk≤n. Due to

equations (4.15) and (4.17) and the definition of δwe get

nk=n(1)

k·n(2)

≤(2b)dk·(√d+1)k

δk(d+1)

=(2b)dk·(√d+1)k

(2b)k(d+1) ·³j(2b)1

d+1 ·(√d+ 1)−1

d+1 ·e−1

k(d+1) ·(k!)−1

k(d+1) ·n1

k(d+1) k´k(d+1)

≤(√d+1)k

(2b)k·³(2b)1

d+1 ·(√d+ 1)−1

d+1 ·e−1

k(d+1) ·(k!)−1

k(d+1) ·n1

k(d+1) ´k(d+1)

≤e−1·(k!)−1·n,

which leads to

∞

k=0

nk≤1 +

b4·q2slog n

(d+1) log log nc

k=0

e−1·(k!)−1·n

≤n. (4.21)

By construction of the codebook ˆ

Ckand in particular by (4.20) and the definition

of δ(4.14) we have for large n

Zmin

y∈ˆ

dH(x, y)sdξ(b)

k(x)

≤(√d+ 1)s

2s·δs

∼(√d+ 1)s

2s·(2b)ds

d+1 ·(√d+ 1) s

d+1 ·es

k(d+1) ·(k!) s

k(d+1) ·n−s

k(d+1) .(4.22)

Now let k > 4·q2slog n

(d+1) log log n. We code the case of kjumps with one of the n0+n1

codebook elements from ˆ

C0∪ˆ

C1, denoted by ˜y(1), . . . , ˜y(n0+n1). Thus, we can give

an upper bound for the distortion between these codebook elements and Ξ(b)

Zmin

{i=1,...,n0+n1}(dH(˜y(i), x))sdξ(b)

k(x)≤(√d·2b)s.(4.23)

Combining equations (4.12), (4.13), (4.22) and (4.23) yields

(D(q),s(log n|Ξ(b), dH))s(4.24)

b4·q2slog n

(d+1) log log nc

k=1

e−λ·(2b)d(λ·(2b)d)k

k!·(√d+ 1)s

2s·

·(2b)ds

d+1 ·(√d+ 1) s

d+1 ·es

k(d+1) ·(k!) s

k(d+1) ·n−s

k(d+1)

+∞

k=b4·q2slog n

(d+1) log log nc+1

e−λ·(2b)d(λ·(2b)d)k

k!·(√d·2b)sas n→ ∞.

(4.25)

We consider the first sum and assert

b4·q2slog n

(d+1) log log nc

k=1

e−λ·(2b)d(λ·(2b)d)k

k!·(2b)sd

d+1 (√d+ 1)sd+2

d+1

2s·³k!·e

n´s

k(d+1)

≤e−(1+o(1))√2s

d+1 log nlog log n, n → ∞.(4.26)

To prove this we define

β(d, λ, b) := log Ãe−λ·(2b)d·(2b)sd

d+1 (√d+ 1)sd+2

d+1

2s!

and for every n∈Nthe function

fn:R+→R+

k7→ e˜

β(d,λ,b)·(λ·(2b)d)k·Γ(k+ 1)−1+ s

k(d+1) ·es

k(d+1) ·n−s

k(d+1)

With Proposition 1.2.1 and 1 ≤k, which implies log k

k≤1, we give an upper

bound for fn

fn(k) = e˜

β(d,λ,b)·(λ(2b)d)k·(Γ(k+ 1))−1+ s

k(d+1) ·es

k(d+1) n−s

k(d+1)

≤e˜

β(d,λ,b)·(λ(2b)d)k·(c1·√k·(k

e)k)−1+ s

k(d+1) ·es

k(d+1) n−s

k(d+1)

= exp ³˜

β(d, λ, b) + klog(λ(2b)d) + ( s

k(d+1) −1) log c1+ ( s

2k(d+1) −1

2) log k´

·exp ³(s

d+1 −k) log k−(s

d+1 −k) + s

k(d+1) −s

k(d+1) log n´

≤exp ³˜

β(d, λ, b) + klog(λ(2b)d) + ( s

d+1 −1) log c1+s

2(d+1) −1

2log k´

·exp ³s

d+1 log k−klog k−s

d+1 +k+s

d+1 −s

k(d+1) log n´

= exp ³˜

β(d, λ, b) + k·(log(λ(2b)d)+1−log k)+( s

d+1 −1

2) log k´

·exp ³−s

k(d+1) log n+s

2(d+1) + ( s

d+1 −1) log c1´

=: hn(k).(4.27)

For simplicity denote β(d, λ, b) := ˜

β(d, λ, b) + s

2(d+1) + ( s

d+1 −1) log c1.

We split the sum from equation (4.24) into the following four parts

¡D(q),s(log n|Ξ(b), dH)¢s

.bλe(2b)dc

k=1

fn(k) +

bqslog n

2(d+1) log log nc

k=b(λe(2b)d)c+1

fn(k)

b4q2slog n

(d+1) log log nc

k=bqslog n

2(d+1) log log nc+1

fn(k)

+∞

k=b4q2slog n

(d+1) log log nc+1

e−λ(2b)d(λ(2b)d)k

k!·(√d·2b)s(4.28)

as n→ ∞.

Part 1: Consider the first part where 1 ≤k≤λe·(2b)d. First assume s

d+1 −1

2≥0.

For these kwe give an upper bound for fn

fn(k)≤hn(k)

≤exp(λe(2b)d·(log(λ(2b)d)+1)+( s

d+1 −1

2) log(λe(2b)d))

·exp(−slog n

(λe(2b)d)(d+1) +β(d, λ, b)).

Therefore we have

Pb(λ(2b)d)ec

k=1 fn(k)

e−√2s

d+1 log nlog log n

≤exp ³λ(2b)de·(log(λ(2b)d)+1)+( s

d+1 −1

2) log(λe(2b)d)´

·exp ³−slog n

(λ(2b)d)e(d+1) +β(d, λ, b) + q2s

d+1 log nlog log n´

−→ 0 as n→ ∞.

In the second case we have s

d+1 −1

2<0. Thus, we estimate

fn(k)≤hn(k)

≤exp(λe(2b)d·(log(λ(2b)d) + 1) −slog n

(λe(2b)d)(d+1) +β(d, λ, b))

and

Pb(λe(2b)d)c

k=1 fn(k)

e−√2s

d+1 log nlog log n≤exp(λe(2b)d·(log(λ(2b)d) + 1))

·exp(−slog n

(λe(2b)d)(d+1) +β(d, λ, b) + q2s

d+1 log nlog log n)

−→ 0, n → ∞.

Hence,

bλ(2b)dec

k=1

fn(k) = o³e−√2s

d+1 log nlog log n´, n → ∞.(4.29)

Part 2: Consider the second part where λe(2b)d≤k≤qslog n

2(d+1) log log n. For these

kwe give an upper bound for hn(k) for s

d+1 −1

2≥0

hn(k)

= exp ³k·(log(λ(2b)d)+1−log k)+( s

d+1 −1

2) log k−s

k(d+1) log n+β(d, λ, b)´

≤exp ³0+( 1

d+1 −1

2) log(qslog n

2(d+1) log log n)−slog n

(d+1)qslog n

2(d+1) log log n

+β(d, λ, b)´

= exp ³(1

d+1 −1

2) log(qslog n

2(d+1) log log n)−q2s

d+1 log nlog log n+β(d, λ, b)´

This leads with equation (4.27) to

bqslog n

2(d+1) log log nc

k=bλ(2b)dec+1

fn(k)≤exp ³(1 + 1

d+1 −1

2) log(qslog n

2(d+1) log log n)´

·exp ³−q2s

d+1 log nlog log n+β(d, λ, b)´

and since

d+1 +1

2) log(qslog n

2(d+1) log log n)−q2s

d+1 log nlog log n+β(d, λ, b)

∼ −q2s

d+1 log nlog log nas n→ ∞,

we have

bqslog n

2(d+1) log log nc

k=bλ(2b)dec+1

fn(k)≤e−(1+o(1))√2s

d+1 log nlog log nas n→ ∞.

For s

d+1 −1

2<0 we estimate

hn(k)≤exp ³(1

d+1 −1

2) log(λe(2b)d)−q2s

d+1 log nlog log n+β(d, λ, b)´

and obtain again

bqslog n

2(d+1) log log nc

k=bλ(2b)dec+1

fn(k)≤e−(1+o(1))√2s

d+1 log nlog log nas n→ ∞.(4.30)

Part 3: Now we come to the third part of the sum. Define

I:= {1, . . . , b4·q2slog n

(d+1) log log nc−b1

2q2slog n

(d+1) log log nc−1}

mi:= b1

2q2slog n

(d+1) log log nc+i

bq2slog n

(d+1) log log nc

and ˜

kmi:= mi·bq2slog n

(d+1) log log nc, i ∈I.

Without loss of generality assume q2slog n

(d+1) log log n≥2. Using the same arguments

as in (3.12) and (3.13) we deduce

2≤mi≤8 for all i∈I.

Consider the case where s

d+1 −1

2≥0. Using the fact that 1

2c+1

2c≥1 for all

c∈Rwe give an upper bound

log(hn(kmi))

=kmi·(log(λ(2b)d)+1−log kmi)+( s

d+1 −1

2) log kmi−slog n

(d+1)kmi+β(d, λ, b)

≤mi·q2slog n

(d+1) log log n·³log(λ(2b)d)+1−log ³mi·q2slog n

(d+1) log log n´´

+ ( s

d+1 −1

2) log ³mi·(q2slog n

(d+1) log log n+ 1)´−slog n

(d+1)·mi·(q2slog n

(d+1) log log n+1)

+β(d, λ, b)

=−(1

2mi+1

2mi)·q2s

d+1 log nlog log n+β(d, λ, b)

+mi·q2slog n

(d+1) log log n·³log(λ(2b)d)+1−log ³mi·q2s

(d+1) log log n´´

+ ( s

d+1 −1

2) log ³mi·(q2slog n

(d+1) log log n+ 1)´+√slog nlog log n

mi√2(√2slog n+√(d+1) log log n)

≤ −q2s

d+1 log nlog log n+β(d, λ, b)

+ 8 ·q2slog n

(d+1) log log n·³log(λ(2b)d)+1−log ³1

2·q2s

(d+1) log log n´´

+ ( s

d+1 −1

2) log ³8·(q2slog n

(d+1) log log n+ 1)´+√slog nlog log n

2√2(√2slog n+√(d+1) log log n)

=−(1 + o(1)) ·r2s

d+ 1 log nlog log nas n→ ∞.

In the case where s

d+1 −1

2<0 we get analogously

log(hn(kmi))

≤mi·q2slog n

(d+1) log log n·³log(λ(2b)d)+1−log ³mi·q2slog n

(d+1) log log n´´

+ ( s

d+1 −1

2) log ³mi·q2slog n

(d+1) log log n´−slog n

(d+1)·mi·(q2slog n

(d+1) log log n+1) +β(d, λ, b)

≤ −q2s

d+1 log nlog log n+β(d, λ, b)

+ 8 ·q2slog n

(d+1) log log n·³log(λ(2b)d)+1−log ³1

2·q2s

(d+1) log log n´´

+ ( s

d+1 −1

2) log ³1

2·q2slog n

(d+1) log log n´+√slog nlog log n

2√2(√2slog n+√(d+1) log log n)

=−(1 + o(1)) ·r2s

d+ 1 log nlog log nas n→ ∞.

Therefore we estimate the third part of the sum

b4q2slog n

(d+1) log log nc

k=bqslog n

2(d+1) log log nc+1

fn(k)≤

b4q2slog n

(d+1) log log nc

k=bqslog n

2(d+1) log log nc+1

hn(k)

≤4q2slog n

(d+1) log log n·exp ³−(1 + o(1)) ·q2s

d+1 log nlog log n´

= exp ³−(1 + o(1)) ·q2s

d+1 log nlog log n´(4.31)

as n→ ∞.

Part 4: It remains the last part of the sum. Remember the estimate

∞

k=b4q2slog n

(d+1) log log nc+1

e−λ(2b)d(λ(2b)d)k

k!·Zmin

y∈C0∪C1

(dH(x, y))sdξ(b)

k(x)

≤∞

k=b4q2slog n

(d+1) log log nc+1

e−λ(2b)d(λ(2b)d)k

k!·(√d·2b)s.

Define

h(k) := e−λ(2b)d(λ(2b)d)k

Γ(k+ 1) ·(√d·2b)s

Due to Proposition 1.2.1 it follows

h(k)≤e−λ(2b)d(λ(2b)d)k

c1·√k(k

e)k·(√d·2b)s

=: h(k).

Hence,

h(b4q2slog n

(d+1) log log nc+ 1)

e−√2s

d+1 ·log nlog log n

≤

h(4q2slog n

(d+1) log log n)

e−√2s

d+1 ·log nlog log n

= exp ³λ(2b)d+ 4q2slog n

(d+1) log log n(log(λ(2b)d) + 1) −1

2log(4q2slog n

(d+1) log log n)´

·exp ³−2q2s

d+1 log nlog log n−4q2slog n

(d+1) log log nlog ¡4q2s

(d+1) log log n¢´

·exp ³−log(c1) + 4q2slog n

(d+1) log log n+slog(√d·2b) + q2s

d+1 log nlog log n´

= exp ³λ(2b)d+ 4q2slog n

(d+1) log log n(log(λ(2b)d) + 1) −1

2log(4q2slog n

(d+1) log log n)´

·exp ³−4q2slog n

(d+1) log log nlog ¡4q2s

(d+1) log log n¢´

·exp ³−log(c1) + 4q2slog n

(d+1) log log n+slog(√d·2b)−q2s

d+1 log nlog log n´

−→ 0 as n→ ∞.

Therefore ˜

h(b4q2slog n

(d+1) log log nc+ 1) = o(e−√2s

d+1 log nlog log n), n → ∞. Then it

follows for 4q2slog n

(d+1) log log n< k that

h(k+ 1)

h(k)=λ(2b)d

k+ 1

<λ(2b)d

4q2slog n

(d+1) log log n+ 1

−→ 0, n → ∞.

Thus, there exists a ˜n∈Nsuch that for all n > ˜nand k > 4q2slog n

(d+1) log log nwe

have ˜

h(k+ 1)

h(k)<1

Hence,

∞

k=b4q2slog n

(d+1) log log nc+1

h(k)

≤˜

h(b4q2slog n

(d+1) log log nc+ 1) ·∞

k=b4q2slog n

(d+1) log log nc+1 ¡1

2¢k−b4q2slog n

(d+1) log log nc−1

= 2 ·˜

h(b4q2slog n

(d+1) log log nc+ 1)

=o(e−√2s

d+1 log nlog log n), n → ∞

and thus,

∞

k=b4q2slog n

(d+1) log log nc+1

e−λ(2b)d(λ(2b)d)k

k!·(√d·2b)s≤o¡e−√2s

d+1 log nlog log n¢(4.32)

as n→ ∞. Combining now equations (4.28), (4.29), (4.30), (4.31) and (4.32)

yields

¡D(q),s(log n|Ξ(b), dH)¢s≤e−(1+o(1))·√2s

d+1 log nlog log n, n → ∞,

and thus

D(q),s(log n|Ξ(b), dH)≤e−(1+o(1))·q2

s(d+1) log nlog log n, n → ∞.

Now we turn to the lower bound for the quantization error of the special Boolean

model with random compact grains.

Theorem 4.3.3 Let l > 0. Consider the Boolean model from Definition 4.1.4

on the cube C:= [−l, l]d⊂Rd. Denoting by dHthe Hausdorff-distance we have

for s > 0

D(q),s(log n|Ξ, dH)≥exp Ã−(1 + o(1))r2

sd ·log nlog log n!, n → ∞.

Proof:

Let

ε:= 2l·Ã&µ2sd ·log n

(d+ 1)2·log log n¶1

2'!−1

Hence, for nlarge enough we have (2l

ε)d∈N. We split the cube C= [−l, l]dinto

small cubes ˜

C1, . . . , ˜

C(2l

ε)dwith side length ε. In the center of each cube we put

a smaller cube with side length ε

2, say C1, . . . , C(2l

ε)d.

Denote by ˜

Athe same event as in Lemma 4.3.1 (i.e. the event that all grains of the

Boolean model with germ outside Chave empty intersection with C). Consider

the event ˆ

Athat inside every small cube Ciis exactly one of the points of the

Poisson point process Φ and that Ri< ε/4 for all i= 1, . . . , (2l/ε)d. Moreover

assume that all grains of the Boolean model with germ outside Chave an empty

intersection with C. In particular in this special case we get that the grains of

the Boolean model, say K1, . . . , K(2l

ε)d, satisfy Ki∩Kj=∅for i6=j. Denote by xj

the germs of the Boolean model. In Figure 4.1 we give a sketch for a realization

of the Boolean model given ˆ

Awith d= 2 and l=ε=1

Using Lemma 4.3.1 we give the likelihood of ˆ

Afor small ε

P[ˆ

A] = Ph

(2l

ε)d

i=1 ³{Φ(Ci) = 1}∩{Ri<ε

4}´∩{Φ(C\(S(2l

ε)d

i=1 Ci)) = 0}∩ ˜

(2l

ε)d

i=1 ³e−λ(ε

2)d·λ(ε

2)d·P[Ri<ε

4]´·e−λ((2l)d−(2l

ε)d·(ε

2)d)·c(λ, l, d)

&e−λ(2l)d·(κ·λ)(2l)d/εd·(εd+1

2d+2 )(2l)d/εd·c(λ, l, d) as ε→0.(4.33)

(−1/2,−1/2)

(−1/2,1/2)

(1/2,−1/2)

(1/2,1/2)

Figure 4.1: The Boolean model conditioned ˆ

Denote by Ξ ˆ

Athe Boolean model Ξ conditioned on ˆ

Let

δ:= ³1

n·((d+1)(2l)d

sεd+ 1)´sεd

(d+1)(2l)d·³Γ(d/2 + 1) ·(ε/2)d·(d+ 1)

πd/2´s

d+1 .

Assume nto be large enough such that we have δ1

s<ε

8. Consider an arbitrary

codebook with nelements ˆ

Ξ1, . . . , ˆ

Ξn, where ˆ

Ξiis an arbitrary compact subset of

[−l, l]dfor all i= 1, . . . , n. Denote by

Ξij := ˆ

Ξi∩˜

the subset of the codebook element ˆ

Ξithat is a subset of ˜

Cj.

P[dH(Ξ ˆ

A,ˆ

Ξi)s< δ] = P[dH(Ξ ˆ

A,ˆ

Ξi)< δ1

we estimate the likelihood that the original signal Ξ ˆ

Aand a codebook element ˆ

Ξi

have a Hausdorff-distance less than δ1

Case 1: If there exists j∈ {1, . . . , (2l

ε)d}such that ˆ

Ξij =˜

Cj∩ˆ

Ξi=∅, then

dH(Ξ ˆ

A,ˆ

Ξi)>ε

8> δ1

because Cj∩Ξˆ

A6=∅. Hence,

P[dH(Ξ ˆ

A,ˆ

Ξi)< δ1

s] = 0.

Case 2: For every j∈ {1, . . . , (2l

ε)d}we have ˆ

Ξij 6=∅.

We discuss some properties of Kj. By definition there is a closed ball with center

xjand radius Rj=1

2·diam(Kj) such that Kj⊂BRj(xj). Thus there exist at

least two points y(1)

jand y(2)

jin Kjwhich satisfy |y(1)

j−y(2)

j|= diam(Kj) and

|y(1)

j−xj|=|y(2)

j−xj|=1

2·diam(Kj). Let

E:= {there is A⊂ˆ

Ξij with diam(A) = diam(ˆ

Ξij) and |A|= 3,

such that dH({xj, y(1)

j, y(2)

j}, A)< δ1

s}.

Clearly {dH(Kj,ˆ

Ξij)< δ 1

s} ⊂ E. We denote the three points of Aby {ˆxij,ˆy(1)

ij ,ˆy(2)

ij }

and assume that |ˆy(1)

ij −ˆy(2)

ij |= diam(ˆ

Ξij).

We discuss some properties of A. If |ˆy(1)

ij −ˆxij|>1

2·diam(ˆ

Ξij)+δ1

sor |ˆy(2)

ij −ˆxij|>

2·diam(ˆ

Ξij) + δ1

sit follows directly

dH({xj, y(1)

j, y(2)

j}, A)> δ1

Thus it follows

P[dH(Kj,ˆ

Ξij)< δ 1

≤P[E]

=P[dH({xj, y(1)

j, y(2)

j},{ˆxij,ˆy(1)

ij ,ˆy(2)

ij })< δ1

≤Zδ1

P[xj∈Bτ(ˆxij)] ·Ph1

2|diam({xj, y(1)

j, y(2)

j})−diam(A)| ≤ δ1

s−τidτ

≤Zδ1

P[xj∈Bτ(ˆxij)] dτ

=Zδ1

πd/2·τd

Γ(d/2 + 1) ·(ε/2)ddτ

(d+ 1) ·πd/2

Γ(d/2 + 1) ·(ε/2)d·δd+1

As this is valid for all j= 1, . . . , (2l

ε)dwe deduce

P[dH(Ξ ˆ

A,ˆ

Ξi)< δ1

≤³1

(d+ 1) ·πd/2

Γ(d/2 + 1) ·(ε/2)d·δd+1

s´(2l

ε)d

for all i= 1, . . . , n.

We denote the distribution of Ξ ˆ

Aby ξˆ

A. With the same arguments as in Section

2.3 we get a lower bound for the quantization error of Ξ ˆ

Adepending on δand ε,

namely

(D(q),s(log n|Ξˆ

A, dH))s

≥δ·inf

Ccodebook Phmin

Ξi∈C

dH(XA,ˆ

Ξi)s≥δi

≥δ·inf

Ccodebook ³1−ξˆ

A¡

[

i=1

Bδ1

s(ˆ

Ξi)¢´

≥δ·inf

Ccodebook ³1−

i=1

ξˆ

A¡Bδ1

s(ˆ

Ξi)¢´

≥δ·inf

Ccodebook ³1−n·sup

ξˆ

A¡Bδ1

s(ˆ

Ξi)¢´

≥δ·³1−n·³1

(d+ 1) ·πd/2

Γ(d/2 + 1) ·(ε/2)d·δd+1

s´(2l

ε)d´.

Using the definition of

δ=³1

n·((d+1)(2l)d

sεd+ 1)´sεd

(d+1)(2l)d·³Γ(d/2 + 1) ·(ε/2)d·(d+ 1)

πd/2´s

d+1

this leads to

(D(q),s(log n|Ξˆ

A, dH))s≥³sεd

(d+ 1)(2l)d+sεd´sεd

(d+1)(2l)d·

·³Γ(d/2 + 1) ·(ε/2)d·(d+ 1)

πd/2´s

d+1 ·

·(d+ 1)(2l)d

(d+ 1)(2l)d+sεd·n−sεd

(d+1)(2l)d.

Weighting the distortion of the event Ξ ˆ

Awith the probability that this event

occurs (see equation (4.33)) yields a lower bound for the quantization error of Ξ.

(D(q),s(log n|Ξ, dH))s≥P[A]·(D(q),s(log n|Ξˆ

A, dH))s

&e−λ(2l)d·(f(0) ·λ)(2l)d/εd·(εd+1

2d+3 )(2l)d/εd·c(λ, l, d)

·³sεd

(d+ 1)(2l)d+sεd´sεd

(d+1)(2l)d·

·³Γ(d/2 + 1) ·(ε/2)d·(d+ 1)

πd/2´s

d+1 ·

·(d+ 1)(2l)d

(d+ 1)(2l)d+sεd·n−sεd

(d+1)(2l)das ε→0.

For simplicity denote

γ(λ, l, d, s) := −λ(2l)d+ log µ³Γ(d/2 + 1) ·(d+ 1)

πd/2´s

d+1 ¶+ log(c(λ, l, d))

and with this we get for small ε

(D(q),s(log n|Ξ, dH))s&exp µγ(λ, l, d, s) + ³2l

ε´dlog ³f(0)λ(2l)d+1

2d+3 ´¶

·exp µ−d+ 1

d³2l

ε´dlog ³³2l

ε´d´¶

·exp µsεd

(d+ 1)(2l)dlog ³sεd

(d+ 1)(2l)d+sεd´¶

·exp µs

d+ 1 log((ε/2)d)¶

·exp µlog ³(d+ 1)(2l)d

(d+ 1)(2l)d+sεd´−sεd

(d+ 1)(2l)dlog n¶.

With the definition of

ε= 2l·Ã&µ2sd ·log n

(d+ 1)2·log log n¶1

2'!−1

n→∞

−→ 0

it holds

2l·Ãµ2sd ·log n

(d+ 1)2·log log n¶1

+ 1!−1

≤ε≤2l·µ(d+ 1)2·log log n

2sd ·log n¶1

This yields for large n

(D(q),s(log n|Ξ, dH))s

&exp µγ(λ, l, d, s) + ³2sd·log n

(d+1)2log log n´1

2log ³f(0)λ(2l)d+1

2d+3 ´¶

·exp µ−d+1

dµ³2sd·log n

(d+1)2log log n´1

2+ 1¶log µ³2sd·log n

(d+1)2log log n´1

2+ 1¶¶

·exp 





sÃ³2sd·log n

(d+1)2log log n´1

2+1!−1

(d+1) log 





sÃ³2sd·log n

(d+1)2log log n´1

2+1!−1

(d+1)+s³(d+1)2log log n

2sd·log n´1

2









·exp Ãs

d+1 log Ãldµ³2sd·log n

(d+1)2log log n´1

2+ 1¶−1!!

·exp 

log Ãd+1

(d+1)+s³(d+1)2log log n

2sd·log n´1

2!−

sµ(d+1)2log log n

2sd·log n¶1

d+1 log n

.

Simplifying this expression yields

(D(q),s(log n|Ξ, dH))s

&exp µγ(λ, l, d, s) + ³2sd·log n

(d+1)2log log n´1

2log ³f(0)λ(2l)d+1

2d+3 ´¶

·exp µ−³2s·log n

dlog log n´1

2log µ√2sd+(d+1)√log log n/ log n

(d+1)√log log n¶¶

·exp µ−log µ³2sd·log n

(d+1)2log log n´1

2+ 1¶¶

·exp 





sÃ³2sd·log n

(d+1)2log log n´1

2+1!−1

(d+1) log 





sÃ³2sd·log n

(d+1)2log log n´1

2+1!−1

(d+1)+s³(d+1)2log log n

2sd·log n´1

2









·exp Ãs

d+1 log Ãldµ³2sd·log n

(d+1)2log log n´1

2+ 1¶−1!!

·exp Ãlog Ãd+1

(d+1)+s³(d+1)2log log n

2sd·log n´1

2!!

·exp ³−¡2s

dlog nlog log n¢1

2´as n→ ∞

and, hence,

D(q),s(log n|Ξ, dH)

&exp µ1

sγ(λ, l, d, s) + ³2d·log n

s(d+1)2log log n´1

2log ³f(0)λ(2l)d+1

2d+3 ´¶

·exp µ−³2·log n

ds log log n´1

2log µ√2sd+(d+1)√log log n/ log n

(d+1)√log log n¶¶

·exp µ−1

slog µ³2sd·log n

(d+1)2log log n´1

2+ 1¶¶

·exp 





Ã³2sd·log n

(d+1)2log log n´1

2+1!−1

(d+1) log 





sÃ³2sd·log n

(d+1)2log log n´1

2+1!−1

(d+1)+s³(d+1)2log log n

2sd·log n´1

2









·exp Ã1

d+1 log Ãldµ³2sd·log n

(d+1)2log log n´1

2+ 1¶−1!!

·exp Ã1

slog Ãd+1

(d+1)+s³(d+1)2log log n

2sd·log n´1

2!−¡2

ds log nlog log n¢1

= exp ³−(1 + o(1)) ·¡2

sd ·log nlog log n¢1

2´as n→ ∞.

and the assertion is proved. Furthermore, for d= 1 and for the case where the

grains are balls with random radii this proves the assertion of Theorem 4.2.1.

Notice that the asymptotics of the upper and the lower bound differ. The asymp-

totics of the lower bound are equal to the asymptotics of the quantization error

of the Poisson point process on a compact cube in Rd. In the case where d= 1

we showed in Section 4.2 that the asymptotics of the quantization error of the

Boolean model are the same as the asymptotics of the quantization error of the

Poisson point process. Thus we conjecture that the lower bound yields the right

asymptotics in the case where d > 1, too. Heuristically, this may be understood

by considering the overlaps of the Boolean model. If the radii are quite large with

high probability, we have many overlaps in the Boolean model (e.g. some grains

may be entirely contained in other grains), and we need not code all points of the

Poisson point process. If the radii are that small that we do not have any over-

laps, the Boolean model is very close to the d-dimensional Poisson point process,

and thus the quantization error asymptotics may be equal.

4.4 The quantization error of the Boolean model

under L1- distance

In this section we give an upper bound for the Boolean model from Definition

4.1.8, the special Boolean model with bounded radii. But now we use the L1-

distance in Rd, given by Definition 3.1.4 instead of the Hausdorff distance.

Theorem 4.4.1 Consider the Boolean model from Definition 4.1.8 on the com-

pact cube [−1

2,1

2]d. For b > 0and s > 0we have

D(q),s(log n|Ξ(b), ρ(d))≤exp Ã−(1 + o(1))s2

s(d+ 1) ·log nlog log n!

as n→ ∞.

Proof:

Let b > 0. As the radii are distributed on the interval [0, b] every point of the

corresponding Poisson point process in the cube [−b, b]dmay have influence on

the cube [−1

2,1

2]d.

As in the proof of Theorem 4.3.2 we split the model into the number of balls, the

location of the centers and the length of the radii and use the same notations as

in this proof. In the case where k= 0 we have no point in [−b, b]d. As in the

proof of Theorem 4.3.2 we define ˆ

C0:= {∅}, which leads to

(D(q),s(log n0|Ξ(b)

0, ρ(d)))s= 0 for n0= 1.(4.34)

In the case where 1 ≤k≤4q2slog n

(d+1) log log nremember the definition

δ:= 2b·³j(2b)1

d+1 ·(√d+ 1)−1

d+1 ·e−1

k(d+1) ·(k!)−1

k(d+1) ·n1

k(d+1) k´−1.

Analogously to equation (2.5) we get 2b

δ∈N. We use the codebooks ˆ

Ckthat are

defined in (4.19)

Ck:= {ˆ

φ(i)

k+Bˆr(j)

k(0) : i= 1, . . . , n(1)

k, j = 1, . . . , n(2)

with n(1)

k=Pk

i=1 µ(2b

δ)d

i¶and n(2)

k=³√d

δ+ 1´kand we define nk:= |ˆ

Ck|.

Analogously to the equation (4.21) we get

∞

k=0

nk≤n

and

nk≥1 for 0 ≤k≤4q2slog n

(d+1) log log n.

In the case where 1 ≤k≤4q2slog n

(d+1) log log nconsider a given realization y(b)

kof Ξ(b)

We have in the codebook ˆ

Ckfor each ball of the original signal a corresponding

coding ball whose center is less than (√dδ)/2 away from the original center and

whose radius differs for less than δ/2 from the original radius (see equations (4.16)

and (4.18)). Hence, we can bound the L1-distance of this two balls by c(d, b)·δ

where c(d, b) is a constant depending only on dand b. A very rough estimate

would be the Hausdorff-distance of the two balls times the surface of the bigger

ball. The surface is bounded by 2πd/2·bd−1

Γ(d/2) , since the radius is bounded by b.

Because the realization y(b)

kof the original signal consists of kballs we deduce

min

ˆyk∈ˆ

ρ(d)(y(b)

k,ˆyk)≤k·c(b, d)·δ

and, hence, we get analogously to equation (4.22) for s > 0

Zmin

ˆyk∈ˆ

ρ(d)(x, ˆyk)sdξ(b)

k(x)≤ks·c(b, d)s·δs.(4.35)

By construction of the codebook ˆ

Ck, by (4.35) and the definition of δwe have for

large n

Zmin

y∈ˆ

ρ(d)(x, y)sdξ(b)

k(x).ks·c(b, d)s·³(2b)dk ·(√d+ 1)k

e−1(k!)−1n´s

k(d+1) .

Since we deal with the cube [−1

2,1

2]dwe use the codebook ˆ

C0∪ˆ

C1for the case

where k > b4q2slog n

(d+1) log log ncand give an upper bound for the L1-distance

Zmin

y∈ˆ

C0∪ˆ

ρ(d)(x, y)sdξ(b)

k(x)≤1.

It follows analogously to equation (4.24) with the definition of δthat for large n

it holds

(D(q),s(log n|Ξ(b), ρ(d)))s.

b4q2slog n

(d+1) log log nc

k=0

e−λ·(2b)d(λ·(2b)d)k

k!·ks·c(l, d)s·

·³(2b)dk ·(√d+ 1)k

e−11

k!·n´s

k(d+1)

+∞

k=b4q2slog n

(d+1) log log nc+1

e−λ·(2b)d(λ·(2b)d)k

k!.(4.36)

100

We consider the first sum and assert

b4q2slog n

(d+1) log log nc

k=1

e−λ·(2b)d(λ·(2b)d)k

k!·ks·c(b, d)s·³(2b)dk ·e·k!·(√d+ 1)k

n´s

k(d+1)

≤e−(1+o(1))√2s

d+1 log nlog log n, n → ∞.

To prove this we define

β(d, λ, b) := log ³e−λ·(2b)d·c(b, d)s·(2b)sd

d+1 ·(√d+ 1)´s

(d+1)

and for every n∈Nthe function

yn:R+→R+

k7→ eˆ

β(d,λ,b)·(λ·(2b)d)k·Γ(k+ 1)−1+ s

k(d+1) ·ks·es

k(d+1) ·n−s

k(d+1)

Analogously to estimate (4.27) we use Proposition 1.2.1 and the relation 1 ≤k,

which implies log k

k≤1, to give an upper bound for yn

yn(k) = eˆ

β(d,λ,b)·(λ·(2b)d)k·Γ(k+ 1)−1+ s

k(d+1) ·ks·es

k(d+1) ·n−s

k(d+1)

≤exp ³k·(log(λ(2b)d)+1−log k)+(s+s

d+1 −1

2) log k−slog n

k(d+1) ´

·exp ³s

2(d+1) + ( s

d+1 −1) log c1−s

d+1 +s

d+1 +ˆ

β(d, λ, b)´

=: ˆ

hn(k).(4.37)

This function ˆ

hnis similar to the bounding function hnfrom (4.27). Only the

term ( s

d+1 −1

2) log kis replaced by (s+s

d+1 −1

2) log k. Hence, we can use the same

arguments as for the sum from equation (4.24), i.e. splitting the sum into three

parts and estimating each part doing a case differentiation for (s+s

d+1 −1

2) less

or greater than zero. This yields

b4q2slog n

(d+1) log log nc

k=1

yn(k)≤e−(1+o(1))√2s

d+1 log nlog log n, n → ∞.(4.38)

The asymptotic upper bound for large n

∞

k=b4q2slog n

(d+1) log log nc+1

e−λ·(2b)d(λ·(2b)d)k

k!≤o(e−(2s

d+1 log nlog log n)1

2)(4.39)

can also be proved via the methods used in Section 4.3 (see equation (4.32)).

Combining equations (4.36), (4.38) and (4.39) yields

(D(q),s(log n|Ξ(b), ρ(d)))s≤e−(1+o(1))√2s

d+1 log nlog log n, n → ∞,

101

which leads to

D(q),s(log n|Ξ(b), ρ(d))≤e−(1+o(1))q2

s(d+1) log nlog log nas n→ ∞.

Although the Hausdorff distance and the L1-distance are not equivalent (see

Remark 3.1.5) we get under both distance terms for the special Boolean model

with bounded grains on a compact cube the same asymptotic upper bound. This

may be caused by the coherency of the Hausdorff and the L1-distance in this

special case. In our constructed codebook we compare every ball of the Boolean

model with another ball in Rdwhose center and radius is closer than δto the

center and the radius of the original, respectively. Therefore we estimate both

the L1-distance and the Hausdorff distance by a constant depending only on the

dimension dand on the bound for the radii times δ.

102

Chapter 5

Open problems

In this chapter we list open problems that result from the last preceding chapters.

5.1 Coding alternating renewal processes

In Chapter 2 we gave asymptotic bounds for the several coding errors of jump pro-

cesses on a bounded interval. In particular we discussed the asymptotic bounds

of a D([0,1],{0,1})-valued process induced by a Poisson point process Φ on

[0,1] and compared the results with the Gaussian case. We found out that in

contrast to the Gaussian case deterministic coding and entropy coding yield dif-

ferent asymptotic errors. In our case entropy coding yields better asymptotics

than coding in a deterministic way.

Question 5.1.1 1.) Will the quantization error asymptotics of Theorem 2.2.1

and Theorem 2.3.1 and the entropy error asymptotics of Theorem 2.5.1 still hold

if we consider a D([0, a], I)-valued process, where a∈R+and Iis not a finite

but an arbitrary subset of R?

2.) Which properties have to be assumed for getting the same asymptotic bounds?

5.2 Coding point processes in bounded metric

spaces

In Chapter 3 we discussed the quantization error of a point process on a bounded

metric space with finite upper Minkowski dimension. Under certain assumptions

on the probability of the number of points we gave an asymptotic upper bound

depending on this upper Minkowski dimension.

Question 5.2.1 1.) What is the asymptotic lower bound of the quantization

error? Does it depend on the lower Minkowski dimension?

103

2.) What changes if we consider not a bounded metric space but an arbitrary

metric space with for example finite Hausdorff dimension?

5.3 Coding the Boolean model

In Chapter 4 we dealt with the Boolean model in Rdin the special case of grains

included by balls with random but bounded radii Riwhose distribution satisfies

P[Ri< t]∼κ·tfor some constant κand t→0. We gave upper and lower

bounds for the quantization error asymptotics. But only in the case of dimension

one the asymptotics of the upper and lower bound coincide.

Question 5.3.1 1.) What are the correct quantization error asymptotics in the

case d > 1?

2.) What would change if the distribution of the radii satisfies P[Ri< t]∼κ·tα

for some α > 0?

3.) Do the bounds hold if the grains of the Boolean model are arbitrary ran-

dom compact sets? Which properties have to be assumed for getting the same

asymptotic bounds?

104

Appendix A

Appendix

A.1 A small ball inequality

Let a∈R+and Xbe a D([0, a],{0,1})-valued random element as stated in

Definition 2.1.7. For ε > 0 with a

ε∈Nwe split the interval [0, a] into small

intervals with length ε, denoted by ˜

I1, . . . , ˜

ε. Put in the center of every interval

Iia smaller interval Ii,i= 1, . . . , a

ε, with length ε

2. Consider the event Athat

X0= 0 and inside every small interval Iiis exactly one of the points of the

Poisson point process ΦX, i.e. the jumps of X, and [0, a]\(∪a/ε

i=1Ii) contains no

point. Let XA:= X|Abe the alternating Poisson renewal process Xconditioned

upon Aand let µX

Abe the distribution of XA. Let δ > 0 with δ < ε/4. Let ˆ

Xbe

an arbitrary element of D([0, a],{0,1}).

Proposition A.1.1 Let ε > 0and Aand XAbe as above. Let δ > 0with

δ < ε/4. Then for every ˆ

X∈ D([0, a],{0,1}), it holds that

Phρa(XA,ˆ

X)< δi≤µ4δ

ε¶a

Proof:

Denote the jumps of XAby {x1, . . . , xa

ε}where xj∈Ij. For arbitrary ˆ

X∈

D([0, a],{0,1}) it holds

Phρa(XA,ˆ

X)< δi≤sup

f:[0,a]→R+

RC, mb., bounded

PhZa

0|f(s)−(XA)s|ds < δi

≤sup

f:[0,a]→R+

RC, mb., bounded

a/ε

i=1 ©Ziε

(i−1)ε|f(s)−(XA)s|ds < δªi

= sup

f:[0,a]→R+

RC, mb., bounded

a/ε

i=1

PhZiε

(i−1)ε|f(s)−(XA)s|ds < δi

105

= sup

f:[0,a]→R+

RC, mb., bounded ³PhZε

0|f(s)−(XA)s|ds < δi´a/ε

≤sup

f:[0,a]→R+

RC, mb., bounded ³PhZ3ε

4|f(s)−(XA)s|ds < δi´a/ε

≤sup

f:[0,a]→R+

RC, mb., bounded ³Ph¯¯Z3ε

f(s)ds −Z3ε

(XA)sds¯¯< δi´a/ε.

Since fis bounded we have κ:= R3ε

4f(s)ds < ∞. The process XAhas in the

interval [0, ε] only the jump x1that is uniformly distributed in the interval [ε

4,3ε

4].

Hence, x1−ε

4is uniformly distributed in the interval [0,ε

2] and we deduce

P[ρa(XA,ˆ

X)< δ]

≤sup

f:[0,a]→R+

RC, mb., bounded ³Ph¯¯Z3ε

f(s)ds −Z3ε

(XA)sds¯¯< δi´a/ε

= sup

f:[0,a]→R+

RC, mb., bounded ³Ph|κ−(x1−ε

4)|< δi´a/ε

= sup

f:[0,a]→R+

RC, mb., bounded ³P£x1∈[ε

4+κ−δ, ε

4+κ+δ]¤´a/ε

≤µ4δ

ε¶a

106

Bibliography

[1] Alsmeyer, G. (1991) Erneuerungstheorie, Teubner Skripten zur Mathema-

tischen Stochastik, Stuttgart

[2] Berger, T. and Gibson, J.D. (1998) Lossy source coding, IEEE Trans. In-

form. Theory 44, 2693-2723

[3] Billingsley, P. (1968) Convergence of Probability Measures, Wiley series in

probability and mathematical statistics, New York (et al.)

[4] Bingham, N.H., Goldie, C.M. and Teugels, J.L. (1987) Regular Variation,

Cambridge University Press, Cambridge

[5] Bucklew, J.A. and Wise, G.L. (1982), New York (et al.) Multidimensional

asymptotic quantization theory with r-th power distortion measures, IEEE

Trans. Inform. Theory 28, 239-247

[6] Cover, T.M. and Thomas, J.A. (1991) Elements of Information Theory,

John Wiley & Sons, Inc., New York (et al.)

[7] Cox, D.R. (1965) Erneuerungstheorie, R. Oldenbourg Verlag, M¨unchen

Wien

[8] Creutzig, J. (2002) Approximation of Gaussian random vectors in Banach

spaces, Ph.D. Dissertation, Friedrich-Schiller-Universit¨at Jena

[9] Daley, D.J. and Vere-Jones, D. (1988) An Introduction to the Theory of

Point Processes, Springer Series in Statistics, New York (et al.)

[10] Delattre, S., Graf, S., Luschgy, H. and Pag`es, G. (2004) Quantization of

probability distributions under norm-based distortion measures, Statistics

and Decisions 22, 261-282

[11] Delattre, S., Graf, S., Luschgy, H. and Pag`es, G. (2006) Quantization

of probability distributions under norm-biased distortion measures II: self-

similar distributions, J. Math. Analysis and Applications, 318, 507-516

107

[12] Dembo, A. and Kontoyiannis, I. (2001) Critical Behaviour in Lossy Source

Coding, IEEE Trans. Inf. Theory 47, 1230-1236

[13] Dembo, A. and Kontoyiannis, I. (2002) Source Coding, Large Deviations,

and Approximate Pattern Matching, IEEE Trans. Inf. Theory 48, 1590-1615

[14] Dereich, S. (2003) High Resolution Coding of Stochastic Processes and

Small Ball Probabilities Ph.D. Dissertation, Technische Universit¨at Berlin

[15] Dereich, S. (2003) Small ball probabilities around random centers of Gaus-

sian measures and applications to quantization, J. Theoret. Probab. 16,

427-229

[16] Dereich, S., Fehringer, F., Matoussi, A. and Scheutzow, M. (2003) On

the link between small ball probabilities and the quantization problem for

Gaussian measures on Banach spaces, J. Theoret. Probab. 16, 249-265

[17] Dereich, S. and Scheutzow, M. (2006) High-resolution quantization and en-

tropy coding for fractional Brownian motion, Electronic Journal of Proba-

bility 11, 700-722

[18] Dereich, S. and Vormoor, C. (2005) The high resolution vector quantization

problem with Orlicz norm distortion, Preprint

[19] Dereich, S., M¨uller-Gronbach, T. and Ritter, K. (2006) Infinite-dimensional

Quadrature and Quantization, Preprint

[20] Falconer, K.J. (1990) Fractal Geometry : Mathematical Foundations and

Applications John Wiley & Sons, Chichester (et al.)

[21] Fehringer, F. (2001) Kodierung von Gaußmaßen Ph.D. Dissertation, Tech-

nische Universit¨at Berlin

[22] Gersho, A. and Gray, R.M. (1992) Vector Quantization and Signal Com-

pression, The Kluwer international series in engineering and computer sci-

ence; 159, Boston (et al.)

[23] Graf, S. and Luschgy, H. (2000) Foundations of Quantization for Probability

Distributions, Lecture Notes in Mathematics 1730, Springer-Verlag, Berlin

(et al.)

[24] Graf, S., Luschgy, H. and Pag`es, G. (2003) Functional quantization and

small ball probabilities for Gaussian processes, Journal of Theoretical Prob-

ability 16, 1047-1062

[25] Graf, S. and Luschgy, H. (2004) Quantization for probability measures with

respect to the geometric mean error, Math. Proc. Cambridge Phil. Soc. 136,

687-717

108

[26] Graf, S. and Luschgy, H. (2005). The point density measure in the quanti-

zation of self-similar probabilities, Math. Proc. Cambridge Phil. Soc. 138,

513-531

[27] Graf, S. and Luschgy, H. (2005) Entropy-constrained functional quantiza-

tion of Gaussian measures Proceedings AMS 133, 3403-3409

[28] Graf, S., Luschgy, H. and Pag`es, G. (2006) Optimal quantizers for Radon

random vectors in a Banach space, Journal of Approximation Theory, To

appear

[29] Gray, R.M. (1998) Quantization, IEEE Trans. Inform. Theory 44, 2325-

2383.

[30] Gray, R.M., Linder, T. and Li, J. (2002) A Lagrangian formulation of

Zador’s entropy-constrained quantization theorem, IEEE Trans. Inf. Theory

48, 695-707

[31] Kolmogorov, A.N. (1965) Three approaches to the definition of the notion of

amount of information, Problemy Peredachi Informatsii 1, 3-11: translated

in [32]

[32] Kolmogorov, A.N. (1993) Selected works of A.N. Kolmogorov. Volume III:

Information theory and the theory of algorithms, Ed. by A.N. Shiryayev,

Kluwer Academic Publishers, Dordrecht

[33] Li, S., Ogura, Y. and Kreinovich, V. (2002) Limit Theorems and Applica-

tions of Set-Valued and Fuzzy Set-Valued Random Variables, Theory and

Decision Library, Series B: Mathematical and Satistical Methods, Vol. 43,

Kluwer Academic Publishers, Dordrecht

[34] Luschgy, H. and Pag`es, G. (2002) Functional quantization of Gaussian pro-

cesses, J. Func. Anal. 196, 486-531

[35] Luschgy, H. and Pag`es, G. (2006) Functional quantization of a class of

Brownian diffusions: A constructive approach, Stochastic Processes and

their Applications 116, 310-336

[36] Mattila, P. (1999) Geometry of Sets and Measures in Euclidean Spaces:

Fractals and Rectifiability, Cambridge Univ. Press (Cambridge studies in

advanced mathematics ; 44), Cambridge (et al.)

[37] Oliver, B.M., Pierce, J. and Shannon, C.E. (1948) The philosophy of PCM,

Proc. IRE 36, 1324-1331

[38] Pierce, J.N. (1970) Asymptotic quantization error for unbounded random

variables, IEEE Trans. Inf. Theory 16, 81-83

109

[39] Rudin, Walter (1976) Principles of Mathematical Analysis, McGraw-Hill

International Editions, New York (et al.)

[40] Shannon, C.E. (1948) A mathematical theory of communication, Bell Syst.

Tech. J. 27, 379-423, 623-656

[41] Shannon, C.E. (1949) Communication in the presence of noise, Proc. IRE

37, 10-21

[42] Shannon, C.E. (1959) Coding theorems for a discrete source with a fidelity

criterion, IRE National Convention Record 4, 142-163

[43] Stoyan, D., Kendall, W.S. and Mecke, J. (1987) Stochastic Geometry and

its Applications, Wiley series in probability and Mathematical Statistics,

John Wiley & Sons, Chichester (et al.)

[44] Zador, P. (1963), Development and evaluation of procedures for quantizing

multivariate distributions, Ph.D. Dissertation, Stanford University

[45] Zador, P. (1966), Topics in the asymptotic quantization of continuous ran-

dom variables, Bell Laboratories Technical Memorandum

[46] Zador, P. (1982), Asymptotic quantization error of continuous signals and

the quantization dimension, IEEE Trans. Inform. Theory, 28, 139-149

[47] Zhu, S. (2005) Quantization for probability measures, Ph.D. Dissertation,

Universit¨at Bremen

110