Fabien Durand
email: fabien.durand@u-picardie.fr

Julien Leroy
email: julien.leroy@u-picardie.fr

S-ADIC CONJECTURE AND BRATTELI DIAGRAMS

Introduction

In their seminal papers [START_REF] Morse | Symbolic dynamics[END_REF][START_REF] Morse | Symbolic Dynamics II. Sturmian trajectories[END_REF] G. A. Hedlund and M. Morse proved that a sequence x ∈ A N is ultimately periodic if and only if p x (n) = n for some n where p x (n) is the word complexity of x, that is the number of distinct words of length n in x. Moreover they showed that sequences satisfying p x (n) = n + 1 for all n exist, are uniformly recurrent, intimately related to the rotations on the torus and S-adic, i.e., produced by an infinite product of finitely many morphisms (3 in fact). Then, certainly induced by the (sub-affine complexity) examples in [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF] and the complexity of substitutions ( [START_REF] Queffélec | Substitution Dynamical Systems-Spectral Analysis[END_REF]), B. Host conjectured that there exists a strong notion of S-adicity which is equivalent to sub-affine complexity. With the help of the nice result of J. Cassaigne [START_REF] Cassaigne | Special factors of sequences with linear subword complexity[END_REF] showing that a sequence x has sub-affine complexity if and only if (p x (n + 1) -p x (n)) n is bounded, Ferenczi proved in [START_REF] Ferenczi | Rank and symbolic complexity[END_REF] that minimal subshifts with sub-affine complexity (i.e., (p X (n)/n) n is bounded, where p X (n) is the number of words of length n appearing in sequences of X) are S-adic (i.e., obtained by an infinite product of finitely many morphisms). And, in the case it is ultimately bounded by 2, he showed that less than 3 27 morphisms are needed. The technicality of the proof did not allow to imagine and define the "strong notion of S-adicity" that is looked for. In [START_REF] Leroy | Some improvements of the S-adic conjecture[END_REF] the second author presented a more detailed proof of Ferenczi's result that leaded to some improvements (see also [START_REF] Leroy | A combinatorial proof of S-adicity for sequences with sub-affine complexity[END_REF]). Following Ferenczi's approach he showed that there exists a set S consisting of 5 morphisms (to be compared to 3 27 ) such that when (p X (n+1)-p X (n)) n is bounded by 2 then X is described by an infinite product of morphisms belonging to S. This provides a "strong notion of S-adicity" which is equivalent to this property. When (X, T ) is such that (p X (n+1)-p X (n)) n is bounded by 2 for all large enough n, then another morphism is needed. We present this result in this note (Theorem 3.1) with a statement that applies to Bratteli-Vershik representations of such subshifts. We recall that Bratteli-Vershik representations of minimal Z-actions on Cantor sets are powerful tools that were used to characterize the topological orbit equivalence [START_REF] Giordano | Topological orbit equivalence and C * -crossed products[END_REF] and that are very useful to solve problems where recurrence properties are involved. Observe it is usually not so easy to find such a representation and difficult to find the "canonical" representation. Nevertheless it has been done for various classical family of dynamical systems such that substitutive subshifts, Toeplitz subshifts, interval exchange transformations, sturmian subshifts, odometers and linearly recurrent subshifts. In this note we present such representations for subshifts such that (p X (n + 1) -p X (n)) n is bounded by 2 for all large enough n.

In Section 2 we recall the definition of Bratteli diagram and Bratteli-Vershik representation. Then we present some combinatorics on words and morphisms that notably help to obtain such representations of subshifts (Corollary 2.5). In Section 3, we present one of the main result of Leroy in [START_REF] Leroy | Contribution la résolution de la conjecture S-adique[END_REF] and, as an application of this result, we obtain BV-representations of S-adic subshifts (X, T ) such that (p X (n + 1) -p X (n)) n is bounded by 2 for all large enough n.

2. Bratteli-Vershik representations of S-adic subshifts 2.1. Bratteli-Vershik representations and subshifts. Consider a minimal Cantor dynamical system (X, T ) (MCDS, also called minimal Z-action on a Cantor set), i.e., a homeomorphism T on a compact metric zero-dimensional space X with no isolated points, such that the orbit {T n x; n ∈ Z} of every point x ∈ X is dense in X. We assume familiarity of the reader with the Bratteli-Vershik diagram representations of such systems, yet we recall it briefly in order to establish the notation. For more details see [START_REF] Herman | Ordered Bratteli diagrams, dimension groups and topological dynamics[END_REF][START_REF] Durand | Combinatorics on Bratteli diagrams and dynamical systems[END_REF]. The vertices of the Bratteli-Vershik diagram B = (V, E) are organized into countably many finite subsets of vertices V i , i ≥ 0 (where V 0 is a singleton {v 0 }) and subsets of edges

E i , i ≥ 1. Thus, V = ∪ i≥0 V i and E = ∪ i≥1 E i .
Every edge e ∈ E i+1 connects a vertex s = s(e) ∈ V i+1 for some i ≥ 0 with some vertex t = t(e) ∈ V i . At least one edge goes upward and at least one goes downward from each vertex in V i+1 . Multiple arrows connecting the same vertices are admitted. We assume that the diagram is simple, i.e., there is a subsequence (i k ) k≥0 such that from every vertex in V i k+1 there is an upward path (going upward at each level) to every vertex in V i k . For each vertex v ∈ V i (except v 0 ) the set of all edges {e 1 , . . . , e l } going upward (to V i-1 ) from v is ordered linearly : let say e 1 < • • • < e l . It will be convenient to consider the morphisms σ B i :

V * i → V * i-1 defined by σ B i (v) = t(e 1 ) • • • t(e l ).
We will say it is the morphism we read at level i on B. In the sequel we will always suppose that B is such that σ

B 1 (v) = v 0 for all v ∈ V 1 .
This ordering induces a lexicographical order on all upward paths from v to v 0 , and a partial order on all infinite upward paths arriving to v 0 . We denote by X B the set of all such infinite paths. We assume that this partial order has a unique minimal element x m (i.e., such that all its edges are minimal for the local order) and a unique maximal one x M (i.e., such that all its edges are minimal for the local order). This defines a map V B sending every element x to its successor in the partial order and sending x M to x m . Theorem 2.1 ( [START_REF] Herman | Ordered Bratteli diagrams, dimension groups and topological dynamics[END_REF]). Let (X, T ) be a minimal Cantor dynamical system. Then, there exists a simple Bratteli diagram B such that (X, T ) is conjugate to (X B , V B ) : there exists a bijective continuous map φ :

X → X B such that φ • T = V B • φ.
This representation theorem has been used in [START_REF] Giordano | Topological orbit equivalence and C * -crossed products[END_REF] to characterize the orbit equivalence relation of MCDS. We say that (X B , V B ) is a BV-representation of (X, T ).

In the sequel (X, T ) will exclusively be a subshift : X is a T -invariant closed subset of A Z (endowed with the product topology) where A is a finite alphabet and T is the shift map (T ((x n ) n ) = (x n+1 ) n ). Note that the shift map will always be denoted by T : we will specify neither X nor A. We say that (X, T ) is generated by x ∈ A Z when X is the set of sequences y such that for any i and j the word A substitution is an endomorphism σ : A * → A * such that there exists a letter a with σ(a) = au where u is not the empty word. The subshift (X σ , T ) it generates consists of x ∈ A Z such that all words x i x i+1 • • • x j of x have an occurrence in some σ n (a). We refer to [START_REF] Queffélec | Substitution Dynamical Systems-Spectral Analysis[END_REF] for more details.

