Rama Cont

David-Antoine Fournié

Functional Ito calculus and stochastic integral representation of martingales

Keywords: stochastic calculus, functional calculus, functional Ito formula, Malliavin derivative, martingale representation, semimartingale, Wiener functionals, Clark-Ocone formula

We develop a non-anticipative calculus for functionals of a continuous semimartingale, using an extension of the Ito formula to path-dependent functionals which possess certain directional derivatives. The construction is based on a pathwise derivative, introduced by B Dupire, for functionals on the space of right-continuous functions with left limits. We show that this functional derivative admits a suitable extension to the space of square-integrable martingales. This extension defines a weak derivative which is shown to be the inverse of the Ito integral and which may be viewed as a non-anticipative "lifting" of the Malliavin derivative.

These results lead to a constructive martingale representation formula for Ito processes. By contrast with the Clark-Haussmann-Ocone formula, this representation only involves nonanticipative quantities which may be computed pathwise.

Introduction

In the analysis of phenomena with stochastic dynamics, Ito's stochastic calculus [START_REF] Ito | On a stochastic integral equation[END_REF][START_REF]On stochastic differential equations[END_REF][START_REF] Dellacherie | Probabilities and potential[END_REF][START_REF] Meyer | Un cours sur les integrales stochastiques[END_REF][START_REF] Kunita | On square integrable martingales[END_REF][START_REF] Protter | Stochastic integration and differential equations[END_REF][START_REF] Revuz | Continuous martingales and Brownian motion[END_REF] has proven to be a powerful and useful tool. A central ingredient of this calculus is the Ito formula [START_REF] Ito | On a stochastic integral equation[END_REF][START_REF]On stochastic differential equations[END_REF][START_REF] Meyer | Un cours sur les integrales stochastiques[END_REF], a change of variable formula for functions ( ) of a semimartingale which allows to represent such quantities in terms of a stochastic integral. Given that in many applications such as statistics of processes, physics or mathematical finance, one is led to consider path-dependent functionals of a semimartingale and its quadratic variation process [ ] such as:

∫ 0 ( , ) [ ]( ), ( , , [ ] ), or [ ( , ( ), [ ]( ))|ℱ ] (1)
(where ( ) denotes the value at time and = ( ( ), ∈ [0, ]) the path up to time ) there has been a sustained interest in extending the framework of stochastic calculus to such path-dependent functionals.

In this context, the Malliavin calculus [START_REF]Calcul des variations stochastique et processus de sauts[END_REF][START_REF] Nualart | Malliavin calculus and its applications[END_REF][START_REF]Stochastic analysis[END_REF][START_REF] Ocone | Malliavin's calculus and stochastic integral representations of functionals of diffusion processes[END_REF][START_REF] Shigekawa | Derivatives of Wiener functionals and absolute continuity of induced measures[END_REF][START_REF] Stroock | The Malliavin calculus, a functional analytic approach[END_REF][START_REF] Watanabe | Analysis of Wiener functionals (Malliavin calculus) and its applications to heat kernels[END_REF] has proven to be a powerful tool for investigating various properties of Brownian functionals. Since the construction of Malliavin derivative does not refer to an underlying filtration ℱ , it naturally leads to representations of functionals in terms of anticipative processes [START_REF] Clark | The representation of functionals of Brownian motion by stochastic integrals[END_REF][START_REF]On the integral representation of functionals of Itô processes[END_REF][START_REF] Ocone | Malliavin's calculus and stochastic integral representations of functionals of diffusion processes[END_REF]. However, in most applications it is more natural to consider non-anticipative versions of such representations.

In a recent insightful work, B. Dupire [START_REF] Dupire | Functional Itô calculus[END_REF] has proposed a method to extend the Ito formula to a functional setting in a non-anticipative manner, using a pathwise functional derivative which quantifies the sensitivity of a functional : ([0, ], ℝ) → ℝ to a variation in the endpoint of a path ∈ ([0, ], ℝ):

∇ ( ) = lim →0 ( + 1 ) -( )
Building on this insight, we develop hereafter a non-anticipative calculus [START_REF]A functional extension of the Ito formula[END_REF] for a class of processes -including the above examples-which may be represented as

( ) = ({ ( ), 0 ≤ ≤ }, { ( ), 0 ≤ ≤ }) = ( , ) (2)
where is the local quadratic variation defined by [ ]( ) = ∫ 0 ( ) and the functional : ([0, ], ℝ ) × ([0, ], + ) → ℝ represents the dependence of on the path = { ( ), 0 ≤ ≤ } of and its quadratic variation. Our first result (Theorem 4.1) is a change of variable formula for path-dependent functionals of the form [START_REF] Bismut | A generalized formula of Itô and some other properties of stochastic flows[END_REF]. Introducing as additional variable allows us to control the dependence of with respect to the "quadratic variation" [ ] by requiring smoothness properties of with respect to the variable in the supremum norm, without resorting to -variation norms as in "rough path" theory [START_REF] Lyons | Differential equations driven by rough signals[END_REF]. This allows our result to cover a wide range of functionals, including the examples in [START_REF] Ahn | Semimartingale integral representation[END_REF].

We then extend this notion of functional derivative to processes: we show that for of the form [START_REF] Bismut | A generalized formula of Itô and some other properties of stochastic flows[END_REF] where satisfies some regularity conditions, the process ∇ = ∇ ( , ) may be defined intrinsically, independently of the choice of in [START_REF] Bismut | A generalized formula of Itô and some other properties of stochastic flows[END_REF]. The operator ∇ is shown to admit an extension to the space of square-integrable martingales, which is the inverse of the Ito integral with respect to : for ∈ ℒ 2 ( ), ∇ (∫ . ) = (Theorem 5.8). In particular, we obtain a constructive version of the martingale representation theorem (Theorem 5.9), which states that for any square-integrable ℱ -martingale ,

( ) = (0) + ∫ 0 ∇ . ℙ -. .
This formula can be seen as a non-anticipative counterpart of the Clark-Haussmann-Ocone formula [START_REF] Clark | The representation of functionals of Brownian motion by stochastic integrals[END_REF][START_REF] Haussmann | Functionals of Itô processes as stochastic integrals[END_REF][START_REF]On the integral representation of functionals of Itô processes[END_REF][START_REF] Karatzas | An extension of Clark's formula[END_REF][START_REF] Ocone | Malliavin's calculus and stochastic integral representations of functionals of diffusion processes[END_REF]. The integrand ∇ is an adapted process which may be computed pathwise, so this formula is more amenable to numerical computations than those based on Malliavin calculus.

Finally, we show that this functional derivative ∇ may be viewed as a non-anticipative "lifting" of the Malliavin derivative (Theorem 6.1): for square-integrable martingales whose terminal values is differentiable in the sense of Malliavin ( )

∈ D 1,2 , we show that ∇ ( ) = [ |ℱ ]
. These results provide a rigorous mathematical framework for developing and extending the ideas proposed by B. Dupire [START_REF] Dupire | Functional Itô calculus[END_REF] for a large class of functionals. In particular, unlike the results derived from the pathwise approach viewpoint presented in [START_REF] Cont | Change of variable formulas for non-anticipative functionals on path space[END_REF][START_REF] Dupire | Functional Itô calculus[END_REF], Theorems 5.8 and 5.9 do not require any pathwise regularity of the functionals and hold for non-anticipative square-integrable processes, including stochastic integrals and functionals which may depend on the quadratic variation of the process.

Functional representation of non-anticipative processes

Let : [0, ] × Ω → ℝ be a continuous, ℝ -valued semimartingale defined on a filtered probability space (Ω, ℱ, ℱ , ℙ) assumed to satisfy the usual hypotheses [START_REF] Dellacherie | Probabilities and potential[END_REF]. Denote by (resp. ) the associated predictable (resp. optional) sigma-algebra on [0, ]. ℱ denotes the (ℙ-

) natural filtration of . The paths of then lie in 0 ([0, ], ℝ ), which we will view as a subspace of ([0, ], ℝ ) the space of cadlag functions with values in ℝ . We denote by [ ] = ([ , ], , = 1.. ) the quadratic (co-)variation process associated to , taking values in the set + of positive × matrices. We assume that

[ ]( ) = ∫ 0 ( ) (3)
for some cadlag process with values in + . Note that need not be a semimartingale. The paths of lie in = ([0, ], + ), the space of cadlag functions with values + .

Horizontal extension and vertical perturbation of a path

Consider a path ∈ ([0, ]), ℝ ) and denote by = ( ( ), 0 ≤ ≤ ) ∈ ([0, ], ℝ ) its restriction to [0, ] for < . For a process we shall similarly denote ( ) its value at and = ( ( ), 0 ≤ ≤ ) its path on [0, ].

For ℎ ≥ 0, we define the horizontal extension ,ℎ ∈ ([0, + ℎ], ℝ ) of to [0, + ℎ] as

,ℎ ( ) = ( ) ∈ [0, ] ; ,ℎ ( ) = ( ) ∈] , + ℎ] (4)
For ℎ ∈ ℝ , we define the vertical perturbation ℎ of as the cadlag path obtained by shifting the endpoint by ℎ:

