TheAnnalsofProbability 2008,Vol.36,No.6,2235–2279 DOI:10.1214/07-AOP388 (cid:13)c InstituteofMathematicalStatistics,2008 A TREE APPROACH TO P-VARIATION AND TO INTEGRATION 9 By Jean Picard 0 0 Universit´e Blaise Pascal 2 We consider a real-valued path; it is possible to associate a tree n tothispath,andweexploretherelationsbetweenthetree,theprop- a J erties of p-variation of the path, and integration with respect to the 2 path.Inparticular,thefractaldimensionofthetreeisestimatedfrom 2 the variations of the path, and Young integrals with respect to the path,aswellasintegralsfromtheroughpathstheory,arewrittenas ] integrals on the tree. Examples include some stochastic paths such R asmartingales, L´evyprocessesandfractional Brownian motions(for P which an estimator of theHurst parameter is given). . h t a 1. Introduction. Consideracontinuouspathω:[0,1]→R.Thep-variation m of ω is defined for p≥1 by [ 2 Vp(ω):=sup |ω(ti+1)−ω(ti)|p v (ti) Xi 8 for subdivisions (t ) of [0,1]. It is well known that the finiteness of V (ω) is 2 i p 1 closely related to the possibility of constructing integrals 1ρdω for some 0 2 functions ρ.ThesimplestcaseiswhenV (ω)is finite(ω hasfinitevariation); 5. then a signed measure dω=dω+−dω−1(the Lebesgue–StieRltjes measure) is 0 defined from ω, and the integral is well defined for any bounded Borel func- 7 tion ρ; if moreover ρ has left and right limits, then the integral is also a 0 : Riemann–Stieltjes integral (it is the limit of Riemann sums). If now ω has v infinite variation (V (ω)=∞) but V (ω) is finite for a larger value of p, i 1 p X it was proved by Young [36] that a Riemann–Stieltjes integral can still be r constructed as soon as V (ρ) is finite for q such that 1/p+1/q>1; as an ap- a q plication, one can consider and solve stochastic differential equations driven by a multidimensional path with finite p-variation if p<2 (in particular a typical fractional Brownian path with Hurst parameter H >1/2). If now p Received May 2007; revised December 2007. AMS 2000 subject classifications. 60G17, 60H05, 26A42. Key words and phrases. Lebesgue–Stieltjesintegrals,roughpaths,realtrees,variations of paths, fractional Brownian motion, L´evyprocesses. This is an electronic reprint of the original article published by the Institute of Mathematical Statistics in The Annals of Probability, 2008,Vol. 36, No. 6, 2235–2279. This reprint differs from the original in pagination and typographic detail. 1 2 J. PICARD is greater than 2, Lyons’s theory of rough paths [20, 21, 22, 23] provides a richerframeworkwhichisstillsuitabletoconsiderandsolvetheseequations. On the other hand, one can associate to ω a metric space (T,δ) which is a compact real tree and which can be used to describe the excursions of ω above any level; see [6, 8] or Chapter 3 of [10]. The tree T can be endowed with its length measure λ, and our aim is to relate the properties of (T,δ,λ) to the questions of p-variation of ω and of integration with respect to ω. These questions are also considered for c`adla`g paths ω (paths which are right-continuous and have left limits), since these paths can be considered as time-changed continuous paths. As an application, we consider the case whereωisapathofastochasticprocesssuchasaL´evyprocessorafractional Brownianmotion(thecaseofastandardBrownianpathhasbeenconsidered in [30]). In Section 2, we introduce the tree T and study its basic properties. In particular, in the finite variation case, we work out the interpretation of its lengthmeasureλbymeansoftheLebesgue–Stieltjesmeasureofω,extending a result of [6]; this result is fundamental for the construction of integrals in Section 4 (see below). We also explain how the tree can be defined in the c`adla`g case. In Section 3, we see in Theorem 3.1 (Theorem 3.10 for the c`adla`g case) that the finiteness of V (ω) is related to some metric properties of T, par- p ticularly its upper box dimension dimT; more precisely, V (ω)=∞, if 1≤p<dimT, (1.1) p V (ω)<∞, if p>dimT. (cid:26) p We give applications of these results to martingales, fractional Brownian motions and L´evy processes. We prove in particular that upper box and Hausdorff dimensions of T coincide for fractional Brownian motions (with Hurst parameter H) and stable L´evy processes (with index α); we also construct an estimator of H based on T, which can be computed by means of a sequence of stopping times (Proposition 3.9). The aim of Section 4 is to construct integrals with respect to ω by means of the tree. Let us assume that ω is continuous and ω(0) = ω(1) = infω (considering the general case adds some notational complication). The con- struction of the integral is based on the following remark (Propositions 2.2 and 2.3): when ω has finite variation, the positive and negative parts dω+ and dω− of dω can be viewed as the images of the length measure λ by two maps τ 7→τր and τ 7→τտ from T to [0,1]; thus 1 (1.2) ρdω= (ρ(τր)−ρ(τտ))λ(dτ). Z0 ZT Whenω hasinfinitevariation,thisprocedurecanstillbeappliedtoconstruct dω+ and dω−; these measures are σ-finitebutnomore finite. However, (1.2) A TREE APPROACH TO P-VARIATIONANDTO INTEGRATION 3 can be viewed as a definition of ρdω provided the term in the right-hand sideisintegrable;thismeansthatthetreecanprovideamechanismbymeans R ofwhichdω+ anddω− compensateeach other.Forinstance,if1/p+1/q>1, V (ω)<∞, V (ρ)<∞ =⇒ |ρ(τր)−ρ(τտ)|λ(dτ)<∞. p q T Z Moreover, inthiscase,theintegraldefinedby (1.2)coincides withtheYoung integral (Theorems 4.1 and 4.5). Consequently, differential equations driven bymultidimensionalpathswithfinitep-variationwithp<2enterourframe- work.Actually, wemay take p>2 for oneof thecomponents (Theorem4.8); this is dueto the fact that the condition V (ρ)<∞ can bereplaced by some q weaker condition V (ρ|ω)<∞. We also prove that the tree approach can q be used to consider multidimensional fractional Brownian motions with pa- rameter H >1/3 (Theorem 4.9); in this case, the right-hand side of (1.2) should be understood as a generalized integral on T (a limit of integrals on subtrees Ta obtained by trimming T), and we recover the integrals of the rough paths theory. The Appendix is devoted to two results which are needed in the article, and which may also be of independent interest. In Appendix A.1, we prove that increments of fractional Brownian motions are asymptotically indepen- dent from the past. In Appendix A.2, we study the time discretization of integrals in the rough paths calculus, in a spirit similar to [13, 15]. Remark 1.1. A lot of work has been devoted to the links between random trees and excursions of some stochastic processes; these links are an extension of the classical Harris correspondence between random walks and random finite trees. Historically, they have first been investigated in the context of Brownian excursions in [1, 18, 26] (see also the courses [10, 32]) with the aim of studying branching processes. In order to consider more general branching mechanisms, L´evy trees, defined by means of L´evy processes X without negative jumps, have been introduced and studied in [7, 19]; they have been related to the notion of real tree in [8]. However, we will not focus here on properties of L´evy trees; a L´evy tree is indeed a tree which is associated to some continuous process related to X (the height process), whereas we will rather consider in our applications the tree which is associated directly to the L´evy process X. Remark 1.2. We work out here a nonlinear approach to integration with respect to one-dimensional paths; consequently, the integral with re- spect to ω +ω is not simply related to integrals with respect to ω and 1 2 1 ω ; moreover, integration with respect to a multidimensional path can be 2 worked out by summing integrals with respect to each component, but this depends on the choice of a frame. 4 J. PICARD Remark 1.3. In the proofs of this article, the letter C will denote con- stant numbers which may change from line to line. For quantities depend- ing on the path ω of a stochastic process, we will rather use the notation K =K(ω). 2. Paths and trees. In this section, we first define the tree associated to a continuous path, describe its length measure, and extend these objects to c`adla`g paths. 2.1. Basic definitions and properties. Consider a continuous function (ω(t);0≤t≤1). The function (2.1) δ(s,t):=ω(s)+ω(t)−2infω [s,t] is a semi-distance on [0,1], where δ(s,t)=0 ⇐⇒ ω(s)=ω(t)=infω. [s,t] The quotient metric space T=([0,1]/δ,δ) is a real tree; this means that between any two points τ and τ in T, there is a unique arc denoted by 1 2 [τ ,τ ] (T is a topological tree), and that [τ ,τ ] is isometric to the interval 1 2 1 2 [0,δ(τ ,τ )] of R; see [8]. Actually, real trees can also be characterized as 1 2 connected metric spaces satisfying the so-called four-point condition, and one can use this condition to prove that T is a real tree; see [6, 10]. We will denote by π the projection of [0,1] onto T; notice that if ω is constant on some interval [s,t], then all the points of this interval are projected on the same point of T. The continuity of π follows from the continuity of ω; in particular, T is compact. In this article we implicitly assume that ω is not constant, so that T is not reduced to a singleton. We now suppose π(0)=π(1), or equivalently (2.2) ω(0)=ω(1)= inf ω. [0,1] AnexampleisgiveninFigure1.Weexplainattheendofthesubsectionhow general paths can be reduced to this case. Under this condition, T becomes a rooted tree by considering π(0)=π(1)=O as the root of the tree, and we can say that a point τ is above τ if τ ∈[O,τ ]. 1 2 2 1 We consider on T the level function ℓ defined by (2.3) ℓ(τ):=ω(0)+δ(O,τ). Then ω=ℓ◦π. For τ in T, define τր:=infπ−1(τ), τտ:=supπ−1(τ), A TREE APPROACH TO P-VARIATIONANDTO INTEGRATION 5 so that ω(τր)=ω(τտ)= inf ω=ℓ(τ). [τր,τտ] In particular Oր=0 and Oտ=1. The set π([τր,τտ]) is exactly the set of points above τ. If now we consider the set π([τր,τտ])\{τ} of points which are strictly above τ, it is made of connected components which are subtrees, and which are called the branches above τ; each of these branches is the projection of a connected component of [τր,τտ]\π−1(τ), and corresponds to an excursion of ω above level ℓ(τ). If there is more than one branch above τ, then τ is said to be a branching point; this means that there is more than one excursion, and the times between these excursions are local minima of ω (a local minimum may be a constancy interval). On the other hand, if there is no branch above τ, then τ is said to be a leaf; this means that π−1(τ)=[τր,τտ], so this holds when τր =τտ or when [τր,τտ] is a constancy interval of ω. Local maxima of ω are projected on leaves of T, but there may be leaves which are not associated to local maxima. Points which are not leaves constitute the skeleton S(T) of the tree. We say that ω is piecewise monotone if there exists a finite subdivision (t ) of [0,1] such that ω is monotone on each [t ,t ]. We also say that T i i i+1 is finite if it has finitely many leaves. If T is not finite, then it has infinitely many branching points, or it has at least a branching point with infinitely Fig.1. Anexampleofpathω withitstreeTrepresentedbydashedlines(theverticallines represent points of the skeleton, and each branching point is represented by a horizontal line); maps τ7→τր, τ 7→τտ and s7→π(s) are also depicted. 6 J. PICARD Fig. 2. The trimmed tree Ta is represented by dashed lines, and its leaves by double arrows; the flattened path ωa is represented by dots when it differs from ω; times Ta, Sa i i and Ua, i≥1, are respectively represented on the curve by bullets, circles and triangles. i many branches above it; in both of these cases, ω has infinitely many local minima and is therefore not piecewise monotone. Conversely, if ω is not piecewise monotone, then it has infinitely many local maxima, and each of them is projected on a different leaf of T, so T is not finite. Thus (2.4) ω is piecewise monotone ⇐⇒ T is finite. We shall also need an operation called trimming, or leaf erasure, due to [25] (see also [10, 11, 17, 26]); to this end, we introduce the function (2.5) h(τ):=sup{ω(t)−ℓ(τ);τր≤t≤τտ}. This is the height of the (or of the highest) branch above τ. In particular, h(τ)=0 if and only if τ is a leaf. Now consider the trimmed tree (2.6) Ta:={τ ∈T;h(τ)≥a}. ThenTa isnonemptyifandonlyifkωk:=supω−infω≥a,andinthiscase, it is a rooted subtree of T (it contains the root O). An example is drawn in Figure 2. As a↓0, the tree Ta increases to the skeleton of T; each branch grows at unitspeed,and anew branchappears at τ if τ is a branchingpoint of T suchthatoneofthebranchesabove τ hasheightexactly a,andanother one has height at least a. This subtree has been introduced in [26] and is A TREE APPROACH TO P-VARIATIONANDTO INTEGRATION 7 related toa-minimaanda-maximaofthepath.Moreprecisely,startingwith Sa=Ta=0, define 0 0 Ta :=inf t∈[Sa,1];ω(t)− sup ω<−a , i+1 i  (cid:26) [Sia,t] (cid:27) (2.7) Sia+1:=inf t∈[Tia+1,1];ω(t)−[Tianf,t]ω>a , (cid:26) i+1 (cid:27) Na:=inf{i;Ta or Sa=inf∅}. Actually, in the case π(0) =iπ(1), TiNaa is still well defined, but not SNaa (notice in particular that if ω is a path of an adapted stochastic process, then Sa and Ta are stopping times). Then Na is the number of leaves of Ta; i i the set of leaves ∂Ta and the set of times (Ta;1≤i≤Na) are in bijection i by means of π and its inverse map τ 7→τտ. Moreover (2.8) inf ω= inf ω=ω(Sa)−a for 1≤i<Na. i [Ta,Ta ] [Ta,Sa] i i+1 i i TheapproximationofTbyTa canalsobeinterpretedasanapproximation ofthepathω;trimmingthetreeisequivalenttoflatteningsomeexcursionsof the path. More precisely, let πa(t) bethe projection of π(t) on Ta (assuming Ta6=∅), and let (2.9) ωa=ℓ◦πa for the level function ℓ defined in (2.3). Then Ta is the associated tree of ωa. The path ωa is continuous, is obtained from ω by means of the change of time ωa(t)=ω(inf{u≥t;π(u)∈Ta}), and satisfies 0≤ω−ωa≤a. Since Ta is finite, it follows from (2.4) that ωa is piecewise monotone. Actually, if Ua is a time of [Ta,Sa] at which ω is i i i minimal (for 1≤i<Na) and if Ua:=0, Ua :=1, then 0 Na (2.10) ω(Ua)=ω(Sa)−a for 1≤i<Na, i i and ωa is nondecreasing on [Ua,Ta ], (2.11) i i+1 ωa is nonincreasing on [Ta,Ua]. (cid:26) i i Consider now a general continuous map ω which does not satisfy π(0)= π(1). Then we can again associate the tree T by means of δ defined by (2.1), but some of the above properties differ. However, it is still possible to apply the above discussion to an extended path ω′ defined on a greater interval, say [−1,2], coinciding with ω on [0,1], and satisfying ω′(−1) = ω′(2) = inf ω′. Then the associated tree T′ contains T as a subtree, [−1,2] and the projection π:[0,1]→T is the restriction of π′:[−1,2]→T′ to [0,1]. 8 J. PICARD Fig. 3. A path with jumps, and its tree (dashed lines). The graph G is the curve aug- mented by the jumps (dotted lines). Are also depicted the map π from G to T, the maps τ 7→τր, τ7→τտ from T to [0,1]; in particular, A=π(0,ω(0)) and B=π(1,ω(1)). Among these paths, we will only consider the minimal extensions; they are those such that T′=T. This means that ω′(−1)=ω′(2)= inf ω, (2.12) [0,1] (ω′ is nondecreasing on [−1,0], nonincreasing on [1,2]. Let U be a time of [0,1] at which ω is minimal and consider (2.13) O:=π(U), A:=π(0), B:=π(1) (these points are drawn in Figure 3 below, in the more general case of paths with jumps). We choose O as the root of T. Then O belongs to [A,B], the points of [O,A] are those such that τր ≤0≤τտ ≤ 1, and the points of [O,B] are those such that 0≤τր≤1≤τտ; for the points of T\[A,B], one has 0<τր≤τտ<1. In particular, if we trim the tree T and if Ta6=∅, then the flattened path ωa of (2.9) is the restriction of ω′a to [0,1]. Moreover, the quantities Na, Ta i and Sa defined in (2.7) and the similar quantities for ω′ satisfy i Na=N′a, Sa=(S′)a, Ta=(T′)a for 1≤i<Na. i i i i At i=Na, the time (T′)a may be after time 1, and in this case Ta is not Na Na defined. A TREE APPROACH TO P-VARIATIONANDTO INTEGRATION 9 2.2. The length measure on the tree. The length measure on T is the unique measure λ which is supported by the skeleton (the set of leaves have zero measure) and such that the measure of an arc is equal to its length; in particular, this measure is σ-finite and atomless. The existence and uniqueness of λ is elementary for the finite subtrees Ta, and it is not difficult to deduce the result for T by letting a↓0. It can be identified to either of the two following measures. Proposition 2.1. Define ∞ ∞ λ := δ dx, λ := δ da= δ da, 1 τ 2 τ τ ZR τ∈S(TX):ℓ(τ)=x Z0 τ∈X∂Ta Z0 τ:hX(τ)=a where δ denotes the Dirac mass at τ. Then λ=λ =λ . τ 1 2 Notice that the number of terms in the sum is at most countable for any x in the definition of λ , whereas it is finite for any a>0 in the definition 1 of λ . The integrals are supported by the interval [infω,supω] for the first 2 one, and [0,supω−infω] for the second one. Proof of Proposition 2.1. The two measures are supported by the skeleton of the tree; in order to check that they are equal to λ, it is sufficient to verify that they coincide with it on arcs [O,τ] for any τ in the skeleton S(T).Themapsℓandhareinjectiveon[O,τ],so,ifλR denotestheLebesgue measure on R, λ1([O,τ])=λR(ℓ([O,τ])), λ2([O,τ])=λR(h([O,τ])). Moreover, ℓ induces a bijection between [O,τ] and [ℓ(O),ℓ(τ)], so λ ([O,τ])=ℓ(τ)−ℓ(O)=δ(O,τ)=λ([O,τ]). 1 Thus λ =λ. For the study of λ , notice that h(τ ) is the distance between 1 2 0 τ and any of the highest points above it. When τ goes from O to τ, then 0 0 h(τ ) is decreasing; more precisely, it jumps at τ , when τ is a branching 0 0 0 point so that no highest point above it is in the direction of τ; thus h has a finite number of negative jumps, and between these jumps, it is affine with slope−1.Consequently, hinducesabijection from [O,τ]ontoits image, and this image has Lebesgue measure δ(O,τ). We deduce that λ =λ. (cid:3) 2 The measure λ is closely related to the two following measures on [0,1]. Say that an excursion begins at time t above level ω(t) if for some ε>0, ω(s)>ω(t) for t<s<t+ε. Let Eր be the set of beginnings of excursions above any level; we can define similarly the set Eտ of ends of excursions. These two sets are in bijection with each other; to each beginning t of an 10 J. PICARD excursion we can associate its end inf{s>t;ω(s)=ω(t)}. If we restrict our- selves to a fixed level x, the sets of beginnings and ends of excursions above x are at most countable, and we can define (2.14) ωր:= δ dx, ωտ:= δ dx. s s Z s∈EրX;ω(s)=x Z s∈EտX;ω(s)=x Proposition2.2. Assume (2.2). Themeasures ωր and ωտ are σ-finite and are respectively the images of λ by the maps τ 7→τր and τ 7→τտ, and λ is the image of ωր and ωտ by the projection π. If (2.2) does not hold, then, with the notation (2.13), the maps τ 7→ τր and τ 7→ τտ are respectively defined on T\[O,A] and T\[O,B]; the relation between ωր and λ (or between ωտ and λ) again holds by restricting λ to T\[O,A] (or T\[O,B]). Proof. We only work out the proof under (2.2); the general case is easilydeducedbyconsideringanextensionofω satisfying(2.12).Wewantto compare the measure ωր carried by the set Eր of beginnings of excursions, with the measure λ carried by the skeleton S(T). If s is in Eր, then π(s) is in S(T) and s=π(s)ր except if s is at a local minimum, or the end of a constancy interval of ω; on the other hand, if τ is in S(T), then τ =π(τր) and τր is in Eր except if it is the beginning of a constancy interval of ω. Since there are at most countably many local minima and constancy intervals, wededucethatthereexists Eր⊂Eր andS (T)⊂S(T)suchthat 0 0 Eր \Eր and S(T)\S (T) are at most countable, and the maps τ 7→τր 0 0 and π are inverse bijections between Eր and S (T). Moreover, λ and ωր 0 0 are atomless, so they are supported respectively by S (T) and Eր. Thus 0 0 the relation between λ and ωր claimed in the proposition follows from this one-to-one property, the definition (2.14) of ωր and the property λ=λ of 1 Proposition 2.1. The case of ωտ is similar, and the σ-finiteness follows from the σ-finiteness of λ. (cid:3) We now give a condition on T with which one can decide whether ω has finite or infinite variation (this characterization is also given in [6]). Proposition 2.3. The measures λ, ωր and ωտ are finite if and only if ω has finite variation. In this case, ωր and ωտ are respectively the positive and negative parts of the Lebesgue–Stieltjes measure of ω. Moreover, 1 (2.15) |dω|=2λ(T)−δ(0,1). Z0 Proof. We first work out the proof under the condition (2.2), so that δ(0,1)=0.Supposealso that T isfinite,sothat λ is finiteand ω is piecewise