y i y i+1 y i+j occurs in x. We set [u.v] X = {x ∈ X|x -|u| • • • x |v|-1 =
To obtain a BV-representation of (X σ , T ), an idea (first developed in [START_REF] Vershik | A theorem on the Markov periodical approximation in ergodic theory[END_REF]) is to consider the Bratteli diagram B where the morphism we read at each level on B is σ. When (X σ , T ) is minimal this provides a measure-theoretical representation which is not necessarily topological. The problem with this construction is that minimal paths correspond to right fixed points and maximal paths to left fixed points of σ. Thus, to obtain such a topological representation, we need to have a unique fixed point in A Z .

In [START_REF] Durand | Substitutive dynamical systems, Bratteli diagrams and dimension groups[END_REF] is shown that to have a stationary BV-representation of (X σ , T ) (i.e., where the substitutions read on the E i are equal up to some bijective changes of the alphabets), it suffices to find a proper substitution ζ such that (X ζ , T ) is conjugate to (X σ , T ). Then the stationary BV-representation is given by the Bratteli diagram where at each level i ≥ 2 we read ζ. Moreover an algorithm is given to find such ζ. Consequently to Lemma 2.2 the following proposition claims it is enough to have ζ left or right proper. Proposition 2.1. Let σ be a left or right proper primitive substitution and τ be a conjugate. Then,

(1) στ and τ σ are proper primitive substitutions ;

(2) (X σ , T ), (X τ , T ), (X τ σ , T ), (X στ , T ), (X B1 , V B1 ) and (X B2 , V B2 ) are pairwise conjugate where B 1 (resp. B 2 ) is the stationary Bratteli diagram we read στ (resp. τ σ) on from level 2.

The algorithm used in [START_REF] Durand | Substitutive dynamical systems, Bratteli diagrams and dimension groups[END_REF] to find BV-representations of substitution subshifts has a simplified version that can be used to find a left (or right) proper substitution. This leads to BV-representations with less edges and vertices. In the sequel we develop the idea of Lemma 2.2 to a more general framework.

Combinatorics on words and BV-representations.

Let S be a (possibly infinite) set of morphisms. An S-adic representation of (X, T ) is a sequence (σ n , a n ) n≥2 where, for all n, σ n : A * n → A * n-1 belongs to S, a n belongs to A n and X is the set of sequences x ∈ A Z 1 such that all words

x i x i+1 • • • x j appear in some σ 2 σ 3 • • • σ n (a n ).
We start the representation with n = 2 in order to fit with the Bratteli diagram notation : σ n will correspond to E n from n = 2. When such a sequence is fixed, we denote by (X n , T ) the subshift generated by (σ k , a k ) k≥n . Observe X n is included in A Z n-1 .

Proposition 2.2. Let (X, T ) be the minimal S-adic subshift defined by (σ n :

A * n → A * n-1 , a n ) n
where the σ n are proper. Suppose that all morphisms σ n extend by concatenation to a one-to-one map from X n to X n-1 . Then, (X, T ) is conjugate to (X B , V B ) where B is the Bratteli diagram such that for all n ≥ 2 the substitution read on B at level n is σ n .

Proof. We can suppose that all the images of σ n starts with the letter a and ends with b. Define, for all n, τ n = σ 2 • • • σ n and (X n , T ) the subshift generated by (σ l :

A * l → A * l-1 , a l ) l≥n . Notice that τ n (X n+1
) is included in X and consider

P(n) = T j τ n ([c] Xn+1 ) | c ∈ A n , 0 ≤ j < |τ n (c)| .
From [START_REF] Herman | Ordered Bratteli diagrams, dimension groups and topological dynamics[END_REF], to conclude, it suffices to prove that (P(n)) n is a nested sequence of partitions generating the topology of X satisfying # ∩ n ∪ c∈An τ n ([c] Xn+1 ) = 1. We prove it is a partition. Let x ∈ X. The maps σ n : X n → X n-1 being one-to-one, there exist a unique couple (y, j), y = (y l ) l∈Z ∈ X n and j ∈ {0, 1, . . . , |τ n (y 0 )| -1}, such that x = T j τ n (y). Then, x belongs to T j τ n ([y 0 ] Xn ) and P(n) is a partition. Now, we prove it is nested. Let Ω = T j τ n+1 ([c] Xn+2 ) be an atom of

P(n + 1). Let σ n+1 (c) = c 1 • • • c l and i such that |τ n (c 1 • • • c i )| ≤ j < |τ n (c 1 • • • c i+1 )|. Then, Ω ⊂ T j-|τn(c1•••ci)| τ n ([c i+1 ] Xn+1
) and (P(n)) n is nested. We let as an exercise to prove it generates the topology of X.

As

τ n+1 ([c] Xn+2 ) ⊂ τ n ([b.a] Xn+1 ), from the assumptions, we deduce ∩ n ∪ c∈An τ n ([c] Xn+1 ) = 1.
Observe that in Proposition 2.2, it is important to suppose that σ n is one-toone. For examples, if the σ n were equal to σ, where σ(a) = ab and σ(b) = ab, then (X, T ) would be a two-point periodic subshift and (X B , V B ) would be the 2-odometer. Using Lemma 2.2 we obtain the following corollary.

Corollary 2.3. Let (X, T ) be the minimal S-adic subshift defined by (σ n , a n ) n≥2 where the σ n are left or right proper. Suppose that for all n the morphisms σ n extend by concatenation to one-to-one maps from X n to X n-1 . Then (X, T ) is conjugate to (X B , V B ) where B is the Bratteli diagram where for all n ≥ 2 :

(1) the substitution read on E 2n is left proper and equal to σ 2n or its conjugate ;

(2) the substitution read on E 2n+1 is right proper and equal to σ 2n+1 or its conjugate.

More can be said about these subshifts but we need the following theorem proved in [START_REF] Downarowicz | Finite rank Bratteli-Vershik diagrams are expansive[END_REF]. We say that a MCDS (Y, S) has topological rank k if k is the smallest integer such that (Y, S) has a BV-representation (X B , V B ) with (|V (n)|) n bounded by k. When such a k does not exist we say that it has infinite topological rank. Examples of such systems are the odometers (k = 1), all primitive substitutive subshifts, all sturmian subshifts (k = 2), all linearly recurrent subshifts, some toeplitz subshifts (see [START_REF] Durand | Combinatorics on Bratteli diagrams and dynamical systems[END_REF] for a survey). In fact, we can be more precise. Let (X B , V B ) be a Bratteli-Vershik representation of (Y, S) whose set of vertices of B is bounded by k. Now let (X n , T ) be the subshift generated by (σ B k , a k ) k≥n , where a k belongs to V k . Then, if there exists n such that (X n , T ) is not periodic then (Y, S) is a subshift, otherwise it is equicontinuous. From this theorem and Corollary 2.3 we deduce the following corollary that enables us to give a BV-representation of any subshift once we have a "nice" S-adic representation.

Corollary 2.5. Let (X, T ) be a MCDS with and (σ n :

A * n → A * n-1 , a n ) n be such that (|A n |) n is bounded by K.
The following are equivalent.

(1) (X, T ) is the non-periodic subshift defined by the sequence (σ n , a n ) n satisfying : For all n the map σ n : X n → X n-1 is well-defined, one-to-one and left or right proper.

(2) (X, T ) is conjugate to (X B , V B ) where B is the Bratteli diagram verifying :

(a) for all n, the substitution read on E 2n is left proper and equal to σ 2n or its conjugate ;

(b) for all n, the substitution read on E 2n+1 is right proper and equal to σ 2n+1 or its conjugate ;

(c) (X 2 , T ), defined by (σ k , a k ) k≥2 , is not periodic.

Moreover, in these situations the topological rank of (X, T ) is bounded by K.

In the next section we apply this corollary to the subshifts having a first difference of word complexity less or equal to 2 in order to obtain their Bratteli-Vershik representations.

Applications to sub-affine complexity

The following result was proven in [START_REF] Leroy | Some improvements of the S-adic conjecture[END_REF]. We adapt it to our context. The original statement gives a complete answer to the S-adic conjecture (see [START_REF] Ferenczi | Rank and symbolic complexity[END_REF]) in a restricted context. Theorem 3.1. Let (X, T ) be an non-periodic minimal subshift such that (p X (n + 1)-p X (n)) n is bounded by 2 for all large enough n, then (X, T ) is an S-adic subshift defined by (σ n , a n ) n≥2 where for all n ≥ Moreover, σ n : X n → X n-1 is one-to-one and there exists an increasing sequence (n i ) i such that for all i, σ ni σ ni+1 • • • σ ni+1 is proper and all letters in {a, b, c} occur in all images σ ni σ ni+1 • • • σ ni+1 (y), y ∈ {a, b, c}. Furthermore, σ 2 can be algorithmically determined.

Theorem 3.1 is weaker than the one in [START_REF] Leroy | Some improvements of the S-adic conjecture[END_REF]. Indeed, the complete result states that there is a labelled directed graph G and some condition (C), both computable, for which a subshift (X, T ) is such that (p X (n + 1) -p X (n)) n is bounded by 2, for all large enough n, if and only if it has a S-adic representation (σ n ) n which is an infinite path in G satisfying the condition (C).

The Bratteli-Vershik version of this result is the following.

Corollary 3.2. With the assumptions and notations of Theorem 3.1, the topological rank of (X, T ) is at most 3. More precisely, (X, T ) is conjugate to (X B , V B ) where B is the Bratteli diagram such that, for all n ≥ 3, the substitution read at level n is σ n .

Références

  uv} and we call such sets cylinder sets. They are clopen sets and form a base of the topology of X. When u is the empty word we write [v] X . 2.2. Proper morphisms, substitutions and BV-representations. In the sequel A, B, A n , . . . are finite alphabets and A * denotes the free monoid generated by A. A morphism σ : A * → B * is left proper (resp. right proper) if there exists a letter l ∈ B (resp. r ∈ B) such that for all a ∈ A, σ(a) = lu(a) (resp. σ(a) = u(a)r) for some u(a) ∈ B * . It is proper when it is both left and right proper. Let σ be left proper. The morphism τ : A * → B * defined by τ (a) = u(a)l is the left conjugate of σ and it is right proper. In the same way we define the right conjugate of σ (it is left proper). Lemma 2.2. Let σ : A * → B * be a left proper (resp. right proper) morphism with first letter l (resp. last letter r) and τ be its left (resp. right) conjugate then for all a ∈ A and n σ n (a)l = lτ n (a) (resp. rσ n (a) = τ n (a)r).

Theorem 2 . 4 (

 24 [START_REF] Downarowicz | Finite rank Bratteli-Vershik diagrams are expansive[END_REF]). Let (Y, S) be a MCDS with topological rank k. Then (Y, S) is expansive if, and only if, k ≥ 2. Otherwise it is equicontinuous.

  3, σ n belongs to S = {D, G, E ab , E bc , M } with D : a → ab, G : a → ba, E ab : a → b, E bc : a → a, M : a → a b → b b → b b → a b → c b → b c → c c → c c → c c → b c → b.


Olivier Curé

Yannick Prié
email: yannick.prie@liris.cnrs.fr

Pierre-Antoine Champin
email: pierre-antoine.champin@liris.cnrs.fr

A Knowledge-Based Approach To Augment Applications With Interaction Traces

This paper presents a trace-based framework for assisting personalization and enrichment of end-user experience in an application. We propose a modular ontology-based architecture, to provide semantics for interaction traces, observed elements and their associated objects, and we extend existing inference services, with a declarative and generic approach, in order to reason with those interaction traces. We present the architecture of our framework and its reasoning levels, provide a proof of concept on a medical Web application, and emphasize that different kinds of actors can benefit from the supported inferences.

Introduction

We present an assistance framework for personalizing and enriching end-user application interactions. These features rely on user profiles generated from interaction traces that provide information on how data is used and created. Our declarative approach is based on explicitly modeled interaction traces consisting of recordings of observed elements (henceforth obsels) that are collected during the use of the application.

A first contribution is to provide a Description Logics (DL) [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] based approach to modeling traces by constructing a global knowledge base of entities and actions that can be reasoned upon. The semantics of interaction traces, obsels and their associated objects are provided through mappings to DL concepts or roles. DL formalism has been selected because it enables to reason in a sound and complete manner, and enables interoperability by underlying Semantic Web technologies. Another contribution is to define means of reasoning over various levels of interaction knowledge. Standard (i.e. subsumption) and non-standard DL inferences support these services. In order to represent uncertainty, a probabilistic approach is used. Various levels of reasoning are presented that support various kinds of user assistance based on the manipulated objects, traces, and user profiles. Moreover, we have implemented this approach in an existing medical application, and have shown its interest by adding several functionalities that have proven valuable to various actors of this system, from admin to end-users.

This paper is organized as follows. Sec. 2 is dedicated to related works. Sec. 3 details how an application can be augmented with our framework for managing interaction traces, while Sec. 4 describes the different reasoning approaches. In Sec. 5, we provide an evaluation on our running example, emphasize on the system's inferences adequacy. Fig. 1. Architecture overview of an application enriched with a trace-based system for assistance 2 Related works Interaction traces have long been considered a valuable source of information, either for an a posteriori analysis of the activity, or during the traced activity in order to provide some kind of user-assistance [START_REF] Wexelblat | History-rich tools for social navigation[END_REF]. The latter is based on the assumption that the traces can help to automatically build a user's profile, instead of requiring the user's to manually provide their personal information and preferences [START_REF] Sugiyama | Adaptive web search based on user profile constructed without any effort from users[END_REF]. Different paradigms have been explored to provide trace-based user-assistance, such as case-based reasoning (traces can be used to dynamically generate cases corresponding to a problem at hand [START_REF] Smyth | A Case-Based perspective on social web search[END_REF]), or machine learning (traces are used as a training set for further recommendations [START_REF] Sugiyama | Adaptive web search based on user profile constructed without any effort from users[END_REF]). Traces can also be modeled using ontologies, allowing complex inferences to be performed in order to assist the user [START_REF] Groza | The NEPOMUK project -on the way to the social semantic desktop[END_REF]. Like our system, this work uses Semantic Web technologies to represent ontologies. There is indeed a growing interest in modeling temporal information related to users' activity on the Semantic Web [START_REF] Champin | SIOC in Action -Representing the Dynamics of Online Communities[END_REF]. [START_REF] Angeletou | Modelling and analysis of user behaviour in online communities[END_REF] combine statistical analysis with a semantic model and rules in order to measure the health of on-line communities by analyzing the behavior of their users. There has been other work aiming at integrating time in DL [START_REF] Artale | Temporal description logics[END_REF] and Semantic Web technologies [START_REF] Anicic | EP-SPARQL: a unified language for event processing and stream reasoning[END_REF][START_REF] Tappolet | Applied temporal RDF: efficient temporal querying of RDF data with SPARQL[END_REF]; however those approaches consider time as a dimension orthogonal to the data. As such, they are not adapted to our approach where time is merely a property of every obsel.

A framework for integrating interaction traces in applications

Fig. 1 describes the different information flows between the components of our architecture. The user interacts (1) with the application, causing updates to the domain database (2) and the interaction traces component (3). In the latter, a subset of the enduser interactions is stored as temporally situated interaction traces, e.g. start of a session or description of an item. This subset of interactions is defined through a set of mapping assertions (Mappings component) between interaction traces and elements of the ontologies. Note that some mapping assertions also relate the database with the ontology (4). A set of interaction traces, mapping assertions and ontologies is used by the Graph generator to define a global graph [START_REF] Baader | Pushing the el envelope[END_REF], containing the overall information involved in the process of describing interactions. Moreover, it integrates metadata such as object specific information coming from the ontologies and/or the domain database. The global graph is passed to the reasoner [START_REF] Champin | SIOC in Action -Representing the Dynamics of Online Communities[END_REF] to generalize on the represented information, computing subsumption relationships between ontology concepts. The generalizations are both stored as (transformed) interaction traces and in the domain database [START_REF] Groza | The NEPOMUK project -on the way to the social semantic desktop[END_REF], e.g. to store end-user models which will be used to personalize the application together with information directly coming from the traces. Finally, the Admin module enables to manage and query information stored as raw or transformed interaction traces (8) to detect assets and drawbacks of the application, e.g. objects that are rarely accessed, etc.