ℎ ( ) = ( ) ∈ [0, [ ℎ ( ) = ( ) + ℎ (5)
or in other words ℎ ( ) = ( ) + ℎ1 = .

Adapted processes as non-anticipative functionals

A process : [0, ] × Ω → ℝ adapted to ℱ may be represented as

( ) = ({ ( ), 0 ≤ ≤ }, { ( ), 0 ≤ ≤ }) = ( , ) (6)
where = ( ) ∈[0, ] is a family of functionals

: ([0, ], ℝ ) × → ℝ
representing the dependence of ( ) on the underlying path of and its quadratic variation. Since is non-anticipative, ( , ) only depends on the restriction of on [0, ]. This motivates the following definition: Definition 2.1 (Non-anticipative functional). A non-anticipative functional on Υ is a family of functionals = ( ) ∈[0, ] where

: ([0, ], ℝ ) × ([0, ], + ) → ℝ ( , ) → ( , )
is measurable with respect to ℬ , the canonical filtration on ([0, ], ℝ ) × ([0, ], + ).

We can also view = ( ) ∈[0, ] as a map defined on the space Υ of stopped paths:

Υ = {( , , -), ( , ) ∈ [0, ] × ([0, ], ℝ × + )} (7)
Whenever the context is clear, we will denote a generic element ( , ) ∈ Υ simply by its second component, the path stopped at . Υ can also be identified with the 'vector bundle'

Λ = ∪ ∈[0, ] ([0, ], ℝ ) × ([0, ], + ). (8)
A natural distance on the space Υ of stopped paths is given by

∞ (( , ), ( ′ , ′ )) = | -′ | + sup ∈[0, ] | , -( ) -′ ′ , -′ ( )| (9) (Υ, ∞ ) is then a metric space, a closed subspace of [0, ] × ([0, ], ℝ × + ), ∥.∥ ∞ )
for the product topology.

Introducing the process as additional variable may seem redundant at this stage: indeed ( ) is itself ℱ -measurable i.e. a functional of . However, it is not a continuous functional on (Υ, ∞ ). Introducing as a second argument in the functional will allow us to control the regularity of with respect to [ ] = ∫ 0 ( ) simply by requiring continuity of in supremum or norms with respect to the "lifted process" ( , ) (see Section 2.3). This idea is analogous in some ways to the approach of rough path theory [START_REF] Lyons | Differential equations driven by rough signals[END_REF], although here we do not resort to p-variation norms.

If is a ℬ -predictable process, then [8, Vol. I,Par. 97]

∀ ∈ [0, ], ( , ) = ( , -)
where -denotes the path defined on [0, ] by

-( ) = ( ) ∈ [0, [ -( ) = ( -)
Note that -is cadlag and should not be confused with the caglad path → ( -).

The functionals discussed in the introduction depend on the process via [ ] = ∫ . 0 ( ) . In particular, they satisfy the condition ( , ) = ( , -). Accordingly, we will assume throughout the paper that all functionals : ([0, ], ℝ ) × → ℝ considered have "predictable" dependence with respect to the second argument:

∀ ∈ [0, ], ∀( , ) ∈ ([0, ], ℝ ) × , ( , ) = ( , -) (10)

Continuity for non-anticipative functionals

We now define a notion of (left) continuity for non-anticipative functionals.

Definition 2.2 (Continuity at fixed times). A functional defined on Υ is said to be continuous at fixed times for the ∞ metric if and only if:

∀ ∈ [0, ), ∀ > 0, ∀( , ) ∈ ([0, ], ℝ ) × , ∃ > 0, ( ′ , ′ ) ∈ ([0, ], ℝ ) × , ∞ (( , ), ( ′ , ′ )) < ⇒ | ( , ) -( ′ , ′ )| < (11)
We now define a notion of joint continuity with respect to time and the underlying path:

Definition 2.3 (Continuous functionals). A non-anticipative functional = ( ) ∈[0, ) is said to be continuous at ( , ) ∈ ([0, ], ℝ ) × if ∀ > 0, ∃ > 0, ∀( ′ , ′ ) ∈ Υ, ∞ (( , ), ( ′ , ′ )) < ⇒ | ( , ) -′ ( ′ , ′ )| < (12)
We denote ℂ 0,0 ([0, )) the set of non-anticipative functionals continuous on Υ.

Definition 2.4 (Left-continuous functionals). A non-anticipative functional = ( , ∈ [0, )) is said to be left-continuous if for each ∈ [0, ), : ([0, ], ℝ ) × → ℝ in the sup norm and ∀ > 0, ∀( , ) ∈ ([0, ], ℝ ) × , ∃ > 0, ∀ℎ ∈ [0, ], ∀( ′ , ′ ) ∈ ([0, -ℎ], ℝ ) × -ℎ , ∞ (( , ), ( ′ , ′ )) < ⇒ | ( , ) --ℎ ( ′ , ′ )| < (13)
We denote ℂ 0,0 ([0, )) the set of left-continuous functionals.

We define analogously the class of right continuous functionals ℂ 0,0 ([0, )). We call a functional "boundedness preserving" if it is bounded on each bounded set of paths:

Definition 2.5 (Boundedness-preserving functionals). Define ([0, )) as the set of non-anticipative functionals such that for every compact subset of ℝ , every > 0 and 0 < :

∃ , , 0 > 0, ∀ ≤ 0 , ∀( , ) ∈ ([0, ], ) × , sup ∈[0, ] | ( )| < ⇒ | ( , )| < , , 0 (14)

Measurability properties

Composing a non-anticipative functional with the process ( , ) yields an ℱ -adapted process ( ) = ( , ). The results below link the measurability and pathwise regularity of to the regularity of the functional .

Lemma 2.6 (Pathwise regularity). If

∈ ℂ 0,0 then for any ( ,

) ∈ ([0, ], ℝ ) × , the path → ( -, -) is left-continuous. Proof. Let ∈ ℂ 0,0 and ∈ [0, ). For ℎ > 0 sufficiently small, ∞ (( -ℎ , -ℎ ), ( -, -)) = sup ∈( -ℎ, ) | ( ) -( -ℎ)| + sup ∈( -ℎ, ) | ( ) -( -ℎ)| + ℎ (15)
Since and are cadlag, this quantity converges to 0 as ℎ → 0+, so

-ℎ ( -ℎ , -ℎ ) -( -, -) ℎ→0 + → 0 so → ( -, -) is left-continuous.
Theorem 2.7. (i) If is continuous at fixed times, then the process defined by (( , ), ) = ( , ) is adapted.

(ii) If ∈ ℂ 0,0 ([0, )), then the process ( ) = ( , ) is optional.

(iii) If ∈ ℂ 0,0 ([0, )), and if either is continuous or verifies [START_REF] Elliott | A short proof of a martingale representation result[END_REF], then is a predictable process.

In particular, any ∈ ℂ 0,0 is a non-anticipative functional in the sense of Definition 2.1. We propose an easy-to-read proof of points (i) and (iii) in the case where is continuous. The (more technical) proof for the cadlag case is given in the Appendix A.

Continuous case. Assume that is continuous at fixed times and that the paths of ( , ) are almost-surely continuous. Let us prove that is ℱ -adapted: ( ) is ℱ -measurable. Introduce the partition = 2 , = 0..2 of [0, ], as well as the following piecewise-constant approximations of and :

( ) = 2 ∑ =0 ( )1 [ , +1 ) ( ) + 1 { } ( ) ( ) = 2 ∑ =0 ( )1 [ , +1 ) ( ) + 1 { } ( ) (16)
The random variable ( ) = ( , ) is a continuous function of the random variables { ( ), ( ), ≤ } hence is ℱ -measurable. The representation above shows in fact that ( ) is ℱ -measurable. and converge respectively to and almost-surely so ( ) → →∞ ( ) a.s., hence ( ) is ℱ -measurable. (i) implies point (iii) since the path of are left-continuous by Lemma 2.6.

3 Pathwise derivatives of non-anticipative functionals

Horizontal and vertical derivatives

We now define pathwise derivatives for a functional = ( ) ∈[0, ) ∈ ℂ 0,0 , following Dupire [START_REF] Dupire | Functional Itô calculus[END_REF].

Definition 3.1 (Horizontal derivative). The horizontal derivative at ( , ) ∈ ([0, ], ℝ ) × of non-anticipative functional = ( ) ∈[0, ) is defined as ( , ) = lim ℎ→0 + +ℎ ( ,ℎ , ,ℎ ) -( , ) ℎ (17)
if the corresponding limit exists. If [START_REF] Jacod | Explicit form and robustness of martingale representations[END_REF] is defined for all ( , ) ∈ Υ the map

: ([0, ], ℝ ) × → ℝ ( , ) → ( , ) (18)
defines a non-anticipative functional = ( ) ∈[0, ] , the horizontal derivative of .

Note that our definition [START_REF] Jacod | Explicit form and robustness of martingale representations[END_REF] is different from the one in [START_REF] Dupire | Functional Itô calculus[END_REF] where the case ( , ) = ( ) is considered.

Dupire [START_REF] Dupire | Functional Itô calculus[END_REF] also introduced a pathwise spatial derivative for such functionals, which we now introduce. Denote ( , = 1.. ) the canonical basis in ℝ .

Definition 3.2. A non-anticipative functional

= ( ) ∈[0, ) is said to be vertically differentiable at ( , ) ∈ ([0, ]), ℝ ) × ([0, ], + ) if ℝ → ℝ → ( , )
is differentiable at 0. Its gradient at 0

∇ ( , ) = (∂ ( , ), = 1.. ) where ∂ ( , ) = lim ℎ→0 ( ℎ , ) -( , ) ℎ (19)
is called the vertical derivative of at ( , ). If [START_REF] Kunita | On square integrable martingales[END_REF] is defined for all ( , ) ∈ Υ, the maps

∇ : ([0, ], ℝ ) × → ℝ ( , ) → ∇ ( , ) (20)
define a non-anticipative functional ∇ = (∇ ) ∈[0, ] , the vertical derivative of . is then said to be vertically differentiable on Υ.

Remark 3.3. ∂ ( , ) is simply the directional derivative of in direction (1 { } , 0). Note that this involves examining cadlag perturbations of the path , even if is continuous.

Remark 3.4. If ( , ) = ( , ( )) with ∈ 1,1 ([0, ) × ℝ ) then we retrieve the usual partial derivatives:

( , ) = ∂ ( , ( )) ∇ ( , ) = ∇ ( , ( )).

Remark 3.5. Bismut [START_REF]Calcul des variations stochastique et processus de sauts[END_REF] considered directional derivatives of functionals on ([0, ], ℝ ) in the direction of purely discontinuous (e.g. piecewise constant) functions with finite variation, which is similar to Def. 3.2. This notion, used in [START_REF]Calcul des variations stochastique et processus de sauts[END_REF] to derive an integration by parts formula for purejump processes, is natural in the context of discontinuous semimartingales. We will show that the directional derivative (19) also intervenes naturally when the underlying process is continuous, which is less obvious. Definition 3.6 (Regular functionals). Define ℂ 1, ([0, )) as the set of functionals ∈ ℂ 0,0 which are • horizontally differentiable with continuous at fixed times,

• times vertically differentiable with ∇ ∈ ℂ 0,0 ([0, )) for = 1.. .

Define ℂ 1, ([0, )) as the set of functionals ∈ ℂ 1,2 such that , ∇ , ..., ∇ ∈ ([0, )). We denote ℂ 1,∞ ([0, )) = ∩ ≥1 ℂ 1, ([0, ).
Note that this notion of regularity only involves directional derivatives with respect to local perturbations of paths, so ∇ and seems to contain less information on the behavior of than, say, the Fréchet derivative which consider perturbations in all directions in 0 ([0, ], ℝ ) or the Malliavin derivative [START_REF] Malliavin | Stochastic calculus of variation and hypoelliptic operators[END_REF][START_REF]Stochastic analysis[END_REF] which examines perturbations in the direction of all absolutely continuous functions. Nevertheless we will show in Section 4 that knowledge of , ∇ , ∇ 2 along the paths of derivatives are sufficient to reconstitute the path of ( ) = ( , ).

Example 1 (Smooth functions). In the case where reduces to a smooth function of ( ), ( , ) = ( , ( )) [START_REF] Malliavin | Stochastic calculus of variation and hypoelliptic operators[END_REF] where ∈ 1, ([0, ] × ℝ ), the pathwise derivatives reduces to the usual ones: ∈ ℂ 1, with:

( , ) = ∂ ( , ( )) ∇ ( , ) = ∂ ( , ( )) (22)
In fact to have ∈ ℂ 1, we just need to be right-differentiable in the time variable, with rightderivative ∂ ( , .) which is continuous in the space variable and , ∇ and ∇ 2 to be jointly leftcontinuous in and continuous in the space variable.

Example 2 (Cylindrical functionals). Let ∈ 0 (ℝ , ℝ), ℎ ∈ (ℝ , ℝ) with ℎ(0) = 0. Then

( ) = ℎ ( ( ) -( -)) 1 ≥ ( ( 1 -), ( 2 -)..., ( -))
is in ℂ 1, with ( ) = 0 and

∀ = 1.. , ∇ ( ) = ℎ ( ) ( ( ) -( -)) 1 ≥ ( ( 1 -), ( 2 -)..., ( -))
Example 3 (Integrals with respect to quadratic variation). A process ( ) = ∫ 0 ( ( )) [ ]( ) where ∈ 0 (ℝ ) may be represented by the functional

( , ) = ∫ 0 ( ( )) ( ) (23)
It is readily observed that ∈ ℂ 1,∞ , with:

Then ∈ ℂ 1,∞ with:

( , ) = -( ) ∇ ( , ) = 2 ( ) ∇ 2 ( , ) = 2 ∇ ( , ) = 0, ≥ 3 (26)
Example 5. = exp( -[ ]/2) may be represented as ( ) = ( )

( , ) = ( )-1 2 ∫ 0 ( ) (27)
Elementary computations show that ∈ ℂ 1,∞ with:

( , ) = - 1 2 ( ) ( , ) ∇ ( , ) = ( , ) (28)
Note that, although may be expressed as a functional of , this functional is not continuous and without introducing the second variable ∈ , it is not possible to represent Examples 3, 4 and 5 as a left-continuous functional of alone. ( , ) = ( -) defines a ℂ 0,∞ functional. All vertical derivatives are 0. However, fails to be horizontally differentiable.

Obstructions to regularity

Example 7 (Jump of at the current time).

( , ) = ( ) -( -) defines a functional which is infinitely differentiable and has regular pathwise derivatives:

( , ) = 0 ∇ ( , ) = 1 (29)
However, the functional itself fails to be ℂ 0,0 .

Example 8 (Jump of at a fixed time).

( , ) = 1 ≥ 0 ( ( 0 ) -( 0 -)) defines a functional in ℂ 0,0 which admits horizontal and vertical derivatives at any order at each point ( , ). However, ∇ ( , ) = 1 = 0 fails to be either right-or left-continuous so is not ℂ 0,1 in the sense of Definition 3.2.

Example 9 (Maximum).

( , ) = sup ≤ ( ) is ℂ 0,0 but fails to be vertically differentiable on the set

{( , ) ∈ ([0, ], ℝ ) × , ( ) = sup ≤ ( )}.
4 Functional Ito calculus

Functional Ito formula

We are now ready to prove our first main result, which is a change of variable formula for nonanticipative functionals of a semimartingale [START_REF]A functional extension of the Ito formula[END_REF][START_REF] Dupire | Functional Itô calculus[END_REF]: Theorem 4.1. For any non-anticipative functional ∈ ℂ 1,2 verifying (10) and any ∈ [0, ),

( , ) -0 ( 0 , 0 ) = ∫ 0 ( , ) + ∫ 0 ∇ ( , ). ( ) + ∫ 0 1 2 tr ( ∇ 2 ( , ) [ ]( ) ) . . (30)
In particular, for any ∈ ℂ 1,2 , ( ) = ( , ) is a semimartingale. [START_REF] Shigekawa | Derivatives of Wiener functionals and absolute continuity of induced measures[END_REF] shows that, for a regular functional ∈ ℂ 1,2 ([0, )), the process = ( , ) may be reconstructed from the second-order jet ( , ∇ , ∇ 2 ) of along the paths of .

Proof. Let us first assume that

does not exit a compact set and that ∥ ∥ ∞ ≤ for some > 0. Let us introduce a sequence of random partitions ( , = 0.. ( )) of [0, ], by adding the jump times of to the dyadic partition ( = 2 , = 0..2 ):

0 = 0 = inf{ > -1 |2 ∈ ℕ or | ( ) -( -)| > 1 } ∧ (31)
on , and and does not depend on nor on . The dominated convergence and the dominated convergence theorem for the stochastic integrals [28, Ch.IV Theorem 32] then ensure that the Lebesgue-Stieltjes integrals converge almost surely, and the stochastic integral in probability, to the terms appearing in [START_REF] Shigekawa | Derivatives of Wiener functionals and absolute continuity of induced measures[END_REF] as → ∞.

Consider now the general case where and may be unbounded. Let be an increasing sequence of compact sets with ∪ ≥0 = ℝ and denote the optional stopping times

= inf{ < | / ∈ or | | > } ∧ .
Applying the previous result to the stopped process ( ∧ , ∧ ) and noting that, by ( 10), ( , ) = ( , -) leads to:

( ∧ , ∧ ) -0 ( 0 , 0 ) = ∫ ∧ 0 ( , ) + 1 2 ∫ ∧ 0 tr ( ∇ 2 ( , ) [ ]( ) ) + ∫ ∧ 0 ∇ ( , ). + ∫ ∧ ( ∧ , ∧ )
The terms in the first line converges almost surely to the integral up to time since ∧ = almost surely for sufficiently large. For the same reason the last term converges almost surely to 0.

Remark 4.2. The above proof is probabilistic and makes use of the (classical) Ito formula [START_REF] Ito | On a stochastic integral equation[END_REF]. In the companion paper [START_REF] Cont | Change of variable formulas for non-anticipative functionals on path space[END_REF] we give a non-probabilistic proof of Theorem 4.1, using the analytical approach of Föllmer [START_REF] Föllmer | Calcul d'Itô sans probabilités[END_REF], which allows to have discontinuous (cadlag) trajectories.

( ( ) - 1 2 [ ]( ) ) = ∫ 0 ( )-1 2 [ ]( ) ( ) (37)
An immediate corollary of Theorem 4.1 is that, if is a local martingale, any ℂ 1,2 functional of which has finite variation is equal to the integral of its horizontal derivative:

Corollary 4.3. If is a local martingale and ∈ ℂ 1,2 , the process ( ) = ( , ) has finite variation if only if ∇ ( , ) = 0 [ ] × ℙ-almost everywhere.
Proof. ( ) is a continuous semimartingale by Theorem 4.1, with semimartingale decomposition given by [START_REF] Shigekawa | Derivatives of Wiener functionals and absolute continuity of induced measures[END_REF]. If has finite variation, then by formula [START_REF] Shigekawa | Derivatives of Wiener functionals and absolute continuity of induced measures[END_REF], its continuous martingale component should be zero i.e. In particular this construction applies to the case where is a standard Brownian motion, where = , so we obtain the existence of a vertical derivative process for ℂ 1,2 Brownian functionals: Definition 4.6 (Vertical derivative of non-anticipative Brownian functionals). Let be a standard d-dimensional Brownian motion. For any ∈ 1,2 ( ) with representation ( ) = ( , ), the predictable process

∇ ( ) = ∇ ( , )
is uniquely defined up to an evanescent set, independently of the choice of ∈ ℂ 1,2 .

Martingale representation formulas

Consider now the case where is a Brownian martingale:

Assumption 5.1. ( ) = (0) + ∫ 0 ( ).
( ) where is a process adapted to ℱ verifying det( ( )

) ∕ = 0 × ℙ -. . (43)
The functional Ito formula (Theorem 4.1) then leads to an explicit martingale representation formula for ℱ -martingales in 1,2 ( ). This result may be seen as a non-anticipative counterpart of the Clark-Haussmann-Ocone formula [START_REF] Clark | The representation of functionals of Brownian motion by stochastic integrals[END_REF][START_REF] Ocone | Malliavin's calculus and stochastic integral representations of functionals of diffusion processes[END_REF][START_REF]On the integral representation of functionals of Itô processes[END_REF] and generalizes other constructive martingale representation formulas previously obtained using Markovian functionals [START_REF] Davis | Functionals of diffusion processes as stochastic integrals[END_REF][START_REF] Elliott | A short proof of a martingale representation result[END_REF][START_REF] Fitzsimmons | A new approach to the martingale representation theorem[END_REF][START_REF] Jacod | Explicit form and robustness of martingale representations[END_REF][START_REF] Pardoux | Backward stochastic differential equations and quaslinear parabolic partial differential equations[END_REF], Malliavin calculus [START_REF] Bismut | A generalized formula of Itô and some other properties of stochastic flows[END_REF][START_REF] Karatzas | An extension of Clark's formula[END_REF][START_REF]On the integral representation of functionals of Itô processes[END_REF][START_REF] Ocone | Malliavin's calculus and stochastic integral representations of functionals of diffusion processes[END_REF][START_REF] Nualart | Malliavin calculus and its applications[END_REF] or other techniques [START_REF] Ahn | Semimartingale integral representation[END_REF][START_REF] Picard | Excursions, stochastic integrals and representation of wiener functionals[END_REF].

Consider an ℱ measurable random variable with | | < ∞ and consider the martingale ( ) = [ |ℱ ].

A martingale representation formula

If admits a representation ( ) = ( , ) where ∈ ℂ 1,2 , we obtain the following stochastic integral representation for in terms of its derivative ∇ with respect to :

Theorem 5.2. If ( ) = ( , ) for some functional ∈ ℂ 1,2 , then:

( ) = (0) + ∫ 0 ∇ ( , ) ( ) = (0) + ∫ 0 ∇ . (44)
Note that regularity assumptions are not on = ( ) but on the functionals ( ) = [ |ℱ ], < , which is typically more regular than itself.

Proof. Theorem 4.1 implies that for ∈ [0, ):

( ) = [ ∫ 0 ( , ) + 1 2 ∫ 0 tr[ ∇ 2 ( , ) [ ]( )] + ∫ 0 ∇ ( , ) ( ) (45)
Given the regularity assumptions on , the first term in this sum is a continuous process with finite variation while the second is a continuous local martingale. However, is a martingale and its Theorem 5.8 (Extension of ∇ to 1,2 ( )). The vertical derivative ∇ : ( ) → ℒ 2 ( ) is closable on 1,2 ( ). Its closure defines a bijective isometry ∇ :

1,2 ( ) → ℒ 2 ( )

∫ . 0 . → (52)
characterized by the following integration by parts formula: for

∈ 1,2 ( ), ∇ is the unique element of ℒ 2 ( ) such that ∀ ∈ ( ), [ ( ) ( )] = [ ∫ 0 ∇ ( )∇ ( ) [ ]( ) ] . (53)
In particular, ∇ is the adjoint of the Ito stochastic integral

: ℒ 2 ( ) → 1,2 ( ) → ∫ . 0 . ( 54
)
in the following sense:

∀ ∈ ℒ 2 ( ), ∀ ∈ 1,2 ( ), [ ( ) ∫ 0 . ] = [ ∫ 0 ∇ [ ] ] (55)
Proof. Any ∈ 1,2 ( ) may be written as ( ) = ∫ 0 ( ) ( ) with ∈ ℒ 2 ( ), which is uniquely defined [ ] × ℙ a.e. The Ito isometry formula then guarantees that (53) holds for . To show that (53) uniquely characterizes , consider ∈ ℒ 2 ( ) which also satisfies (53), then, denoting ( ) = ∫ . 0 its stochastic integral with respect to , (53) then implies that

∀ ∈ ( ), < ( ) -, > 1,2 ( ) = [( ( ) - ∫ 0 ) ( )] = 0 which implies ( ) = [ ] × ℙ a.e. since by construction ( ) is dense in 1,2 ( ). Hence, ∇ : ( ) → ℒ 2 ( ) is closable on 1,2 ( ).
This construction shows that ∇ : 1,2 ( ) → ℒ 2 ( ) is a bijective isometry which coincides with the adjoint of the Ito integral on 1,2 ( ).

Thus, the Ito integral with respect to : ℒ 2 ( ) → 1,2 ( ) admits an inverse on 1,2 ( ) which is an extension of the (pathwise) vertical derivative ∇ operator introduced in Definition 3.2, and

∀ ∈ ℒ 2 ( ), ∇ (∫ . 0 ) = (56)
holds in the sense of equality in ℒ 2 ( ).

The above results now allow us to state a general version of the martingale representation formula, valid for all square-integrable martingales: Theorem 5.9 (Martingale representation formula: general case). For any square-integrable ℱmartingale ,

( ) = (0) + ∫ 0 ∇ ℙ -. .

Relation with the Malliavin derivative

The above results hold in particular in the case where = is a Brownian motion. In this case, the vertical derivative ∇ may be related to the Malliavin derivative [START_REF]Stochastic analysis[END_REF][START_REF] Bismut | A generalized formula of Itô and some other properties of stochastic flows[END_REF][START_REF]Calcul des variations stochastique et processus de sauts[END_REF][START_REF] Stroock | The Malliavin calculus, a functional analytic approach[END_REF] as follows.

Consider the canonical Wiener space (Ω 0 = 0 ([0, ], ℝ ), ∥.∥ ∞ , ℙ) endowed with its Borelian -algebra, the filtration of the canonical process. Consider an ℱ -measurable functional Thus, the conditional expectation operator (more precisely: the predictable projection on ℱ [8, Vol. I]) can be viewed as a morphism which "lifts" relations obtained in the framework of Malliavin calculus into relations between non-anticipative quantities, where the Malliavin derivative and the Skorokhod integral are replaced, respectively, by the vertical derivative ∇ and the Ito stochastic integral.

From a computational viewpoint, unlike the Clark-Haussmann-Ocone representation which requires to simulate the anticipative process and compute conditional expectations, ∇ only involves non-anticipative quantities which can be computed path by path. It is thus more amenable to numerical computations. This topic is further explored in a forthcoming work.

(Example 4 .

 4 The martingale ( ) = ( ) 2 -[ ]( ) is represented by the functional ( , ) = ( ) 2 -

  It is instructive to observe what prevents a functional from being regular in the sense of Definition 3.6. The examples below illustrate the fundamental obstructions to regularity: Example 6 (Delayed functionals). Let > 0.

Example 10 .Example 11 . 2 ∫0

 10112 If ( , ) = ( , ( )) where ∈ 1,2 ([0, ] × ℝ ),[START_REF] Shigekawa | Derivatives of Wiener functionals and absolute continuity of induced measures[END_REF] reduces to the standard Itô formula. For the functional in Example 5) ( , ) = ( )-1 ( ) , the formula (30) yields the well-known integral representation exp

∫ 0 ∇

 0 ( , ). ( ) = 0 a.s. Computing its quadratic variation, we obtain ∫ particular that ∥∂ ( , )∥ 2 = 0 [ ] × ℙ-almost everywhere for = 1.. . Thus, ∇ ( , ) = 0 for ( , ) / ∈ ⊂ [0, ] × Ω where ∫ [ ] × ℙ = 0 for = 1.. .

D 1 , 2 → 2 (

 122 = ( ( ), ∈ [0, ]) = ( ) with [| | 2 ] < ∞. Ifis differentiable in the Malliavin sense[START_REF] Bismut | A generalized formula of Itô and some other properties of stochastic flows[END_REF][START_REF]Stochastic analysis[END_REF][START_REF] Nualart | Malliavin calculus and its applications[END_REF][START_REF] Stroock | The Malliavin calculus, a functional analytic approach[END_REF] e.g.∈ D 1,2 with Malliavin derivative , then the Clark-Haussmann-Ocone formula[START_REF] Ocone | Malliavin's calculus and stochastic integral representations of functionals of diffusion processes[END_REF][START_REF] Nualart | Malliavin calculus and its applications[END_REF] gives a stochastic integral representation of in terms of the Malliavin derivative of : the predictable projection of the Malliavin derivative. This yields a stochastic integral representation of the martingale ( ) = [ |ℱ ]:( ) = [ |ℱ ] = [ ]+ have been obtained under a variety of conditions[START_REF] Bismut | A generalized formula of Itô and some other properties of stochastic flows[END_REF][START_REF] Davis | Functionals of diffusion processes as stochastic integrals[END_REF][START_REF] Fitzsimmons | A new approach to the martingale representation theorem[END_REF][START_REF] Karatzas | An extension of Clark's formula[END_REF][START_REF] Pardoux | Backward stochastic differential equations and quaslinear parabolic partial differential equations[END_REF][START_REF] Nualart | Malliavin calculus and its applications[END_REF].Denote by• 2 ([0, ] × Ω) the set of (anticipative) processes on [0, ] with∫ 0 ∥ ( )∥ 2 < ∞. •the Malliavin derivative operator, which associates to a random variable ∈ D 1,2 (0, ) the (anticipative) process ()∈[0, ] ∈ 2 ([0, ] × Ω). Theorem 6.1 (Lifting theorem). The following diagram is commutative is the sense of × ℙ equality: .|ℱ ]) ∈[0, ] ↑( [.|ℱ ]) ∈[0, ] [0, ] × Ω)In other words, the conditional expectation operator intertwines ∇ with the Malliavin derivative:∀ ∈ 2 (Ω 0 , ℱ , ℙ), ∇ ( [ |ℱ ]) = [ |ℱ ](58)Proof. The Clark-Haussmann-Ocone formula[START_REF] Ocone | Malliavin's calculus and stochastic integral representations of functionals of diffusion processes[END_REF] gives∀ ∈ D 1,2, the predictable projection of the Malliavin derivative. On other hand theorem 5.2 gives: ∀ ∈ 2 (Ω 0 , ℱ , ℙ), = [ |ℱ ]. Hence [ |ℱ ] = ∇ [ |ℱ ], × ℙ almost everywhere.

The following arguments apply pathwise. Lemma A. [START_REF]Calcul des variations stochastique et processus de sauts[END_REF]

where we have used the fact that has predictable dependence in the second variable to have ( , ) = ( , -). The first term in [START_REF] Watanabe | Analysis of Wiener functionals (Malliavin calculus) and its applications to heat kernels[END_REF] can be written (ℎ ) -(0) where:

Since ∈ ℂ 1,2 ([0, ]), is right-differentiable and left-continuous by Lemma 2.6, so:

The second term in [START_REF] Watanabe | Analysis of Wiener functionals (Malliavin calculus) and its applications to heat kernels[END_REF] can be written ( ( +1 )-( ))-(0) where ( ) = ( -, ).

Since ∈ ℂ 1,2 , is a 2 function and

). Applying the Ito formula to between 0 and +1 -and the (ℱ + ) ≥0 continuous semimartingale ( ( + )) ≥0 , yields:

Summing over ≥ 0 and denoting ( ) the index such that ∈ [ ( ) , ( )+1 ), we have shown:

( , ) converges to ( , ) almost surely. Since all approximations of ( , ) appearing in the various integrals have a ∞ -distance from ( , ) less than → 0, the continuity at fixed times of and left-continuity ∇ , ∇ 2 imply that the integrands appearing in the above integrals converge respectively to ( , ), ∇ ( , ), ∇ 2 ( , ) as → ∞. Since the derivatives are in the integrands in the various above integrals are bounded by a constant dependant only

Vertical derivative of an adapted process

For a (ℱ -adapted) process , the the functional representation (42) is not unique, and the vertical ∇ depends on the choice of representation . However, Theorem 4.1 implies that the process ∇ ( , ) has an intrinsic character i.e. independent of the chosen representation:

Then, outside an evanescent set:

Proof. Let ( ) = ( ) + ( ) where is a continuous process with finite variation and is a continuous local martingale. There exists Ω 1 ⊂ Ω such that ℙ(Ω 1 ) = 1 and for ∈ Ω the path of → ( , ) is continuous and → ( , ) is cadlag. Theorem 4.1 implies that the local martingale part of 0 = 1 ( , ) -2 ( , ) can be written:

Considering its quadratic variation, we have, on Ω 1

By Lemma 2.6 (∇ 1 ( , ) = ∇ 1 ( -, -) since is continuous and verifies [START_REF] Elliott | A short proof of a martingale representation result[END_REF]. So on Ω 1 the integrand in (41) is left-continuous; therefore (41) implies that for < and ∈ Ω 1 ,

In the case where for all < , ( -) is almost surely positive definite, Corollary 4.4 allows to define intrinsically the pathwise derivative of a process which admits a functional representation ( ) = ( , ):

Definition 4.5 (Vertical derivative of a process). Define 1,2 ( ) the set of ℱ -adapted processes which admit a functional representation in ℂ 1,2 :

)) ∕ = 0 × ℙ almost-everywhere then for any ∈ 1,2 ( ), the predictable process:

is uniquely defined up to an evanescent set, independently of the choice of ∈ ℂ 1,2 in the representation (42). We will call ∇ the vertical derivative of with respect to .

decomposition as sum of a finite variation process and a local martingale is unique [START_REF] Revuz | Continuous martingales and Brownian motion[END_REF]. Hence the first term is 0 and: ( ) = ∫ 0 ( , ) . Since ∈ ℂ 0,0 ([0, ]) ( ) has limit ( , ) as → , so the stochastic integral also converges.

yields the familiar formula:

Extension to square-integrable functionals

Let ℒ 2 ( ) be the Hilbert space of progressively-measurable processes such that:

and ℐ 2 ( ) be the space of square-integrable stochastic integrals with respect to :

( ) is then a bijective isometry from ℒ 2 ( ) to ℐ 2 ( ).

We will now show that the operator ∇ : → ℒ 2 ( ) admits a suitable extension to ℐ 2 ( ) which verifies

i.e. ∇ is the inverse of the Ito stochastic integral with respect to .

Definition 5.3 (Space of test processes). The space of test processes ( ) is defined as

Theorem 5.2 allows to define intrinsically the vertical derivative of a process in ( ) as an element of ℒ 2 ( ). Definition 5.4. Let ∈ ( ), define the process ∇ ∈ ℒ 2 ( ) as the equivalence class of ∇ ( , ), which does not depend on the choice of the representation functional ( ) = ( , ) Proposition 5.5 (Integration by parts on ( )). Let , ∈ ( ). Then:

Proof. Let , ∈ ( ) ⊂ 1,2 ( ). Then , are martingales with (0) = (0) = 0 and

Applying Theorem 5.2 to and , we obtain

Applying the Ito isometry formula yields the result.

Using this result, we can extend the operator ∇ in a weak sense to a suitable space of the space of (square-integrable) stochastic integrals, where ∇ is characterized by (51) being satisfied against all test processes.

The following definition introduces the Hilbert space 1,2 ( ) of martingales on which ∇ acts as a weak derivative, characterized by integration-by-part formula (51). This definition may be also viewed as a non-anticipative counterpart of Wiener-Sobolev spaces in the Malliavin calculus [START_REF]Stochastic analysis[END_REF][START_REF] Shigekawa | Derivatives of Wiener functionals and absolute continuity of induced measures[END_REF]. Definition 5.6 (Martingale Sobolev space). The Martingale Sobolev space 1,2 ( ) is defined as the closure in ℐ 2 ( ) of ( ).

The Martingale Sobolev space 1,2 ( ) is in fact none other than ℐ 2 ( ), the set of squareintegrable stochastic integrals:

Proof. We first observe that the set of "cylindrical" processes of the form , ,( 1 ,.., ) ( ) = ( ( 1 ), ..., ( ))1 > where ≥ 1, 0 ≤ 1 < .. < ≤ and ∈ ∞ (ℝ , ℝ) is a total set in ℒ 2 ( ) i.e. the linear span of is dense in ℒ 2 ( ). For such an integrand , ,( 1,.., ) , the stochastic integral with respect to is given by the martingale