Representation of Interaction Traces. We use the meta-model proposed in [START_REF] Laflaquière | A trace-based System Framework for Experience Management and Engineering[END_REF] for managing interaction traces: a trace is defined as a list of timestamped obsels, holding a set of attributes and relations. Each trace is related to a trace model, defining the different types of obsel the trace can contain, and which attributes and relations obsels of each type can have. A trace-based management system (TBMS) collects obsels from the application in so-called primary traces. A TBMS also manages transformed traces, which are computed based on the content of other traces, providing higher levels of interpretation. Hence we have three knowledge containers for each trace: its metadata , its model, and the list of contained obsels. In our framework, the set of obsels recorded in an interaction trace is the representation of an end-user's interactions with a given application. They mainly correspond to CRUD (Create, Read, Update, Delete) operations, but can be extended to higher level operations (e.g. Copy, Paste).

Each end-user session is represented by a single trace, satisfying the schema (idT, idU, ssDate, seDate) where attributes respectively identify an interaction trace, the subject of the trace (i.e. the end-user whose activity is recorded), the session start and end dates. Traces then contain a number of obsels describing the data operations performed within the application during the session. Obsels satisfy the schema (idT, obselDate, idObj, op, objField, oldValue, newValue) where idT references the containing trace, obselDate is the timestamp of the obsel (and must be comprised between ssDate and seDate of the containing trace), idObj identifies the object impacted by the interaction, op identifies the data operation performed on that object, objField identifies the object's field impacted by the operation, if appropriate, and oldValue and newValue contain, if appropriate, the field value before and after the operation respectively. The last three attributes are optional, depending on the kind of operation. That is a Retrieve operation does not impact a specific field of an object and has none of those three attributes; a Delete operation only has an old value, an Insert operation only has a new value and an Update operation has the three attributes filled in.

Ontologies for traces. A particular attention has been given to the ease of plugging in and out ontologies and to provide a comprehensive decoupled organization. The default setting of our framework consists of the following 4 ontologies. The general trace ontology provides a model for a high-level view of interaction traces. It contains 3 concepts: Trace, Obsel and Subject (the user whose interaction was traced); 2 object properties: describes and composedOf, respectively relating an interaction trace to its subject and its obsels; 4 datatype properties, supporting subject identification and temporal infor- The domain specific ontology describes the semantics of the objects observed in the interaction traces. In opposition to the other ontologies of the architecture, this component may integrate an ABox.Obviously, the more information is provided on observed objects (either in a TBox or an ABox), the more accurate the results of our inferences. The domain trace bridge ontology links the trace generic ontology to the domain specific ontology. It contains 2 concepts: Object and Field, and 2 properties to identify an object and relate an object to its fields. These 2 concepts subsume some of the concepts of the domain specific ontology and are related to some of the trace generic ontology concepts via object properties, e.g. onObject and hasField.

General Trace Ontology Trace Generic Ontology Domain Trace Bridge Ontology Domain Specific Ontology

Example 1: Fig . 2 provides a comprehensive view of a framework instance for our medical application. The domain trace bridge ontology provides information on drug objects which have a certain form (i.e. allopathy or homeopathy), treat some therapeutic classes and contain some molecules. Two other concepts of this ontology, namely Con-traIndication and SideEffect are subsumed by the Field concept of the domain trace bridge ontology. Note that only Drug is subsumed by the Object concept from the bridge ontology, so only operations on drugs will be recorded in the trace. However, Molecule and TherapeuticClass can be used as external knowledge to support inferences on drugs and the related obsels.

If our framework was to be used in a completely different domain, the domain specific ontology would have to be replaced. The modular structure would however make it easy to reuse an existing Semantic Web ontology for the new application domain, and link it to the other ontologies through mappings to the domain trace bridge ontology.

Reasoning over traces

We model interaction traces using a set of ontologies, using DL to provide them with model-theoretic semantics [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]. A DL knowledge base (KB) is composed of a TBox and an ABox which respectively correspond to a set of terminological axioms and concept/property assertions. A key feature of DLs is to integrate in the system the following set of standard inferences: concept satisfaction and subsumption, instance checking, realization and retrieval. Although we use some of these inferences, we also adapt two non standard DL inferences named Most Specific Concept (MSC) and Least Common Subsumer (LCS) [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]. The MSC of an individual α wrt a KB is the concept description C such that (i) α is an instance of C and (ii) if there is another concept C' of which α is an instance of, then C' is more general w.r.t. subsumption than C. The LCS of a given set S of concept descriptions is the most specific concept (wrt the subsumption relationship) subsuming all concepts descriptions in S . In general, they are computed with either a structural subsumption algorithm or via the specification of a normal form. Within our framework, MSC is used to generate DL concepts (hence models) from individuals corresponding to instances of interaction traces, obsels or their objects. Given these instances, the system generates concept description in the EL DL [START_REF] Baader | Pushing the el envelope[END_REF] which underpins the OWL2 EL fragment. This DL presents good properties in terms of reasoning: subsumption is polynomial even if one allows for cyclic terminologies and the MSC of an ABox individual always exists. Moreover, users' goals and intentions are too complex to be entirely accounted for by formal inferences. To handle this uncertainty, we use Probabilistic EL [START_REF] Gutiérrez-Basulto | A closer look at the probabilistic description logic prob-el[END_REF], an extension of EL that associates probabilities to concept descriptions.

As seen in Fig. 1(5), the reasonner works on a global graph generated from different knowledge sources. Fig. 3(a) presents some interaction traces performed over our medical application while Fig. 3(b) displays its associated instance graph. Note that the contains, treats and hasForm properties associated to the :obj1 node can not be generated from the interaction traces. In fact they correspond to external knowledge retrieved from the domain database. This is a difference with the original TBMS approach [START_REF] Laflaquière | A trace-based System Framework for Experience Management and Engineering[END_REF]. A major advantage of using ontologies is the ability to generalize patterns discovered with type inference, i.e. the most common concept that satisfies a given situation.

Inferencing over various levels of interaction knowledge. The analysis of the end-user's behavior can be performed at different levels. We propose 5 of them which cover a wide range of relevant features and still support a generic approach. They correspond to the main DL concept abstractions found in our ontologies: Field, Object, Obsel, Trace and Subject. These levels require different forms of processing: a finite model checking approach handled with a simple query answering interface; or a more elaborate logical reasoning. Inference services provided by each level build on the previous ones.

The Field level is the most specialized level and little information can be retrieved from it. Intuitively, it enables to retrieve which kind of fields specified in the Domain specific ontology have been observed. Hence a simple query answering interface is sufficient. For instance, the question: "Which fields have been observed?" may be answered with an enumeration of subconcepts of the Field concept that have been effectively observed. This query may help to detect which fields are never operated upon.

The Object level is central as it is the first one to require logical reasoning and all remaining levels build on its inferences. Both query answering and logical reasoning are needed at this level. For instance, query answering can be used to identify objects operated upon. The main logical reasoning of this level enables to generalize on a given object description (detailed in Sec. 4).

The Obsel level enables to study the operation associated to an observed object. Typical queries are CRUD-like and reasoning amounts to generalize obsel description.

The Trace level is an interesting level due to the non-functionality of the com-posedOf property, i.e. a trace can be composed of several obsels. Moreover, an interaction trace is associated to some temporal values representing its begin and end session dates. Thus, a query answering approach can answer to questions such as "When was a trace recorded? How long did it last?". Logical reasoning is mainly concerned with generalizing a given interaction trace. An interesting aspect of reasoning at this level involves considering ordered sequences of generalized traces. By storing the result of that generalization as transformed traces, we can then query sequences of similar sessions.

Finally, the Subject level enables to infer over a set of interactions performed by an end-user. Query answering can be used to reply to the following questions for a given end-user: "When did this user use the application for the last time?", "How often does this user use the application?". We can also consider queries involving a group of endusers, i.e. queries aggregating over end-users. Logical reasoning amounts essentially in defining an end-user profile (i.e. concept descriptions) given her set of interaction traces. In our running example, this user profile aims to define her pharmacology expertise, i.e. in terms of molecules, therapeutic classes and drug forms she is an expert in.

Reasoning method. The reasoning methods needed by our levels of analysis are based on the following 3 algorithms. The first algorithm, simpMSC, corresponds to a simplified version of MSC and aims to generate a DL concept description for any individual present in the global graph. These DL concepts are specified by the following normal form: A i ⊓ ∃r j A k where A i and A k are atomic concepts and r j is an object property. The algorithm takes as input an individual α and acts as follows. For all assertions of the form Γ(α) (i.e. defining the type of α), it creates a conjunction AC of Γs. Moreover, for all assertions of the form r(α, β) with r an object property assertion, it creates a conjunction EQ of ∃r.β. The algorithm returns as output AC ⊓ EQ. This algorithm is used at both the Object and Obsel levels respectively to produce a DL concept for an object in terms of elements of the Domain specific ontology and an obsel in terms of elements of the Trace generic ontology and Domain specific ontology.

Example 2: Consider the :obj1 individual in Fig. 3. Its assertion set contains: a type definition Drug(:obj1), 3 object property assertions (contains(:obj1, Paracetamol), hasForm(:obj1, Allo) and treats(:obj1,AntiPyretic)) and a data type property assertion: (hasOb jectID(:obj1,3595583)). The execution of simpMSC over this individual returns: Drug ⊓ ∃contains.Paracetamol ⊓ ∃treats.AntiPyretic ⊓ ∃hasForm.Allo.

The second algorithm, probLCS, corresponds to an approximation of LCS extended with probabilities on concepts. We use the notation of [START_REF] Gutiérrez-Basulto | A closer look at the probabilistic description logic prob-el[END_REF]: a concept T race ⊓ ∃composedO f (P =1/2 Retrieve⊓∃onOb ject.O1) describes an interaction trace composed of an obsel on object O1 and a Retrieve data operation with probability 0.5. We restrict probabilities to occur in front of DL concepts and allow disjunction in the form A ⊔ B ⊑ C since it can be eliminated modulo the introduction of the new concept C.

The input of this algorithm is a set of concept descriptions produced by simpMSC. In a first step, a disjunction of atomic concepts is computed. That is, it counts the number of occurrences of each non quantified atomic concepts over the set of descriptions and produces a probabilistic formula for each of them where the probability is the number of occurrences of this concept divided by the total number of occurrences of the set. In the second step, for each distinct existentially quantified property, the first step is applied over its set of concepts. The probLCS algorithm serves at the Trace level to specify a probabilistic view of the obsels present in an interaction trace.

Example 3: Consider the obsels of Fig. 3 (i.e. :obsels i with i ∈ [START_REF] Angeletou | Modelling and analysis of user behaviour in online communities[END_REF][START_REF] Artale | Temporal description logics[END_REF]). Applying simpMSC to these obsel individuals yields the respective concepts (where O1 is the concept description from Ex. 2): Retrieve ⊓ ∃onOb ject.O1, Create ⊓ ∃onField.ContraIndication ⊓ ∃onOb ject.O1, Delete ⊓ ∃onField.S ideE f f ect ⊓ ∃onOb ject.O1. Computing probLCS over this set yields the following concept:

(P =1/3 Retrieve⊔P =1/3 Create⊔P =1/3 Delete) ⊓ ∃onField.(P =1/3 ContraIndication⊔P =1/3 SideEffect) ⊓ ∃onOb ject.P =3/3 O1
The last algorithm, setProb, operates on a set of probabilistic concepts to create a generalized concept, using the notion of concept comparability.

Definition 1: The comparability property, defined over the normal form of a probabilistic concept, i.e. (S C) ⊓ (∃rS C) where S C, standing for Simple Concept, is a disjunction of probabilistic atomic concept, is stated as follows: non quantified simple concepts are comparable and simple concepts existentially quantified by the same property are also comparable. No other concepts are comparable.

Given this comparability property, the generalization of probabilistic concepts is defined as summing the probabilities of comparable simple concepts. To compute a relevant sum, all probabilities are expressed over the total number of occurrences found locally. This approach enables to sum properties and to have a coherent global view of the distribution of probabilities. The setProb algorithm is used at the Subject level when a generalization of interaction traces described by a given end-user is required.

Example 4: Consider the composition of the 2 following interaction traces: -(P =1/3 Retrieve ⊔ P =1/3 Create ⊔ P =1/3 Delete) ⊓ ∃onField.(P =1/3 ContraIndication ⊔P =1/3 SideEffect) ⊓ ∃onOb ject.P =3/3 O1 -(P =2/4 Retrieve ⊔ P =2/4 U pdate) ⊓ ∃onField.(P =2/4 SideEffect) ⊓ ∃onOb ject.P =4/4 O2 The execution of setProb over these interaction traces yields: (P =3/7 Retrieve ⊔ P =1/7 Create ⊔ P =1/7 Delete ⊔ P 2/7 U pdate) ⊓ ∃onField.(P =1/7 ContraIndication ⊔P =3/7 SideEffect) ⊓ ∃onOb ject.(P =3/7 O1 ⊔ P 4/7 O2)

The probabilities of the concept description computed by setProb represent the uncertainty of our conclusions about the user's activity at a certain level. In the context of the Subject level, this concept description serves to create an approximation of a user model. A threshold θ is used to cope with the uncertainty of our approximation.

Definition 2: Given a probabilistic DL concept, a certain rewriting of this concept wrt a threshold θ is computed by retaining only the inner concepts whose probability is superior or equal to θ.

The certain rewriting of a probabilistic concept wrt to a threshold θ serves to generate a model for a given subject. That is the remaining concepts of the description specify the expertise/point of interest of the end-user.

Example 5: Consider the probabilistic concept generated in Ex. 4 and a threshold θ=1/3. The certain version corresponds to: (Retrieve) ⊓ ∃ onField.(SideEffect) ⊓ ∃ onObject.(O1 ⊔ O2 ) where the drug O1 (resp. O2) has form Allo, treats Cough and contains Dextromethorphan (resp. has form Phyto and treats the respiratory system). This enables to define a user model corresponding to a domain expert involved in Retrieve data operation and side effect field over allopathic and phytotherapeutic drugs of both the Cough and respiratory system, containing the Dextromethorphan molecule.

Finally, testing subsumption of concepts filling the onObject property is performed. Intuitively, using the Domain specific ontology, the system checks for concepts covering wrt. to subsumption. Thus a set of subsumed concepts are replaced with the super concept. This approach limits the size of generated user models and improves their relevance by relating them to named concepts rather than complex concepts expressions.

Trace-based assistance in a self-prescription application

Reasoning occurs at the different levels of interaction knowledge. Several kinds of actors (end-user, staff manager and developer) can benefit from various inference services.

At the Object level, the system can efficiently compute statistics on frequently modified objects and fields and hence provide up-to-date information on market evolution.

The Obsel reasoning level enables to detect repetitive operations performed on same category objects. The system then proposes the end-user to execute them automatically on the remaining objects in this category, as soon as it has been repeated more than a given threshold (defaulting to 3). This kind of information also supports the discovery of some integrity constraints, e.g. which fields or objects are most frequently updated for the drug category of homeopathy or respiratory system. For example, it is relatively frequent in the medical domain that some molecules are being attributed new properties. This may cause drugs containing that molecule to change from OTC to requiring a prescription. After the end-user has changed the state of 3 such drugs, the system will offer to make the change to all remaining drugs. Before the adoption of our trace reasoning level, all modifications had to performed manually.

In our medical application, all modifications are double-checked by an expert of this product's category, i.e. either form, molecule or therapeutic class. For instance, a homeopathy expert usually does not have the expertise to check information on the allopathy drug category. The Subject level automatically generates this expertise profile for each user based on their interaction traces. Based on these user models, we are able to personalize the home page of each end-user in the following way: (i) she is only asked to check drugs in her domain of expertise, (ii) she is provided with a list of contacts in her domain of expertise and (iii) health news displayed in the application are prioritized according to her domain of expertise. This approach has simplified the tasks of our team of health care professionals and has significantly lowered time delivery of data updates.

The administration tool is also very useful to improve our system. Due to different forms of reasoning, it enables to identify drug categories not frequently operated upon (obsel level), to control the cleaning/checking activity of a given domain expert (trace level), to detect domains of expertise missing in a team of end-users, to discover who checks and/or overrules the updates of a given expert (subject level), etc. Evaluation. We have conducted an evaluation to highlight our framework's assets and weaknesses on certain criteria related to Subject level reasoning and user profiles: a) productivity gain of end-users, b) correctness of the models generated for each end-user. The experimentations have been conducted on our medical application over a real dataset involving 12 health care professionals over 3 months and resulting in the recording of 420 interaction traces and over 23000 obsels.

The first experiment tackles the gain of productivity of end-users. The experimentation took place after a period of 2 months of recording interaction traces.None of them were aware of the existence of the framework. Given the user models generated after the recording of 2 months of interaction traces, we divided the group of 12 end-users into 3 homogeneous (i.e. based on the precision of their models) groups of 4 persons. Then over a period of 3 weeks, we conducted a survey over the evolution of the precision of the check box. This box is displayed on the home page of each end-user and contains a list of drugs that have been recently modified and which need a checking by another health care professionals before being put into production. Hence, it is an invitation for end-users to control the information associated to a given drug. For group #1, the check box did not benefit from the inferences of the framework. The end-users hence had to browse the list of drugs to find by themselves the ones in which they have some expertise. For group #2, the check box was progressively taking benefit from the 2 months of analysis. That is in the first week, the box benefited from the user model deduced after 3 weeks of analysis, in the second week, it benefited from 6 weeks of analysis and in the last week it used the models generated over the 2 months of analysis. In the case of group #3, the check box benefited from the 2 months of analysis right from day one of the experimentation. Participants in each group rated the adequacy of the drugs presented in the check box according to their medical expertise. A Likert scale with 5 ordered responses was used, ranging from '5=strongly adapted' to '1= not adapted'. Fig. 4(a) emphasizes that group #1 does not see any improvement in adequacy of the box list. As expected, through the period of the evaluation, participants of group #2 sensed an improvement in the adaptability of the proposed list of drugs. Finally, the improvement was felt right away for members of group #3. The second experiment was conducted right after the first one and once all end-users were informed about the existence and aim of the framework. We presented a comprehensive view (i.e. presented in natural language) of the user model generated for each participants (out of the 2 months plus 3 weeks of storing interaction traces on experiment #1) and asked them to rate (using the same Likert scale as in ( 1)) the precision of their profile. Fig. 4(b) presents the average of individual results over members of the 3 groups. The averages range from 4.5 for group #1 to 4.75 for group #3. We consider these results to be satisfactory as it rewards the work invested on this framework. Anyhow, the quality of these results is related to the well-defined expertise of each health care professional participating to the project.

Fig. 2 .

 2 Fig. 2. Ontology-based framework for considering both traces and domain objets

Fig. 3 .

 3 Fig.3. A trace extract and its graph instance (with some data omitted for readability)

Fig. 4 .

 4 Fig. 4. Results of experimentations


Hadj El

Dia Aly

ERROR BOUNDS FOR SMALL JUMPS OF L ÉVY PROCESSES

Keywords: Approximation of small jumps, Lévy processes, Skorokhod embedding, Spitzer identity AMS subject classifications. 60G51, 65N15 JEL classification. C02, C15

Error bounds for small jumps of Lévy processes

El Hadj Aly Dia

1. Introduction. In the recent years, the use of general Lévy processes in financial models has grown extensively (see [START_REF] Barndorff-Nielsen | Normal inverse Gaussian distributions and stochastic volatility modelling[END_REF][START_REF] Carr | The fine structure of asset returns: An empirical investigation[END_REF][START_REF] Eberlein | Application of generalized hyperbolic Lévy motions to finance[END_REF]). A variety of numerical methods have been subsequently developed, in particular methods based on Fourier analysis (see [START_REF] Broadie | A double-exponential fast Gauss transform algorithm for pricing discrete path-dependent options[END_REF][START_REF] Feng | Pricing discretely monitored barrier options and defaultable bonds in Lévy process models: a fast Hilbert transform approach[END_REF][START_REF] Feng | Computing exponential moments of the discrete maximum of a Lévy process and lookback Options[END_REF][START_REF] Petrella | Numerical pricing of discrete barrier and lookback options via Laplace transforms[END_REF]). Nonetheless, in many situations, Monte-Carlo methods have to be used. The simulation of a Lévy process with infinite Lévy measure is not straightforward, except in some special cases like the Gamma or Inverse Gaussian models. In practice, the small jumps of the Lévy process are either just truncated or replaced by a Brownian motion with the same variance (see [START_REF] Asmussen | Approximations of small jumps of Lévy processes with a view towards simulation[END_REF][START_REF] Cont | Financial Modelling with Jump Processes[END_REF][START_REF] Cont | Integro-differential equations for option prices in exponential Lévy models[END_REF][START_REF] Rydberg | The normal inverse gaussian lévy process: simulation and approximation[END_REF][START_REF] Signahl | On error rates in Normal approximations and simulation schemes for Lévy processes[END_REF]). The latter approach was introduced by Asmussen and Rosinski [START_REF] Asmussen | Approximations of small jumps of Lévy processes with a view towards simulation[END_REF], who showed that, under suitable conditions, the normalized cumulated small jumps asymptotically behave like a Brownian motion.

The purpose of this article is to derive bounds for the errors generated by these two methods of approximation in the computation of functions of Lévy processes at a fixed time or functionals of the whole path of Lévy processes. We also derive bounds for the cumulative distribution functions. These bounds can be used to determine which type of approximations to use, since replacing small jumps by Brownian is more time-consuming (if we use Monte Carlo methods). Our bounds can be applied to derive approximation errors for lookback, barrier, American or Asian options. But this latter point will not be developed, and is left to another paper.

The characteristic function of a real Lévy process X with generating triplet (γ, b 2 , ν) is given by

Ee iuXt = exp t iγu - b 2 u 2 2 + +∞ -∞ e iux -1 -iux1 |x|≤1 ν(dx) ,
where γ ∈ R, b ≥ 0, and ν is a Lévy measure. The process X is the independent sum of a drift term γt, a Brownian component bB t , and a compensated jump part with Lévy measure ν. The process X has finite (resp. infinite) activity if ν(R) < ∞ (resp. ν(R) = +∞). For 0 < ǫ ≤ 1, the process X ǫ is defined by

X ǫ t = γt + bB t + 0≤s≤t ∆X s 1 {|∆Xs|>ǫ} -t ǫ<|x|≤1 xν(dx).
The process X ǫ is obtained (from X) by subtracting the compensated sum of jumps not exceeding ǫ in absolute value. Let R ǫ = X -X ǫ .

(1.1)

The process R ǫ is a Lévy process with characteristic function

Ee iuR ǫ t = exp t |x|≤ǫ e iux -1 -iux ν(dx) .
It holds E (R ǫ t ) = 0 and Var (R ǫ t ) = σ(ǫ) 2 t, where

σ(ǫ) = |x|≤ǫ x 2 ν(dx).
Note that lim ǫ→0 σ(ǫ) = 0. The behavior of σ(ǫ) when ǫ goes to 0 is known for classical models (VG, NIG, CGMY...). As noted in Example 2.3 of [START_REF] Asmussen | Approximations of small jumps of Lévy processes with a view towards simulation[END_REF], if ν(dx) = |x| -1-α L(x)dx, where α ∈ (0, 2) and L is slowly varying at 0 , then it holds σ(ǫ) ∼ ((L(-ǫ) + L(ǫ)) /(2 -α))

1/2 ǫ 1-α/2 ; consequently, lim ǫ→0 σ(ǫ)/ǫ = +∞. We also define the process Xǫ by

Xǫ t = X ǫ t + σ(ǫ) Ŵt , t ≥ 0,
where Ŵ is a standard Brownian motion independent of X. We aim to study the behavior of the errors made by replacing X by X ǫ or Xǫ , with respect to the level ǫ. These errors are studied for the process X at a fixed date and for its running supremum. Set, for any t ≥ 0,