where the functional is defined on Υ as:

Since is bounded, is obviously square integrable so ∈ ( ). Hence ( ) ⊂ ( ). Since is a bijective isometry from ℒ 2 ( ) to ℐ 2 ( ), the density of in ℒ 2 ( ) entails the density of ( ) in ℐ 2 ( ), so 1,2 ( ) = ℐ 2 ( ).

A Proof of Theorem 2.7

In order to prove theorem 2.7 in the general case where is only required to be cadlag, we need the following three lemmas. The first lemma states a property analogous to 'uniform continuity' for cadlag functions:

Proof. If (61) does not hold, then there exists a sequence ( ,

We can extract a convergent subsequence ( ( ) ) such that ( ) → . Noting that either an infinity of terms of the sequence are less than or an infinity are more than , we can extract monotone subsequences ( , Lemma A.2. If ∈ ℝ and is an adapted cadlag process defined on a filtered probability space (Ω, ℱ, (ℱ ) ≥0 , ℙ) and is a optional time, then:

is a stopping time.

Proof. We can write that:

and, using Lemma A.1,

Lemma A.3 (Uniform approximation of cadlag functions by step functions).

Let ∈ ([0, ], ℝ ) and = ( ) ≥1, =0.. a sequence of partitions (0 = 0 < 1 < ... < = ) of [0, ] such that:

) using the notation of Lemma A.1. Then, applying Lemma A.1 to we obtain, for ≥ , sup

We can now prove Theorem 2.7 in the case where is a cadlag adapted process. Proof of Theorem 2.7: Let us first show that ( , ) is adapted. Define:

From lemma A.2, are stopping times. Define the following piecewise constant approximations of and along the partition ( , ≥ 0):

as well as their truncations of rank :

The approximations ( , ) are ℱ -measurable as they are continuous functions of the random variables: {( ( )1 ≤ , ( )1 ≤ ), ≤ } so their limit ( , ) is also ℱ -measurable. Thanks to Lemma A.3, and converge uniformly to and , hence ( , ) converges to ( , ) since : ( ([0, ], ℝ )× , ∥.∥ ∞ ) → ℝ is continuous.

To show the optionality of in point (ii), we will show that it as limit of right-continuous adapted processes. For ∈ [0, ], define ( ) to be the integer such that ∈ [ , ( +1) ). Define the process: = ( ( )) ( ( ( )) , ( ( )) ), which is piecewise-constant and has right-continuous trajectories, and is also adapted by the first part of the theorem. Since ∈ ℂ 0,0 , ( ) → ( ) almost surely, which proves that is optional. Point (iii) follows from (i) and lemma 2.6, since in both cases ( , ) = ( -, -) hence has left-continuous trajectories.


Frédéric Morlot
email: frederic.morlot@ens.fr

Franc ¸ois Baccelli
email: francois.baccelli@ens.fr

Salah Eddine Elayoubi
email: salaheddine.elayoubi@orange-ftgroup.com

An Interaction-Based Mobility Model for Dynamic Hot Spot Analysis

In this paper, we analyze phenomena related to user clumps and hot spots occuring in mobile networks at the occasion of large urban mass gatherings in large cities. Our analysis is based on observations made on mobility traces of GSM users in several large cities. Classical mobility models, such as the random waypoint, do not allow one to represent the observed dynamics of clumps in a proper manner. This motivates the introduction and the mathematical analysis of a new interaction-based mobility model, which is the main contribution of the present paper. This model is shown to allow one to describe the dynamics of clumps and in particular to predict key phenomena such as the building of hot spots and the scattering between hot spots, which play a key role in the engineering of wireless networks during such events. We show how to obtain the main parameters of this model from simple communication activity measurements and we illustrate this calibration process on real cases.

I. INTRODUCTION

Traces collected by wireless operators in urban environments during multi event mass gatherings reveal that user mobility is extremely volatile and leads to the formation of hot spots, exemplified on the snapshot of Figure 1 which was gathered during one the 2008 Paris Fête de la Musique, where unpredicted gatherings are triggered by a large number of spontaneous street concerts taking place throughout the city. Such observations have also been made during other events, like a summer festival in Poland and Euro2008 soccer matches in Spain and in Romania. A key phenomenon within this context concerns the dynamics of these hot spots, namely their formation and their disaggregation which is random both in space and time.

Accurate and yet tractable user mobility models allowing one to represent these phenomena would significantly improve the robustness and the realism of the simulators and the analytical models used by wireless communication operators. They would hence ameliorate the understanding of the impact of mass mobility on QoS within this setting. Predicting hot spots dynamics could also help in the design and the tuning of adaptive radio resource allocation schemes, where it is fundamental to have an idea of some time caracteristics of the system. This allows a better utilization of the corresponding infrastructure and eventually a better QoS and better services to end users. As existing models are not completely adapted to the phenomena we observe on traces, such as the random dynamic hot spot phenomena alluded to above, we propose a new mobility model taking into account interaction between different users and show by a mathematical analysis based on Markov chain theory that this interaction-mobility model is sufficient to generate random hot spots. For this, we will represent an urban area as a collection of potential hot spot zones. These zones represent potentially attractive points in the city during such mass gatherings.

The basic assumption in our model is that users influence each other. In Section III, we first study the "sheep model", where this mutual influence is particularly strong and where hot spots form at random in time and space, but are stable once formed (i.e. there is no disaggregation of hot spots in this model yet). We start with the 2-zone case, in which we find closed forms for the mean time for the formation of a stable hot spot and for the law of its location. We also give asymptotic estimates for these quantities, and upper bounds on the convergence speed. We then generalize the previous results to an arbitrary number of zones.

Section IV introduces the "sheep and maverick" model, which is more realistic, yet tractable, and which features all key phenomena identified on the traces and alluded to above: the formation of hot spots at random times and places, that we will refer to as filling, their disaggregation that we will refer to as scattering, and the dynamics between them.

In a last part, we leverage filling and scattering in the "sheep and maverick" model to calibrate our mobility model and show that it can be made consistent with the traces.

II. THE NEED FOR A NEW MODEL

First, let us describe more precisely the phenomenon we want to model. A first remark is the existence of hot spots, that follow some dynamics. On the snaphots of Fig. 2, the crowd moves in large numbers outside a zone: we shall call that a hot spot scattering. A new or a few new hot spots then build up at other locations: we shall call that a hot spot filling. We now survey existing mobility models and discuss how they could be adapted to cope with these phenomena.

The most popular mobility model used in communication networks is probably the Random Waypoint Model (see [START_REF] Boudec | Perfect Simulation and Stationarity of a Class of Mobility Models[END_REF]). This model is easy to simulate and is analytically tractable in many situations depending of the mobility rules of the individuals on the domain (wrap around, edge reflection...). However, it applies to a single mobile user, or to a collection of users moving independently.

Using this model, in order to take clumping into account, we would have to choose a trip selection rule which gives more mass to potentially attractive zones. As a consequence, the law of the location of a single user would clearly favour these zones. However, such a situation prevents any macroscopic time dynamics. Indeed, with a large number of independent users, all following the same law, each snapshot would be more or less the same, very close to the theoretical location law. This follows directly from Sanov's theorem (see for instance [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF], Theorem 6.2.10).

Thus, all clumps would happen at predefined locations and the sudden hot spot scattering as well as the sudden new hot spot aggregation observed in our traces would happen with extremely small probability.

More generally, any multi user model built from the superposition of many independent single user motions will exhibit the same "lack of hot spot dynamics", while a key point observed within traces is a strong dependence between users, since there is clearly a joint motion from a hotspot to another leading to reinforced clumping in the corresponding zone.

Nomadic Community Mobility Model or Reference Point Group Mobility Model (see [START_REF] Camp | A Survey of Mobility Models for Ad Hoc Network Research[END_REF]) consist in making small groups of users move in a mean given direction, while the users themselves are allowed to walk here and there around the imposed direction. These models are well adapted for a group of visitors in a museum for instance, where the trajectory is more or less the same for everyone. However, such a system does not allow us to make groups scatter.

Let us now review some ideas about modelling users' interactions. Since we need a strong dependence among users, a natural attempt could be to work with permanental processes ( [START_REF] Peres | Zeros of Gaussian Analytic Functions and Determinantal Point Processes[END_REF]) that are known to exhibit frequent clumping. However, permanental processes are nothing but particular Cox processes (see [START_REF] Peres | Zeros of Gaussian Analytic Functions and Determinantal Point Processes[END_REF], Remark 3.6.3.). This means that we would have to choose an underlying intensity measure which varies over time to cope with the dynamics of clumping zones, which is as difficult as building directly a convenient model.

Another class of mobility models that could be considered is the class of spatial birth and death processes (see [START_REF] Garcia | Spatial birth and death processes as solutions of stochastic equations[END_REF]) first studied by Preston in 1975 (see [START_REF] Preston | Spatial birth-and-death processes[END_REF]). Such a process can simulate characteristic point patterns if one chooses its stationary distribution in a proper manner. Furthermore, in contrast to the random waypoint model, it provides a real time dynamics. However, this model is known to lead to Gibbs point processes which are usually not analytically tractable.

This state of the art leads us to the conclusion that there is a need for a tractable model allowing one to exhibit the type of hot spot dynamics observed in communication traces.

III. THE SHEEP MODEL

The aim of this section is to model user clumping in some predefined zones. The basic idea is that users tend to move towards places where there are already more people, creating a self-enhanced clumping.

A. General Overview

Let us divide the city into zones, that are exchanging mobiles one with another. In each zone, a mobile waits during an exponential time with parameter before deciding whether to change its zone or not.

In a first step, let us suppose that the mobiles are totally influenced by their environment: they behave as sheep. They decide to move towards one zone or another with a probability proportional to the current repartition of the population (see Fig. 3) of the zone. In other words, if we denote by the total number of mobiles, by 1 the number of mobiles in the first zone, by 2 the number of mobiles in the second zone, etc., a mobile from the -th zone decides to move to the ′ -th zone with probability ′ / . Conversely, he decides to stay in the -th zone with probability:

= 1 - ∑ ′ ∕ = ′ .
Obviously, there are absorbing states, which correspond to the situation where all mobiles are in the same zone (these are the stable hot spots mentioned in the introduction). If we denote a state by n = ( 1 , . . . ,

), then an absorbing state is given by: e = (0, . . . , , . . . , 0)

-ℎ , 1 ≤ ≤ .
We first study the 2-zone case for the sake of progressive exposition.

B. The 2-zone Problem

In this section we take = 2. Let us denote by n( ) = ( ( ), -( )) the state of the system at time . Each mobile stays in his zone during a random exponential time with parameter , before deciding whether to move or not. All waiting times are supposed to be independent. In other words, the system features a superposition of exponential clocks ( clocks in the left zone and in the right zone). The rate of events in the left zone is , and that in the right zone ( -) . An event in the left zone leads to a transition with probability -whereas an event in the right zone eads to a transition with probability . The whole process is Markov, with transitions described in Fig. 4. Let us denote by = ( , ′ ) the infinitesimal generator. 1) Mean Absorption Time: We are interested in characterizing mobility between different zones. For instance, we would like to give an estimate of , the first time to reach an absorbing state, starting from the current state of the network n: = inf{ /n( ) = (0, ) or ( , 0)}. The average value of is given by ℎ n = [ |n(0) = n]. We know (see [START_REF] Norris | Markov Chains, Cambridge Series in Statistical and Probabilistic Mathematics[END_REF], Theorem 3.3.3. about hitting times) that the vector h is the minimum solution of the equation:

{ ℎ (0, ) = ℎ ( ,0) = 0 ∀ / ∈ {0, }, ∑ 0< < ℎ ( , -) = -1. (1)
We prove in appendix A that:

ℎ n = 1 ⎛ ⎝ ∑ 1 < ≤ 1 + ∑ 2 < ≤ 2 ⎞ ⎠ . (2)
2) Asymptotic Estimate: Typically, corresponds to the number of users in a city district, thus it is quite large. In order to speed up computations, it can be useful to use an asymptotic estimate of ℎ n . Let = 1 / , for 1 ≤ 1 ≤ -1. We want an estimate that can be used for large values of , and for all values of . This means that the quality of this estimate should only depend on . Since is large, we consider as a continuous variable taking its values in ]0, 1[. The computation in appendix A gives:

ℎ n ∼ - ( ( 1
-) log(1 -) + log( ) ) (3)
and n ≤ 2/ , where n is the absolute error of the approximate. Fig. 5 exemplifies the approximation curve. = 80 and = 1 min -1 . The circles represent ℎn, and the continuous line represents the estimate.

3) Absorption Probability: So far we have obtained a closed form for the mean absorption time, as well as an asymptotic estimate. Now we would like to determine the probability to reach state (0, ) rather than state ( , 0), starting from n = ( , -). We shall denote this probability by n . Using , we obtain the transitions for the imbedded Markov chain of the process (see Fig. 6). +(1,-1) . Using the fact that (0, ) = 1 and ( ,0) = 0, we conclude immediately that:

n = 2 / .
(4)

C. More Clumping Zones

We now consider the same problem with zones. 1) Description of the system: Now a state is a -uplet n = ( 1 , 2 , . . . ,

), with ∑ = . Hence the space of possible states is a ( -1)-dimensional variety. A transition from the -th zone to the ′ -th zone is given by:

n → n ′ = n + e ′ -e .
In the most general case, there are ( -1) possible transitions (corresponding to existing couples ( , ′ )). The transition rate corresponding to the mobility → ′ is given by:

nn ′ = ′ .
2) Absorption Time: Generalizing equation ( 2) leads to:

ℎ n = 1 ( -1) ⎛ ⎝ ∑ 1≤ ≤ ∑ < ≤ ⎞ ⎠ (5)
(for a proof, see appendix B).

Here is for example a 2-dimensional surface representing the mean absorption time for = 3 (see Fig. 7). Then, defining = / , it is immediate to generalize equation ( 3) to find 1 :

ℎ(x) ∼ -( -1) ∑ log( ) (6)
and | (x)| ≤ .

3) Absorption Probability: In the same way as in section III-B3, we can compute the probability to reach an absorbing state rather than another one, for example say e . We use recursive formulas between a state and its neighbours. For example, in the most general case, we have:

n = ∑ ∕ = ( , ′ ) ′ n+e ′ -e ∑ ∕ = ( , ′ ) ′ .
Using then the fact that ∀ ∕ = , e = 0, we obtain all the n 's recursively. In fact, it is quite easy to generalize equation ( 4) to obtain n ( ) = / = .

1 It is worth noting that this asymptotic estimate is exactly the formula of entropy. In fact, using the axiomatic definition of entropy given in [START_REF] Cover | Elements of Information Theory[END_REF], Problem 2.46 p.53, we can understand intuitively where this fact comes from. Basically, if a family of continuous symmetric functions ( 1 , . . . , ) ( ≥ 2) verifies the following "grouping" equation:

( 1 , . . . , ) = -1 ( 1 + 2 , 3 , . . . , ) +( 1 + 2 ) 2 ( 1 1 + 2 , 2 1 + 2
) ,

then we have = -∑ log( ) up to a normalization. And in our case, considering the union zones 1 and 2 as one big zone, we obtain a new system of -1 zones, obeying the same rules as before since they are additive (for instance, a sheep from one of the two first zones decides to stay in this union with probability 1 + 2 , etc...).

IV. MAVERICKS AND HOT SPOTS DYNAMICS

So far, we have modeled the phenomenon of clumping in one given zone, which is only an aspect of what can be observed in dense urban networks during exceptional events. The sheep model has a major drawback, which prevents it to fit reality: as soon as it has reached an absorbing state, it does not evolve any more. This does not account for scattering, where a hot spot suddenly disaggregates before reforming in other zones.

This section aims at modeling scattering. We introduce some users, the mavericks, who are not influenced by the others. In the model, mavericks coexist with sheep. During a transition, mavericks choose uniformly their target zone, including their current zone, independently from other mobiles (which is a simple instance of independent random waypoint motion). In this new model, states of the form e are not absorbing anymore.

We introduce maverickness as follows2 : at each transition, an individual decides to behave as a maverick with probability ( is the maverickness rate), and as a sheep with probability 1 -. The new rate of the ( → ′ ) transition is hence given by:

nn ′ = ( ⋅ 1 + (1 -) ′ ) .

A. Mean Reaching Time

We call reaching time the time to reach any extremal state, namely a state of the form e from some . On Fig. 8, we have plotted the evolution of the mean reaching time with respect to .

As grows, one can observe several phenomena:

• The mean reaching time grows exponentially with . On Fig. 9, we have plotted the maximal mean reaching time with respect to (this corresponds to the case where all zones initially contain each approximately / individuals). • On Fig. 8, as increases (in other words, as the system becomes saturated by mavericks), the surface becomes very quickly plateau-shaped (this is already the case for = 0.08). Apart from the regions close to extremal states, all reaching times are more or less the same, which means that reaching times become insensitive to initial state. Even if the system starts from a state close to an extremal point, it takes a large excursion and a long time to reach one of the extreme states. It is interesting to observe that such a small proportion of mavericks can induce such a perturbation (for further details, see section IV-B). This is not yet a proof but just an indication that there is scattering (we propose a systematic study of scattering in section IV-C).

B. Phase Transition

To characterize the phase transition observed in Fig. 8, we calculate the invariant measure of the "sheep and maverick" Markov process, and observe if there is a value of for which all configurations are equiprobable. is given by the equation = 0. Let = (1-) , we have:

(n) = ∏ =1 1 ! -1 ∏ =0 ( + ), (7)
where is a normalizing constant. This result is proved in appendix C, along with an asymptotic estimate. On Fig. 10, we plot the invariant measure with respect to for = 2 and = 50. As already indicated by Fig. 8, it appears that when grows, the influence of mavericks is more and more noticeable. For higher values of , the probability is more concentrated on uniformly-spread states.

There is a critical value where the curve's shape reverses. What does the transition look like? Is it possible to obtain a completely flat curve (or surface in the general case) ? Expression [START_REF] Leaves | Dynamic Spectrum Allocation in Composite Reconfigurable Wireless Networks[END_REF] shows that it is possible. It is sufficient to impose -1 = 0 to obtain a uniform distribution. This corresponds to the critical value: = + .

• for < , the influence of the sheep remains noticeable. This is the most interesting case, because the system still exhibits clumping. • for = , all states are equivalent3 .

• for > , the sheep loose very fast their influence. As traces reveal the existence of clumping, we shall assume until the end of the paper that < .

C. Macro-states and Hot Spot Dynamics

The system is fully characterized by four parameters, which are , , and . The three first parameters can be directly measured, but cannot. And yet, it is of major importance. In a sense, it represents the propensity of users to clump. How can we make it best fit reality ? We would like to find a typical characteristic of the system, easy to measure and strongly related to . This is what this subsection aims at.

Let us study further the case < . If we simulate such a system, we observe clumping as expected, but we also observe scattering. We would like to evaluate how often a scattering happens. However, extremal states of the form e are extremely rare, so that it would be difficult to base our analysis on them. We will rather consider "macro-states", which are the union of several states close to one of the extremal states.

For example, let us denote by the macro-state in which the -th zone contains a significant proportion of the population:

= {n : > sup }, where sup is an upper bound for a zone to be considered as dense. Conversely, we define = {n : < inf }, where inf is a lower bound. Then a scattering is simply a transition from to . More precisely, for fixed, we define the corresponding scattering time as the duration between the first instant when we reach and the first instant when we reach after that. Another option would have consisted in using the last time we leave before reaching in place. But this is not a stopping time, which would make such a choice more difficult to handle using Markov chain theory. Hence the former definition. By symmetry, we can suppose that = 1 for example, and omit subscript in the following. At the first instant when we reach , we are necessarily in = {n/ 1 = sup + 1}. From the strong Markov property, the prediction of the future of the chain is condionally independent of the past given the state of the system at this stopping time.

It is shown in appendix D that [ |n (0) = n] is given the following analytic expression:

(1 -) sup+1 ∑ = inf ∑ = ∏ ≤ < ( ) ( ( -1) + -) , (8)
with

( ) = ( -)( + ) ( ( -1) + -) .
The expression in (8) only depends on the fact that 1 = sup + 1, but not on the exact value of n itself. Hence, the strong Markov property actually implies that [ ] = [START_REF] Boudec | Perfect Simulation and Stationarity of a Class of Mobility Models[END_REF]. Let min be the value of such that [ ] is minimum. For certain values of , [ ] is strictly decreasing over [0, 1], so that min = 1, but for some other values of (like = 1000), [ ] starts increasing after min . . For each curve, the vertical solid line corresponds to the critical value , while the dotted line corresponds to min (whenever it is less than the right bound of the axis).

In the same way, we can compute the mean "filling time" of a zone, which is the dual of the scattering time, and which we propose to define as the time for the population in a given zone to grow from inf to sup . We have:

[ ] = (1 -) -inf +1 ∑ = -sup ∑ = ∏ ≤ < ( ) ( + -) , (9)
with

( ) = 1 ( -) = ( -)( ( -1) + ) ( + -) .
Note that it is easy to find some recursive formulas for the computation of [ ] and [ ], allowing to decrease its complexity down to a Big-O of .

V. CALIBRATION WITH TRACES

The aim of this section is to see whether the crowd movements observed in the traces can be described by our "sheep and maverick" mobility model.