M t = sup 0≤s≤t X s , M ǫ t = sup 0≤s≤t X ǫ s , M ǫ t = sup 0≤s≤t Xǫ s .
Unless stated otherwise, X is a Lévy process with generating triplet (γ, b 2 , ν).

The paper is organized as follows. In the next section, we will study the errors resulting from the truncation of the compensated sum of small jumps. The results of that section are based on estimates for the moments of R ǫ . We also derive an estimate for the expectation E (M t -M ǫ t ), by using Spitzer's identity. In Section 3 we study the errors resulting from Brownian approximation. The process X will be approximated by the process Xǫ . A major result of Section 3 is Theorem 2, which states an error bound for the expectation of a function of the supremum. This result is the consequence of Theorem 3.7, which relies on the Skorohod embedding theorem.

2. Truncation of the compensated sum of small jumps. In this section, we will study the errors resulting from the approximation of X by X ǫ . These errors are related to the moments of R ǫ . Define

σ 0 (ǫ) = max (σ(ǫ), ǫ) .
(2.1)

The next result will be useful for many proofs in this paper. Proposition 2.1. Let X be a Lévy process and R ǫ defined in (1.1). Then

E |R ǫ t | 4 = t |x|≤ǫ x 4 ν(dx) + 3 tσ(ǫ) 2 2 ,
and for any real q > 0

E |R ǫ t | q ≤ K q,t σ 0 (ǫ) q ,
where K q,t is a positive constant which depends only on q and t. [START_REF] Tankov | Lévy processes in finance: inverse problems and dependence modelling[END_REF]. Substituting into the general formula

Proof. Let c k (R ǫ t ) denote the kth cumulant of R ǫ t . Then c 1 (R ǫ t ) = E (R ǫ t ) = 0, and, for any k ≥ 2, c k (R ǫ t ) = t |x|≤ǫ x k ν(dx) (note that c 2 (R ǫ t ) = Var (R ǫ t ) = σ 2 (ǫ)t). See Proposition 1.2 of
µ ′ 4 = c 4 + 4c 3 c 1 + 3c 2 2 + 6c 2 c 2 1 + c 4 1 (cf. (2.
3) below), where, here and below, µ

′ k and c k denote the kth moment and kth cumulant of a distribution, respectively, gives the first part of the proposition. We now prove the second part. Let n = ⌈q/2⌉. Since 0 < q/(2n) ≤ 1,

E |R ǫ t | q ≤ E |R ǫ t | 2n q 2n
(by Jensen's inequality for concave functions). It thus suffices to prove the result for the case q = 2n, n ∈ N; in fact, for any n ∈ N, it holds

|E (R ǫ t ) n | ≤ K n,t σ 0 (ǫ) n . (2.
2)

The last inequality can be proved by induction as follows. It is trivial for n = 0, 1, 2. Suppose that (2.2) holds for all n < m. Then, by the well-known result (see e.g. Theorem 2 of [START_REF] Morris | Natural exponential families with quadratic variance functions[END_REF])

µ ′ m = m-1 n=0 m -1 n µ ′ n c m-n , m ≥ 1, (2.3)
for all m ≥ 2 we have (recall that c 1 (R ǫ t ) = 0)

|E (R ǫ t ) m | ≤ m-2 n=0 m -1 n |E (R ǫ t ) n | |c m-n (R ǫ t )| .
Hence, in view of the induction hypothesis, it suffices to show that

|c m-n (R ǫ t )| ≤ tσ 0 (ǫ) m-n . Since m -n ≥ 2, we have c m-n (R ǫ t ) = t |x|≤ǫ x m-n ν(dx)
, and hence

|c m-n (R ǫ t )| ≤ t |x|≤ǫ |x| m-n ν(dx) ≤ tǫ m-n-2 |x|≤ǫ |x| 2 ν(dx) ≤ tσ 0 (ǫ) m-n .
The proposition is thus established.

2.1.

Estimates for smooth functions. Let X be a Lévy process and f a C-Lipschitz function where C > 0. Then,

E |f (X t ) -f (X ǫ t )| ≤ CE |R ǫ t | ≤ C E |R ǫ t | 2 ≤ C √ tσ(ǫ).
Note that we do not ask that f (X t ) be integrable. If f is more regular, sharper estimates can be derived, as shown in the following proposition. Proposition 2.2. Let X be an infinite activity Lévy process.

1. If f ∈ C 1 (R) and satisfies E f ′ (X ǫ t ) < ∞, and if there exists β > 1 such that sup ǫ∈(0,1] E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) β 1 β
is finite and integrable with respect to θ on [0, 1], then

E (f (X t ) -f (X ǫ t )) = o (σ 0 (ǫ)) . 2. If f ∈ C 2 (R) and satisfies E f ′ (X ǫ t ) + E f ′′ (X ǫ t ) < ∞, and if there ex- ists β > 1 such that sup ǫ∈(0,1] E f ′′ (X ǫ t + θR ǫ t ) -f ′′ (X ǫ t ) β 1 β
is finite and integrable with respect to θ on [0, 1], then

E (f (X t ) -f (X ǫ t )) = σ(ǫ) 2 t 2 Ef ′′ (X ǫ t ) + o σ 0 (ǫ) 2 .
Note that, if f has bounded derivatives or f is the exponential function and e βXt is integrable, where β > 1, the conditions in the above proposition are satisfied. Recall that the truncation of small jumps is used when ν(R) = ∞. In typical applications, we have lim inf σ(ǫ)/ǫ > 0, so that o σ 0 (ǫ) 2 is in fact o σ(ǫ) 2 .

Proof. To prove part 1, we first write f

(X t ) -f (X ǫ t ) as f (X t ) -f (X ǫ t ) = 1 0 f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) R ǫ t dθ + f ′ (X ǫ t ) R ǫ t ( 2.4)
(by Theorem 27.4 of [START_REF] Sato | Lévy processes and Infinitely Divisible Distributions[END_REF], R ǫ t = 0 a.s.). Since R ǫ t and X ǫ t are independent, E f ′ (X ǫ t ) R ǫ t = 0. For any 1 < α < β, by Hölder's inequality,

E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) R ǫ t ≤ E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) α 1 α E |R ǫ t | α α-1 α-1 α
. By Lyapunov's inequality,

E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) α 1 α ≤ E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) β 1 β
.

Further, the assumption

sup ǫ∈(0,1] E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) β < ∞ implies that the collection f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) α ǫ∈(0,1]
is uniformly integrable; hence, since

f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) α → 0 a.s. as ǫ → 0, E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) α → 0 (pointwise for θ ∈ [0, 1]). Therefore, by dominated convergence, lim ǫ→0 1 0 E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) α 1 α dθ = 0.
Combined with Proposition 2.1, it thus follows that

1 0 E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) R ǫ t dθ = o (σ 0 (ǫ)) .
Part 1 of the proposition then follows from (2.4) (using Fubini's theorem). We now prove the second part of the proposition. Using Taylor's formula we get

E (f (X t ) -f (X ǫ t )) = E f ′ (X ǫ t ) (X t -X ǫ t ) + Xt X ǫ t f ′′ (x) (X t -x)dx = E f ′ (X ǫ t ) R ǫ t + 1 0 f ′′ (X ǫ t + θR ǫ t ) (1 -θ) (R ǫ t ) 2 dθ = E 1 0 f ′′ (X ǫ t + θR ǫ t ) (1 -θ) (R ǫ t ) 2 dθ = E 1 0 f ′′ (X ǫ t ) (1 -θ) (R ǫ t ) 2 dθ +E 1 0 f ′′ (X ǫ t + θR ǫ t ) -f ′′ (X ǫ t ) (1 -θ) (R ǫ t ) 2 dθ .
The first expectation after the last equality sign is equal to σ(ǫ) 2 t 2 Ef ′′ (X ǫ t ) while the second one can be shown to be o σ 0 (ǫ) 2 by following the proof of part 1. The proposition is proved.

Remark 2.3. Assume that X is an integrable infinite activity Lévy process and

that f ∈ C 1 (R) with f ′ being C-Lipschitz. Then |E (f (X t ) -f (X ǫ t ))| ≤ Cσ(ǫ) 2 t 2 . Indeed, E f ′ (X ǫ t ) R ǫ t = 0 (by the assumptions on X and f , E f ′ (X ǫ t ) < ∞)
, and so the result follows directly from (2.4) using

|E (f (X t ) -f (X ǫ t ))| ≤ E 1 0 f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) |R ǫ t | dθ .
We will consider now the case of the supremum process. Proposition 2.4. Let X be a Lévy process and f a K-Lipschitz function. Then

E |f (M t ) -f (M ǫ t )| ≤ 2K √ tσ(ǫ).
Proof. We have

E f sup 0≤s≤t X s -f sup 0≤s≤t X ǫ s ≤ KE sup 0≤s≤t X s -sup 0≤s≤t X ǫ s ≤ KE sup 0≤s≤t |R ǫ s | ≤ K E sup 0≤s≤t |R ǫ s | 2 .
Note that R ǫ is a càdlàg martingale. So, using Doob's inequality, we get

E f sup 0≤s≤t X s -f sup 0≤s≤t X ǫ s ≤ 2K E |R ǫ t | 2 = 2K √ tσ(ǫ).
Remark 2.5. Suppose that X is an integrable Lévy process and f a function from R + × R to R, K-Lipschitz with respect to its second variable. Then

sup τ ∈T [0,t] Ef (τ, X τ ) -sup τ ∈T [0,t] Ef (τ, X ǫ τ ) ≤ 2K √ tσ(ǫ),
where T [0,t] denotes the set of stopping times with values in [0, t]. For a proof, the reader is referred to [START_REF] Dia | Options exotiques dans les modèles exponentiels de Lévy[END_REF], pp. 67 -68.

The bound in Proposition 2.4 might not be optimal. This is what suggests the following result.

Theorem 2.6. Let X be an integrable infinite activity Lévy process. Then

0 ≤ E (M t -M ǫ t ) = o (σ(ǫ)) .
Proof. Using Spitzer's identity (see Proposition 1 in Section 3 of [START_REF] Dia | Connecting discrete and continuous lookback or hindsight options in exponential Lévy models[END_REF] for details), we have

E (M t -M ǫ t ) = t 0 EX + s s ds - t 0 E (X ǫ s ) + s ds = t 0 E X + s -(X ǫ s ) + ds s .
It holds

X + s -(X ǫ s ) + = (X ǫ s + R ǫ s ) + -(X ǫ s ) + = (X ǫ s + R ǫ s ) 1 X ǫ s +R ǫ s >0 -X ǫ s 1 X ǫ s >0 = (X ǫ s + R ǫ s ) 1 X ǫ s >0 + 1 X ǫ s +R ǫ s >0,X ǫ s ≤0 -1 X ǫ s +R ǫ s ≤0,X ǫ s >0 -X ǫ s 1 X ǫ s >0 = (X ǫ s + R ǫ s ) 1 X ǫ s +R ǫ s >0,X ǫ s ≤0 -1 X ǫ s +R ǫ s ≤0,X ǫ s >0 + R ǫ s 1 X ǫ s >0 = (|R ǫ s | -|X ǫ s |) + 1 X ǫ s +R ǫ s >0,X ǫ s ≤0 + 1 X ǫ s +R ǫ s ≤0,X ǫ s >0 + R ǫ s 1 X ǫ s >0 . Set I ǫ s = E X + s -(X ǫ s ) + . Thus, since E R ǫ s 1 X ǫ s >0 = 0 (by independence), 0 ≤ I ǫ s ≤ E (|R ǫ s | -|X ǫ s |) + .
By the left inequality,

E (M t -M ǫ t ) ≥ 0. We now prove that E (M t -M ǫ t ) = o (σ(ǫ)). Since (|R ǫ s | -|X ǫ s |) + ≤ |R ǫ s | 1 |X ǫ s |<|R ǫ s | , we get I ǫ s ≤ E |R ǫ s | 1 |X ǫ s |<|R ǫ s | .
Hence, by Cauchy-Scwarz inequality,

I ǫ s ≤ E |R ǫ s | 2 1 2 E 1 |X ǫ s |<|R ǫ s | 2 1 2 = σ(ǫ) √ sP [|X ǫ s | < |R ǫ s |] 1 2 .
Thus,

0 ≤ E (M t -M ǫ t ) ≤ σ(ǫ) t 0 P [|X ǫ s | < |R ǫ s |] 1 2 ds √ s . Since ν(R) = ∞, R ǫ s → 0 a.s. and X ǫ s → X s a.s. with X s = 0. Hence P [|X ǫ s | < |R ǫ s |] 1 2 → 0 as ǫ → 0. Therefore, by dominated convergence, lim ǫ→0 t 0 P [|X ǫ s | < |R ǫ s |] 1 2 ds √ s = 0,
and so E (M t -M ǫ t ) = o (σ(ǫ)). In financial applications, the function f in Proposition 2.4 is not always Lipschitz, as for call lookback option where the function is exponential. Hence the following proposition.

Proposition 2.7. Let X be a Lévy process and p > 1. If Ee pMt < ∞, then

E e Mt -e M ǫ t ≤ C p,t σ 0 (ǫ), where C p,t is a positive constant independent of ǫ. Lemma 2.8. Let p > 0. If Ee pMt < ∞ , then sup 0<δ≤1 Ee pM δ t < ∞.
Remark 2.9. For any p > 0, Ee pMt < ∞ if and only if x>1 e px ν(dx) < ∞.

The "only if" part follows from Theorem 25.3 of [START_REF] Sato | Lévy processes and Infinitely Divisible Distributions[END_REF], noting that e pXt ≤ e pMt . For the "if" part, decompose X as the independent sum [START_REF] Sato | Lévy processes and Infinitely Divisible Distributions[END_REF] that E e p sup 0≤s≤t Ys is finite; so is E e pZt by the former theorem, under the assumption that x>1 e px ν(dx) < ∞.

X = Y + Z + Z ′ of
Hence E e pMt < ∞.

Proof. [Proof of Lemma 2.8] For δ ∈ (0, 1], define Rδ = X δ -X 1 . The process Rδ is the compensated sum of jumps belonging to (δ, 1] in absolute value. So

Ee pM δ t ≤ Ee p sup 0≤s≤t X 1 s +p sup 0≤s≤t Rδ s ≤ Ee p sup 0≤s≤t X 1 s Ee p sup 0≤s≤t | Rδ s | .
By hypothesis and Remark 2.9, noting that Remark 2.9 holds also for

M 1 t , Ee p sup 0≤s≤t X 1 s < ∞. We need to bound Ee p sup 0≤s≤t | Rδ s | independently of δ. We have Ee p sup 0≤s≤t | Rδ s | = E +∞ n=0 p sup 0≤s≤t Rδ s n n! = 1 + pE sup 0≤s≤t Rδ s + +∞ n=2 p n n! E sup 0≤s≤t Rδ s n .
By Doob's inequality ( Rδ is a càdlàg martingale)

Ee p sup 0≤s≤t | Rδ s | ≤ 1 + p E sup 0≤s≤t Rδ s 2 + +∞ n=2 p n n! n n -1 n E Rδ t n ≤ 1 + 2p E Rδ t 2 + +∞ n=2 p n n! 2 n E Rδ t n ≤ 2p Var Rδ t + E +∞ n=0 p n n! 2 n Rδ t n ≤ 2p t δ<|x|≤1 x 2 ν(dx) + Ee 2p| Rδ t | ≤ 2p tσ(1) 2 + Ee 2p Rδ t + Ee -2p Rδ t .
It thus suffices to show that sup 0<δ≤1 Ee β Rδ t < ∞ for any β ∈ R. Indeed, we have

Ee β Rδ t = exp t δ<|x|≤1 e βx -1 -βx ν(dx)
(a moment-generating function of a compensated compound Poisson process). By Taylor's theorem, e βx -1 -βx = β 2 x 2 e βξ /2 for any |x| ≤ 1, where ξ is some number between 0 and x. This completes the proof, as it implies that

Ee β Rδ t ≤ exp β 2 t 2 e |β| |x|≤1
x 2 ν(dx) .

Proof. [Proof of Proposition 2.7] By the mean value theorem, we have

e Mt -e M ǫ t = (M t -M ǫ t ) e Mǫ t ,
where M ǫ t is between M t and M ǫ t . Let q be defined such that 1 p + 1 q = 1.

E e Mt -e M ǫ t ≤ E |M t -M ǫ t | e Mǫ t ≤ E sup 0≤s≤t |R ǫ s | e Mǫ t ≤ E sup 0≤s≤t |R ǫ s | q 1 q Ee p Mǫ t 1 p .
Hence, using Doob's inequality and then Proposition 2.1, we get

E e Mt -e M ǫ t ≤ q q -1 (E |R ǫ t | q ) 1 q Ee p Mǫ t 1 p ≤ C p,t σ 0 (ǫ) E e pMt + e pM ǫ t 1 p ,
where C p,t denotes a constant depending on p and t. We conclude the proof by Lemma 2.8.

Estimates for cumulative distribution functions.

For cumulative distribution functions, bounds are expected to be bigger. However, in some cases we can get similar results as in Lipschitz case. In the first result below, we assume local boundedness of the probability density function of the Lévy process X and its supremum process M at a fixed time t. The regularity of the probability density function of a Lévy process is studied in [START_REF] Sato | Lévy processes and Infinitely Divisible Distributions[END_REF][START_REF] Bertoin | Lévy Processes[END_REF]. For the supremum process see [START_REF] Chaumont | On the law of the supremum of Lévy processes[END_REF][START_REF] Dia | Options exotiques dans les modèles exponentiels de Lévy[END_REF].

Proposition 2.10. Let X be a Lévy process.

1. If b > 0, then sup x∈R |P [X t ≥ x] -P [X ǫ t ≥ x]| ≤ 1 √ 2πb σ(ǫ).
2. If X t has a locally bounded probability density function and x ∈ R, then for any q ∈ (0, 1),

|P [X t ≥ x] -P [X ǫ t ≥ x]| ≤ C x,t,q σ 0 (ǫ) 1-q ,
where, here and below, C x,t,q denotes a positive constant depending on x, t and q. 3. If M t has a locally bounded probability density function on (0, +∞) and x > 0, then for any q ∈ (0, 1/2),

|P [M t ≥ x] -P [M ǫ t ≥ x]| ≤ C x,t,q σ 0 (ǫ) 1-q .
Lemma 2.11. Let X and Y be two r.v.'s. We assume that X has a bounded density in a neighbourhood of x ∈ R, and there exists p > 0 such that E |X -Y | p is finite. Then there exists a constant K x > 0, such that for any δ > 0

|P [X ≥ x] -P [Y ≥ x]| ≤ K x δ + E |X -Y | p δ p .
Proof. We have

|P [X ≥ x] -P [Y ≥ x]| = |P [X ≥ x, Y < x] -P [X < x, Y ≥ x]| .
We will study the above terms on the right of the equality.

P [X ≥ x, Y < x] = P [x ≤ X < x + (X -Y )] = P [x ≤ X < x + (X -Y ) , |X -Y | ≤ δ] +P [x ≤ X < x + (X -Y ) , |X -Y | > δ] ≤ P [x ≤ X < x + δ] + P [|X -Y | > δ] .
Suppose that X has a bounded density f in the interval [x -δ 0 , x + δ 0 ], δ 0 > 0 fixed, and let

K x = max sup x-δ0≤t≤x+δ0 f (t), 1 δ 0 .
By considering the cases δ < δ 0 and δ ≥ δ 0 separately, it is readily checked that

P [x ≤ X < x + δ] ≤ K x δ,
for any δ > 0. Thus, using Markov's inequality, we get

P [X ≥ x, Y < x] ≤ K x δ + E |X -Y | p δ p .
Similarly, using

P [x -δ ≤ X < x] ≤ K x δ, it holds that P [X < x, Y ≥ x] ≤ K x δ + E |X -Y | p δ p .
Lemma 2.11 is thus established.

Proof.

[Proof of Proposition 2.10] We have

|P [X t ≥ x] -P [X ǫ t ≥ x]| = |P [X t ≥ x, X ǫ t < x] -P [X t < x, X ǫ t ≥ x]| . (2.5)
It holds that

P [X t ≥ x, X ǫ t < x] = P [x -(X t -X ǫ t ) ≤ X ǫ t < x] = P [x -R ǫ t ≤ bB t + (X ǫ t -bB t ) < x] .
Note that bB t is independent of X ǫ t -bB t and R ǫ t , and 1

√

2πtb is an upper bound of the probability density function of bB t . Then, by conditioning on the pair (R ǫ t , X ǫ t -bB t ), it can be concluded that

P [x -R ǫ t ≤ bB t + (X ǫ t -bB t ) < x] ≤ 1 √ 2πtb E |R ǫ t | . Therefore, using that E |R ǫ t | ≤ σ(ǫ) √ t, P [X t ≥ x, X ǫ t < x] ≤ 1 √ 2πb σ(ǫ).
Similarly

P [X t < x, X ǫ t ≥ x] = P [x ≤ X ǫ t < x -(X t -X ǫ t )] = P [x ≤ σB t + (X ǫ t -σB t ) < x -R ǫ t ] ≤ 1 √ 2πσ σ(ǫ).
Hence part 1 of the proposition follows from (2.5). We now prove part 2 of the proposition. Let p > 0. By Lemma 2.11 followed by Proposition 2.1, there exist positive constants K x,t and K p,t such that

|P [X t ≥ x] -P [X ǫ t ≥ x]| ≤ K x,t δ + E |X t -X ǫ t | p δ p = K x,t δ + E |R ǫ t | p δ p ≤ K x,t δ + K p,t σ 0 (ǫ) p δ p for any δ > 0. Choosing δ = σ 0 (ǫ) p p+1 yields |P [X t ≥ x] -P [X ǫ t ≥ x]| ≤ 2 max (K x,t , K p,t ) σ 0 (ǫ) p p+1 ,
and so the result follows since p/(p + 1) can be chosen arbitrarily in (0, 1). We now prove part 3 of the proposition. Let p > 1. By Lemma 2.11, there exists a constant K ′ x,t > 0 such that

|P [M t ≥ x] -P [M ǫ t ≥ x]| ≤ K ′ x,t δ + E |M t -M ǫ t | p δ p
for any δ > 0. On the other hand

E |M t -M ǫ t | p ≤ E sup 0≤s≤t |X s -X ǫ s | p = E sup 0≤s≤t |R ǫ s | p .
So by Doob's inequality, we have, using the constant K p,t from part 2,

E |M t -M ǫ t | p ≤ p p -1 p E |R ǫ t | p ≤ K p,t p p -1 p σ 0 (ǫ) p .
Part 3 of the proposition then follows by choosing δ = σ 0 (ǫ) p p+1 .

3. Approximation of the compensated sum of small jumps by a Brownian motion. In this section we will replace R ǫ by a Brownian motion. This method gives better results, subject to a convergence assumption. In fact, Asmussen and Rosinski proved ([1], Theorem 2.1) that, if X is a Lévy process, then the process σ(ǫ) -1 R ǫ converges in distribution to a standard Brownian motion, when ǫ → 0, if and only if for any k > 0 lim The conditions (3.1) and (3.2) are equivalent if ν does not have atoms in some neighbourhood of zero ([1], Proposition 2.1).

3.1.

Estimates for smooth functions. The errors resulting from Brownian approximation have not been much studied in the literature, at least theoretically. There are some results which we can find in [START_REF] Cont | Financial Modelling with Jump Processes[END_REF][START_REF] Cont | Integro-differential equations for option prices in exponential Lévy models[END_REF].

Proposition 3.1. Let X be an infinite activity Lévy process and t > 0.

1. If f ∈ C 1 (R) and satisfies E |f ′ (X ǫ t )| < ∞, and if there exists β > 1 such that sup ǫ∈(0,1] E f ′ X ǫ t + θσ(ǫ) Ŵt -f ′ (X ǫ t ) β 1 β
and