We propose to use [ ] or [ ] for our calibration. These quantities can be measured. Let us now see that if [ ] and are known for instance, we can then deduce by solving an inverse problem. If the function [ ] = ( ) is injective, at least for < , this inverse problem can be solved without ambiguity. We know that ( ) is decreasing on ]0, min [, so that a necessary and sufficient condition is ≤ min . On Fig. 11, this is always the case, but this is not true in general; a counter-example is = 2, = 100, sup / = 0.99%. In practice, min seems to be hard to compute analytically, so that we could not find a simple sufficient condition.

Our experiences show that such counter-examples appear to be extremely rare, especially when > 2. It seems that most choices of inf and sup satisfy the injectivity of ( ) on ]0, [. However, if it turned out that it is impossible to choose inf and sup properly, we advise to complement the measure of [ ] with a measure of [ ] for instance.

In contrast, when measuring just [ ], one has to be more cautious, since the injectivity of ( ) = [ ] on ]0, [ seems less common.

Let us consider for instance the transfer that happens between Parc des Princes and Longchamp (see Fig. 2). Observing carefully our data, we conclude that there are three attracting zones:

• Longchamp itself • the Parc des Princes, northern part • the Parc des Princes, southern part so that we take = 3. On Fig. 12, one can see the numbers of users in each zone. The total number of traces remains more or less constant, so that we choose an average value of = 4830. This gives = 6.2 × 10 -4 . Choosing to calibrate first on Longchamp filling, we take sup / = 55% and inf / = 45%. After verifying that ( ) is injective on ]0, [, we find = 0.6 × 10 -4 , that is, ≪ . This was to expect, since scattering is very clear in our case.

In order to verify this value, we also measure the Parc des Princes South scattering, which yields = 0.5 × 10 -4 . Now, if our model is consistent, it has to predict other clumps or scattering over Paris. Let us consider the triangle Châtelet-Saint Michel-Bastille for instance, in the heart of Paris (see Fig. 13). These zones are attractive. Besides, we consider a fourth zone which is the complementary region inside the triangle. That one experiences scattering, whereas the three attractive zones experience filling at the same time. Theoretically, a filling of a zone from 5% to 28% for instance should last about 10800 seconds, according to the value of we found previously. Now, the filling of Bastille lasts about 11300 seconds, so does the filling of Châtelet, and the filling of Saint Michel lasts about 11000 seconds, which is very close to our prediction.

VI. CONCLUSION AND PERSPECTIVES

In this paper, we proposed a new mobility model able to represent and quantify the hot spots found on traces, along with their random time dynamics. Our aim was not to build a generic mobility model, adapted to every kind of situation, but rather to focus on multi-event mass gatherings. We have proved our model to be analytically tractable, by derivating closed forms and asymptotic estimates. Using measurements from a GSM network, we also showed how to calibrate the model to fit reality. In addition, our model was proved to be able to predict the order of magnitude of hot spots in different time-space situations.

Apart from the main application, which consists in building an efficient mobility model for network simulators, we describe here some applications, that rely on the ability to predicting clumping or scattering with a good likelihood.

A. Dynamic Spectrum Allocation and Software Defined Radio

Dynamic Spectrum Allocation (see [START_REF] Leaves | Dynamic Spectrum Allocation in Composite Reconfigurable Wireless Networks[END_REF]), consists in allocating variable bandwidth resources, according to differrent zones and different densities of population. As for Software Defined Radio (see [START_REF] Mitola | Cognitive Radio: an Integrated Agent Architecture for Software Defined Radio[END_REF]), it consists in deploying base stations that are able to switch from a system (like GSM) to another one (like UMTS), depending on the demand.

Even if they have not been implemented in real networks yet, these two domains are today quite an active field of research. It is crucial that implemented algorithms can have an idea of the typical evolution durations of the system.

For instance, if we can predict if a zone that is full will remain so for a long time, or if an empty zone will soon fill, one can decide with much more accuracy whether allocating resources or not.

More generally, some optimization algorithms are known to depend massively on the tuning of a key parameter. For instance, [START_REF] Kauffmann | Measurement-Based Self Organization of Interfering 802.11 Wireless Access Networks[END_REF] proposes an algorithm to optimize radio ressources in a 802.11 network, based on Gibbs sampler. The "temperature parameter" of the sampler has to be tuned very carefully, so that the optimizer can react quicklier than the typical time of evolution of the system itself. More concretely, in our case, supposing that we want to take users mobility into account in a 802.11 network, if we can anticipate a scattering, we are able to adapt the optimizer in a suitable manner.

Also in the case of a genetic algorithm, it can be interesting to adapt the cross-over and the mutation rates of the optimizer to react to a sudden evolution of the system. Indeed, the higher these rates, the stronger the diversity of the genetic population. In our case, a scattering is likely to modify drastically the system to optimize. Thus it is useful broaden preventatively the variety of solutions that are explored.

B. Data Caching in Dense Ad-hoc Networks

In a dense data ad-hoc network, it can be useful to add some fixed servers which keep the most frequently asked data in cache memories. Various algorithms already exist on this subject (see for instance [5][13]). The question is where and when should we cache memory ?

The idea is to select some strategic places where people usually clump together. These are our zones. Suppose that, using section V, we have previously evaluated over the study area, possibly for a different number of users and zones. Then, measuring in real-time the actual number of users and computing the corresponding scattering times, as soon as a zone exhibits clumping, one knows how long on average this will last. In other words, one knows if it is worth caching data at that place.

Conversely, if a zone is almost empty, one knows, using "filling times", if there is a risk that we will soon encounter a peak of population and have to rush to cache memory there. After multiplying such members and removing terms that only depend on or , we obtain:

(n) ∼ ′ ∏ =1 1 ( )! ( + ) ( + )-1 2 ,
where ′ is another normalizing constant. If we introduce the relative error n , using the mean value theorem, one can obtain the following bound:

n ≤ e 4 + 4 2 2 -1 ∼ /4 .

Fig. 1 .

 1 Fig. 1. Communication activity during Fête de la Musique in Paris, on June 21 st , 2008. It is 11:23 pm. One can observe important hot spots in the center (Châtelet, Bastille, Saint-Michel) as well as at the Parc des Princes (the city stadium) and Longchamp (the city park).

Fig. 2 .

 2 Fig. 2. Communication activity in Paris on June 21 st , 2008, between 07:47 pm and 11:17 pm. One can observe scattering from the Parc des Princes (south) to Longchamp (north).

Fig. 3 . 4 .

 34 Fig. 3. The sheep model. Here, = 7 and = 4. The mobile in the upperleft corner has 4 choices. The four decision probabilities are proportional to the numbers of mobiles.

Fig. 4 .

 4 Fig. 4. Diagram of the markovian transitions.

Fig. 5 .

 5 Fig. 5. Asymptotic estimate of ℎn [in min].= 80 and = 1 min -1 . The circles represent ℎn, and the continuous line represents the estimate.

Fig. 6 .

 6 Fig. 6. Imbedded Markov chain of the process.Conditioning with respect to 1 , the first transition time, and using Markov property, we get n = 1 2

Fig. 7 .

 7 Fig. 7. Mean absorption time [in min] for = 50, = 3 and = 1 min -1 . The z-axis represents the time, whereas the initial state is represented on the horizontal plane, in barycentric coordinates with respect to each of the three absorbing states.

1 Fig. 8 .Fig. 9 .

 189 Fig. 8. Mean reaching time [in min] for= 50, = 3 and = 1 min -1 . The maverickness rate grows from 0 to 0.1. Note that the scale of the -axis varies.

Fig. 10 .

 10 Fig. 10. Invariant measure for = 50, = 2 and = 1 min -1 . When exceeds 0.038, the shape of the curve reverses.

Fig. 11

 11 depicts the evolution of [ ] in function of for several values of .

Fig. 11 .

 11 Fig. 11. Mean scattering time [in min] with respect to . sup/ = 80%, inf / = 20%, = 3 and = 1 min -1 . For each curve, the vertical solid line corresponds to the critical value , while the dotted line corresponds to min (whenever it is less than the right bound of the axis).

Fig. 12 .

 12 Fig. 12. Traces collected during the Fête de la Musique between the three attracting zones.

Fig. 13 .

 13 Fig. 13. Traces collected during the Fête de la Musique in the triangle Châtelet-Saint Michel-Bastille.

  log

.

  Approximating ( * ) by a Riemann's integral, one can find:

There are several possible coexistence models. A first model would consist in choosing a fixed population of sheep and mavericks at the beginning of the simulation; the main objection against this model ist that it is quite constrained: suppose there are only 20 individuals; if we want to reach a "maverickness" rate of 0.01% for example, this is impossible.

As → ∞, this assumption can be interpreted as follows: since ∼ / , it means that, asymptotically, there are as many mavericks as zones.

APPENDIX

A. Resolution of Equation (1) ∑

0< < ℎ ( , -) = -1 can be rewritten as:

otherwise: 2ℎ n -ℎ n+(-1,1) -ℎ n+(1,-1) = ( -) .

Thus we have to invert the matrix = ( , ) with , = 2, , -1 = -1, = -1, , = 0 otherwise. One can easily check that -1 is given by / , where the elements of are:

Equation (2) follows immediately.

Let us now give an asymptotic estimate of this expression. We introduce = 1 / , = / and = 1/ . We have:

Both sums of the right handside can be interpreted as Riemann integrals on [ , 1] and [1 -, 1]. Let us work out the first one for example:

A fortiori:

We would obtain the same inequality replacing by 1 -. Defining the remainder:

we have n ≤ 2. Thus, our estimate is (-log( ) -(1 -) log(1 -))/ , and the error is uniformly bounded by 2/ . Note that even for = 1/ or = -1/ , which yields the minimum nonzero value of ℎ n , the remainder still remains a little-o of ℎ n .

B. Proof of equation (5)

We are now looking for the solution of equation (1) in dimensions. In fact, we assume that (5) is the solution, and we prove it. First remark: if n is an absorbing state, (5) is equal to 0. Then, let us introduce nn ′ = ℎ n ′ -ℎ n . One can easily check that ∀n,

• let us determine nn ′ ; if n ′ is not an absorbing state, we have:

. Now, if n ′ is an absorbing state, it means that = 1 and ′ = -1. Then equation [START_REF] Hara | Replica Allocation Methods in Ad Hoc Networks with Data Update[END_REF] gives:

so that it is easy to check that the previous expression of nn ′ is still valid.

• now, let us prove that expression (5) verifies [START_REF] Camp | A Survey of Mobility Models for Ad Hoc Network Research[END_REF]. In a first time, let us focus on the most general case, ie when none of the s is zero. We can write:

which completes the proof of the general case. At last, if a is zero, the ( → ′ ) transition is forbidden, so that the corresponding term above should not be taken into account. But fortunately, in that case we have ′ / ( -1) = 0, so that previous calculation still holds.

C. Steady-state Computation

In this section, we will explain how to find progressively expression [START_REF] Leaves | Dynamic Spectrum Allocation in Composite Reconfigurable Wireless Networks[END_REF]. First let us take = 2 and keep notations of section III-B. For more simplicity, let us also introduce successively:

= 2(1 -) ,

Then balance equations give us, if / ∈ {0, }:

-

(

+ +1, ( + 1) = , ( ).

Multiplying by (1-) yields:

( -1) ( -1) + ( + 1) ( + 1) = ( ( ) + ( )) ( ). So that if we introduce:

we obtain: ∀ / ∈ {0, }, ( ) = ( + 1). Hence ( ) = (1) = 0. Finally:

In order to generalize this formula, we would like to rewrite it in a symmetric manner w.r.t. 1 and 2 . In fact, we have:

. This is equation ( 7) in case = 2. Now we can reasonably suppose that [START_REF] Leaves | Dynamic Spectrum Allocation in Composite Reconfigurable Wireless Networks[END_REF] still holds in the general case. In fact, this is quite immediate. Indeed, previous calculation assures us that in case = 2, global balance equations are satisfied. Now, thanks to the product form of (7), we know by the same calculation that in the general case, the partial balance equations along one transition are satisfied. In other words, ∀( , ′ ), if we denote n + e ′e by n ′ and ne ′ + e by n ′′ , we have n ′ ,n (n

This achieves the proof. Note that we can also find an asymptotic approximate of this expression. We have:

D. Proof of equation (8)

As previously, let us begin with the case = 2. We are in state ( , -) and we are looking for the hitting time ℎ of {n/ 1 < inf }.

We want to obtain an analytical formula of ℎ (let us say for inf ≤ ≤ , since otherwise ℎ = 0). If we introduce = ℎ -ℎ -1 , we have the following recursion ( inf + 1 ≤ ≤ -1):

.

Then the idea is to introduce:

We obtain the following value of -+1 :

so that, for inf + 1 ≤ ≤ , is equal to:

Since , ℎ + , -1 ℎ -1 = -1, we also have: = -1/ , = 2/ = . Finally:

and:

To determine the ℎ s, we still miss an equation. This is the last one before reaching {n/ 1 < inf }:

Together with ℎ inf +1 -ℎ inf = inf +1 , this leads successively to:

and, more generally, to:

In particular, for = sup + 1, we obtain the claimed formula. Now suppose we are in the general case. It is perfectly correct to consider the union of the -1 last zones as one big zone. A sheep will stay in this "macro-zone" with probability 2 +...+ , and a maverick will stay with probability -1 . This last probability is the only adaptation we have to make in the previous calculation. Introducing ′ = ( -1) , we obtain the following new recursion:

The rest of the calculation is exactly the same. In particular, for a fixed , the result is the same for each n such that 1 = .