sup ǫ∈(0,1] E f ′ (X ǫ t + θR ǫ t ) -f ′ (X ǫ t ) β 1 β
are finite and integrable with re-

spect to θ on [0, 1], then E f (X t ) -f Xǫ t = o (σ 0 (ǫ)) . 2. If f ∈ C 2 (R) and satisfies E |f ′ (X ǫ t )| + E |f ′′ (X ǫ t )| < ∞,
and if there exists

β > 1 such that sup ǫ∈(0,1] E f ′′ X ǫ t + θσ(ǫ) Ŵt -f ′′ (X ǫ t ) β 1 β
and

sup ǫ∈(0,1] E |f ′′ (X ǫ t + θR ǫ t ) -f ′′ (X ǫ t )| β 1
β are finite and integrable with re-

spect to θ on [0, 1], then E f (X t ) -f Xǫ t = o σ 0 (ǫ) 2 .
Examples of functions satisfying the above conditions are noted after Proposition 2.2.

Proof. We consider only part 2. The proof for part 1 is similar. By Proposition 2.2, we have

E (f (X t ) -f (X ǫ t )) = σ(ǫ) 2 t 2 Ef ′′ (X ǫ t ) + o σ 0 (ǫ) 2 .
On the other hand, using the same reasoning as in the proof of Proposition 2.2 (we will replace R ǫ by σ(ǫ) Ŵ ) we get

E f (X ǫ t + σ(ǫ) Ŵt ) -f (X ǫ t ) = σ(ǫ) 2 t 2 Ef ′′ (X ǫ t ) + o σ 0 (ǫ) 2 . Hence E f (X t ) -f ( Xǫ t ) = o σ 0 (ǫ) 2 .
The combination of Proposition 6.2 of [START_REF] Cont | Financial Modelling with Jump Processes[END_REF] and the Spitzer's identity for Lévy processes (Proposition 1 of [START_REF] Dia | Connecting discrete and continuous lookback or hindsight options in exponential Lévy models[END_REF]) leads to the following result.

Proposition 3.2. Let X be an integrable infinite activity Lévy process. Then

EM t -E M ǫ t ≤ 33σ(ǫ)ρ(ǫ) 1 + log √ t 2ρ(ǫ)
,

where ρ(ǫ) = σ(ǫ) -3 |x|≤ǫ |x| 3 ν(dx). Remark 3.3. Under condition (3.2), we have lim ǫ→0 ρ(ǫ) = 0 and, in turn,

σ(ǫ)ρ(ǫ) 1 + log √ t 2ρ(ǫ) = o (σ(ǫ)) .
Proof. Let δ ∈ (0, t). Using Spitzer's identity for Lévy processes, we have

EM t -E M ǫ t = t 0 EX + s s ds - t 0 E( Xǫ s ) + s ds ≤ δ 0 EX + s -E( Xǫ s ) + ds s + t δ EX + s -E( Xǫ s ) + ds s .
On the one hand,

EX + s -E( Xǫ s ) + ≤ E (X ǫ s + R ǫ s ) + -(X ǫ s + σ(ǫ) Ŵs ) + ≤ E R ǫ s -σ(ǫ) Ŵs ≤ 1 + 2 π √ sσ(ǫ).
On the other hand, it follows from Proposition 6.2 of [START_REF] Cont | Financial Modelling with Jump Processes[END_REF] that

EX + s -E( Xǫ s ) + ≤ Aσ(ǫ)ρ(ǫ),
with A < 16.5 (consider the function f (x) = x + ). Therefore,

EM t -E M ǫ t ≤ 2 1 + 2 π σ(ǫ) √ δ + Aσ(ǫ)ρ(ǫ) log t δ ≤ 16.5σ(ǫ) √ δ + ρ(ǫ) log t δ .
The last expression is minimal for δ = 4ρ(ǫ) 2 , and so the desired result follows by substitution.

3.2.

Estimates by Skorokhod embedding. We will use a powerful tool to prove the results of this section. This is the Skorokhod embedding theorem. We will begin by defining some useful notations.

Definition 3.4. We define

β(ǫ) = |x|≤ǫ x 4 ν(dx) (σ 0 (ǫ)) 4 , β t p,θ (ǫ) = β(ǫ) pθ p+4θ log t β(ǫ) 2θ p+4θ + 3 p + 1 , β t 1 (ǫ) = β(ǫ) 1 6
log t β(ǫ)

1 3 + 3 + 1 , β t 2 (ǫ) = β(ǫ) 1 4
log t β(ǫ)

1 4 + 3 + 1 .
Remark 3.5. Note that under condition (3.2), we have lim ǫ→0 β(ǫ) = 0. The proof of Proposition 3.2 cannot be extended to the Lipschitz functions, because the reformulation of the Spitzer identity for Lévy processes cannot be applied in that case. We have to use another method. Define

V j,n = R ǫ jt n -R ǫ (j-1) t n , j = 1, . . . , n, so that R ǫ kt/n = k j=1 V j,n , k = 1, .
. . , n. The V j,n are i.i.d. with the same distribution as R ǫ t/n , hence E (V j,n ) = 0 and Var (V j,n ) = σ(ǫ) 2 t/n. Thus, by Skorokhod's embedding theorem (Theorem 1 of [START_REF] Skorokhod | Studies in the Theory of Random Processes[END_REF], see p. 163), there exist positive i.i.d. r.v.'s τ j , j = 1, . . . , n, and a standard Brownian motion, B, such that the (partial sums) R ǫ kt/n and the

Bτ1+•••+τ k , k = 1, . . . , n, have the same joint distributions; moreover, E (τ 1 ) = Var (V 1,n ) and Eτ 2 1 ≤ 4EV 4 1,n . (3.3)
Further, note that the σ(ǫ) Ŵkt/n and Bσ(ǫ) 2 kt/n , k = 1, . . . , n, have the same joint distributions. Set

T k = τ 1 + • • • + τ k , T ǫ k = σ(ǫ) 2 kt n .
This setting will be used in all of the subsequent results. Theorem 3.6. Let X be an integrable infinite activity Lévy process, and f a Lipschitz function. Then

Ef (M t ) -Ef M ǫ t ≤ C t σ 0 (ǫ)β t 1 (ǫ),
where C t is a positive constant independent of ǫ.

Proof. Set

I ǫ f = E f sup 0≤s≤t X s -f sup 0≤s≤t X ǫ s + σ(ǫ) Ŵs I ǫ f (n) = E f sup 0≤k≤n X kt n -f sup 0≤k≤n X ǫ kt n + σ(ǫ) Ŵ kt n .
Because f is, say, K-Lipschitz, we can show that

f sup 0≤k≤n X kt n -f sup 0≤k≤n X ǫ kt n + σ(ǫ) Ŵ kt n ≤ K sup 0≤s≤t |R ǫ s | + σ(ǫ) sup 0≤s≤t
Ŵs .

As the right hand side expression is integrable, by dominated convergence we can deduce that lim n→+∞ I ǫ f (n) = I ǫ f . It holds that

I ǫ f (n) = E f sup 0≤k≤n X ǫ kt n + BT k -f sup 0≤k≤n X ǫ kt n + BT ǫ k ≤ KE sup 0≤k≤n X ǫ kt n + BT k -sup 0≤k≤n X ǫ kt n + BT ǫ k ≤ KE sup 1≤k≤n BT k -BT ǫ k .
Part 1 of the following theorem concludes the proof. Theorem 3.7. Let X be an infinite activity Lévy process. Then:

• It holds that lim sup n→+∞ E sup 1≤k≤n BT k -BT ǫ k ≤ C t σ 0 (ǫ)β t 1 (ǫ).
• It holds that

lim sup n→+∞ E sup 1≤k≤n BT k -BT ǫ k 2 ≤ C t σ 0 (ǫ) 2 β t 2 (ǫ).
• For any reals p ≥ 1 and θ ∈ (0, 1), it holds that

lim sup n→+∞ E sup 1≤k≤n BT k -BT ǫ k p ≤ C p,θ,t σ 0 (ǫ) p β t p,θ (ǫ).
In the above, C t and C p,θ,t are constants independent of ǫ. This theorem is the main result of this section. Lemma 3.8. Let X be an infinite activity Lévy process. Then, for any δ > 0, lim sup

n→+∞ P sup 1≤k≤n |T k -T ǫ k | > δ ≤ 4tσ 0 (ǫ) 4 β(ǫ) δ 2 . Proof. As T k -T ǫ k = k i=1 (τ i -E (τ i ))
, by Kolmogorov's inequality

P sup 1≤k≤n |T k -T ǫ k | > δ ≤ Var (T n -T ǫ n ) δ 2 ≤ nVar (τ 1 ) δ 2 ≤ nEτ 2 1 δ 2 ≤ 4nE R ǫ t n 4 δ 2 ,
where the last inequality follows from (3.3). The proof then follows from Proposition 2.1.

Proof. [Proof of Theorem 3.7] For δ > 0, we have

E sup 1≤k≤n BT k -BT ǫ k = I 1 + I 2 ,
with

I 1 = E sup 1≤k≤n BT k -BT ǫ k 1 {sup 1≤k≤n |Tk-T ǫ k |≤δ} I 2 = E sup 1≤k≤n BT k -BT ǫ k 1 {sup 1≤k≤n |Tk-T ǫ k |>δ} . On {sup 1≤k≤n |T k -T ǫ k | ≤ δ}, set, for k fixed, s 1 = T ǫ k ∧ T k s 2 = T ǫ k ∨ T k . We have s 1 ≤ s 2 ≤ s 1 + δ.
Let j be such that jδ ≤ s 1 < (j + 1)δ. We have s 1 ≤ s 2 ≤ (j + 2)δ. If jδ ≤ s 1 ≤ s 2 ≤ (j + 1)δ, we have

Bs1 -Bs2 ≤ Bs1 -Bjδ + Bjδ -Bs2 ≤ 2 sup 0≤j≤ σ(ǫ) 2 t δ +1 sup jδ≤u≤(j+1)δ Bu -Bjδ . If jδ ≤ s 1 ≤ (j + 1)δ ≤ s 2 ≤ (j + 2)δ, we have Bs1 -Bs2 ≤ Bs1 -Bjδ + Bjδ -B(j+1)δ + B(j+1)δ -Bs2 ≤ 3 sup 0≤j≤ σ(ǫ) 2 t δ +2 sup jδ≤u≤(j+1)δ
Bu -Bjδ .

Hence

I 1 ≤ 3E sup 0≤j≤ σ(ǫ) 2 t δ +2 sup jδ≤u≤(j+1)δ Bu -Bjδ = 3E sup 1≤j≤ σ(ǫ) 2 t δ +3 sup (j-1)δ≤u≤jδ
Bu -B(j-1)δ .

The r.v.'s sup (j-1)δ≤u≤jδ Bu -B(j-1)δ .

In our case V 1 = sup 0≤u≤1 Bu . So V 1 ≤ sup 0≤u≤1 Bu + sup 0≤u≤1 -Bu .
For α ∈ (0, 1/8), we have

Ee αV 2 1 ≤ Ee 2α (sup 0≤u≤1 Bu) 2 +(sup 0≤u≤1 (-Bu)) 2 ≤ Ee 4α(sup 0≤u≤1 Bu) 2 1 2
Ee 4α(sup 0≤u≤1 (-Bu))

2 1 2 = Ee 4α(sup 0≤u≤1 Bu) 2 = (1 -8α) -1 2 .
The last equality follows from sup 0≤u≤1 Bu 2 ∼ χ 2 1 upon using the moment-generating function of the χ 2 1 distribution, given by (1 -2β) -1 2 for β < 1 2 . It follows straightforwardly from the above that, for α ∈ (0, 1 8 ),

I 1 ≤ C α √ δ log σ(ǫ) 2 t δ + 3 ,
where

C α = 3 1 α 1 -log(1-8α) 2 log(3)
. Consider now I 2 . We have

I2 ≤ E sup 1≤k≤n BT k -BT ǫ k 2 1 2 P sup 1≤k≤n |T k -T ǫ k | > δ 1 2 ≤ E sup 1≤k≤n BT k + sup 1≤k≤n BT ǫ k 2 1 2 P sup 1≤k≤n |T k -T ǫ k | > δ 1 2 ≤ E sup 0≤s≤t |R ǫ s | 2 1 2 + E sup 0≤s≤σ(ǫ) 2 t Bs 2 1 2 P sup 1≤k≤n |T k -T ǫ k | > δ 1 2 ≤ 2 E |R ǫ t | 2 1 2 + E Bσ(ǫ) 2 t 2 1 2 P sup 1≤k≤n |T k -T ǫ k | > δ 1 2 ≤ 4 √ tσ(ǫ) P sup 1≤k≤n |T k -T ǫ k | > δ 1 2
, where the fourth inequality is obtained using Doob's inequality. So, by Lemma 3.8, we have

lim sup n→+∞ I2 ≤ 4 √ tσ(ǫ) 4tσ0(ǫ) 4 β(ǫ) δ 2 1 2
.

Hence

lim sup n→+∞ E sup 1≤k≤n BT k -BT ǫ k ≤ Cα δ log σ(ǫ) 2 t δ + 3 + 8t δ σ(ǫ)σ0(ǫ) 2 β(ǫ).
Part 1 now follows by letting C t = max (C α , 8t) and choosing δ = σ 0 (ǫ) 2 β(ǫ) 1 3 . For the proof of parts 2 and 3 of the theorem, we refer the reader to [ [START_REF] Dia | Options exotiques dans les modèles exponentiels de Lévy[END_REF], pp. 86-89]. However, some small corrections are needed in the proof of part 3 in order to comply with the definition of β t p,θ (ǫ). Remark 3.9. Letting θ = 1/2 and p = 1, 2 in the definition of β t p,θ (ǫ), we see that part 3 of Theorem 3 partially generalizes parts 1 and 2. It may be relevant to note here that for part 3 the proof used the function g(x) = α -1 log(x) p , whereas for parts 1 and 2 it used the function g(x) = α -1 log(x) p/2 , p = 1, 2, respectively.

The following result follows directly from part 1 of Theorem 3. Proposition 3.10. Let X be an integrable infinite activity Lévy process, and f a Lipschitz function. Then

Ef (X t ) -Ef Xǫ t ≤ C t β t 1 (ǫ)σ 0 (ǫ), where C t is a positive constant. Proof. We have R ǫ t = d BTn , σ(ǫ) Ŵt = d BT ǫ n . So, if f is K-Lipschitz, we have Ef (X t ) -Ef Xǫ t = Ef X ǫ t + BTn -Ef X ǫ t + BT ǫ n ≤ KE BTn -BT ǫ n .
We conclude with Theorem 3.7.

For non-Lipschitz functions, we have the following result.

Proposition 3.11. Let X be an infinite activity Lévy process and p > 1. If Ee pMt < ∞, then for any x ∈ R and for any θ ∈ (0, 1)

E e Mt -x + -E e Mǫ t -x + ≤ C p,θ,t σ 0 (ǫ) β t p p-1 ,θ (ǫ) 1-1 p ,
where C p,θ,t is a positive constant independent of ǫ.

Proof. Define

M n t = sup 0≤k≤n X ǫ kt n + R ǫ kt n , M ǫ,n t = sup 0≤k≤n X ǫ kt n + σ(ǫ) Ŵ kt n .
We

≤ E sup 0≤k≤n BT k -BT ǫ k p p-1 1-1 p Ee p Ūǫ,n t 1 p ≤ E sup 0≤k≤n BT k -BT ǫ k p p-1 1-1 p E e pM n t + e p Mǫ,n t 1 p ≤ E sup 0≤k≤n BT k -BT ǫ k p p-1
E e Mt -x + -E e M ǫ t -x + = lim n→+∞ E e M n t -x + -E e M ǫ,n t -x + = lim sup n→+∞ E e U n t -x + -E e Û ǫ,n t -x + ≤ C p,θ,t σ0(ǫ) β t p p-1 ,θ (ǫ) 1-1 p .
3.3. Estimates for cumulative distribution functions. The bounds obtained in this section are better than those obtained by truncation, provided that condition (3.2) is satisfied.

Proposition 3.12. Let X be an infinite activity Lévy process. Below, the constants C t and C x,t,q,θ are independent of ǫ.

1. If b > 0, then

sup x∈R P [X t ≥ x] -P Xǫ t ≥ x ≤ C t σ 0 (ǫ)β t 1 (ǫ).
2. If X t has a locally bounded probability density function and x ∈ R, then for any pair of reals θ ∈ (0, 1), q ∈ (0, 1/2],

P [X t ≥ x] -P Xǫ t ≥ x ≤ C x,t,q,θ σ 0 (ǫ) 1-q β t 1 q -1,θ (ǫ) q .

3. If M t has a locally bounded probability density function on (0, +∞) and x > 0, then for any pair of reals θ ∈ (0, 1), q ∈ (0, 1/2],

P [M t ≥ x] -P M ǫ t ≥ x ≤ C x,t,q,θ σ 0 (ǫ)

P Y t ≥ x, Ŷ ǫ t < x ≤ 1 b √ 2πt E BTn -BT ǫ n .
Analogously, it also holds that

P Y t < x, Ŷ ǫ t ≥ x ≤ 1 b √ 2πt E BTn -BT ǫ n .
We get the first part of the proposition by using Theorem 3.7.

We now prove the second part of the proposition. Let p ≥ 1. By Lemma 2.11, there exists K x,t > 0 such that, for any δ > 0, .

P [Y t ≥ x] -P Ŷ ǫ t ≥ x ≤ K x,
The result then follows by substituting p = 1/q -1.

For the third part of the proposition, we use the notation of Proposition

  Lévy processes, where Y has Lévy measure [ν] {|x|≤1} , and Z and Z ′ are pure jump with Lévy measures [ν] {x>1} and [ν] {x<-1} , respectively. Here [ν] E denotes the restriction of ν to E. Note that M t ≤ sup 0≤s≤t Y s +Z t ; thus E e pMt ≤ E e p sup 0≤s≤t Ys E e pZt . It can be deduced from Theorems 25.3 and 25.18 of

  +3 are i.i.d. r.v.'s with the same distribution as sup 0≤u≤1 Bu . On the other hand, we know that if (V j ) 1≤j≤m are i.i.d. r.v.'s satisfying Ee αV 2 1 < ∞ where α is a positive real, then

	tribution as sup 0≤u≤δ Bu and, in turn,	1≤j≤ √ δ sup 0≤u≤1 Bu . Then σ(ǫ) 2 t δ are i.i.d. with the same dis-+3
			I 1 ≤ 3	√ δE	1≤j≤	sup δ σ(ǫ) 2 t	+3	V j ,
	where (V j ) 1≤j≤ σ(ǫ) 2 t δ
			E sup 1≤j≤m	V j ≤ g mEe αV 2 1	,
	where g : x ∈ [1, +∞) → 1 α log(x). Indeed, since g is concave, we have
	E sup 1≤j≤m	1≤j≤m V j = E sup	g e αV 2 j
		= Eg	sup	e αV 2 j	, because g is non-decreasing
			1≤j≤m
		1≤j≤m ≤ g E sup	e αV 2 j	, by Jensen's inequality
		≤ g	  E	j=1 m	e αV 2 j	  , because g is non-decreasing
		= g mEe αV 2 1

  know that lim n→+∞ M n t = M t a.s. and lim n→+∞

								M ǫ,n t	= M ǫ t a.s. Set
		U n t = sup 0≤k≤n	X ǫ kt n	+ BT k , Û ǫ,n t	= sup 0≤k≤n	X ǫ kt n	+ BT ǫ k	.
	So M n t = d U n t and M ǫ,n t	= d Û ǫ,n t . By the mean value theorem, we have
			e U n t -e	Ûǫ,n t	= U n t -Û ǫ,n t	e	Ūǫ,n t	,
	where Ū ǫ,n t	is between U n t and Û ǫ,n t . Set
		I ǫ n = E e U n t -x	Ûǫ,n
	Thus
		I ǫ n ≤ E e U n t -e	Ûǫ,n t
		≤ E U n t -Û ǫ,n t	e	Ūǫ,n
								Ūǫ,n t

+ -E e t -x + . t ≤ E sup 0≤k≤n BT k -BT ǫ k e

.

  So using dominated convergence, Theorem 3.7 and Lemma 2.8, we get

		1-1 p	E e pMt + e p Mǫ t	1 p .
	But
	E e pMt + e p Mǫ t	≤ E e pMt + e pσ(ǫ) sup 0≤s≤t Ŵs e pM ǫ t
		p 2 2 σ(ǫ) 2 t Ee pM ǫ t 2 σ(ǫ) 2 t E e pMt + e pM ǫ ≤ Ee pMt + 2e ≤ 2e p 2 t

  By construction, bB t is independent of Ŷ ǫ t -bB t and of BTn -BT ǫ n . Further, 2πt is an upper bound of the probability density function of bB t . By conditioning on the pair BTn -BT ǫ n , Ŷ ǫ t -bB t , it can thus be concluded that

	Proof. Recall that R ǫ t = d	BTn and σ(ǫ) Ŵt = d	BT ǫ n . Set
	Y t = X ǫ t + BTn , Ŷ ǫ t = X ǫ t + BT ǫ n .
	Thus
	P [X 1 √ b

1-q β t 1 q -1,θ (ǫ) q . t ≥ x] -P Xǫ t ≥ x = P [Y t ≥ x] -P Ŷ ǫ t ≥ x = P Y t ≥ x, Ŷ ǫ t < x -P Y t < x, Ŷ ǫ t ≥ x .

It holds that

P Y t ≥ x, Ŷ ǫ t < x = P x -Y t -Ŷ ǫ t ≤ Ŷ ǫ t < x = P x -BTn -BT ǫ n ≤ bB t + Ŷ ǫ t -bB t < x .

  Hence, given θ ∈ (0, 1), by Theorem 3.7 there exists a constant C p,θ,t > 0 such thatP [Y t ≥ x] -P Ŷ ǫ t ≥ x ≤ K x,t δ + C p,θ,t

			t δ + = K x,t δ +	t E Y t -Ŷ ǫ δ p E BTn -BT ǫ p n δ p	p	.
				σ 0 (ǫ) p β t p,θ (ǫ) δ p	.
	Choosing δ = σ 0 (ǫ)	p p+1 β t p,θ (ǫ)	1 p+1 yields
	P [Y p p+1 β t p,θ (ǫ)	1 p+1

t ≥ x] -P Ŷ ǫ t ≥ x ≤ 2 max (K x,t , C p,θ,t ) σ 0 (ǫ)

  By the assumption on M t , there exists a constant K > 0 such thatP [M t ∈ I x,δ ] < K ′x,t δ for any δ > 0. Combined with Theorem 3.7, letting n → ∞ yields for some constant C p,θ,t > 0. So as in part 2, the result follows by choosing δ = σ 0 (ǫ)

	lim n→∞	P [U n t ≥ x] -P Û ǫ,n t	≥ x ≤ K	′ x,t δ + C p,θ,t	σ 0 (ǫ) p β t p,θ (ǫ) δ p	,
	p p+1 β t p,θ (ǫ)	1 p+1 .

3.11

. Note that

P [M t ≥ x] -P M ǫ t ≥ x = lim n→∞ P [M n t ≥ x] -P M ǫ,n t ≥ x = lim n→∞ P [U n t ≥ x] -P Û ǫ,n t ≥ x .

Let p ≥ 1 and put I x,δ = [x -δ, x + δ). Using the proof of Lemma 2.11, we have

P [U n t ≥ x] -P Û ǫ,n t ≥ x ≤ P [U n t ∈ I x,δ ] + E U n t -Û ǫ,n t p δ p ≤ P [M n t ∈ I x,δ ] + E sup 1≤k≤n BT k -BT ǫ k p δ p ,

for any δ > 0.

′ x,t REFERENCES