J Vovelle

Approximation by PDEs MA2 2020-21

In this course, we will see how to understand and describe the large scale limit of various discrete evolution systems (random and deterministic) with the help of partial differential equations. This will be the occasion to use, and discover, some standard tools from the theory of PDEs, of numerical analysis, and of statistical physics.

Introduction

Discrete conservation laws

Suppose that we are given a family T of open polyhedral sets forming a partition of the space R d : for all distinct K, L ∈ T , we assume that K ∩ L = ∅ and that K ∩ L is contained in an hyperplane of R d . The partition is understood up to a negligible set: the Lebesgue measure of R d \ K∈T K is zero. The picture 1 below gives the example of a triangulation of the plane. We consider the following evolution of an extensive quantity u: let 0 = t 0 < t 1 < • • • < t n < • • • be some discrete times, let U n K denote the amount of the quantity u in the cell K at time t n . We assume that U n+1 K is given by the formula

U n+1 K = U n K + ∆t n L∈N (K)
|K|L|Q n L→K .

(1.1)

The notations used in (1.1) are the following ones: ∆t n is the length t n+1 -t n of the time interval, N (K) is the set of neighbors of K: L ∈ T is a neighbor of K if K|L := K ∩ L is non-empty and of finite (N -1)-dimensional Hausdorff measure |K|L| (in particular, K is not a neighbor of K). The quantity ∆t n |K|L|Q n L→K represents a certain flux of the quantity u that has passed through the interface K|L from the cell L to the cell K between the times t n and t n+1 . We have put in factor the term ∆t n |K|L| because we prefer to work with densities, rather than with scale-dependent quantities (the typical scales here depend on the size of the cells and of ∆t n and will tend to zero at some point later on). For the same reason, it is more appropriate to introduce |K|, the Lebesgue measure of the cell K, and to work with the scaled quantity u n K = U n K /|K|, which satisfies the equation

u n+1 K = u n K + ∆t n |K| L∈N (K)
|K|L|Q n L→K .

(1.2)

Assume that the densities of flux Q n L→K satisfy the following condition:

Q n L→K = -Q n K→L , (1.3)
for all n ∈ N, for all K, L ∈ T being neighbors. The condition (1.3) ensures that the (algebraic) quantity of u that was given by the cell K to the cell L is the quantity of u received by the cell L from the cell K. Under (1.3), the evolution given by (1.2) is conservative: we will show in particular that, when it makes sense, the quantity K∈T |K|u n K is constant with respect to n. Our objective will be to explain what is the limit of (u n K ) when ∆t n and |K| tends to 0. We need to be more specific on our framework to achieve this goal. Let us simply say for the moment that what we will obtain in the end are some conservation laws ∂ t u + div x (Q) = 0, (1.4) where Q(x) is a function of x, u(x) and ∇u(x). The derivation of (1.4) is related to the analysis of the Finite Volume method, which is used to compute the solution of conservation laws such as (1.4) with the help of the discrete formulation (1.2).

The symmetric simple exclusion process

Let 0 < N < L be some integers. Consider N particles located at one of the site 1, . . . , L -1 that evolve according to the following process: there is always one particle at site 0 and, for each site x ∈ {1, . . . , L -1}, we draw a random time T x that follows an exponential law of parameter λ > 0, so that the family {T y } is independent. Consider the point x * at which x → T x is minimal and let the particle at x * jump from its original site x to a new site y with probability p(x * , y), the jump occurring under the restriction that the arrival site y is vacant. Then start over. This process is called an exclusion process for the reason that jumps to occupied sites are excluded.

It is termed simple to make the distinction with some more complicated situations, where the probability of a jump from x to y may depend not only on x and y, but on the whole interval [x, y] and on the disposition of particles in this interval. We also call the process symmetric when p(x, x + l) = p(x, x -l), whenever the quantities are well defined. Here we will consider the case p(x, y) = 0 if |x -y| = 1, so that only jumps to left or right immediate neighboring site are possible, and equi-probable. At the boundary, we assume p(0, 1) = 0, p(L -1, L -2) = 1. We can put in correspondence this evolution of particles with the evolution of a random interface described as follows: we set H(0) = 0 and, for x ∈ {1, . . . , L}, define H as the discrete primitive function

H(x) =

x-1 y=0 (2η(y) -1), (1.5) where η(y) ∈ {0, 1} is the number of particle at y. Then we interpolate linearly between those points. Conversely, we deduce η(x) from H by the "differentiation" formula η(x) = [1 + H(x + 1) -H(x)]/2. In the situation where the site x is occupied and the site x + 1 is vacant, the shape (above {x, x + 1, x + 2}) of the function H is ∧. If the particle at x jumps at x + 1, it becomes ∨, -and conversely. We consider then the following problem: assume that L and N are very large.

For definiteness, we will take L = 2N , which ensures that H(L) = 0. Consider the change of scale h L t (x) = L -1 H t (Lx), x ∈ (0, 1).

(1.6)

What can we say about the evolution of the profile t → h L t , for, possibly, t very large? We will see that, under adequate conditions on the initial data, and after the following parabolic change of time scale:

h L t (x) = h L L 2 t = L -1 H L 2 t (Lx), x ∈ (0, 1), t > 0, (1.7)
we have a kind of law of large numbers: for all final time T > 0, h L is converging in probability in L ∞ (0, T ; L 2 (0, 1)) to a deterministic profile h which is completely determined as a solution of the heat equation with homogeneous Dirichlet boundary conditions.

Interacting particle systems

We will now consider a problem similar to the previous one, with the difference that it is multidimensional and that jumps to occupied sites are not excluded. Let Λ N be a finite subset of Z d . We consider a system of particles scattered on Λ N , which interact as follows: let x denote a typical site of Λ N and let η t (x) denote the number of particles located at site x at time t. We will be interested in the evolution in time of the functions x → η t (x). The state space is therefore E N := N Λ N , the set of functions Λ N → N. The evolution is described by the following algorithm: each site x has its own clock that is independent from the clocks at other sites, and that rings after a time T x which is a random variable of exponential law of parameter λ(η(x)). Assume that it is at the site x * that a clock is ringing first. If η(x * ) > 0, then one particle of the site x * jumps to an other site y chosen at random in Λ N , according to a transition probability p(x * , y) (possibly, at that stage, some exclusion rules may be added, see Section ??). Then we start over. Let us consider the case where Λ N is the discrete torus T d N = Z d /N Z d and p is compatible and translation invariant: for all l ∈ N Z d , m ∈ Z d , p(x + l, y) = p(x, y), p(x + m, y + m) = p(x, y).

(1.8)

Let us zoom out (cf. (1.6)) by considering the function

[0, 1) d x → N -1 η t ([N x]) (1.9)
extended by periodicity. In (1.9), [N x] is the element x of T d N {0, • • • , N -1} d such that x i ≤ N x i < x i + 1 for all i = 1, . . . , d. May it be the case that, possibly after a change of time scale (cf. (1.7)), some averaging phenomena would lead to a given deterministic behaviour? We will see that the question has to be refined, before being answered positively (at least in certain cases).

Martingales in continuous time

Conditional expectation

Proposition 2.1 (Conditional expectancy). Let (Ω, F, P) be a probability space and let G ⊂ F be a sub-σ-algebra of F. Let X be real-valued random variable which is integrable: X ∈ L 1 (Ω, F, P). Then there exists a unique G-measurable and integrable random variable Z such that

E(1 A X) = E(1 A Z), ∀A ∈ G.
(2.1)

We call Z the conditional expectancy of X knowing G, denoted E(X|G).

Roughly speaking, E(X|G) is the average of X with respect to all the events not relative to G.

The following facts or examples illustrate this fact.

Fact 1. If G = F, then E(X|F) = X a.s. If G is the trivial σ-algebra {∅, Ω}, then E(X|G) = E(X).

Example 1. When G is the σ-algebra generated by an event A ∈ F, G = {∅, A, A c , Ω}, then

E(X|G) = E(1 A X) P(A) 1 A + E(1 A c X) P(A c ) 1 A c . If X = 1 B where B ∈ F, this gives E(1 B |G) = P(B|A)1 A + P(B|A c )1 A c .
Fact 2. One has the following tower property: if H is a sub-σ-algebra of G, then

E(E(X|G)|H) = E(X|H) a.s. (2.2)
As a particular case, when H = {∅, Ω}, we obtain E[E(X|G)] = E[X].

Example 2. Let X, Y be two independent random variable and let f : R 2 → R be a bounded Borel function. Then Z = E(f (X, Y )|σ(Y )) is σ(Y )-measurable, and it is known that such a function can be written h(Y ), where h is Borel. In general, when saying that a σ(Y )-measurable function has the form h(Y ), we have no particular information on h. Here, however, we know very well what is h: it is the function obtained by averaging with respect to "all that is not Y ", i.e. E(f (X, Y )|σ(Y )) = h(Y ), h(y) := E(f (X, y)).

(2.3) Example 3. Let D denote the set of dyadic cubes in [0, 1) d , and for n ∈ N, let D n denote the subset of dyadic cubes of length 2 -n : all cubes in D n are translation by an element of 2 -n Z d of the basic cube [0, 2 -n ) d . Let f : [0, 1) d → R be integrable. The piecewise-constant function f n equal to the averaged value of f over each cube Q in D n can be seen as the conditional expectancy E(f |F n ) by taking Ω = [0, 1) 2 , P being the Lebesgue measure, F the Borel σ-algebra, and F n being the σ-algebra generated by all the cubes in D n (verification left as en exercise). There is a consistency property in this approximation process, which is the following one: for all m < n, averaging the finer approximation f n over the coarser grid corresponding to D m gives f m :

E(f n |F m ) = f m a.s. (2.4)
The property (2.4) follows from the tower property (2.2) for example. It is an instance of a martingale property.

Martingales

Definition 2.1 (Filtration). Let (Ω, F, P) be a probability space. A family (F t ) t≥0 of sub-σalgebras of F is said to be a filtration if the family is increasing with respect to t: F s ⊂ F t for all 0 ≤ s ≤ t. The space (Ω, F, (F t ) t≥0 , P) is called a filtered space.

Definition 2.2 (Adapted process). Let (Ω, F, (F t ) t≥0 , P) be a filtered space. A real-valued process (X t ) t≥0 is said to be adapted if, for all t ≥ 0, X t is F t -measurable.

Definition 2.3 (Martingale). Let (Ω, F, (F t ) t≥0 , P) be a filtered space. Let (X t ) t≥0 be an adapted real-valued process such that, for all t ≥ 0, X t ∈ L1 (Ω). The process (X t ) t≥0 is said to be a martingale if, for all 0 ≤ s ≤ t, X s = E(X t |F s ) a.s.

E [(M * T ) p ] ≤ p p -1 p E|M T | p , M * T = sup t∈[0,T ] |M t |, (2.5)
is satisfied.

A digression on the Calderón-Zygmund decomposition

The Calderón-Zygmund decomposition

Let f : [0, 1) d → R be a non-negative, integrable function. Let λ > 0 be a fixed threshold such that the integral of f over [0, 1) d is smaller than λ/2. In terms of Example 3. in Section 2.1, this means E[f ] ≤ λ/2. Consider (see Remark 2.2) that being below λ is "not wandering too much", while being above λ is "wandering too much". What is the behavior of the martingale (f n ) defined in the Example 3. in Section 2.1? Let T be the stopping time T = inf{n ≥ 0; f n > λ}. We know that T > 0 almost surely. If T = +∞, then f n ≤ λ for all n, and thus f = lim f n ≤ λ. Here we use the intuitive fact that f = lim f n . We have to specify the mode of convergence however and to justify the convergence. The convergence is almost sure. One can use the martingale convergence theorem for example (probabilistic approach) or the dyadic version of the Lebesgue differentiation theorem (analyst's approach). In any case, we obtain: f ≤ λ a.s. on {T = +∞}. The set {T < +∞} can be written as an at most countable collection (Q i ) i∈I of dyadic cubes. Indeed, it is the union over n ≥ 1 of the sets {T = n}, and

{T = n} is a union of dyadic cubes in D n (because f n is constant on each Q ∈ D n ). If Q is one of the cubes that enter in the decomposition of {T = n}, and if Q ∈ D n-1 is the twice bigger cube containing Q, then the averaged value of f on Q is smaller than λ (otherwise T < n). It follows that λ ≤ 1 |Q| Q f (x)dx ≤ 1 |Q| Q f (x)dx = 2 d |Q | Q f (x)dx ≤ 2 d λ. (2.6)
From these considerations on martingales, we can deduce the following statement.

Lemma 2.3 (Calderón-Zygmund). Let f : R d → R be a non-negative, integrable function. Let λ > 0. There exists an at most countable family

(Q i ) i∈I of dyadic cubes such that ∀i ∈ I, λ ≤ 1 |Q i | Qi f (x)dx ≤ 2 d λ, (2.7)
and f ≤ λ a.e. on the complementary set

R d \ ∪ i∈I Q i . Proof of Lemma 2.3. fix N large enough such that 2 -N d f L 1 (R d ) ≤ λ/2.
Consider the countable decomposition of R d by all the dyadic cubes of size 2 N . On each such cube R, we apply the analysis performed before the statement of the lemma. This analysis was done with the starting cube R = [0, 1) d , but can be readily adapted to the general case. The final family of cube (Q i ) i∈I is then the union of the families obtained on each such cube R.

The Calderón-Zygmund lemma is applied to obtain a decomposition of f = g + b, where

g = i∈ 1 |Q i | Qi f (x)dx 1 Qi + f 1 R d \∪ i∈I Qi (2.8) and b = f -g = i∈I b i , b i = f - 1 |Q i | Qi f (x)dx 1 Qi . (2.9)
The function g is considered as the good part, since it is controlled in size by λ; more precisely, |g(x)| ≤ (2 d + 1)λ. The function b is considered as the "bad" part. It is not controlled in size but has the properties that b i is supported in Q i and has zero integral. The Calderón-Zygmund is fundamental in harmonic analysis. Note that, if we come back again to the probabilistic approach (and restrict things to [0, 1) d ), then g is simply f T , while b = f -f T .

Application to elliptic estimates

Let U be an open subset of R d , d ≥ 2. Let f : U → R be measurable. The Newtonian potential of f in U is the function u defined by the convolution product

u(x) = U G(x -y)f (y)dy, x ∈ R d , ( 2.10)
where the function G is defined by

G(x) =    -1 2π ln |x| if d = 2, 1 d(d -2)ω d 1 |x| d-2 if d ≥ 3, (2.11)
where ω d is the d-dimensional Lebesgue measure of the unit ball in dimension d. Although G is singular at the origin, the function u is well defined and has some given regularity/integrability properties, depending on the regularity/integrability properties of f . See [START_REF] Gilbarg | Elliptic partial differential equations of second order[END_REF]Chapter 4.]. Since G is the fundamental solution of the Laplace equation in R d , the function u satisfies -∆u = f in U , again under adequate regularity/integrability properties of u and f . The Newtonian potential is also used to express a solution of the Poisson equation -∆v = f as the sum u + w, where w is harmonic in U (no considerations on boundary conditions here). We will use the Calderón-Zygmund decomposition to prove the gain of regularity of two derivatives in the space L p . Theorem 2.4. Let 1 < p < +∞. Let f be bounded and locally Hölder continuous and let u be given by (2.10). Then u is of class C 2 in U , -∆u = f in U , and

∂ 2 ij u L p (U ) ≤ C f L p (U ) , (2.12)
for all i, j ∈ {1, . . . , d}, where the constant C depends on d and p only.

We will focus on (2.12). See [13, p.55] for the proof that u is of class C 2 in U and satisfies the Poisson equation -∆u = f in U . Informally, we have

∂ 2 ij u(x) = R d K ij (x -y) f (y)dy,
where f is the extension of f by 0 outside U , and where K ij has a non-integrable singularity of type |x| -d at the origin. We can also write (again informally),

∂ 2 ij u = R i R j f , where R j is the Riesz transform. It is defined a priori as the application L 2 (R d ) → L 2 (R d )
given, after conjugation with the Fourier Transform, by

F(R j f )(ξ) = i ξ j |ξ| F(f )(ξ), F(f )(ξ) = R d f (x)e -ix•ξ dx. (2.13)
We recognize the expression of the operator f → ∂ xj (-∆) 1/2 f . Using the expression of Fourier transform of the homogeneous function ξ → ξj |ξ| , [START_REF] Friedlander | Introduction to the theory of distributions[END_REF], we also obtain (still informally at that stage) the expression

R j f (x) = R d K j (x -y)f (y)dy, where K j (x) = Γ((d+1)/2) π (d+1)/2
xj |x| d+1 has a non-integrable singularity at the origin. We will use the Calderón-Zygmund decomposition to establish the following result.

Theorem 2.5 (Singular Integral

). Let K ∈ C(R d \ {0}) be a given kernel. Assume that, for all f ∈ C ∞ c (R d ), for all x ∈ R d , the limit T f (x) = lim ε→0 T ε f (x), T ε f (x) = |x-y|>ε K(x -y)f (y)dy, (2.14)
exists, that there is a constant A ≥ 0 such that

T f L 2 (R d ) ≤ A f L 2 (R d ) , (2.15
)

for all f ∈ C ∞ c (R d ), and sup y∈B (2B) c |K(z) -K(z -y)|dz ≤ A, (2.16)
for all ball B = B(0, r), r > 0, centred at the origin (with 2B = B(0, 2r)). Then, for all 1 < p < +∞, there exists a constant A p ≥ 0 such that

T f L p (R d ) ≤ A p f L p (R d ) ,
(2.17)

for all f ∈ C ∞ c (R d ).
Let us do few comments on the result. First, see [21, p.19] for a more general statement. Second, note that the constant A does not depend on the radius r in the regularity condition (2.16).

Let us consider the case of the Riesz transform. Using the definition (2.13) and the expression

F(|x| -(d-1) ) = α d |ξ| -1 for the Fourier Transform of the tempered distribution x → |x| -(d-1)
(where α d is a constant depending on d only), we see that

R j f (x) = β d R d |x -y| -(d-1) ∂ j f (y)dy, (2.18)
(where β d also denotes a constant depending on d only). Set K(z) = β d zj |z| d+1 . Let ν ε (x, y) denote the outward unit normal to the ball B(x, ε) at a point y of the boundary and let (e i ) 1,d denote the canonical basis of R d . We use the identity ∂ j ϕ = div(ϕe j ) and the Green formula to obtain

T ε f (x) = |x-y|>ε K(x -y)f (y)dy = β d |x-y|>ε |x -y| -(d-1) ∂ j f (y)dy + r ε , where r ε = β d |x-y|=ε |x -y| -(d-1) ν ε (x, y) • e j ∂ j f (y)dσ(y).
We have ν ε (x, y) = y-x |y-x| , hence

r ε = β d ε -(d-1) |x-y|=ε y -x |y -x| • e j ∂ j f (y)dσ(y) = β d |z|=1 z |z| • e j ∂ j f (x + εz)dσ(z). Since |z|=1 z |z| • e j dσ(z) = 0
by symmetry, we obtain, for f smooth enough,

r ε = β d |z|=1 z |z| • e j [∂ j f (x + εz) -∂ j f (x)]dσ(z) = O(ε).
This shows that the limit in (2.

y∈B1 (2B1) c |K(z) -K(z -y)|dz < +∞, (2.19)
where (2.20) gives the desired result.

B 1 = B(0,
|K(z) -K(z -y)| = 1 0 (∇K)(z -ty) • ydt ≤ 1 0 |∇K(z -ty)|dt ≤ C(d) 1 0 1 |z -ty| d+1 dt ≤ C (d) |z| d+1 . (2.20) Indeed, |z| ≤ |z -ty| + 1 ≤ |z -ty| + |z|/2, which gives |z| ≤ 2|z -ty| for t ∈ [0, 1]. The bound in
Proof of Theorem 2.5. We use the Marcinkiewicz' interpolation Theorem (see the footnote in [21, page 12]) and a duality argument to reduce the proof to the weak-(1, 1) estimate

|{|T f | > α}| ≤ A 1 α f L 1 (R d ) , (2.21) for α > 0, f ∈ C ∞ c (R d ),
where |E| denotes the d-dimensional measure of a Borel set E. Let us apply the Calderón-Zygmund decomposition:

|{|T f | > α}| ≤ |{|T g| > α/2}| + |{|T b| > α/2}| . (2.22)
Although f is smooth, g and b may be not smooth.

|{|T g| > α/2}| ≤ 4 α 2 T g 2 L 2 ≤ 4A 2 α 2 g 2 L 2 .
We have seen that the pointwise bound |g(x

)| ≤ (1 + 2 d )λ is satisfied. We have also g L 1 (R d ) ≤ f L 1 (R d ) as a direct application of (2.8). Therefore g 2 L 2 is bounded by (1 + 2 d )λ f L 1 (R d )
and we conclude that

|{|T g| > α/2}| ≤ (2 d + 1) 4A 2 α 2 λ f L 1 (R d ) . (2.23)
To estimate the second term in (2.22), we first note that, given a Borel set E, we have, using the Markov inequality,

|{|T b| > α/2}| ≤ |{|T b| > α/2} ∩ E| + |E c | ≤ 2 α E |T b(x)|dx + |E c |.
By the decomposition (2.9), we deduce that

|{|T b| > α/2}| ≤ 2 α i∈I E |T b i (x)|dx + |E c |. ( 2
T b i (x) = Bi (K(x -y) -K(x -x i ))b i (y)dy.
With Fubini's theorem, we deduce that

E |T b i (x)|dx ≤ Bi E |K(x -y) -K(x -x i )|dx|b i (y)|dy. Take E = ∩ j∈I (2B j ) c . Then E |K(x-y)-K(x-x i )|dx ≤ (2Bi) c |K(x-y)-K(x-x i )|dx = (2B i ) c |K(z +x i -y)-K(z)|dz,
where

B i = x i + B i . Using (2.16
) and (2.9) gives us

|{|T b| > α/2}| ≤ 2A α i∈I Bi |b i (y)|dy + |E c | ≤ 2A α f L 1 (R d ) + |E c |.
(2.25) By (2.6), we also have

|E c | ≤ i∈I |2B i | = 2 d i∈I |B i | ≤ 2 d c -1 d λ f L 1 (R d ) .
The final estimate

|{|T f | > α}| ≤ C(A, d)(α -2 λ + α -1 + λ -1 ) f L 1 (R d )
follows from (2.23) and (2.25). Taking λ = α, we conclude to (2.21).

Markov processes

We consider Markov processes taking values in a Polish space E. Recall that a process X = (X t ) t≥0 is a collection of random variables: for each t ≥ 0, X t : (Ω, F) → (E, B(E)) is measurable (on E we always consider the Borel σ-algebra, denoted B(E). The law of the process is obtained by considering the random variable X : Ω → E R+ , where E R+ is the set of functions from R + to E. On E R+ , we consider the cylindrical σ-algebra, which is the σ-algebra generated by the evaluations maps π t : [START_REF] Tao | An introduction to measure theory[END_REF]Chapter 2.4]. Then, the law of X is described by the set of finite-dimensional distributions P(A), where A is a cylindrical set of the form

E R+ → E, π t (f ) := f (t),
A = {X t1 ∈ B 1 , . . . , X tn ∈ B n } , ( 3.1)
for some n ∈ N, B 1 , . . . , B n some Borel subsets of E and t 1 , . . . , t n ≥ 0. The filtration (F X t ) denotes the filtration generated by X: for a given t ≥ 0, F X t is the σ-algebra generated by the sets A of the form (3.1), with all times t i ≤ t. We will also denote by BM(E) the Banach space of bounded Borel-measurable functions on E with the sup-norm

ϕ BM(E) = sup x∈E |ϕ(x)|. (3.2)
The set BC(E) is the subspace of continuous bounded functions.

Definition

By Markov process, we mean the triplet constituted of a Markov semi-group, some probability kernels, and the associated Markov processes. More precisely, we suppose first that we are given:

1. a Markov semi-group P = (P t ) t≥0 , which is defined a priori as a family of endomorphisms of the space BM(E) that satisfy the initial condition P 0 = Id, the semi-group property P t • P s = P t+s for t, s ≥ 0, the preservation of positivity P t ϕ ≥ 0 when ϕ ≥ 0, while fixing the constant function 1 equal to 1 everywhere: P t 1 = 1 for all t ≥ 0, 2. a probability kernel Q(t, x, B): for all ϕ ∈ BM(E), for all x ∈ E,

P t ϕ(x) = E ϕ(y)Q(t, x, dy), ( 3.3)
where, for every t ≥ 0, for every x ∈ E, Q(t, x, •) is a probability measure and the dependence in x is measurable, in the sense that the right-hand side of (3.3) is a measurable function of x, 3. a set X = {(X x t ) t≥0 ; x ∈ E} of Markov processes indexed by their starting points x: X x 0 = x almost surely, such that:

• the finite-dimensional distributions of (X x t ) t≥0 are given by

P(X x 0 ∈ B 0 , X x t1 ∈ B 1 , . . . , X x t k ∈ B k ) = B0 • • • B k-1 Q(t k -t k-1 , y k-1 , B k ) × Q(t k-1 -t k-2 , y k-2 , dy k-1 ) • • • Q(t 1
, y 0 , dy 1 )µ(dy 0 ), (3.4) where 0

≤ t 1 ≤ • • • ≤ t k , B 0 , . . . , B k ∈ B(E) and µ = δ x (Dirac mass), • the Markov property E ϕ(X x t+s )|F X t = P s ϕ(X x t ) (3.5)
is satisfied for all s, t ≥ 0, ϕ ∈ BM(E).

There are a lot of redundancies in the definition above, that we will now analyse. It is not limiting, however, to assume that all these elements are given altogether, all the more since the processes (X x t ) t≥0 will generally have additional pathwise properties, being typically continuous or càdlàg. They may also satisfy the Markov property (3.5) with respect to a given filtration (F t ) larger than (F X t ). First, we need to define an appropriate mode on convergence of functions in BM(E). Definition 3.1. We say that there is bounded pointwise convergence of a sequence

(ϕ n ) in BM(E) to ϕ ∈ BM(E) if sup n ϕ n BM(E) < +∞ and ϕ n (x) → ϕ(x) for all x ∈ E. This mode of convergence is denoted ϕ n b.p.c.
-→ ϕ.

Q(t + s, x, A) = E Q(s, y, A)Q(t,
P µ (X 0 ∈ B 0 , X t1 ∈ B 1 , . . . , X t k ∈ B k ) (3.9)
is given by the right-hand side of (3.4).

We denote by E µ the expectancy operator associated to P µ . When µ = δ x , we use the notations P x and E x . The Kolmogorov extension theorem, [START_REF] Tao | An introduction to measure theory[END_REF], can be used to construct the measure P µ . The probability space is the path space: Ω = E R+ . The σ-algebra F is the cylindrical σ-algebra (called product σ-algebra in [START_REF] Tao | An introduction to measure theory[END_REF]Chapter 2.4]). The process X is then the canonical process X t (ω) = ω(t).

In the following two results, we establish the link between the Markov property and the Chapman-Kolmogorov (or semi-group) property.

µ [ϕ(X t+s )1 A ] = E µ [P s ϕ(X t )1 A ] , (3.11)
for all A ∈ F X t . We can see both members of (3.11) as measures in A. Since F X t is generated by cylindrical sets that form a π-system, it is sufficient, [START_REF] Billingsley | Probability and measure[END_REF]Theorem 3.3], to establish (3.11) for A of the form

A = {X 0 ∈ B 0 , X t1 ∈ B 1 , . . . , X tn ∈ B n } , 0 < t 1 < • • • < t n ≤ t.
(3.12)

Since (3.11) is linear in ϕ and the continuity property (3.6) is satisfied we can also reduce the proof of (3.11) to the case where ϕ is a characteristic function 1 B , with B ∈ B(E). Alternatively, the same kind of argument shows that, for all ψ ∈ BM(E) and A of the form (3.12), we have

E µ [ψ(X t )1 A ] = B0 • • • Bn P t-tn ψ(y n )Q(t n -t n-1 , y n-1 , dy n ) • • • Q(t 1
, y 0 , dy 1 )µ(dy 0 ), (3.13) since (3.4) and (3.3) show that (3.13) is true when ψ = 1 Bn+1 . We will use (3.13) and the Chapman-Kolmogorov (or, more precisely, semi-group) property to conclude. Taking ψ = P s ϕ in (3.13) and using the semi-group property, we see that the right-hand side of (3.11) is Proof of Proposition 3.5. We will establish the equivalent semi-group property for (P t ). Let ϕ ∈ BM(E). By the tower property (2.2), we have

B0 • • • Bn P t+s-tn ϕ(y n )Q(t n -t n-1 , y n-1 , dy n ) • • • Q(t 1 ,
P t+s ϕ(x) = E x [ϕ(X t+s )] = E x E x ϕ(X t+s )|F X t .
The Markov property then gives

P t+s ϕ(x) = E x [P s ϕ(X t )] = (P t • P s )ϕ(x),
which is the desired identity.

Invariant measures and weak convergence of probability measures

Let (P, Q, X) be a Markov process as in Section 3.1. If µ is a probability measure on E, we denote by P * t µ the law at time t of X t , when X 0 ∼ µ:

P * t µ, ϕ := E µ [ϕ(X t )] .
The notation can be justified as follows: using (3.13) with A = Ω, i.e.

B 0 = • • • = B n = E, we see that E µ [ϕ(X t )] = E P t ψ(y)µ(dy) = µ, P t ϕ .
This establishes the expected formula

P * t µ, ϕ = µ, P t ϕ . (3.15)
Definition 3.2 (Invariant measure). A probability measure µ on E is said to be an invariant measure if P * t µ = µ for all t ≥ 0. To find an invariant measure µ, one must choose X 0 conveniently, to ensure that X t follows the same law µ for all t ≥ 0: an invariant measure is a fixed-point for the evolution in distribution of the Markov process. As far as the evolution of the distribution P * t µ of the Markov process is concerned, we can wonder what are the continuity property of t → P * t µ. The space P 1 (E) of Borel probability measures on E is a subset of the dual space to the Banach space BC(E) (the norm being the sup norm (3.2)). We consider the weak- * topology on

P 1 (E) 2 . A sequence (µ n ) converges to µ in P 1 (E) if µ n , ϕ → µ, ϕ , (3.16)
for all ϕ ∈ BC(E). When (3.17) is realized, it is customary to say that "(µ n ) converges weakly to µ". Let us state without proof the following version of the Portmanteau Theorem (see [14, p.4,5] for the proof).

Theorem 3.6. The following five statements are equivalent.

(i) (µ n ) converges weakly to µ,

(ii) (3.16
) is satisfied for all uniformly continuous and bounded functions ϕ on E,

(iii) lim sup µ n (F ) ≤ µ(F ) for all closed set F , (iv) lim inf µ n (G) ≥ µ(G) for all open set G, (v) lim µ n (A) = µ(A) for all Borel set A such that µ(∂A) = 0.
Coming back to t → P * t µ, we see that

P * t µ → P * s µ if lim t→s P * t µ, ϕ = P * s µ, ϕ , (3.17)
for all ϕ ∈ BC(E).

Definition 3.3 (Stochastic continuity of the semi-group).

Let s ≥ 0. The semi-group (P t ) t≥0 is said to be stochastically continuous at

s if P t ϕ b.p.c.
-→ P s ϕ when t → s for every ϕ ∈ BC(E). We say that (P t ) t≥0 is stochastically continuous if it is stochastically continuous at very point.

The stochastic continuity of (P t ) t≥0 at s is equivalent to the weak convergence (3.17). Indeed, if (3.17) is satisfied, then µ, P t ϕ → µ, P s ϕ by the duality formula (3.15). Taking µ = δ x especially, we obtain

P t ϕ(x) → P s ϕ(x). Since |P t ϕ(x)| ≤ ϕ BC(E)
, we obtain the b.p. convergence. Reciprocally, µ, P t ϕ → µ, P s ϕ follows from the stochastic continuity by dominated convergence. There is also a notion of stochastic continuity for processes: a stochastic process (X t ) is stochastically continuous at s if X t → X s in probability for the topology of E: for all δ > 0,

lim t→s P(d(X t , X s ) > δ) = 0, (3.18)
where d is the distance on E.

Exercise 3.4 (Stochastic continuity). Let (X t ) be a Markov process, and let P t be defined by

P t ϕ(x) = E x [ϕ(X t )].
Show that stochastic continuity of (X t ) at s implies stochastic continuity of (P t ) at s (Hint: use (ii) in Theorem 3.6). The solution to Exercise 3.4 is here.

Definition 3.5 (Feller semi-group).

A semi-group (P t ) t≥0 is said to be Feller if

P t : BC(E) → BC(E),
for all t ≥ 0:

P t ϕ ∈ BC(E) when ϕ ∈ BC(E).
If (P t ) t≥0 is Feller and (µ n ) converges weakly to µ, then we can test (3.16) against P t ϕ. Using the duality relation (3.15), we conclude that (P * t µ n ) converges weakly to P * t µ. The following exercises are all about invariant measures. Exercise 3.6 (Invariant measure for a discrete Ornstein-Uhlenbeck process). Let X 0 , X 1 , . . . be the sequence of random variables on R defined as follows: X 0 is chosen at random, according to a law µ 0 , then, X N being known, a random variable Z N +1 taking the values +1 or -1 with equi-probability is drawn independently on X 0 , . . . , X N and X N +1 given by

X N +1 = 1 2 X N + Z N +1 .
1. What means µ 0 = δ 0 ? What are then the law µ 1 , µ 2 of X 1 and X 2 respectively?

2. Consider the case

µ 0 = 1 2 δ -2 + 1 2 δ +2 . Compute µ 1 , µ 2 , µ 3 .
Can you guess a general formula for µ N ?

3. Find an invariant measure.

The solution to Exercise 3.6 is here. Exercise 3.7 (Invariant measure by Cesàro convergence). Suppose that (P t ) t≥0 is stochastically continuous and Feller. For T > 0, and µ ∈ P 1 (E), let μT be the probability measure defined by

μT , ϕ = 1 T T 0 P * t µ, ϕ dt.
Suppose that there exists a probability measure ν on E such that, for at least on µ ∈ P 1 (E), μT converge weakly to ν when T → +∞. Show that ν is an invariant measure.

The solution to Exercise 3.7 is here.

Exercise 3.8 (Invariant measures for deterministic systems). Let (Φ t ) t≥0 denote the flow associated to the ordinary differential equation ẋ = F (x). Here F : R d → R d is a (globally) Lipschitz continuous function.

1. Show that P t ϕ := ϕ • Φ t defines a Markov semi-group on BM(R d ).

2. Punctual equilibria. Let x 1 , . . . , x n be some zeros of F . Show that any convex combination of the Dirac masses δ x1 , . . . , δ xn is an invariant measure.

3. Hamiltonian system. Suppose that d = n + n, x = (p, q) and

F p q = D q H(p, q) -D p H(p, q) ,
where

H : R n × R n → R is of class C 2 . (a) Show that t → H • Φ t (x) is constant for all x.
(b) Assume that e -βH ∈ L 1 (R d ) for all β > 0. We introduce the Gibbs measure µ β , which is the measure of density Z(β) -1 e -βH with respect to the Lebesgue measure (Z(β) = e -βH(x) dx is a normalizing factor). Show that µ β is an invariant measure.

The solution to Exercise 3.8 is here.

Infinitesimal generator

Given a Markov process as in Section 3.1, we would like to define the associated infinitesimal generator. There are various possible approaches. In [START_REF] Bakry | Analysis and geometry of Markov diffusion operators[END_REF] for example, it is assumed that the process admits an invariant measure µ. The semi-group can then be extended as a contraction semi-group on L 2 (µ). By assuming additionally that this extension gives rise to a strongly continuous semi-group, [1, Property (vi), p.11], one can use the standard theory of strongly continuous semi-group, [START_REF] Pazy | Semigroups of Linear Operators and Applications to Partial Differential Equations[END_REF], to define the infinitesimal generator. One may wonder why not simply working in BM(E), or BC(E), which are Banach spaces, to apply the standard theory of strongly continuous semi-group. The difficulty is that the continuity property P t ϕ → ϕ when t → 0 is too stringent in that context, at least when E is infinite-dimensional. Consider for example the simple deterministic case where P t ϕ is given as the composition ϕ • Φ t with a flow (Φ t ). Let E be the Hilbert space E = 2 (N), with orthonormal basis (e n ) n∈N , and let Φ t be given by

Φ t (x) = ∞ n=0 e -λnt x, e n e n ,
where (λ n ) is an increasing sequence converging to +∞. In general, one cannot control the distance Φ t (x) -x 2 (N) uniformly in x (this is possible when x is restricted to a compact set), so even if ϕ is uniformly continuous, one does not expect the convergence

lim t→0 sup x∈E |P t ϕ(x) -ϕ(x)| = 0.
We consider a different mode of convergence therefore, the bounded pointwise convergence (Definition 3.1). A function ϕ ∈ BM(E) is in the domain D(L ) of the infinitesimal generator L of (P t ) if there exists ψ ∈ BM(E) such that

P t ϕ -ϕ t b.p.c.
-→ ψ, (3.19) when t → 0. We then set L ϕ = ψ. Note that, on the elements ϕ ∈ D(L ), the property of continuity P t ϕ b.p.c.

-→ ϕ (3.20)

when t → 0, is satisfied. By the semi-group property, (3.20) implies more generally the property of continuity from the right P t ϕ b.p.c.

-→ P t * ϕ when t ↓ t * , for every t * ≥ 0. The semi-group property, and the continuity of P t with respect to b.p. convergence, that can be deduced from (3.3) (see (3.6)), have also the following consequence: if ϕ ∈ D(L ), then P t ϕ ∈ D(L ) for all t ≥ 0 and

P t+h ϕ -P t ϕ h b.p.c. -→ P t L ϕ = L P t ϕ, ( 3.21)
when h → 0 + .

Martingale property of Markov processes

Consider a Markov process as in Section 3.1, which is Markov with respect to a filtration (F t ), and has a generator L , as defined as in Section 3.3. We make the following hypotheses:

1. stochastic continuity: we have P t ϕ b.p.c.

-→ P t * ϕ when t → t * for every ϕ ∈ BC(E) and every

t * ≥ 0, 2. measurability: the application (ω, t) → X t (ω) is measurable Ω × R + → E.
We have then the following result.

Theorem 3.7. Let ϕ ∈ D(L ) ∩ BC(E). Then M t := ϕ(X t ) -ϕ(X 0 ) - t 0 L ϕ(X s )ds (3.22)
is a (F t )-martingale. If furthermore |ϕ| 2 is in the domain of L , then the process (Z t ) defined by

Z t := |M t | 2 - t 0 (L |ϕ| 2 -2ϕL ϕ)(X s )ds, (3.23)
is a (F t )-martingale.

Remark 3.1 (Quadratic variation). If (X t ) has continuous trajectories, then

A t := t 0 (L |ϕ| 2 -2ϕL ϕ)(X s )ds (3.24)
is the quadratic variation M, M t , [15, p.38], of (M t ). In the general case where (X t ) is càdlàg,

(A t ) is the compensator, [15, p.32], of the quadratic variation [M, M ] t , [15, p.51], of (M t ). For instance, if (X t = N t ) is a Poisson Process of rate λ, then L ϕ(n) = λ(ϕ(n + 1) -ϕ(n))
and

A t := λ t 0 (ϕ(N s + 1) -ϕ(N s )) 2 ds.
Taking ϕ = Id, gives the standard fact that (N t -λt) is a martingale.

Proof of Theorem 3.7. Let 0 ≤ s ≤ t. By the Markov property, we have

E[M t |F s ] -M s = E[M t -M s |F s ] = P t-s ϕ(X s ) -ϕ(X s ) - t s [P σ-s L ϕ](X s )dσ. (3.25)
To establish (3.25) we have used the fact that

E t s ψ(σ)dσ |F s = t s E [ψ(σ) |F s ] dσ, (3.26) with ψ(ω, σ) := L ϕ(X σ (ω))
, which is a measurable function. The identity (3.26) follows from the linearity of the conditional expectation when ψ is a simple function, and standard arguments give the general case. From (3.25) and the identity

P t ϕ(x) -ϕ(x) = t 0 P s L ϕ(x)ds, (3.27) for all ϕ ∈ D(L ), x ∈ E, t ≥ 0, we conclude that E[M t |F s ] -M s = 0. To establish (3.27), we notice that β(t) := P t ϕ(x) -ϕ(x)
is a continuous function (here we use the stochastic continuity of (P t )), which is right-differentiable at every point, with right-differential β (t+) := P t L ϕ(x) which is a bounded (by stochastic continuity of (P t ), it is even continuous if L ϕ ∈ BC(E) -but this is not assumed a priori). Lemma 3.8 below then gives the result. The proof of the martingale property for (3.23) is divided in several steps. First, we fix two times 0 ≤ τ < τ ≤ T . We fix a subdivision σ = (t i ) 0,n of [0, τ ], chosen in such a way that τ is always one of the t i , say τ = t l (the index l may hence vary with σ). By C(ϕ), we will denote any constant that depend on ϕ and is independent on σ and may vary from lines to lines. We also denote by A = O(B) any estimate of the form |A| ≤ C(ϕ)|B|. At last, we introduce the following notations: we denote by δ ti K the increment K ti+1 -K ti of a function t → K t . We also denote by E ti the conditional expectation with respect to F ti . Our aim is to show that

A τ = lim |σ|→0 n-1 i=0 E ti |δ ti M | 2 , (3.28)
where the limit is taken in L 2 (Ω). Indeed, taking (3.28) for granted, E[Z τ -Z τ |F τ ] is the limit when |σ| → 0 of the quantity

E |M tn | 2 -|M t l | 2 - n-1 i=l E ti |δ ti M | 2 F τ . (3.29)
Let us show that (3.29) = 0. To simplify the presentation3 , we will treat the case t l = τ = 0, F 0 = {∅, Ω} (it makes sense to consider that F 0 is the trivial sigma algebra since M 0 = 0). We have

E |M tn | 2 = E   n-1 i=0 δ ti M 2   . (3.30)
In (3.30), we can expand the square. The contribution of the double products is zero since, if j > i, then, using the fact that δ ti M is F tj -measurable, we have

E δ ti M δ tj M = E E tj δ tj M δ ti M = 0.
The last identity follows from the martingale property E tj δ tj M = 0. This implies (3.29) = 0, and thus E[Z τ -Z τ |F τ ] = 0. The proof of (3.28) is divided into three steps.

Step 1. We show that

A τ = lim |σ|→0 n-1 i=0 E ti [δ ti A], with a convergence in L 2 (Ω). Since A τ = n-1 i=0 δ ti A, we have to show that lim |σ|→0 n-1 i=0 ζ i = 0 in L 2 (Ω), where ζ i := δ ti A -E ti [δ ti A].
The method is similar to the analysis of (3.29) above: we decompose

E n-1 i=0 ζ i 2 = n-1 i=0 E |ζ i | 2 + 2 0≤i<j<n E [ζ i ζ j ] . ( 3
δ ti M = δ ti ϕ(X) - ti+1 ti L ϕ(X s )ds, (3.32)
we deduce E ti [δ ti ϕ(X)] = O(δt i ). We can apply the previous estimate to |ϕ| 2 , since |ϕ| 2 is in the domain of L by hypothesis (cf. (3.34) below), to get E ti δ ti |ϕ| 2 (X) = O(δt i ). On the other hand, we have also the identity

|δ ti ϕ(X)| 2 = δ ti |ϕ| 2 (X) -2ϕ(X ti )δ ti ϕ(X). (3.33)
Taking expectation with respect to F ti in (3.33) and using the fact that

E ti [ϕ(X ti )δ ti ϕ(X)] = ϕ(X ti )E ti [δ ti ϕ(X)]
gives the desired estimate

E ti |δ ti ϕ(X)| 2 = O(δt i ).
We can insert this result in (3.32) to obtain also

E ti |δ ti M | 2 = O(δt i ).
Step 3. We conclude the proof. First, we note that (3.32) applied to ϕ 2 gives

δ ti M (2) = δ ti |ϕ| 2 (X) - ti+1 ti L |ϕ| 2 (X s )ds, (3.34)
where M

(2)

t := |ϕ| 2 (X t ) -|ϕ| 2 (x) - t 0 L |ϕ| 2 (X s )ds.
We combine (3.32), (3.33) and (3.34) to obtain the identity

|δ ti M | 2 + 2δ ti M ti+1 ti L ϕ(X s )ds + ti+1 ti L ϕ(X s )ds 2 = δ ti M (2) + ti+1 ti L |ϕ| 2 (X s )ds -2ϕ(X ti ) δ ti M + ti+1 ti L ϕ(X s )ds . (3.35)
Taking the conditional expectation E ti in (3.35) and using the Markov property gives us

E ti |δ ti M | 2 = E ti [δ ti A] -2E ti ti+1 ti (ϕ(X ti ) -ϕ(X s ))L ϕ(X s )ds + O(|δt i | 3/2 ).
(3.36) Indeed, we have discarded the terms

E ti 2δ ti M ti+1 ti L ϕ(X s )ds and E ti ti+1 ti L ϕ(X s )ds 2 , which are respectively O(|δt i | 3/2 ) and O(|δt i | 2 ). To obtain the O(|δt i | 3/2 )-estimate, we use the bound 2δ ti M ti+1 ti L ϕ(X s )ds ≤ η|δ ti M | + η -1 ti+1 ti L ϕ(X s )ds 2 , then
Step 2, and then we choose η = (δt i ) 1/2 . We can repeat Step 2, where we consider the time interval

[t i , s] instead of [t i , t i+1 ], to obtain the estimate E ti |ϕ(X ti ) -ϕ(X s )| 2 = O(δt i ), when t i ≤ s ≤ t i+1 . Consequently, the last term in (3.36) is also O(|δt i | 3/2 )
. By summing with respect to i in (3.36), we deduce finally that

n-1 i=0 E ti [δ ti A] = n-1 i=0 E ti |δ ti M | 2 + O(|σ| 1/2
β(τ + h) -β(τ ) h = β(τ + h) -D(τ ) h ≥ D(τ + h) -D(τ ) h ,
for h > 0 small enough gives, at the limit h → 0+, the contradiction β (τ +) ≥ M + δ/2. Exercise 3.9 (Carré du champ). The operator

Γ : ϕ → 1 2 L |ϕ| 2 -ϕL ϕ is called the "carré du champ", [1, p.viii]. 1. Let F : R d → R d be Lipschitz continuous. Let (X x t ) be given as the solution to the Cauchy Problem d dt X x t = F (X x t ), X x 0 = x. Compute Γ on C 1 b (R d ) (bounded C 1 function with bounded first derivatives).
2. (For those who know SDEs). Let F be as above and σ : R d → M d (R) be Lipschitz continuous. Let (X x t ) be given as the solution to the Cauchy Problem C 2 function with bounded first and second derivatives).

dX x t = F (X x t )dt + σ(X x t )dW t , X x 0 = x, (3.39) where (W t ) is a d-dimensional Wiener process. Compute Γ on C 2 b (R d ) (bounded
3. In the general case, show that Γ(ϕ) ≥ 0 for all ϕ.

The solution to Exercise 3.9 is here.

The results of Theorem 3.7 can be extended to the case where the test function ϕ also depends on t. We will need this result only in the simple case where the test function has the form θ(t)ϕ(x).

Corollary 3.9. Let ϕ ∈ D(L ) satisfies |ϕ| 2 ∈ D(L ). Let θ ∈ C 1 (R + ) and let ψ(t, x) = θ(t)ϕ(x).
Then, the process

M t := ψ(t, X t ) -ψ(0, X 0 ) - t 0 (∂ t + L )ψ(s, X s )ds (3.40)
is a (F t )-martingale and the process (Z t ) defined by

Z t := |M t | 2 - t 0 ((∂ t + L )|ψ| 2 -2ψ(∂ t + L )ψ)(s, X s )ds, (3.41) is a (F t )-martingale.
Proof of Corollary 3.9. By the Markov property, we have

E [M t -M s |F s ] = θ(t)(P t-s ϕ)(X s ) -θ(s)ϕ(X s ) - t s (θ (σ)(P σ-s ϕ)(X s ) + θ(σ) d dσ (P σ-s ϕ)(X s ))dσ.
By explicit integration, we see that (M t ) is a (F t )-martingale. We compute then

(∂ t + L )|ψ| 2 -2ψ(∂ t + L )ψ = θ 2 (L |ϕ| 2 -2ϕL ϕ).
Let us examine the proof of the second part of Theorem 3.7. Since θ is locally Lipschitz continuous, we have

θ(t) = θ(t i ) + O(δt i ), for t ∈ [t i , t i+1 ].
Using this approximation, it is easy to show, by adapting the proof of Theorem 3.7, that, in our context, (Z t ) is a martingale.

Exercise 3.10 (Markov process with finite state space). Let (P, Q, X) be a Markov process.

Assume that the state space E is finite, E = {x 1 , . . . , x L }. We introduce the family of matrices

A(t) = a ij (t), with a ij(t) = Q(t, x i , {x j }), i.e. a ij (t) = P xi (X(t) = x j ).
4. Give the equation satisfied by an invariant measure.

The solution to Exercise 3.10 is here.

Exercise 3.11 (Markov process in discrete time). We consider now a Markov process (X n ) n≥0 in discrete time.

1. Assume that the state space E is finite. How can you rephrase the questions and answers of the previous exercise 3.10?

2. Give and prove the equivalent statement to Theorem 3.7. More precisely, let

L = P 1 -Id, let ϕ ∈ BM(E). Show that M n = ϕ(X n ) -ϕ(X 0 ) - n-1 k=0 L ϕ(X k ) (3.42)
and

Z n := |M n | 2 - n-1 k=0 Γ[ϕ](X k ) (3.43)
are martingales. In (3.43), Γ(ϕ) is a certain non-negative expression that you will have to identify.

The solution to Exercise 3.11 is here.

Evolution of a random interface

In this part we establish the limit behavior of the symmetric simple exclusion process. More precisely, we show in Theorem 4.1 that, after an adequate change of scales, the random interface associated to the symmetric simple exclusion process converges in probability to the solution of a heat equation.

Change of scale and limit behavior

Let X L denote the discrete interval X L = {0, . . . , L}. Let E L be the set of functions H :

X L → R such that H(L) = 0. Let E (1)
L be the convex subset of E L constituted of the functions H such that H(0) = 0 and |H(x + 1) -H(x)| = 1 for all x ∈ {0, . . . , L -1}. The space E

(1) L is the state space for the process described in Section 1.2. To H ∈ E L , we associate a function Ĥ :

[0, 1] → R defined by Ĥ(x) = L -1 H( Lx ), (4.1)
where p = y , defined for y ≥ 0, is the integer such that p ≤ y < p + 1. The map H → Ĥ is an isometry E L → L 2 (0, 1) when E L and L 2 (0, 1) are endowed with the respective scalar products

H, G E L = 1 L 3 x∈X L H(x)G(x), f, g L 2 = 1 0 f (x)g(x)dx. (4.2) Indeed, given H, G ∈ E L , we compute Ĥ, Ĝ L 2 (0,1) = L-1 x=0 x+1 L x L Ĥ(y) Ĝ(y)dy = L-1 x=0 1 L 3 H(x)G(x) = H, G E L . (4.3)
Since H → Ĥ is an isometry, a natural left-inverse is given by calculating the adjoint operator. This is easily done, and we obtain a map L 2 (0, 1) → E L , which, to h ∈ L 2 (0, 1) associates the function in E L given by

Jh(L) = 0, Jh(x) = L 2 x+1 L x L h(x)dx, x = 0, . . . , L -1. (4.4)
However, we will work preferably with the related application h → ȟ, defined by ȟ(x) = Lh(L -1 x). The reason of this modification is apparent in Proposition 4.5. If h is Lipschitz continuous on [0, 1] and h(1) = 0, then |Jh(x) -ȟ(x)| is bounded by Lip(h). This implies that

| Ĥ, h L 2 (0,1) -H, ȟ E L | ≤ Lip(h)L -2 sup x∈X L |H(x)|, (4.5)
for all H ∈ E L . Let h in be a continuous function on [0, 1], which is 1-Lipschitz continuous and satisfies the boundary conditions h in (0) = h in (1) = 0. Given such a function h in , we build an initial datum

H in ∈ E (1)
L for the evolution of the random interface. We want h in to be close to Ĥin in a certain norm. It is simpler to consider things in the space E L , in which case we require H in and the function ȟin to be at distance O(1) for a certain norm. Note that the graph of a profile

H ∈ E (1)
L is a subset of the lattice

R = {(x, H); x ∈ {0, • • • , L}, H ∈ Z x } ,
where we have set

Z x = 2Z if x is even, Z x = 2Z + 1 if x is odd.
To build H in , we draw the graph Gr L of ȟin . Then we choose the closest points of Gr L in R to obtain the graph of H in . We check that H in satisfies the constraint |H in (x + 1) -H in (x)| = 1 (it follows from the fact that h in is 1-Lipschitz continuous). We have then sup

x∈X L ȟin (x) -H in (x) ≤ 1 ⇒ sup x∈X L |Jh in (x) -H in (x)| ≤ 2, (4.6) hence Jh in -H in E L ≤ 2L -1 . This gives Ĥin -h in L 2 (0,1) ≤ 2L -1 . (4.7)
Let (H t ) be the Markov process described in Section 1.2 (we will show below in Section 4.2 that it is a Markov process indeed) that starts from H in . We fix a time T > 0 and consider the solution to the heat equation on [0, 1] with Dirichlet homogeneous boundary conditions and initial datum h in : this the function h ∈ L 2 (0, T ; H 1 0 (0, 1)) such that ∂ t h ∈ L 2 (0, T ; H -1 (0, 1)) and

∂ t h(t), g L 2 (0,1) + ∂ x h(t), ∂ x g L 2 (0,1) = 0, (4.8)
for all g ∈ H 1 0 (0, 1) and a.e. t ∈ (0, T ), and h(0) = h in , see [8, p.374]. We call such a function h a weak solution to the following problem:

∂ t h -∂ 2
x h = 0 in (0, +∞) × (0, 1), (4.9)

h(t, x) = 0 for (t, x) ∈ (0, +∞) × ({0} ∪ {1}), (4.10)
h(0, x) = h in (x) for x ∈ (0, 1). (4.11)

We will establish the following result. L satisfy (4.7), and let (H t ) be the Markov process described in Section 1.2 that starts from H in . Then the rescaled process ( ĤL 2 t ) converges to h in probability when L tends to +∞, in the sense that, for all T > 0, for all δ > 0, one has

lim L→+∞ P sup t∈[0,T ] ĤL 2 t -h(t, •) L 2 (0,1) > δ = 0.
(4.12)

Markov property

We will show in this part that the process (H t ) described in Section 1.2 is a Markov process and give the expression of its generator. First, the general procedure using "clocks", that transform discrete-time Markov processes into continuous-time Markov processes is analysed. We begin this step with a section of remainder about Poisson processes. In a second step, we study the discrete-time Markov process that gives rise to (H t ).

Poisson processes

P(N (t + s) -N (t) = k) = e -λs (λs) k k! . ( 4
P(Γ(A) = n) = e -µ(A) µ(A) n n! .
In the third item 3, we use the following convention: a random variable X with Poisson's law of parameter 0 is concentrated on 0: P(X = 0) = 1. Similarly, a random variable X with Poisson's law of parameter +∞ is concentrated on +∞: P(X = +∞) = 1.

(R d ) < +∞. Let A 1 , . . . , A k be some disjoints subsets of R d . Let n 1 , . . . , n k and n ∈ N be such that n 0 := n - k i=1 n i ≥ 0. Show that P(Γ(A 1 ) = n 1 , . . . , Γ(A k ) = n k |Γ(R d ) = n) = n! n 0 !n 1 ! • • • n k ! [ν(A 0 )] n0 • • • [ν(A k )] n k , (4.14) where A 0 = R d \ (A 1 ∪ • • • ∪ A k ), (4.15)
and ν is the normalized measure defined by

ν(A) = µ(A) µ(R d ) . ( 4

.16)

In the right-hand side of (4.14) appears the multinomial distribution with parameters n and

p 0 = ν(A 0 ), p 1 = ν(A 1 ), . . . , p k = ν(A k ).
This link between Poisson point processes and multinomial distribution will be exploited to give a construction of a Poisson point process. It will also be exploited in Exercise 4.6 below to complete Exercise 4.3.

2. Let µ be a finite measure on R d with no atoms. Let ν be the probability measure defined by (4.16) and let X 1 , . . . , X n be some iid random variables of law ν.

P(N (t 1 ) = n 1 , . . . , N (t k ) = n k ) = e -λ(t1-t0) (λ(t 1 -t 0 )) n1-n0 (n 1 -n 0 )! • • • e -λ(t k -t k-1 ) (λ(t k -t k-1 )) n k -n k-1 (n k -n k-1 )! , (4.18) for all 0 ≤ t 1 ≤ • • • ≤ t k and n 1 ≤ • • • ≤ n k .
We will need the following tools. Let t > 0.

Let U 1 , . . . , U n be some independent uniform random variables on [0, t]. The order statistics of (U 1 , . . . , U n ) is the rearrangement (U (1) , . . . , U (n) ) of the variables U i in increasing order:

U (1) < • • • < U (n) , {U (1) , . . . , U (n) } = {U 1 , . . . , U n }. Let ∆ denote the subset {0 < u 1 < u 2 < • • • < u n < t} of [0, t] n .
The variables U i are exchangeable, so the law of (U (1) , . . . , U (n) ) is given by ) be the filtration generated by (ξ t , N (t)) t≥0 . Then (ξ t ) t≥0 is a time-homogeneous Markov process with respect to (F t ) t≥0 , with transition operator and infinitesimal generator given by Π t = exp (-λt(Id -P 1 )) , L = -λ(Id -P 1 ), (4.20) respectively.

E ϕ(U (1) , . . . , U (n) ) = n! • • • ∆ ϕ(u 1 , . . . , u n )du 1 • • • du n . ( 4
Proof of Proposition 4.3. Note first that P n = P n 1 for all n ≥ 0. This is the semi-group property in discrete time. Then, we want to establish the following kind of Markov property: for all A ∈ F t , for all ϕ ∈ BM(E),

E 1 A ϕ(X n+N (t) ) = E 1 A P n ϕ(X N (t) ) . ( 4
E[ϕ(X N (t+s) )|F t ] = ∞ n=0 E[ϕ(X N (t+s) )1 N (t+s)-N (t)=n |F t ].
By independence, this gives

E[ϕ(X N (t+s) )|F t ] = ∞ n=0 P(N (t + s) -N (t) = n)E[ϕ(X N (t)+n )|F t ].
In the last summand, we replace

P(N (t + s) -N (t) = n) = e -λs (λs) n n! , E[ϕ(X N (t)+n )|F t ] = P n 1 ϕ(X N (t) ).
The summation over n gives E[ϕ(ξ t+s )|F t ] = (Π s ϕ)(ξ t ), where Π t is defined by (4.20). It follows that (ξ t ) t≥0 is a time-homogeneous Markov process with respect to (F t ) t≥0 . It is also clear that L = -(Id -P 1 ). To establish (4.21), we observe that each side of the equality defines a set-function, by dependance on A, which is a finite measure. By [3, Theorem 3.3], it is sufficient to prove (4.21) for all sets A in a class M which is a π-system generating F t , in the sense that σ(M) = F t . To that effect, we consider the class M of sets of the form

B ∩ D ∩ {N (t) = m}, where m ∈ N, B ∈ F X m , D ∈ F N t .
It is clear that M is a π-system. The σ-algebra F t is generated by all the random variables X N (t1) , . . . , X N (tj ) and N (s 1 ), . . . , N (s k ) for j, k ∈ N * and times t i , s i ≤ t. By considering all the possible values taken by N (t 1 ), . . . , N (t j ) and N (t), the event

X N (t1) ∈ Γ 1 , . . . , X N (tj ) ∈ Γ j , N (s 1 ) ∈ E 1 , . . . , N (s k ) ∈ E k ,
where Γ 1 , . . . , Γ j ∈ B(E), E 1 , . . . , E k ⊂ N, can be written as a union over

m 1 ∈ N, . . . , m j , m ∈ N of the intersection A := A 1 ∩ A 2 ∩ {N (t) = m} of the events A 1 = X m1 ∈ Γ 1 , . . . , X mj ∈ Γ j with the events A 2 = {N (t 1 ) = m 1 , . . . , N (t j ) = m j } ∩ {N (s 1 ) ∈ E 1 , . . . , N (s k ) ∈ E k }.
Since N is non-decreasing and t i ≤ t, the set A is possibly non-empty only if the integers m i are all smaller than m. In the latter case, we have A ∈ M. We conclude that σ(M) = F t . For A = B ∩ D ∩ {N (t) = m} ∈ M, we have then

E 1 A ϕ(X n+N (t) ) = P(D ∩ {N (t) = m})E [1 B ϕ(X

Markov property for the symmetric simple exclusion process

The evolution of the symmetric simple exclusion process is described in Section 1.2. Recall that we are in the situation where L = 2N , and that, to a given configuration η of particles, is associated the function H ∈ E L given by

H(x) = x-1 y=0 (2η(y) -1). (4.22)
The evolution of (H t ) can thus be described as follows 1. Let X L := {0, . . . , L -1}. Draw a family (T x ) x∈X L of independent exponential variables of parameter 1.

2. Select the point x * such that T x * = inf y∈X L T y .

3. Perform the transformation H Tx * -→ H Tx * according to the rule of evolution of the symmetric simple exclusion process.

Start over.

Let us first give some precisions on step 3. Then we will discuss the steps 1-2 can be replaced by the following procedure. Let

E (0) L = {H ∈ E L ; H(0) = 0}
Introduce the discrete Laplace operator ∆ D :

E (0) L → E (0) L defined by ∆ D H(x) = 0 if x = 0 or L and ∆ D H(x) = H(x + 1) + H(x -1) -2H(x), ∀x ∈ {1, . . . , L -1}, (4.23)
The index D in ∆ D is for "Dirichlet", since ∆ D is actually the discrete Laplace operator with homogeneous Dirichlet boundary conditions. Consider the transformation

H ← H + δ x ∆ D H (4.24) where δ x (y) = 1 x=y , x ∈ X L . (4.25)
We consider the graph of H (when H is extended as a piecewise affine function). Examining 4.25 shows that (4.24) is the transformation that flips a corner at x (local extremum) in a the graph of H into the opposite corner (nothing happens if H has no local extremum at x). We also consider the different possible configurations of particles, to observe that, when the site x is selected at time t, H t-becomes H t-+ δ x+k ∆ D H t-:

H t-← H t-+ δ x+k ∆ D H t- (4.26)
where k is a random variable (independent on the variables T y ) with Bernoulli distribution b(1/2): P(k = 1) = P(k = 0) = 1/2. Let us now discuss the steps 1-2. We assert that it can be replaced by the following procedure: draw a time T with exponential law of parameter L, select, independently a site x ∈ X L with uniform law (and then perform (4.26) at time t = T ). Indeed, if T and T are two exponential independent random variables of parameters λ and λ , then T ∧ T is also an exponential random variable of parameter λ + λ :

P(T ∧ T > t) = P({T > t} ∩ {T > t}) = P(T > t)P(T > t) = e -λt e -λ t = e -(λ+λ )t . Let p x (t) = P T x = inf y∈X L T y ; T x > t .
Clearly, p x (t) = p y (t) for all x, y ∈ X L . Since T := inf y∈X L T y is exponential of parameter L, this gives

p x (t) = 1 L y∈X L p y (t) 1 L P   z∈X L {T z = inf y∈X L T y ; T z > t}   ,
which is simply

p x (t) = 1 L P( T > t) = P(Y = x, T > t),
where Y is uniform in X L and independent on T . With that approach, we see that

H t = H N (t)
, where (N (t)) is a Poisson process of parameter L and (H n ) is an independent process that evolves in discrete time as follows

H n+1 = H n + δ Y+k ∆ D H n
The process (H n ) is Markov and time-homogeneous with transition operator P 1 given by

P 1 ϕ(H) = E H ϕ(H 1 ) = 1 L L-1 x=0 1 2 ϕ(H + δ x ∆ D H) + 1 2 ϕ(H + δ x+1 ∆ D H) = 1 L L-1 x=1 ϕ(H + δ x ∆ D H) + 1 2L ϕ(H + δ 0 ∆ D H) + 1 2L ϕ(H + δ L ∆ D H) (4.27)
From Proposition 4.3 and (4.27), we deduce the following result.

Theorem 4.4. Let E

(1)

L be the set of functions H : X L → R such that H(0) = 0 and |H x+1 -H x | = 1 for all x ∈ X L (in the case x = L -1, we use the convention H(L) = 0). Let ∆ D and δ be defined by (4.23) and (4.25) respectively. The symmetric simple exclusion process (H t ) described in Section 1.2 is a Markov process with generator L given by

L ϕ(H) = L-1 x=1 (ϕ(H + δ x ∆ D H) -ϕ(H)) + 1 2L (ϕ(H + δ 0 ∆ D H) -ϕ(H)) + 1 2L (ϕ(H + δ L ∆ D H) -ϕ(H)), (4.28)
with domain the set of functions ϕ : E

(1) L → R.

Deterministic limit

The result of Theorem (4.1) is a kind of law of large numbers (a "functional law of large numbers"). Indeed, let us introduce the average

H t = E [H t ].
The convergence (4.12) is a consequence of these two following facts:

1. after change of scale, the symmetric simple exclusion process is close to its average value with high probability: for all δ > 0,

lim L→+∞ P sup t∈[0,T ] ĤL 2 t -ĤL 2 t L 2 (0,1) > δ = 0, ( 4
∂ t H t -∆ D H t = 0 in (0, +∞) × {1, . . . , L -1}, (4.31)
H t (0) = 0 for all t ∈ (0, +∞), (4.32)

H 0 (x) = H in (x) for all x ∈ {1, . . . , L -1}. (4.33)
Different approaches to the convergence result (4.30) are possible. Our proof will be based on a spectral decomposition that will be exploited also to establish the averaging property (4.29) in Section 4.4.

Proposition 4.5 (Spectral basis). The Laplace operator with homogeneous Dirchlet boundary conditions in dimension 1, which is the operator -∂ 2

x , with domain

D(-∂ 2 x ) = h ∈ H 2 (0, 1); h(0) = h(1) = 0
admits a spectral basis (a k ) k∈N * , where a k (x) = √ 2 sin(πkx). This constitutes an orthonormal basis of L 2 (0, 1). The eigenvalue associated to

a k is µ k = π 2 k 2 . Let E (0)
L be the subset of E L constituted of the functions H such that H(0) = 0. The discrete Laplace operator -∆ D :

E (0) L → E (0)
L is self-adjoint and admits the spectral basis (ǎ k ) 1≤k≤L-1 . The eigenvalue associated to ǎk is ν k = 4 sin 2 πk 2L . Proof of Proposition 4.5. We simply give the proof of some assertions about the discrete case.

If we extend any H ∈ E (0)

L to the value L by setting

H(L) = 0, then for H, G in E (0) L , we easily check that -∆ D H = D -• D + H, where D + H(x) = H(x + 1) -H(x), D -H(x) = H(x) -H(x -1).

Then we use the formula D -H, G E

L = -H, D + G E L to get -∆ D H, G E L = D + H, D + G E L = H, -∆ D G E L . ( 4
h(t) = ∞ k=1 e -µ k t h in , a k L 2 (0,1) , (4.37)
and that H t is given by

H t = L-1 k=1 e -ν k t H in , ǎk E L . (4.38)
Regularity of functions can be expressed in terms of decay of the "Fourier" coefficients. This is what accounts for the following result. for all k ≥ 1, where (a k ) k∈N * is the orthonormal basis defined in Proposition 4.5.

Proof of Lemma 4.6. At time t, we have h(t, •), a k L 2 (0,1) = e -µ k t h in , a k L 2 (0,1) . It is sufficient to consider the case t = 0 therefore. The estimate (4.39) then follows from the fact that the function h in is 1-Lipschitz continuous. Indeed, integration by parts gives

h in , a k L 2 (0,1) = -h in , A k L 2 (0,1) , A k (x) = x 0 a k (y)dy = √ 2 πk (1 -cos(πkx)),
and then the bound

| h in , a k L 2 (0,1) | ≤ √ 2/πk.
We need a result similar to Lemma 4.6 on functions of the discrete variable x ∈ X L .

Lemma 4.7. There exists a constant

C ≥ 0 such that | H, ǎk E L | ≤ C k , | Ĥ, a k L 2 (0,1) | ≤ C k , (4.40) for all H ∈ E (1)
L , for all k ∈ {1, . . . , L -1}, where (a k ) k∈N * is the orthonormal basis defined in Proposition 4.5. One can take C = √ 2.

Proof of Lemma 4.7. This time we use a discrete integration by parts:

H, ǎk E L = 1 L 3 L-1 x=1 (H(x) -H(x -1)) B k (x), (4.41)
where

B k (x) := √ 2L L-1 y=x sin(kπy/L) satisfies |B k (x)| ≤ √ 2L 2 k -1 for all x ∈ X L . Indeed, we compute |B k (x)| = √ 2L Im L-1 y=x e iπky/L ≤ √ 2L 1 -e iπk(L-x)/L 1 -e iπk/L ≤ 2L √ 2 |1 -e iπk/L | .
We have

|1 -e iπk/L | = 2 sin(πk/(2L)) ≥ 2k/L, since sin(x) ≥ (2/π)x if x ∈ [0, π/2], which gives |B k (x)| ≤ √ 2L 2 k -1 as desired.
The product Ĥ, a k L 2 (0,1) satisfies an identity similar to (4.41), with

B k (x) := L 2 √ 2 L-1 y=x (y+1)/L y/L sin(πkz)dz.
Using the bound

|B k (x)| = √ 2L 2 πk | cos(πk) -cos(πkx/L)| ≤ 2 √ 2L 2 πk ,
we obtain the second estimate in (4.40).

Proof of the convergence (4.30). Let K(L)

satisfy lim L→+∞ K(L) = +∞, K(L) = o(L 2/5
K(L) k=1 h(t, •), a k L 2 (0,1) -H L 2 t , ǎk E L 2 . (4.43)
We use (4.5) and the fact that

H(x) ≤ L for all x ∈ X L when H ∈ E (1) L . Since Lip(a k ) = O(k), we obtain K(L) k=1 ĤL 2 t , a k L 2 (0,1) -H L 2 t , ǎk E L 2 = K(L) k=1 O(L -1 k) 2 = O(L -2 K(L) 3 ) = o(
K(L) k=1 e -µ k t h in , a k L 2 (0,1) -e -L 2 ν k t H in , ǎk E L 2 . ( 4
| ĥin (x) -Ĥin (x)| ≤ L -1 sup x∈X L | ȟin (x) -H in (x)| ≤ L -1 .
We have also sup

x∈[0,1] | ĥin (x) -h in (x)| = sup x∈[0,1] |h in ([xL]/L) -h in (x)| ≤ L -1 ,
since h in is 1-Lipschitz continuous. Finally, we can estimate the L 2 -norm by the L ∞ -norm to obtain h in -Ĥin L 2 (0,1) ≤ 2L -1 and

| h in , a k L 2 (0,1) -Ĥin , a k L 2 (0,1) | ≤ 2L -1 . ( 4
K(L) k=1 e -µ k t -e -L 2 ν k t 2 h in , a k 2 L 2 (0,1) . (4.47)
At that point, we need to compare the eigenvalues µ k to the rescaled eigenvalues

L 2 ν k . The two standard inequalities 2 π x ≤ sin(x) ≤ x, | sin(x) -x| ≤ x 3 , for 0 ≤ x ≤ π 2 , have the consequence that there exists a constant C ≥ 0 such that 4 π 2 µ k ≤ L 2 ν k ≤ µ k , µ k -L 2 ν k ≤ C k 3 L , ( 4.48)
for all k ∈ {1, • • • , L -1}. Using (4.39), we deduce that (4.47) is bounded from above by

C 2 T L -2 K(L) 5 h in 2 L 2 (0,1) , which is o(1) since K(L) = o(L 2/5
) by hypothesis. This concludes the proof.

Averaging

In this section, we will establish the convergence (4.29). We use (4.3) and Proposition 4.5, which give

ĤL 2 t -ĤL 2 t 2 L 2 (0,1) = L-1 k=1 | H L 2 t -H L 2 t , ǎk E L | 2 . ( 4
E (0) L , we obtain L ϕ k (H) = -ν k ϕ k (H), when H ∈ E (0)
L . Let us then apply Corollary 3.9 with ψ(t, H) = e ν k t ϕ k (H). The quantity (∂ t + L )ψ vanishes and we obtain that

M (k) t := e ν k t H t , ǎk E L -H in , ǎk E L (4.50)
and

Z (k) t := M (k) t 2 - t 0 e 2ν k s (L |ϕ k | 2 -2ϕ k L ϕ k )(H s )ds (4.51) are both martingales. Since t → E M (k) t
is constant, by the martingale property, and vanishes at t = 0, we have 0

= E M (k) t = e ν k t H t , ǎk E L -H in , ǎk E L .
Consequently our quantity of interest is

H t -H t , ǎk E L = e -ν k t M (k)
t . We can use the Doob's martingale inequality (Theorem 2.2 with p = 2), and the trivial bound e -ν k t ≤ 1, to obtain the estimate

P sup t∈[0,L 2 T ] | H t -H t , ǎk E L | > a ≤ 4 a 2 E|M (k) L 2 T | 2 . (4.52) Since E Z (k) t
= 0, (4.51) gives us the bound from above

P sup t∈[0,L 2 T ] | H t -H t , ǎk E L | > a ≤ 4 a 2 L 2 T 0 e 2ν k s (L |ϕ k | 2 -2ϕ k L ϕ k )(H s )ds. ( 4
L-1 k=K(L) | H L 2 t -H L 2 t , ǎk E L | 2 ≤ C 2 k≥K(L) 1 k 2 ≤ C 2 K(L) -1 . (4.54)
We have only to consider the indexes k ≤ K(L) hence. If this is not exactly a bounded range of indexes, we will see that the loss of the e -ν k t factor in (4.52) is not a problem. We go back to the computation of the carré du champ now. We can write ϕ k as the sum over x ∈ {1, . . . , L-1} of L -3 ǎk (x)π x , where π x is the evaluation at x. We need to compute L (π x ⊗π y ) therefore, where π x ⊗ π y (H) := H(x)H(y). By (4.28), this is

L (π x ⊗ π y )(H) = L-1 z=0 [(H(x) + δ z (x)∆ D H(x))(H(y) + δ z (y)∆ D H(y)) -H(x)H(y)] ,
which is equal to

H(y)∆ D H(x) + H(x)∆ D H(y) if x = y, and to 2H(x)∆ D H(x) + |∆ D H(x)| 2 if x = y. We obtain (L |ϕ k | 2 -2ϕ k L ϕ k )(H) = 1 L 6 L-1 x=1 |ǎ k (x)| 2 |∆ D H(x)| 2 . (4.55) If H ∈ E (1) L , then |∆ D H(x)| ≤ 2 for all x.
This shows that the right-hand side of (4.55) is bounded by 4L -3 ǎk

2 E L . Since ǎk is normalized, we conclude finally that 0 ≤ (L |ϕ k | 2 -2ϕ k L ϕ k )(H) ≤ 4L -3 , (4.56) for all H ∈ E (1)
L . Let θ ∈ (0, 1/2) be fixed and let A L denote the event

A L = 1≤k<K(L) sup t∈[0,L 2 T ] | H t -H t , ǎk E L | ≤ L -θ .
Let us choose K(L) = (log(L)) 1/3 . We will show that we have then lim L→+∞ P(A L ) = 1. By (4.49) and (4.54) and, we see that

sup t∈[0,T ] H L 2 t -H L 2 t 2 L 2 (0,1) ≤ C 2 (log(L)) -1/3 + (log(L)) 1/3 L -2θ ,
when A L is realized, so it is clearly sufficient to prove lim L→+∞ P(A L ) = 1 to get the desired result. The union bound gives

P(A c L ) ≤ 1≤k<K(L) P sup t∈[0,L 2 T ] | H t -H t , ǎk E L | > L -θ .
Using (4.53) and ( 4.56), we obtain

P(A c L ) ≤ 16L 2θ 1≤k<K(L) L 2 T 0 e ν k s L -3 ds ≤ 16L 2θ-1 1≤k<K(L) e ν k L 2 T ν k L 2 . (4.57)
From the inequality 2 π x ≤ sin(x) ≤ x for 0 ≤ x ≤ π 2 , we infer that ν k L 2 is bounded between 16k 2 and 4π 2 k 2 . We deduce then from (4.57) that

P(A c L ) ≤ L 2θ-1 1≤k<K(L) e 4π 2 k 2 T k 2 ≤ SL 2θ-1 e 4π 2 T (log(L)) 2/3 ,
where S = k≥1 k -2 = π 2 /6 is finite. This shows that lim L→+∞ P(A L ) = 1, as required.

Conservation laws and the Finite Volume method

Discrete conservation laws, continuous limit

We go back to Section 1.1 of the introductory part. We considered a discrete evolution equation

u n+1 K = u n K + ∆t n |K| L∈N (K)
|K|L|Q n L→K .

(5.1)

The quantity u n K represents the density of a certain extensive quantity u in the space-time cell K × (t n , t n+1 ). The time grid is constituted from the discrete times

t 0 < t 1 < • • • < t n < • • • ,
where t n = n∆t, n ∈ N for a fixed time-step ∆t. The space R d is partitioned as follows: we are given a family T of disjoint open bounded sets such that:

• for all distinct K, L ∈ T , the interface K ∩ L is contained in an hyperplane of R d ,
• up to a negligible set for the d-dimensional Lebesgue measure, the union of the sets

K in T is equal to R d .
We also use the following notations:

• K|L is the intersection K ∩ L, • |K| is the d-dimensional Lebesgue measure of K and |K|L| is the d-1-dimensional Lebesgue measure of K|L, K L M N K|L Figure 2: A mesh in R 2 • N (K) = {L ∈ T ; 0 < |K|L| < +∞} is the set of neighbors of K,
• when K ∈ T and L ∈ N (K), n K→L is the outward unit normal to K along K|L and Q n K→L is some numerical flux, ∆t Q n K→L representing the amount of u that has passed from K to L trough the interface K|L on the time interval (t n , t n+1) .

In the introductory section 1.1, we also assumed that the condition

Q n L→K = -Q n K→L , (5.2)
for all n ∈ N, for all K, L ∈ T being neighbors, is satisfied. The condition (1.3) ensures that, in the time interval (t n , t n+1 ), the (algebraic) quantity of u transferred from the cell K to the cell L is the exact opposite of the quantity of u transferred from L to K: no loss or creation of u occurs at the interface K|L. Define

h = sup K∈T diam(K), u h,∆t = n∈N K∈T u n k 1 K×[tn,tn+1) . (5.3)
Under some additional conditions on the the discrete fluxes Q n K→L , we will study the limit when h, ∆t → 0 of u h,k . We will show that we obtain in the limit a conservation law

∂ t u + div x (Q) = 0, (5.4)
where Q = Q(x, t). There are various instances of such conservation laws. For example the heat equation ∂ t -div(K∇u) = 0 or the diffusion equation ∂ t -div(D∇u) = 0, the flux being then given by the the Fourier law, Q = -K∇ x u, or the Fick law, Q = -D∇u respectively. An other example is the continuity equation

∂ t u + div x (au) = 0, (5.5)
where a is a vector-field over R d . The continuity equation can be rewritten

∂ t u + a • ∇ x u + div x (a)u = 0, (5.6)
and coincides with the transport equation ∂u + a • ∇ x u = 0 when a is divergence-free. We can also mention the Fokker-Planck equation of the kinetic theory of gases,

∂ t f + v • ∇ x f + F (x) • ∇ v f = div v (∇ v f + vf ), (5.7)
which is of the form (1.4), or more precisely

∂ t f + div x,v (Q) = 0, with a flux Q = vf F (x)f -(∇ v f + vf ) .
In all these examples, the equations are linear. We can also consider the non-linear equations

∂ t u -∆φ(u) = 0, (5.8)
or

∂ t u + div x (A(u)) = 0, (5.9)
where A : R → R d . The hydrodynamic limits of particles in stochastic interaction that we will consider later can be of very different types, including in particular (5.8) and (5.9). Although both (5.8) and (5.9) may be considered in our framework, we will restrict our attention to models with (5.9) as continuous limit. We refer to [START_REF] Eymard | Convergence of a finite volume scheme for parabolic degenerate equations[END_REF] for the derivation of (5.8).

Discrete fluxes

We will begin this section with a discussion on expected discrete fluxes in some specific situations, before giving the description of our general framework. First let us start from (5.9), and see how this can approximate by a discrete system of equations (this is the usual procedure in numerical analysis). Let us integrate (5.9) on a space-time cell K × (t n , t n+1 ). We assume that u is smooth for simplicity (beware that this is typically not the case of the solutions to (5.9)). Using Stokes' formula, we obtain

K u(t n+1 , x)dx - K u(t n , x)dx = - tn+1 tn ∂K A(u) • ndσdt. ( 5.10)
We use the approximation

K u(t m , x)dx ∼ |K|u m K and develop ∂K A(u) • ndσ = L∈N (K) K|L A(u) • n K→L dσ. ( 5.11)
This gives us the equation

u n+1 K = u n K - 1 |K| L∈N (K) tn+1 tn K|L A(u) • n K→L dσdt. ( 5.12)
We would like to use an approximation like

tn+1 tn K|L A(u) • n K→L dσdt ∆t n |K|L|A(u n M ) • n K→L ,
where M is either the cell K or the cell L, but, precisely, how to make this choice? The study of linear equations gives some insight on this problem.

Discrete fluxes for linear equations

Consider the continuity equation (5.5). Assume for simplicity that the vector field a is constant. Then (5.5) is equivalent to the transport equation (5.6). What one would observe by looking at the behavior of the solution to (5.6) on the interface K|L between the times t n and t n+1 is a flow of u across K|L in the direction u. Let n K→L denote the unit normal to K along K|L in the direction of L. The value of |a • n K→L | ponders the amplitude of the flux across K|L, while the sign of a • n K→L determines the direction of the flow of u across K|L. It is quite natural then to set

Q n K→L = a • n K→L u n K if a • n K→L ≥ 0.
The condition of conservation (5.2) will be satisfied then if we also set

Q n K→L = a • n K→L u n L when a • n K→L ≤ 0.
This can be summed up in the formula

Q n K→L = (a • n K→L ) + u n K -(a • n K→L ) -u n L . ( 5.13)
A generalization of (5.14) in the case where a is a non-constant vector field is

Q n K→L = a + K→L u n K -a - K→L u n L , (5.14)
where

a K→L = 1 |K|L| K|L a(x) • n K→L dσ(x). ( 5.15)
A further generalization of (5.13) can be given in the case where the flux A(u) in (5.9) actually depends on x also and is of the form A(x, u) = f (u)a(x), where f is a non-decreasing locally Lipschitz function R → R and a : R d → R d is a divergence-free smooth vector field. Indeed, (5.9) can be rewritten as the non-linear transport equation ∂ t u + f (u)a • ∇ x u = 0 and, using the definition (5.15), the sign of f (u)a K→L is the sign of a K→L since f (u) ≥ 0. In that situation, one can consider the flux

Q n K→L = a + K→L f (u n K ) -a - K→L f (u n L ). (5.16)

General monotone fluxes

Consider the case of a general flux A in (5.9). By general flux A, we mean any function A : R → R d that is locally Lipschitz continuous. Sometimes, we also the consider the extension to some fluxes A(x, u) depending also on the space variable. What kind of numerical flux may be compatible with such an expected limit as (5.9)? Inspired by the examples in Section 5.3, we look for some numerical fluxes Q n K→L given by a relation

Q n K→L = A K→L (u n K , u n L ), (5.17)
where A K→L is a function with the following properties:

1. compatibility with the flux A:

A K→L (v, v) = A(v) • n K→L , ( 5.18)
for all v ∈ R, 2. regularity: the function A K→L is locally Lipschitz continuous: for every R > 0, there exists a constant L A (R) ≥ 0 such that

|A K→L (v, w) -A K→L (v , w )| ≤ L A (R)(|v -v | + |w -w |), (5.19)
for all v, v , w, w ∈ [-R, R] and for all neighboring cells K, L ∈ T , 3. monotony: for all v, w ∈ R, the function A K→L (v, •) is non-increasing, while the function

A K→L (•, w) is non-decreasing,

conservation property:

A K→L (v, w) = -A L→K (w, v), (5.20)
for all v, w ∈ R and for all neighboring cells K, L ∈ T .

If we choose the definition (5.17) of the flux, then (5.20) yields the conservation property (5.2).

There is some redundancy in the properties required above: (5.20) and the single fact that A K→L (v, •) is non-increasing implies that A K→L (•, w) is non-decreasing for instance. In the next two paragraphs we infer some consequences on the discrete evolution equation (5.1) of (5.17), (5.18), (5.19), (5.20) and the monotony properties of A K→L .

Exercise 5.1

(Godunov flux, Engquist-Osher flux). Define A G K→L (v, w) as follows: if v ≤ w, then A G K→L (v, w) is the minimum value of u → A(u) • n K→L on the interval [v, w]. If w ≤ v, then A G K→L (v, w) is the maximum value of u → A(u) • n K→L on the interval [w, v]. Define also A EO K→L (v, w) by the formula A EO K→L (v, w) = v 0 (a(ξ) • n K→L ) + dξ - w 0 (a(ξ) • n K→L ) -dξ,
where a(u) = A (u). Show that A G K→L and A EO K→L have the required properties and show that they coincide with the upwind flux (5.13) in the linear case A(u) = au. The solution to Exercise 5.1 is here.

Constants as solutions

Any constant function u n K ≡ v is solution to (5.1). By (5.18), we have indeed

L∈N (K) |K|L|Q n K→L = L∈N (K) |K|L|A(v) • n K→L = L∈N (K) K|L A(v) • n K→L dσ(x).
We use the Stokes formula

L∈N (K) K|L Ψ(x) • n K→L dσ(x) = K div Ψ(x)dx, (5.21)
to obtain

L∈N (K)
|K|L|Q n K→L = 0, as desired.

Exercise 5.2 (Spatially dependent flux). Assume that A(x, u) satisfies the divergence-free condition (div x A)(x, u) = 0 for all u ∈ R. Assume also that Q n K→L is given by (5.17), where A K→L satisfies the following generalized version of (5.18):

A K→L (v, v) = 1 |K|L| K|L A(x, v) • n K→L dσ(x). ( 5.22)
Show that constant are solutions. The solution to Exercise 5.2 is here.

Asymptotic behavior

We consider the behavior of the numerical solution to (5.1) when the characteristic scales h and ∆t get smaller and smaller. Let (∆t (k) ) be a sequence of positive reals that converge to 0, let (T k ) be a sequence of meshes that are Z d -periodic and such that h k := sup K∈T k diam(K) tends to 0 when k → +∞. We assume that (5.29) is satisfied for all k, for all K ∈ T k , where α is independent on k. We also assume that (5. [START_REF] Pazy | Semigroups of Linear Operators and Applications to Partial Differential Equations[END_REF]) is satisfied with a Lipschitz constant L A (R) independent on k. Let (u 0 K ) K∈T k be given by (5.25), where

u 0 ∈ L ∞ (T d ). Consider the CFL condition sup n≥0 ∆t (k) n ≤ ∆t (k) L A (R) ≤ α 2 h k , ( 5.43)
where

R ≥ u 0 L ∞ (T d ) .
Let T > 0 be fixed. By Proposition 5.3, the solution

u (k) := u h k ,∆t (k) of (5.1) satisfies the bound u (k) L ∞ (T d ×(0,T )) ≤ R for all k.
Consequently, there is a subsequence still denoted (u (k) ) which converges to a certain function u in L ∞ (T d × (0, T )) for the weak- * topology. We would like to show that u is solution to the conservation law (5.9). In the case where A is not a linear function, there are two difficulties to establish this:

1. we use a weak mode of convergence (convergence in L ∞ (T d × (0, T )) for the weak- * topology), which is not sufficient in all generality to deal with the convergence of non-linear terms, 2. the theory of the Cauchy Problem for (5.9) in L ∞ requires a specific treatment, via the use of entropy solutions.

We will establish the convergence of (u (k) ) towards a solution of (5.9) in the linear case only, see Section 5.10. Some additional estimates on u (k) are necessary for this, and we will give them in the following section 5.7, for a general numerical fluxes, associated, via (5.18), to a not-necessarily linear flux A. We refer to [START_REF] Eymard | Finite volume methods[END_REF]Chapter 6] for the proof of convergence of (5.1) in the general case.

Energy estimate

Consider the parabolic equation

u t + div(A(u)) -η∆u = 0 in T d × (0, +∞).
(5.44)

Here η > 0 is supposed to be small. The flux in (5.44) is A(u) -η∇u. This is a perturbation of the flux A(u). The addition of the term -η∇u has a stabilizing effect, of the same nature as the stabilizing effect discussed at the end of Section 5.5, in relation with the monotony properties of the numerical fluxes. In (5.44), the additional term -η∆u has a positive contribution in the energy estimate: if we multiply (5.44) by u (say, a smooth solution) and integrate over T d ×(0, t), we obtain

t 0 1 2 d dt T d u 2 dxds + t 0 T d u div(A(u))dxds -η t 0 T d u∆udxds = 0. (5.45)
We develop the term

u div(A(u)) = uA (u) • ∇u = B (u) • ∇u = div(B(u)), B (u) := uA (u),
and, using periodicity, we obtain

1 2 T d |u(x, t)| 2 dx + η t 0 T d |∇u| 2 dxds ≤ 1 2 T d |u 0 | 2 dx.
We will establish a similar result in the discrete case.

The remaining term in the right-hand side of (5.51) will be absorbed in J ∆x , by means of the CFL condition. The summation formula (5.40) and the conservation property (5.20) give the following expression of J ∆x :

J ∆x = 1 2 N -1 n=0 ∆t n K∈T L∈N (K) u n K {A K→L (u n K , u n L ) -A K→L (u n K , u n K )} -u n L {A K→L (u n K , u n L ) -A K→L (u n L , u n L )}. (5.52)
Denote by ψ K→L an anti-derivative of z → z d dz A K→L (z, z). Integration by parts shows that

ψ K→L (v) -ψ K→L (w) = v{A K→L (v, v) -A K→L (v, w)} -w{A K→L (w, w) -A K→L (v, w)} + v w {A K→L (v, w) -A K→L (z, z)}dz. (5.53) Taking w = u n L , v = u n K in (5.53) shows that J ∆x = 1 2 N -1 n=0 ∆t n    K∈T L∈N (K) u n K u n L {A K→L (u n K , u n L ) -A K→L (z, z)}dz + R n ∆x    , ( 5.54)
where the remainder term is

R n ∆x = - 1 2 K∈T L∈N (K) ψ K→L (u n K ) -ψ K→L (u n L ).
The cancellation property (5.23) and (5.40) give R n ∆x = 0. We conclude that J ∆x = D(t N ). The estimate (5.47) will be established (as a consequence of (5.51)) if we can prove that 1 2

N -1 n=0 K∈T |K||u n+1 K -u n K | 2 ≤ (1 -ξ)J ∆x .
(5.55)

We use Equation (5.24) and the Cauchy-Schwarz inequality to get

u n+1 K -u n K 2 ≤ (∆t) 2 |∂K| |K| 2 L∈N (K) |K|L||A K→L (u n K , u n L ) -A K→L (u n K , u n K )| 2 .
The CFL condition (5.46) gives then (5.55) with a term J * ∆x instead of J ∆x , where

J * ∆x = 1 4L A (R) N n=0 ∆t n K∈T L∈N (K) |K|L||A K→L (u n K , u n L ) -A K→L (u n K , u n K )| 2 .
To conclude, we show that J * ∆x ≤ J ∆x = D(t N ). To that purpose, we use the following inequality:

r 0 B(z)dz ≥ 1 2 Lip(B) B(r) 2 , r ∈ [0, R] ( 5
for all test-function ϕ ∈ C ∞ c (T d × [0, T ))
, where µ i h,∆t , i ∈ {0, 1, 2)} are some non-negative measures on T d × [0, T ] which satisfy the estimate

µ i h,∆t (T d × [0, T ]) ≤ C(∆t 1/2 + h 1/2 + ω L 1 (u 0 ; h)), (5.63)
where C is a constant depending only on the dimension d, on T , on the constant α in (5.29), on R, on L A (R) (cf. (5.19)), and on the constant ξ in (5.46).

Remark 5.4 (Entropy solutions). When A is non-linear, weak solutions to (5.60) are non unique.

The Cauchy Problem for (5.9) is solved in the class of weak entropy solutions. A function u ∈ L ∞ (T d × (0, T )) is said to be a weak entropy solution to (5.9) on (0, T ) with initial datum

u 0 if T 0 T d (η(u)ϕ t + Φ(u) • ∇ x ϕ)dxdt + T d η(u 0 (x))ϕ(x, 0)dx ≥ 0, (5.64)
for all non-negative test-function ϕ ∈ C ∞ c (T d × [0, T )) and all entropy, entropy-flux pair (η, Φ). This means that η is of class C 2 , convex, Φ is locally lipschitz continuous, Φ (u) = η (u)A (u) for a.e. u ∈ R. Actually, it is sufficient to establish (5.60) for a family of generating entropy, entropy-flux pairs. One generally considers the Kruzhkov entropies η(u) = |u -r|, where the parameter r runs in R. Such a η is not of class C 2 , but the associated flux is well defined. We can also work with the semi Kruzhkov entropies η ± (u) = (u -r) ± . The associated fluxes are

Φ + (u; r) = A(u ∨ r) -A(r), Φ -(u; r) = A(u) -A(u ∧ r).
(5.65)

We can see on the expressions (5.36) and (5.65) (we take v n K ≡ r in (5.36)) that we have already established a discrete version of (5.64):

(u n+1 K -r) + ≤ (u n K -r) + + ∆t n |K| L∈N (K) |K|L|[Φ K→L (u n K , u n K ; r) -Φ K→L (u n K , u n L ; r)], (5.66)
where Φ K→L (v, w; r) = A K→L (v ∨ r, w ∨ r) -A K→L (r, r). If we start from (5.66) and adapt in a suitable way the proof of Theorem 5.5, we can establish that u h,∆t is an approximate weak entropy solution to (5.9) on (0, T ) with initial datum u 0 in the sense that (5.67) for all non-negative test-function ϕ ∈ C ∞ c (T d × [0, T )) and for all r ∈ R, where µ h,∆t satisfies an estimate similar to (5.63). See [START_REF] Eymard | Finite volume methods[END_REF].

T 0 T d (η ± (u h,∆t ; r)ϕ t + Φ ± (u h,∆t ; r) • ∇ x ϕ)dxdt + T d η ± (u 0 (x); r)ϕ(x, 0)dx ≥ -µ 0 h,∆t , |ϕ| -µ 1 h,∆t , |∂ t ϕ| -µ 2 h,∆t , |∇ x ϕ| ,
Proof of Theorem 5.5. Let ϕ ∈ C ∞ c (T d × [0, T )).
We first look at the error done at initial time. Define the error ε 0 (ϕ) by the formula

ε 0 (ϕ) = T d (u 0 (x) -u h,∆t (x, 0))ϕ(x, 0)dx.
(5.68)

By decomposition of the integral in (5.68), we have

ε 0 (ϕ) = K∈T K (u 0 (x) -u 0 K )ϕ(x, 0)dx.
For x ∈ K, u 0 (x) -u h,∆t (x, 0) is the average over K of y → u 0 (x) -u 0 (y). Using Fubini's theorem, this gives the inequality |ε 0 (ϕ)| ≤ µ 0 h,∆t (|ϕ|), where

µ 0 h,∆t (ψ) = K∈T K 1 |K| K |u 0 (x) -u 0 (y)|ψ(x, 0)dxdy
In particular, we have

|µ 0 h,∆t (T d × [0, T ])| ≤ K∈T K 1 |K| K |u 0 (x) -u 0 (y)|dxdy.
This can be written

|µ 0 h,∆t (T d × [0, T ])| ≤ K∈T 1 |K| x∈T d y∈K 1 K (x)|u 0 (x) -u 0 (y)|dxdy.
We do the change of variable y = x + z to obtain

|µ 0 h,∆t (T d × [0, T ])| ≤ K∈T 1 |K| x∈T d z∈K-x 1 K (x)|u 0 (x) -u 0 (x + z)|dxdz,
and thus

|µ 0 h,∆t (T d × [0, T ])| ≤ K∈T 1 |K| x∈T d z∈B(0,h) 1 K (x)|u 0 (x) -u 0 (x + z)|dxdz, since K -x ⊂ B(0, h) if x ∈ K.
We use the first bound of (5.29) and the fact that the sum over K of 1 K (x) is 1 for a.e. x to get

|µ 0 h,∆t (T d × [0, T ])| ≤ 1 αh d x∈T d z∈B(0,h) |u 0 (x) -u 0 (x + z)|dxdz,
We can exchange the integrals in x and z then to obtain

|µ 0 h,∆t (T d × [0, T ])| ≤ |B(0, h)| αh d sup |z|≤h x∈T d |u 0 (x) -u 0 (x + z)|dxdz.
This gives the first estimate

|µ 0 h,∆t (T d × [0, T ])| ≤ α -1 |B(0, 1)|ω(u 0 ; h).
(5.69)

Let us now study the term

I t = T 0 T d u h,∆t ϕ t dxdt + T d u h,∆t (x, 0)ϕ(x, 0)dx.
Let N ∈ N be such that t N -1 < T ≤ t N . Since ϕ is compactly supported in T d × [0, T ), we can assume that T = t N . We expand I t as

I t = N -1 n=0 K∈T |K|u n K (ϕ K (t n+1 ) -ϕ K (t n )) + K∈T |K|u 0 K ϕ K (0),
where ϕ K (t) is the average value of ϕ(•, t) on the cell K. A discrete integration by parts gives

I t = - N -1 n=0 K∈T |K|(u n+1 K -u n K )ϕ K (t n+1 ).
(5.70)

We proceed similarly with the term

I x = T 0 T d A(u h,∆t ) • ∇ x ϕdxdt.
We expand I x as

I x = N -1 n=0 K∈T tn+1 tn K A(u n K ) • ∇ x ϕdxdt.
By the Stokes formula, this gives

I x = N -1 n=0 ∆t K∈T L∈N (K) |K|L|A(u n K ) • n K→L ϕ n K|L , (5.71)
where ϕ n K|L is the average of the function ϕ on K|L × (t n , t n+1 ). We use the consistency property (5.18)

to write A(u n K ) • n K→L = A K→L (u n K , u n K ).
We also add a corrective term to the sum in (5.71) to obtain

I x = N -1 n=0 ∆t K∈T L∈N (K) |K|L|(A K→L (u n K , u n K ) -A K→L (u n K , u n L ))ϕ n K|L .
(5.72)

By the anti-symmetry property of the term A K→L (u n K , u n L ))ϕ n K|L (cf. (5.20)) and the summation formula (5.40), (5.71) and (5.72) coincide indeed. Let us now denote by ϕ n K the average value of the function ϕ over K × (t n , t n+1 ). If we replace the quantities ϕ K (t n+1 ) in (5.70) and ϕ n K|L in (5.72) by ϕ n K , then we obtain I t + I x = 0. This follows from (5.24). Consequently, we have I t + I x = ε 1 (ϕ) + ε 2 (ϕ), where

ε 1 (ϕ) = N -1 n=0 K∈T |K|(u n+1 K -u n K )(ϕ n K -ϕ K (t n+1 )),
and

ε 2 (ϕ) = N -1 n=0 ∆t K∈T L∈N (K) |K|L|(A K→L (u n K , u n K ) -A K→L (u n K , u n L ))(ϕ n K|L -ϕ n K ).
To conclude to (5.62), we need to examine the error terms ε 1 (ϕ) and ε 2 (ϕ). Since In particular, the total mass of µ 1 h,∆t is

µ 1 h,∆t (T d × [0, T ]) = N -1 n=0 ∆t K∈T |K||u n K -u n+1 K |.
(5.74)

By the Cauchy-Schwarz inequality and (5.58), we have

µ 1 h,∆t (T d × [0, T ]) 2 ≤ T 1 -ξ ξ u 0 2 L 2 (T d ) ∆t.
(5.75)

Similarly, we develop

ϕ K|L -ϕ K = 1 |K|L||K| K|L K |ϕ(x) -ϕ(y)|dxdσ(y)
and use the development ϕ(x) -ϕ(y) = We have |x -y| ≤ h when x ∈ K, y ∈ K|L, so

1 0 ∇ϕ(ry + (1 -r)x) • (x -y)dr to obtain |ε 2 (ϕ)| ≤ µ 2 h,∆t , |∇ϕ| , where ψ, µ 2 h,∆t := N -1 n=0 K∈T L∈N (K) |A K→L (u n K , u n K ) -A K→L (u n K , u n L )| × 1 |K|
µ 2 h,∆t (T d × [0, T ]) ≤ h N -1 n=0 ∆t K∈T L∈N (K) |K|L||A K→L (u n K , u n K ) -A K→L (u n K , u n L )|. (5.77)
We use the Cauchy-Schwarz inequality and the estimate (5.59) to get the bound

µ 2 h,∆t (T d × [0, T ]) 2 ≤ h 2 ΓL A (R) u 0 2 L 2 (T d ) .
The factor Γ is

Γ = N -1 n=0 ∆t K∈T L∈N (K) |K|L|| = T K∈T |∂K|.
By (5.29), we have the bound Γ ≤ T α -2 h -1 , which shows that

µ 2 h,∆t (T d × [0, T ]) 2 ≤ T α -2 L A (R) u 0 2 L 2 (T d ) h. (5.78)
We can bound the L 2 -norm of u 0 by R in (5.75) and (5.78). This gives the desired estimate (5.63).

Convergence in the linear case

We restrict now our analysis to the case of a linear flux A: A(u) = au. In this context, we consider a possibly non-constant vector field a. More precisely, we will assume that a ∈ C 1 (T d ; R d ) and that a is divergence free: div(a(x)) = 0 for all x ∈ T d . We consider then the scheme (5.1) with a numerical flux given by (5.14)-(5.15), which is called the upwind, or upstream, flux. We have then (5.17) with some numerical flux functions

A K→L (v, w) = a + K→L v -a - K→L w (5.79)
which satisfies all the properties listed in Section 5.4, with L A (R) = a L ∞ (T d ) . We will admit that Theorem 5.5 remains valid, in the sense that we have

T 0 T D (u h,∆t ϕ t + u h,∆t a(x) • ∇ x ϕ)dxdt + T d u 0 (x)ϕ(x, 0)dx ≤ µ 0 h,∆t , |ϕ| + µ 1 h,∆t , |∂ t ϕ| + µ 2 h,∆t , |∇ x ϕ| , (5.80)
and (5.63). In the asymptotic situation ∆t → 0, h → 0 described in Section 5.6.3, we can pass to the limit in (5.80). This shows that u is a weak solution to (5.5) on (0, T ) with initial datum u 0 , in the following sense (similar to Def. 5.4).

Definition 5.5 (Weak solution). Let

u 0 ∈ L ∞ (T d ). A function u ∈ L ∞ (T d × (0, T )
) is said to be a weak solution to (5.5) on (0, T ) with initial datum u 0 if

T 0 T d u(ϕ t + a(x) • ∇ x ϕ)dxdt + T d u 0 (x)ϕ(x, 0)dx = 0, (5.81)
for all test-function ϕ ∈ C ∞ c (T d × [0, T )).
We use then the following theorem.

Theorem 5.6. Let u 0 ∈ L ∞ (T d ) and T > 0. The continuity equation (5.5) admits a unique weak solution in L ∞ (T d × (0, T )) with initial datum u 0 . It is given explicitly by u(x, t) = u 0 • Φ t (x), where (Φ t ) is the flow associated to the ODE ẋ = a(x) and Φ t is the inverse4 of x → Φ t (x).

Exercise 5.6 (Uniqueness in transport equations). Prove Theorem 5.6 (beware, this is not obvious). The solution to Exercise 5.6 is here.

Error estimate in the linear case

Our aim in this section and the following ones is to establish the following result.

Theorem 5.7.

Let u 0 ∈ L ∞ ∩ BV(T d ) and T > 0. Let A(x, u) = a(x)u, where a ∈ C 1 (T d ; R d ) is divergence-free. Let u h,
for all ϕ ∈ C 1 c (U ; R d ).
The sup in (5.83) is then equal to κ(U ). Proof of Theorem 5.8. In essential, the proof is an application of the theorem of representation of Riesz. We take as a reference Theorem 6.19 in [START_REF] Rudin | Real and complex analysis[END_REF]. In [START_REF] Rudin | Real and complex analysis[END_REF], the result is given for a functional of complex-valued functions. Since we need to consider a functional of vector valued functions, we will come back on the main steps of the proof of Theorem 6.19 in [START_REF] Rudin | Real and complex analysis[END_REF]. For simplicity, we will use the same notations as Rudin, except that vector-valued function are denoted using bold fonts. Consider the functional

Φ(f ) = - U u div(f )dx It is defined for f ∈ C 1 c (U ; R d )
. By (5.83), it can be extended to a linear continuous functional (still denoted Φ) on C 0 (U ; R d ). We consider then the further extension to C 0 (U ; C d ) defined by Φ(f ) := Φ(f 1 ) + iΦ(f 2 ), where f 1 is the real part of f and f 2 the imaginary part of f . Our aim is to prove that there exists a non-negative regular finite measure λ on U and a Borel map

g : U → R d such that |g(x)| = 1 for λ-a.e. x ∈ U and Φ(f ) = U f • gdλ, (5.88)
for all f ∈ C 0 (U ; R d ), where (f • g)(x) = d i=1 f i (x)g i (x). Let us focus on the "factor" λ in (5.88). If (5.88) is satisfied, then the functional

ϕ → U ϕdλ, defined for ϕ ∈ C c (U ; R), dominates Φ in the sense that, if ϕ ≥ 0, then sup |Φ(h)|; h ∈ C c (U ; C d ), |h| ≤ ϕ ≤ U ϕdλ.
(5.89)

For ϕ ∈ C c (U ; R + ), we define Λ(ϕ) as the left-hand side of (5.89):

Λ(f ) = sup |Φ(h)|; h ∈ C c (U ; C d ), |h| ≤ ϕ . ( 5

.90)

This can be seen as a functional analogue to (5.85). Our aim is to show that we have the representation

Λ(ϕ) = U ϕdλ. (5.91) For a general ϕ ∈ C c (U ; R), we set Λ(ϕ) = Λ(ϕ + ) -Λ(ϕ -).
It is easy to see that this defines a continuous functional on C c (U ; R) which is positive. We will show that Λ is actually a linear functional (see below). By the representation theorem of Riesz, [20, Theorem 2.14], there exists a non-negative regular finite measure λ on U such that (5.91) is satisfied for all ϕ ∈ C c (U ; R). Next, we use the following representation result.

Proposition 5.9. Every continuous linear form Ψ on E := L 1 (U, λ; C d ) admits a representation

Ψ(f ) = U f • gdλ, g ∈ L ∞ (U ; C d ).
(5.92)

We have Ψ E = g L ∞ (U ) in this correspondence, where g L ∞ (U ) is the the essential supremum over x ∈ U of the euclidean norm |g(x)| of g(x) and Ψ E is the norm of the linear form Ψ.

Proposition 5.9 is an extension of [START_REF] Rudin | Real and complex analysis[END_REF]Theorem 6.16] to the vector valued case. We admit this result, which can be proved by a systematic examination of the proof of [START_REF] Rudin | Real and complex analysis[END_REF]Theorem 6.16

|Φ(f )| ≤ U |g|dλ, f ∈ C c (U ; C d ), |f (x)| ≤ 1.
Taking the sup over f in the previous inequality gives Λ(1) ≤ U |g|dλ. Since Λ(1) = λ(U ), |g| is equal to 1 λ-a.e. To finish the proof, let us show that the map Λ defined by (5.90) is linear.

Let f, g ∈ C c (U ; R + ), ε > 0 and h 1 , h 2 ∈ C c (U ; C d ) such that Λ(f ) ≤ |Φ(h 1 )| + ε, Λ(g) ≤ |Φ(h 2 )| + ε.
There are some complex numbers α 1 , α 2 ∈ C of modulus 1 such that |Φ(h i )| = α i Φ(h i ). Then the sum Λ(f ) + Λ(g) is bounded by

α 1 Φ(h 1 ) + α 2 Φ(h 2 ) + 2ε = Φ(α 1 h 1 + α 2 h 2 ) + 2ε ≤ Λ(f + g) + 2ε
, which shows that Λ(f ) + Λ(g) ≤ Λ(f + g). To prove the converse inequality, consider h ∈ C c (U ; C d ) satisfying the constraint |h| ≤ f + g and set V = {f + g > 0} and

h 1 = f f + g 1 V h, h 2 = g f + g 1 V h. Then h 1 , h 2 ∈ C c (U ; C d ) (why?), h 1 + h 2 = h, |h 1 | ≤ f , |h 2 | ≤ g, which shows that |Φ(h)| ≤ Λ(f ) + Λ(g).
Taking the sup over h gives the desired result.

Notation: if u ∈ BV(U ), we denote by Du the (vector-valued) complex measure nκ in (5.87) and by |Du| the measure κ. The norm u BV(U ) of u is defined as

u BV(U ) = u L 1 (U ) + |Du|(U ). ( 5
(E) = |D1 E |(R d ).
We can now begin the study of the two most important terms in (5.119): µ 1 h,∆t , |∂ t ϕ| and µ 2 h,∆t , |∇ x ϕ| . To that purpose, we need to come back to the definition of µ 1 h,∆t and µ 2 h,∆t in the proof of Theorem 5.5, cf. (5.73) and (5.76):

µ 1 h,∆t , ψ = N -1 n=0 K∈T |u n K -u n+1 K | tn+1 tn K ψ(x, t)dxdt, ( 5.121)
and (taking into account the expression (5.14) of the numerical flux in (5.76)):

µ 2 h,∆t , ψ := N -1 n=0 K∈T L∈N (K) a - K→L |u n K -u n L | × 1 |K| tn+1 tn K|L K 1 0 ψ(ry + (1 -r)x, t)|x -y|drdxdσ(y)dt. (5.122)
The norm of the gradient

∇ x ϕ(x, t) = (∇Φ t (x)) * (∇ x ϕ 0 ) • Φ t (x) is bounded by ∇Φ t L ∞ (T d ) ∇ x ϕ 0 L ∞ (T d ) .
We have d ) . This last bound comes from the identities (where ∇Φ = (∂ i Φ j ) i,j )

∇ x ϕ 0 L ∞ (T d ) ≤ L ≤ h -1/2 and ∇Φ t L ∞ (T d ) ≤ e t a C 1 (T d ;R
∇Φ t = exp t 0 ∇a • Φ s ds , I d = ∇Φ t (x)(∇Φ t )(Φ t (x)), for all x ∈ T d . Using the transport equation ∂ t ϕ = -a • ∇ x ϕ, we deduce from these estimates that ∇ (t,x) ϕ L ∞ (T d ×[0,T ]) ≤ Ch -1/2 , ( 5.123)
where C depends on a C 1 (T d ;R d ) and T only. We also remark that the derivatives ∇ (t,x) ϕ are supported in the "streak" S = 0≤t≤T Φ t ( ∂A L -1 ) × {t}.

This has the consequence that

µ 1 h,∆t , |∂ t ϕ| ≤ Ch -1/2 N -1 n=0 ∆t K∈T |K||u n K -u n+1 K |χ(K × (t n , t n+1 )), where χ(K × (t n , t n+1 )) = 1 if K × (t n , t n+1
) intersects the set S, and 0 otherwise. By the Cauchy-Schwarz inequality and (5.58), we obtain

| µ 1 h,∆t , |∂ t ϕ| | 2 ≤ Ch -1 ∆tD(t N ) N -1 n=0 ∆t K∈T |K|χ(K × (t n , t n+1 )). ( 5

.124)

To estimate the term

S := N -1 n=0 ∆t K∈T |K|χ(K × (t n , t n+1 ))
Proof of Lemma 6.1. The set of closed subsets of E is a π-system. By [3, Theorem 3.3], it is sufficient to show that ν 1 (A) = ν 2 (A) for all closed sets A. This follows from the pointwise monotone convergence ϕ n ↓ 1 A , where the function

ϕ n (x) = 1 -min(1, nd(x, A))
is continuous.

Let ϕ ∈ BC(E). By Lemma 6.1, it is sufficient to show that P * t ν, ϕ = ν, ϕ . We write

P * t μT , ϕ = 1 T T 0 P * t+s µ, ϕ ds, ( 6.2)
(we will justify later this commutation relation). A change of variable gives then

P * t μT , ϕ = 1 T T +t t P * s µ, ϕ ds = T + t T μT , ϕ - t T μt , ϕ . (6.3)
Using the Feller property of (P t ) and the convergence μT → ν, we can pass to the limit in (6.3) to obtain the desired identity P * t ν, ϕ = ν, ϕ . There remains to justify (6.2). By continuity of t → P * t µ, ϕ , we have the following convergence of Riemann sums

1 N N -1 n=0 P * sn µ → μT , s n = nT N .
We apply P * t to each member (the convergence holds true owing to the Feller property of (P t )). By linearity of P * t , we get 1 N

N -1 n=0 P * t (P * sn µ) → P * t μT . ( 6.4)
The semi-group property of P t implies P * t (P * s µ) = P * t+s µ, therefore the left-hand side of (6.4) is again a Riemann sum, which converges to the right-hand side of (6.2). This gives the desired result. Back to Exercise 3.7.

Solution to Exercise 3.8.

1. Quite clear.

2. Quite clear also ! 3. (a) Let (p(t), q(t)) = Φ t (p, q). We compute the time derivative of H(p(t), q(t)):

d dt H(p(t), q(t)) = D p H(p, q) ṗ + D q H(p, q) q = 0. (b) We have P * t µ β , ϕ = 1 Z(β) R d ϕ • Φ t (x)e -βH(x) dx.
The change of variable y = Φ t (x) has the inverse x = Φ -t (y) since the system is autonomous, and has Jacobian 1 since

div (p,q) (D q H, -D p H) = n i=1 ∂ 2 p i q i H -∂ 2 p i q i H = 0.
Using the identity H • Φ -t = H, we obtain

R d ϕ • Φ t (x)e -βH(x) dx = R d ϕe -βH(x) dx.
Back to Exercise 3.8.

Solution to Exercise 3.9. Let us first prove that Γ(ϕ) ≥ 0. Let ϕ ∈ D(L ) be such that ϕ 2 ∈ D(L ). Then 2Γ(ϕ) is the limit for b.p. convergence when t → 0+ of the quantity

P t [ϕ 2 ] -ϕ 2 t -2ϕ P t ϕ -ϕ t . ( 6.5)
Since P t is given by

P t ϕ(x) = E ϕ(y)Q(t, x, dy),
where Q is a probability kernel, we can apply the Jensen inequality to bound (6.5) from below by

[P t ϕ] 2 -ϕ 2 t -2ϕ P t ϕ -ϕ t . ( 6.6)
Rearranging the expression, we see that (6.6) is equal to t -1 (P t ϕ -ϕ) 2 ≥ 0.

Let us now consider the case of an ODE: Ẋt = F (X t ). Let Φ t denote the associate flow, so that X x t = Φ t (x). There is no randomness here, so we may consider that we are given a probability space (Ω, F, P) with F = {∅, Ω} the trivial σ-algebra. However, it is sometimes relevant to put randomness in the initial datum only. In that configuration, we consider a non-trivial σ-algebra F and a trivial filtration F t = F, for all t. In any case, we obtain a Markov process with transition operator

P t ϕ = ϕ • Φ t . Then we compute L ϕ(x) = F (x) • ∇ϕ(x) when ϕ ∈ C 1 b (R d ) and 2Γ(ϕ) = F • ∇(ϕ 2 ) -2ϕF • ∇ϕ = 0.
In the case of the SDE (3.39), showing that (X t ) is a Markov process is not immediate, see, e.g., [2, p.313]. Define the non-negative matrix a = σ * σ. By the Itô formula, we have, for

ϕ ∈ C 2 b (R d ), E [ϕ(X t )] = E [ϕ(X 0 )] + t 0 E [L ϕ(X s )] ds, ( 6.7)
where L is given by

L ϕ(x) = F (x) • ∇ϕ + 1 2 a(x) : D 2 ϕ(x). ( 6.8)
In (6.8), we use the following notations: D 2 ϕ is the Hessian Matrix with ij-components ∂ 2 xixj ϕ; A : B is the scalar product of d × d matrices:

A : B = d i,j=1 A ij B ij .
It follows from (6.7) and the continuity properties of the solution to (3.39) that the generator of (X t ) is indeed the operator L of (6.8). A simple computation gives then Γ(ϕ)(x) = a(x) : ∇ϕ(x) ⊗ ∇ϕ(x).

(6.9)

In (6.9), we use the following notation: given u, v ∈ R d , u ⊗ v is the (rank-1) matrix with ijelement u i v j . Then A : u ⊗ v = Av • u, scalar product of Av with u. This gives us the alternative expression Γ(ϕ)(x) = a(x)∇ϕ(x) • ∇ϕ(x) = |σ(x)∇ϕ(x)| 2 .

In the particular case σ(x) = I d , we obtain Γ(ϕ) = |∇ϕ| 2 . Back to Exercise 3.9.

Solution to Exercise 3.10. We have Consequently, there is strict equivalence between A(t) * µ = µ for all t ≥ 0, and L * µ = 0. Back to Exercise 3.10.

P t ϕ(x i ) = E xi ϕ(X t ) = L j=1 E xi 1 X(t)
Solution to Exercise 3.11. Assume E = {x 1 , . . . , x L } as in Exercise 3.10. Let A denote the matrix A(1): a ij = P xi (X 1 = x j ). We still have P n ϕ = A(n)ϕ and P * n µ = A(n) * µ. By the semi-group property, we have A(n) = A n for all n ≥ 0. The equation satisfied by the invariant measure is (A * -Id)µ = 0 (the equivalent to L here is A -Id). Let us come back to the case of a general state space E (a Polish space in our framework). Let us first prove that (M n ) is a martingale. We can use the tower property (2.2) to show that it is sufficient to establish the identity E [M n+1 |F n ] = M n for all n ≥ 0. By the Markov property, we obain

E [M n+1 |F n ] = P 1 ϕ(X n ) -ϕ(X 0 ) - n k=0 L ϕ(X k ).
Since L = P 1 -Id, this is precisely the desired identity E [M n+1 |F n ] = M n . Let us look at (3.43) now. Again, we want to prove that E [Z n+1 |F n ] = Z n . We write

M n+1 = ϕ(X n+1 ) -Y n , Y n = ϕ(X 0 ) + n k=0 L ϕ(X k ),
where Y n is F n -measurable. This gives

E |M n+1 | 2 |F n = E |ϕ(X n+1 )| 2 |F n -2Y n E [ϕ(X n+1 )|F n ] + |Y n | 2 = P 1 |ϕ| 2 (X n ) -2Y n P 1 ϕ(X n ) + |Y n | 2 = P 1 |ϕ| 2 (X n ) + Y n (Y n -2P 1 ϕ(X n ))
We have also Y n = ϕ(X n ) + L ϕ(X n ) -M n = P 1 ϕ(X n ) -M n , hence

E |M n+1 | 2 |F n = P 1 |ϕ| 2 (X n ) -(P 1 ϕ(X n ) -M n )(P 1 ϕ(X n ) + M n ).
and

E |M n+1 | 2 |F n -|M n | 2 = P 1 |ϕ| 2 (X n ) -|P 1 ϕ(X n )| 2 .
We obtain then ( By independence, µ (Sn,Tn+1) = µ Sn ⊗ µ Tn+1 , so

P(N (t) = n) = t s=0 ∞ τ =t-s
λ n s n-1 (n -1)! e -λs dsλe -λτ dτ = e -λt (λt) n n! .

The assertion that N (t) is càdlàg is a deterministic statement, it comes from the fact that Γ is a measure: indeed, we note that, whatever the Radon measure µ on R + , the map t → µ([0, t]) is càdlàg. It is clear that N (0) = 0 a.s. and that (N (t)) has jumps of amplitude +1.

Back to Exercise 4.3.

Solution to Exercise 4.5.

1. (a) Assume by contradiction µ({x 0 }) > 0. For A = {x 0 }, we have then P(Γ(A) ≥ 2) > 0, which is absurd since A cannot contain more than one point. = e -λ(t1-t0) (λ(t 1 -t 0 )) n1-n0 (n 1 -n 0 )! • • • e -λ(t k+1 -t k ) (λ(t k+1 -t k )) n k+1 -n k (n k+1 -n k )! = P(N (t 1 ) = n 1 , . . . , N (t k ) = n k )P(N (t + s) -N (t) = m) (6.14) This shows that N (t + s) -N (t) is independent on F N t and follows a Poisson distribution of parameter λs. Therefore, (N (t)) is a Poisson process, as defined in Definition 4.2.

Back to Exercise 4.5.

Solution to Exercise 4.6.

1. By independence, the quantity E ϕ(S 1 , . . . , S n )1 Sn≤t<Sn+1 is equal to

E ϕ(T 1 , T 1 + T 2 . . . , T 1 + • • • + T n )1 T1+•••+Tn≤t<T1+•••+Tn+Tn+1 = ∞ t1=0 • • • ∞ tn+1=0 ϕ(t 1 , t 1 + t 2 , . . . , t 1 + • • • + t n )1 t1+•••+tn≤t<t1+•••+tn+tn+1 × λ n+1 e -λ(t1+•••+tn+1) dt 1 • • • dt n+1 .
We do the change of variable (of Jacobian 1)

u 1 = t 1 , u 2 = t 1 + t 2 , . . . , u n+1 = t 1 + • • • + t n+1
to get the expression Solution to Exercise 5.6. We only give the sketch of the proof. By linearity, it is sufficient to consider the case u 0 = 0, in which case we want to prove u ≡ 0. If u is smooth, then ∂ t u + a • ∇u = 0 (recall that a is divergence free). By the usual chain-rule formula, it follows that ∂ t β(u) + a • ∇β(u) = 0 for any function β of class C 1 . By integration, we obtain It is sufficient to apply (6.16) with a non-negative function β such that β(s) = 0 if, and only if, s = 0, for example β(s) = s 2 , to conclude. In this special case β(s) = s 2 , we can reformulate things as follows: our aim is to justify the "energy estimate"

∂ t u 2 + a • ∇ x (u 2 ) = 0
for a weak solution u. This is a standard problem. It is discussed for example in [16, Section III.2.] for parabolic equations, or [23,Appendix A.20] for the kinetic Fokker-Planck equation.

For transport equation, specifically, this problem is treated in [START_REF] Diperna | Ordinary differential equations, transport theory and Sobolev spaces[END_REF]. Actually, [START_REF] Diperna | Ordinary differential equations, transport theory and Sobolev spaces[END_REF] deals with less regular fields a, which, instead of being Lipschitz continuous, have a mere Sobolev regularity. See Section II.2 in [START_REF] Diperna | Ordinary differential equations, transport theory and Sobolev spaces[END_REF].

To show that (x, t) → u 0 • Φ t (x) is a weak solution, do the change of variable x = Φ t (x) in the weak formulation. Back to Exercise 5.6.

Solution to Exercise 5.8.

1. Let ϕ ∈ C 1 c (U ). We have f (x)ϕ(x)dx. (6.17

)
If ϕ is supported in (-r, r) with r < 1, then (6.17) is bounded by f L 1 (-r,r) ϕ C(-1,1) . We have u ∈ BV(U ) if, and only if there is a finite constant C such that | 1 -1 f (x)ϕ(x)dx| ≤ C ϕ C(-1,1) for all ϕ ∈ C 1 c (U ). Clearly, f ∈ L 1 (U ) implies u ∈ BV(U ). Conversely, if u ∈ BV(U ), let us consider, for ε > 0, χ ε the characteristic function of the interval (-1 + ε, 1 -ε) and (ρ ε ), an approximation of the unit with ρ ε supported in (-ε, ε). Let also ψ be a function in C 1 c (U ). We have then We consider then a non-decreasing sequence of functions ψ ∈ C 1 c (U ) which converges pointwise to the constant function 1. By monotone convergence, (6.19) gives f ∈ L 1 (U ).

2. Let ϕ ∈ C 1 c (U ). We have Back to Exercise 5.8.

Solution to Exercise 5.9. In the first case, we assume f ∈ L 1 (-1, 1). Then (6.17

. 13 ) 3 . 4 . 3 (

 13343 The aim of Exercise 4.3 below is to make the relation between the count of exponential arrival times (these are the clocks that we use in Section 1.2 for instance) and Poisson processes. This relation is only partially established in Exercise 4.3. To complete the analysis, we introduce the notion of Poisson point process in R d . Exercise 4.5 gives several results and the construction of Poisson point processes. This is used in Exercise 4.6 to complete Exercise 4.Exercise Poisson process). Let (T n ) be a sequence of i.i.d. random variables with exponential law of parameter λ > 0: P(T n > t) = e -λt . We define a sequence of times S 0 , S 1 , . . . as follows: S 0 = 0 and, for n ≥ 1, S n = T 1 + . . . + T n . Given an interval I of R + , we denote by Γ(I) the number of times S n that fall in I: Γ(I) = #(S ∩ I), S = {S n ; n ∈ N}.

Exercise 4 . 5 (

 45 Construction of a Poisson point process). 1. Let Π be a Poisson point process of intensity µ on R d . (a) Show that µ has no atom. (b) Suppose that µ is finite: µ

( a )

 a Show that, almost-surely, Π n = {X 1 , . . . , X n } contains n points. (b) Let Γ n (A) = #{A ∩ Π n }. Show that Γ n satisfies (4.14) (with the same n).

( 1 - 1 x=0 e 2iπkx/L = 1 .L

 111 .34) This shows that -∆ D is self-adjoint. We also have -∆ D ǎk = ν k ǎk , withν k = (e iπk/L + e -iπk/L -2) = 4 sin 2 πk 2L . (4.35) The second identity in (4.35) uses the elementary trigonometry formula 1 -cos(2a) = 2 sin 2 (a) (4.36) Let 1 ≤ k, l ≤ L -1. Using (4.34) and the fact that ν k = ν l if k = l, we obtain the orthogonality relation ǎk , ǎl E L = 0 when k = l. If k = l, the trigonometric identity (4.36) gives ǎk , ǎk E L = L -1x∈X L cos(2πkx/L)) = 1 -L -1 Re L-The family (ǎ k ) 1≤k≤L-1 is free since ǎk , ǎl E L = δ kl . It constitutes a basis of E ) = L -1. This concludes the proof. It follows from Proposition 4.5 that the solution h to (4.9)-(4.10)-(4.11) is given by

Lemma 4 . 6 .

 46 Let h in be a 1-Lipschitz continuous function on [0, 1] vanishing at 0 and 1. Let h be the unique solution to (4.9)-(4.10)-(4.11) (see (4.8)). Then sup t∈(0,T ) | h(t, •), a k L 2 (0,1)

2 r 0 B

 20 .56) valid for any non-decreasing Lipschitz continuous function B on [0, R]. To obtain (5.56), we simply use the formula B(r) 2 = (s)B (s)ds,

  + (1 -r)x, t)|x -y|drdxdσ(y)dt.(5.76)

  By letting t → 0, we deduce that A satisfies the ODE A (t) = L A(t) = A(t)L , which implies A(t) = e tL since A(0) = I L . The equation satisfied by an invariant measure is A(t) * µ = µ for all t ≥ 0. By differentiation, we obtain L * µ = 0. Of course the latter equation implies (L * ) n µ = 0 for all n ≥ 1, and thusA(t) * µ = e tL * µ = n≥0 (L * ) n n! µ = µ.

0 λ 2 e

 02 3.43) by using the definition Γ[ϕ] = P 1 |ϕ| 2 -|P 1 ϕ| 2 . The Jensen inequality applied toP 1 ϕ(x) = E ϕ(y)Q(1, x, dy) shows that Γ[ϕ] ≥ 0.Back to Exercise 3.11.Solution to Exercise 4.3. Each T n has density f : t → λe -λt 1 R+ (t) with respect to the Lebesgue measure on R. By independence, S n has the law f * • • • * f (convolution n times). We computef * f (t) = R λ 2 e -λs e -λ(t-s) 1 R+ (s)1 R+ (t -s)ds = t -λt ds1 R+ (t) = λ 2 te -λt 1 R+ (t),and, by recursion onn, f * • • • * f (t) = λ n t n-1(n-1)! e -λt 1 R+ (t). We compute thenP(N (t) = n) = P(S n ≤ t < S n+1 ) = P(S n ≤ t < S n + T n+1 ) = E[1 Sn≤t<Sn+Tn+1 ] = t s=0 ∞ τ =t-sdµ (Sn,Tn+1) (s, τ ).

7 .

 7 When d = 1, µ = λ×restriction of the Lebesgue measure to R + , the process N (t) = Γ([0, t]) is a counting process with Poisson's distribution of parameter λt. If 0 ≤ t, s and t1 ≤ • • • ≤ t k ≤ t, then P(N (t 1 ) = n 1 , . . . , N (t k ) = n k , N (t + s) -N (t) = m) (6.12) = P(Γ(A 1 ) = n 1 , Γ(A 2 ) = n 2 -n 1 . . . , Γ(A k ) = n k -n k-1 , Γ(A) = m), (6.13)whereA 1 = [0, t 1 ], A 2 = (t 1 , t 2 ], . . . , A k = (t k-1 , t k ], A = (t,t + s]. We can always assume that t k = t. Using the independence properties of the Poisson point process, we obtain then, setting t 0 = 0 and n 0 = 0 and t k+1 = t + s, n k+1 = m + n k , P(N (t 1 ) = n 1 , . . . , N (t k ) = n k , N (t + s) -N (t) = m)

  1 , u 2 , . . . , u n )λ n+1 e -λun+1 du 1 • • • du n+1 = λ n e -λt 1 , u 2 , . . . , u n )du 1 • • • du n = λ n n! e -λt E[ϕ(U (1) , . . . , U (n) )]This gives us the identityE ϕ(S 1 , . . . , S n )1 N (t)=n = E[ϕ(U (1) , . . . , U (n) )]P(N (t) = n),as desired.

1 - 1 u 1 - 1 u 1 - 1

 111111 (x)ϕ (x)dx = -(x)ϕ(x)dx = -

1 - 1 f

 11 sign(f ) ε ψdx ≤ C, ϕ ε := (ϕχ ε ) * ρ ε . (6.18)Taking the limit ε → 0 in(6.18) gives

ϕ

  (x)dx = -ϕ(0) ≤ ϕ C(-1,1) , (6.20) hence u ∈ BV(U ).

3 .

 3 By the Stokes' formula, we have, forϕ ∈ C 1 c (U ), U u div ϕdx = B(0,1/2) div ϕdx = ∂B(0,1/2) ϕ(x) • n(x)dσ(x) ≤ π ϕ C(-1,1) , (6.21)hence u ∈ BV(U ).

1 0 1 0 1 0

 111 ) shows that Du = f λ, where λ is the Lebesgue measure on(-1, 1). By[START_REF] Rudin | Real and complex analysis[END_REF] Theorem 6.13], we have |Du| = |f |λ then and u BV(U ) = u L 1 (U ) + f L 1 (U ) . In the second case,(6.20) shows that Du = δ 0 , the Dirac mass at 0. Then |Du| = δ 0 also and u BV(U ) = u L 1 (U ) + 1 = 2. In the third case,(6.21) shows that Du = nσ, where n is the outward unit normal to U on ∂U and σ the surface measure. By [20, Theorem 6.13] again, |Du| = σ. We compute then u BV(U ) = π/4 + π = 5π/4. Back to Exercise 5.9.Solution to Exercise 5.11. Assume first that u is of classC 1 . Let h ∈ [0, 1]. For x ∈ Q = (0, 1) d and z ∈ R d with |z| ≤ h, we have |u(x + z) -u(x)| = (∇u)(x + rz) • zdr ≤ h |∇u|(x + rz)dr.We do the change of variable (x , r ) = (x + rz, r) of Jacobian determinant 1 to obtainQ |u(x + z) -u(x)|dx ≤ h Q+rz |∇u(x)|dxdr ≤ h Q |∇u(x)|dx = h|Du|(Q ),where Q = (-1, 2) d . This gives ω L 1 (u; h) ≤ |Du|(Q )h. This estimate remains true in the general case by Theorem 5.11 applied on U = Q . Since |Du|(Q ) ≤ 3 d |Du|(T d ), we obtain the desired result with C = 3 d . Back to Exercise 5.11.

  Remark 2.1. A martingale with continuous (resp., càdlàg 1 ) trajectories is said to be a continuous (resp., càdlàg) martingale. Remark 2.2. With respect to a fixed time t > 0, conditioning on F s with s ≤ t is a way to average X t over all events which occurred between times s and t. For a martingale X, this will let the position X

s unchanged. We expect a martingale not to wander too much therefore. We will see and use several instance of this general principle. See Section 2.3 for a first example. Let us also state the following result. Theorem 2.2 (Doob's martingale inequality). Let p > 1. Let (M t ) t∈[0,T ] be a càdlàg, real-valued martingale, such that E|M T | p < +∞. Then the inequality

  All the computations below can be justified by working first we T ε , defined in (2.14), and then letting ε → 0. The first piece in (2.22) is easy to estimate: we use the Chebychev inequality and the L 2 -estimate (2.15) to obtain

  .24) Let x i denote the center of Q i . Let B i denote the ball with same center as Q i and diameter diam(Q i ). We have |B i | = c d |Q i | for a given constant c d . We use the cancellation property satisfied by b i to write

Proposition 3.1. Let

  (P t ) t≥0 be a semi-group as in 1. Assume that, for each t ≥ 0,

	[ϕ n	b.p.c. -→ ϕ] ⇒ [P t ϕ n	b.p.c. -→ P t ϕ].	(3.6)
	Then there exists a probability kernel as in 2. such that (3.3) is satisfied.
	Proof of Proposition 3.1. We give the main ideas of the proof. First observe that (3.3) implies
	the continuity property (3.6): it is natural to assume (3.6) therefore. Set
		Q(t, x, A) = (P t 1 A )(x)	(3.7)
	For each fixed t, x, this defines a non-negative set function Q(t, x, •) such that Q(t, x, E) = 1. The
	only delicate point to show that Q(t, x, •) is a probability measure is the countable additivity. It
	follows from (3.6) and the convergence ϕ n	b.p.c. -→ ϕ, when A 1 , . . . , A n . . . are disjoint Borel sets in
	E, ϕ n = 1 ∪ 1≤k≤n A k , ϕ = 1 ∪ 1≤k A k . By (3.7), (3.3) is satisfied when ϕ is a characteristic function.
	By linearity, this remains true for simple functions. Any ϕ ∈ BM(E) can be approached for
	bounded pointwise convergence by a sequence of simple functions, this gives the relation (3.3) in
	all its generality.
	Proposition 3.2. Let Q be a probability kernel as in 2. Assume that

  Proof of Proposition 3.2. We define P t by the relation(3.3). Then (P t ) t≥0 has all the desired properties listed in 1. The only point that must be studied carefully is the semi-group property.

	The relation (3.8) is called the Chapman Kolmogorov relation.
	It is sufficient to establish that P t+s ϕ = P t (P s ϕ) is satisfied for characteristic functions, but
	then, this is equivalent to (3.8).
	Let us now study the relation between the process given in 3. and the probability kernel Q.
	First, we state without proof the following result. See, e.g. [7, Theorem 1.1 p.157], for the proof.
	Proposition 3.3. Let Q be a probability kernel as in 2. Then there exists a measurable space
	(Ω, F), a process (X t ) t≥0 on (Ω, F) such that: for all probability measure µ on E, there exists
	a probability measure P µ on (Ω, F), such that, under P µ , (X t ) t≥0 has the finite-dimensional
	distributions given by (3.4): for all 0 ≤ t 1 ≤ • • • ≤ t k , B 0 , . . . , B k ∈ B(E), the probability
	x, dy),	(3.8)
	is satisfied for every t, s ≥ 0, x ∈ E, A ∈ B(E). Then there exists a Markov semi-group as in 1.
	such that (3.3) is satisfied.

  ). defines a measurable function of t as limit of measurable functions. Since it is bounded by hypothesis, it is integrable. Let T > 0. Let m, M ∈ R be such that m ≤ β (t + ) ≤ M for every t ∈ [0, T ]. We will show that

		t
		β (s+)ds,	(3.37)
		0
	for all t ≥ 0.
	Proof of Lemma 3.8. Note first that
	β (t+) = lim
	m ≤	β(t) -β(0) t	≤ M,	(3.38)
	This equality, combined with Step 1, yields (3.28). This achieves the proof.

Lemma 3.8. Let β : R + → R be a continuous function, right-differentiable at every point, such that t → β (t+) is bounded. Then

β(t) -β(0) = n→+∞ n(β(t + n -1 ) -β(t))

for all t ∈ [0, T ]. This gives the conclusion by considering

β(t) = β(t) -β(0) -t 0 β (s+)ds,

and applying (3.38) with m = M = 0. For t ∈ (0, T ], let us denote by Γ(t) the quotient in

(3.38)

. We set Γ(0) = β (0+) to extend Γ by continuity at 0. Let δ > 0. Assume that there exists t 1 ∈ [0, T ] such that Γ(t 1 ) > M + δ. By continuity of Γ, we have t 1 > 0. By restricting things to [0, t 1 ] if necessary, we can assume t 1 = T . Let now D(t) = β(0) + (M + δ/2)t be a parametrization of the straight-line with slope M + δ/2 having the same origin as the graph of β. We have β(T ) > D(T ). Let τ denote the infimum of the points t ∈ [0, T ] such that β > D on [t, T ]. By continuity, τ is well defined, τ ∈ [0, T ) and β(τ ) = D(τ ). At this stage, a picture is useful: at the point τ , the graph of β crosses the straight line t → β(0) + (M + δ/2)t and is above this straight line on [τ, T ]. It is clear that this contradicts the fact that β (τ +) ≤ M and, indeed, the inequality

  Theorem 4.1. Let h in be a 1-Lipschitz continuous function on [0, 1] vanishing at 0 and 1 and satisfying h in ∈ H 2 (0, 1). Let h be the unique solution to (4.9)-(4.10)-(4.11) (see (4.8)). Let H in ∈ E

	(1)

  (Poisson point process). Let µ be a (non-negative) measure on the Borel σalgebra of R d . Let (Ω, F, P) be a given probability space. A Poisson process Π with intensity µ on R d is a map from Ω into the set of countable subsets of R d such that 1. for all Borel subset A of R d , Γ(A) := #{Π ∩ A} is a random variable, 2. for all disjoint Borel subsets A 1 , . . . , A k of R d , the random variables Γ(A 1 ), . . . , Γ(A k ) are independent, 3. for all Borel subset A of R d , Γ(A) follows a Poisson distribution of parameter µ(A):

	The solution to Exercise 4.3 is here.
	Definition 4.4
	1. Compute the (density of the) law of S n .
	2. Let N (t) = Γ([0, t]). Show that N (t) is a counting process and is Poisson of parameter λt
	(hint: P(N (t) = n) = P(S n ≤ t < S n+1 )).

  3. Let µ be a finite measure without atoms. We use the analysis ofQuestions 1 and 2 to build a Poisson point process of intensity µ on R d . Let ν be the probability measure defined by (4.16) and let X 1 , X 2 , . . . , be some iid random variables of law ν. Let N be a Poisson distribution of parameter µ(R d ) independent on (X n ) n≥1 . Let Π = {X 1 , . . . , X N }. Show that Π is a Poisson point process of intensity µ on R d . (Superposition principle). Let Π 1 , Π 2 , . . . be a countable collection of independent Poisson point processes on R d with respective intensity measures µ 1 , µ 2 , . . . Then Let µ be a measure on R d without atoms that can be written as (4.17) where each µ n is finite. Show that there exists a Poisson point process on R d with intensity measure µ. The solution to Exercise 4.5 is here. (Poisson process -continued). To complete the analysis of Exercise 4.3, it is sufficient (why?) to show that

	4. Show the following result
	Theorem 4.2 Π =	Π n
	n≥1
	is a Poisson point process on R d with intensity measure
	µ =	µ n .	(4.17)
	n≥1
	5. Exercise 4.6

6. Show that a σ-finite measure can be written as (4.17) where each µ n is finite.

7. Let λ > 0. Consider the case where d = 1, and µ is λ times the restriction of the Lebesgue measure to R + . What is the process N (t) = Γ([0, t]) then?

2 From discrete-time to continuous-time Markov process Proposition 4.3.

  Sn≤t<Sn+1 in terms of the variables T 1 , . . . , T n+1 and do the adequate changes of variables. Let E be a Polish space. Let (X n ) n≥0 be a discrete time-homogeneous Markov chain on E with transition operator P n , n ∈ N. Let N (t) be a Poisson process of exponent λ > 0 independent on (X n ) n≥0 and let ξ t = X N (t) . Let also (F t ) = (F

	4.2.(ξ,N )
	t
	2. Conclude.
	The solution to Exercise 4.6 is here.

.

[START_REF] Pazy | Semigroups of Linear Operators and Applications to Partial Differential Equations[END_REF]

1. Show that, conditionally to N t = n, (S 1 , . . . , S n ) has the law of (U (1) , . . . , U (n) ).

Hint: Express E ϕ(S 1 , . . . , S n )1

  ).

	By Lemma 4.6, Lemma 4.7 and the Parseval identity, we have
	sup t∈[0,T ]	h(t, •) -ĤL 2 t	2 L 2 (0,1) = sup t∈[0,T ]	k=1 K(L)	h(t, •) -ĤL 2 t , a k L 2 (0,1)	2	+ o(1)	(4.42)

when L → +∞. We will show that (4.42) can be approached, still with an o(1) error, by sup t∈

[0,T ]

  .45) Let us compare h in , a k L 2 (0,1) to H in , ǎk E L . By (4.6), we have

	sup
	x∈[0,1]

  .46) By (4.5), we also haveH in , ǎk E L = Ĥin , a k L 2 (0,1) + O(L -1 k).

	An estimate similar to (4.44)
	then shows that (4.45) is equal (up to o(1)) to
	sup
	t∈[0,T ]

  .49)We need to analyze the behavior on [0, L 2 T ] of the process H t , ǎk E L , which is of the form ϕ k (H t ), with ϕ k (H) = H, ǎk E L . The formula (4.28) for the generator L of (H t ) gives L ϕ k (H) = ∆ D H, ǎk E L . By Proposition 4.5 and the fact that ∆ D is self-adjoint on

  .53)We will compute the "carré du champ" L |ϕ k | 2 -2ϕ k L ϕ k to understand better what gives (4.53). Before we start, let us pause a moment to consider the inequalities that we have used. We come back to (4.52) in particular, where we have discarded the term e -ν

k t . We may have lost something here. If k is O(1), then ν k is of order L -2 for L large, and t → e -ν k t is not smaller than a given positive constant on the time interval [0, L 2 T ]. If k takes greater values, then things are different. However, as soon as k ≥ K(L), where K(L) is a quantity that grows to +∞ with L, but possibly very slowly, we can use the bound of Lemma 4.7 to get the estimate

  ∆t be the solution of the upwind Finite Volume method (5.1) with fluxes given by (5.17)-(5.79)-(5.15). Let u ∈ L ∞ (T d × (0, T )) be the weak solution to (5.5) on (0, T ) with initial datum u 0 . Assume that (5.29) and (5.46) are satisfied. Assume also that ∆t ≤ C 0 h2. (See [20, p. 130]). A complex measure µ defined on the Borel subsets of a topologicalHausdorff space X is said to be regular if for all Borel set A,|µ|(A) = sup {|µ|(K); K compact ⊂ A} = inf {|µ|(V ); Vopen ⊃ A} . (Structure theorem for functions of bounded variations). Let U be an open set in R d . Let u ∈ L 1 (U ). Then u ∈ BV(U ) if, and only if, there exists a non-negative regular finite measure κ on U and a Borel map n : U → R d such that |n(x)| = 1 for κ-a.e. x ∈ U and

			(5.86)
	Theorem 5.8 U	ϕ • ndκ,	(5.87)

U

u div ϕdx = -

  ∈ C c (U ; C d ). Since C c (U ; C d )is dense, we can extend Φ as a continuous linear form on E with norm Φ E ≤ 1. This gives us the representation (5.88) with g L

			]. Let
	us apply Proposition 5.9 to Φ. The functional Φ satisfies the hypotheses of the proposition:
	(5.89) with ϕ = |h| shows that
	|Φ(h)| ≤	|h|dλ,	(5.93)
	U
	for all h

∞ (U ) ≤ 1. To conclude, there remains to show that |g(x)| = 1 for λ-a.e. x ∈ U . By (5.88) and the Cauchy-Schwarz inequality |f • g| ≤ |f ||g|, we have

  .94) Lebesgue measurable set E of R d is said to have finite perimeter in U if 1 E ∈ BV(R d ).In that case, we set P

	Exercise 5.9 (Some functions of bounded variation). Compute Du, |Du| and u BV(U ) for the
	functions u considered in the exercise 5.8.
	The solution to Exercise 5.9 is here.
	Definition 5.10 (Set of finite perimeter).	1. A

  =xj ϕ(x j ) = ij (t)ϕ(x j ), which gives P t ϕ = A(t)ϕ. With the conventions that are used, we observe that ϕ, µ = (ϕ, µ), where (•, •) is the canonical scalar product in R L . Consequently, is the adjoint of the matrix A(t). The semi-group property reads A(t + s) = A(t)A(s). It follows that

	L	L
	j=1 a A(t + s) -A(s) P xi (X(t) = x j )ϕ(x j ) = j=1 t = A(s) A(t) -I L t = A(t) -I L t A(s).

ϕ, P * t µ = P t ϕ, µ = (A(t)ϕ, µ) = (ϕ, A(t) * µ),

and we obtain P * t µ = A(t) * µ, where A(t) *

càdlàg meaning "continue à droite avec limites à gauche", i.e. "continuous from the right with left limits" at each points

This topology on P 1 (E) is metrizable: this is a non-obvious fact,[START_REF] Billingsley | Convergence of probability measures[END_REF] Theorem 6.8], in particular we cannot simply build a metric based on a dense countable subset of BC(E) since BC(E) may be not separable (see the argument in[14, p.6] however)

the general case is left as an exercise, use the tower property(2.2)

If ϕ : E → R, we still denote by ϕ the vector (ϕ(x i )) 1≤i≤L . Give the expression of P t ϕ as a product matrix-vector.

If µ is a probability measure on E, we still denote by µ the vector (µ({x i }) 1≤i≤L . Give the expression of P * t µ as a product matrix-vector.

We assume that t → A(t), from R + into M L (R) is of class C 1 . Show that A(t) = e tL ,where L = A (0) is the generator.

an expression of Φ t is Φ t (x) = Φ -t (x), this is a consequence of the group property Φt • Φs = Φ t+s ; when the sense of the time evolution does matter, for instance in the study of stochastic differential equations, it is important to define Φ t as the inverse of x → Φt(x), not as Φ -t (x)

For later use, we record the identity

|K|L|A K→L (u n K , u n K ) = 0, (5.23) valid for all neighboring cells K, L ∈ T . We can use it to transform (5.1) into the identity

(5.24)

On the formula (5.24), we can see the stabilizing effect of the monotony of the numerical flux. Imagine that u n K > u n L for all neighboring cells L of K. Then

for all L since A K→L is non-increasing in its second argument, which implies that u n+1 K ≤ u n K . The estimates in the following two sections essentially use this.

Comparison principle

Periodic discrete conservation law

In all that follows we will consider for simplicity a periodic setting. We assume that the mesh T is periodic, in the sense that there exists a mesh T of the hypercube (0, 1) d such every K ∈ T is the translation of an element K of T by a vector of Z d . We also assume that K → u 0 K is periodic, in the sense that K ∼ L (where the relation of equivalence K ∼ L is defined by

L . This will be the case if we assume, as will be done later, that ∀K ∈ T , u 0

where u 0 : R d → R is Z d -periodic. We denote by T d the d-dimensional torus T d = R d /Z d .

Comparison principle and consequences

Remember the notation (5.3): K×[tn,tn+1) .

Note in particular that, if F : R → R is continuous, then

(5.26) Proposition 5.1 (L 1 -contraction). Let u h,∆t and v h,∆t be two sequences defined by (5.1), with a flux given as in Section 5. [START_REF] Billingsley | Convergence of probability measures[END_REF]. Define

|K|L|.

Let n ∈ N be fixed, and assume that the conditions

are satisfied for all K ∈ T , where L A is defined in (5.19). We have then

(5.28) Remark 5.1 (CFL condition). Recall that h is defined in (5.3) by h = sup K∈T diam(K). Suppose that there exists α > 0 such that

for all K ∈ T . Then (5.27) is satisfied if ∆t ≤ Ch, (5.30) where C -1 = 2α -2 L A (R), and R is a bound for all the quantities R n K (w), w = u h,∆t or v h,∆t (we will see soon how to ensure that R is finite). The condition (5.30) puts a constraint of the size of the time step, depending on the size of the space-step h. It is called a Courant-Friedrichs-Lewy (CFL) condition. (5.31)

We have then the formula (u -v) + = u ∨ v -v, (5.32) for all u, v ∈ R. Our first goal is to estimate u n+1 K ∨ v n+1 K . Let us consider the right-hand side of (5.24). It is a non-decreasing function of the variables u n L , L ∈ N (K). With respect to the variable u n K , it can be written as a sum Id + f , where f is a locally Lipschitz continuous function. On the domain where Lip(f ) ≤ 1, it will be also an non-decreasing function of u n K . Actually, our function f here is has the form F (u, u, u), where

is a non-decreasing function of u 1 . We are only interested in the Lipschitz dependency of this function with respect to u 2 and u 3 , which, using (5.19), is bounded by the first term in (5.27).

To sum up, as long as the first condition in (5.27) is satisfied, we have

where H n K is a non-decreasing function of its arguments. We deduce, under (5.27), that

for all K ∈ T . Then we use (5.32) and (5.33) to obtain the inequality

(5.35)

We write (5.35) under the form

(5.37)

We multiply (5.36) by |K| and sum over K ∈ T . It gives us the desired estimate (5.28), provided we can show that

The cancellation property (5.38) follows from the two identities

(5.39) The left identity in (5.39) follows from (5.23). The second identity in (5.39) is a consequence of (5.20) and of the formula

satisfied by any periodic function a : T × T → R. Indeed, if K * ∈ T and L * ∈ N (K), then the term a(L * , K * ) in the right-hand side of (5.40) will appear in the sum on the left when K = L * and L = K * (in the case where the interface K * |L * is on the boundary of (0, 1) d , we need to use the periodic character of a to complete this argument).

From Proposition 5.1, we deduce first a comparison principle and an L ∞ estimate.

Proposition 5.2 (Comparison principle, L 1 estimate). Under the hypotheses of Proposition 5.1, we have

Then, under the CFL condition

is proved by recursion on n, using the comparison principle and the fact that the constant functions R and -R are solutions of (5.1).

Proposition 5.4 (Energy estimate)

Assume that the following CFL condition is satisfied: there exists ξ ∈]0, 1] such that

(5.46)

Then we have the energy estimate

(5.47)

Remark 5.2. the term D(t N ) is non-negative. Indeed, using the monotony properties of A K→L , we have

Proof of Proposition 5.4. Note first that

By Proposition 5.3, we deduce that

To start with the energy estimate, we multiply the identity (5.24) by |K|u n K and we sum the result over K ∈ T and n ∈ {0, . . . , N -1}. We obtain an identity J ∆t + J ∆x = 0, where

and

, which is the "finite difference" version of the the continuous identity u∂ t u = 1 2 ∂ t u 2 . It gives

(5.50)

We leave as an exercise the proof that (5.25) implies u h,∆t (0

. From (5.50), we deduce that

and bound B (s) by Lip(B). Suppose u n K ≥ u n L for instance. Then (5.56) applied to B(z

We use the fact that A K→L (u n K , z) ≥ A K→L (z, z) since u n K ≥ z to get the desired identity. The reasoning in the case u n K ≤ u n L is similar.

Remark 5.3 (Discrete H 1 -estimate in the time variable). Note that (5.55) and (5.47) give the estimate

for all N ≥ 1. Note also that the inequality J * ∆x ≤ D(t N ) in the proof above and (5.47) give the estimate

for all N ≥ 1.

Approximate weak solutions

In this section, we will prove that u (k) obtained in Section 5.6.3 is an approximate weak solution of (5.9).

Definition 5.4 (Weak solution)

) is said to be a weak solution to (5.9) on (0, T ) with initial datum u 0 if

Notation: if u : T d → R and 1 ≤ p < +∞, we denote by ω L p (u; h) the modulus of continuity in L p (T d ):

(5.61)

Assume that the CFL condition (5.46) is satisfied for all K ∈ T . Then u h,∆t is an approximate weak solution to (5.9) on (0, T ) with initial datum u 0 in the sense that

for a certain constant C 0 . Then, there is a constant c(d) > 0 depending on d only such that, for h, ∆t ≤ c(d), we have the error estimate

where C is a constant depending only on the dimension d, on T , on C 0 , on a C 1 (T d ) , on the constant α in (5.29) and on the constant ξ in (5.46).

We will make some comments on Theorem 5.7, but first we need a brief remainder on the space BV.

Functions of bounded variations

where the supremum is taken over all

We denote by BV(U ) the space of functions of bounded variations.

We denote by BV loc (U ) the space of functions having locally bounded variations, defined as the set of functions u ∈ L 1 loc (U ) such that u ∈ BV(V ) for all open subset V ⊂⊂ U (this last notation means that there exists a compact

Exercise 5.8 (Some functions of bounded variation).

1.

Let u be the characteristic function of the disk B(0, 1/2). Show that u ∈ BV(U ). The solution to Exercise 5.8 is here.

To enunciate the following structure theorem for functions of bounded variations, let us recall the following facts about measures. [START_REF] Rudin | Real and complex analysis[END_REF]Chapter 6]). Let (X, A) be a measure space. A complex measure over (X, A) is a set function µ : A → C such that, for all A ∈ A, one has

(See

for all countable partition (A i ) i≥1 of A, the sum in (5.84) being absolutely convergent. If µ is a complex measure, the formula

where the supremum is taken over all countable partitions (A i ) i≥1 of A, defines a nonnegative finite measure |µ| on A called the total variation of µ.

Let U be an open subset of R

We now state without proof the following results.

(5.101)

We take the measure |Du| of Q 1 , not Q, in (5.101). This makes a difference if |Du| has a singular part with respect to the Lebesgue measure. This singular part may be due to some jumps of u, which is the case if we consider piecewise constant functions. Let u ∈ L 1 (T d ), denote by u h the piecewise constant function defined by

and we have

Since K|L is included in an hyperplane H, by hypothesis, the Hausdorff measure H d-1 (A ∩ K|L) in (5.103) can simply be rewritten λ H (A ∩ K|L), where λ H is the (d -1)-dimensional Lebesgue measure on H.

Comments on the error estimate

If 1 < p < +∞, one can establish the error estimate

(5.105)

See [START_REF] Merlet | L ∞ -and L 2 -error estimates for a finite volume approximation of linear advection[END_REF]. The estimate (5.105) cannot be generalized when the flux in the conservation law (5.9) is non-linear, for the reason that W 1,p (T d ) is not stable in the evolution: if u 0 ∈ W 1,p (T d ), there may be some time t > 0 such that the (entropy) solution u of (5.9) starting from u 0 loses the W 1,p (T d ) regularity at time t. This is a consequence of the apparition of discontinuities and is already clear in dimension d = 1. On the contrary, the space BV(T d ) is stable in the evolution by (5.9). For general fluxes A, the error estimate (5.82) is observed in numerical practice, but has not been established yet, except when the mesh is a cartesian mesh, i.e. each cell is a product of one-dimensional cells of a one-dimensional mesh.

Error estimate in the linear case: proof

The following proof of the error estimate (5.82) is taken from [START_REF] Merlet | Error estimate for the finite volume scheme applied to the advection equation[END_REF]. A different proof, using probabilistic tools, has been given in [START_REF] Delarue | Probabilistic analysis of the upwind scheme for transport equations[END_REF].

Reduction of the problem

Projection on piecewise constant functions and BV-norm. We will use several times the following result.

Proposition 5.15. Consider the map u → u h defined by (5.102). There exists a constant C ≥ 0 only depending on d and on the constant α in (5.29) such that, if u ∈ BV(T d ), then

(5.106)

Proof of Proposition 5.15. Let K ∈ T and let L ∈ N (K). We will establish first the estimate

where

). Using Theorem 5.10 and Theorem 5.11 with U = B(x K , 2h), we may suppose that u ∈ BV ∩ C 1 (B(x K , 2h)), in which case (cf. (5.96))

Since |x -y| ≤ 2h for every (x, y) ∈ K × L, we have then

Now we perform the change of variables (x, y, r) → (w = x -y, z = (1 -r)x + ry, r = r), of Jacobian determinant equal to 1, and of inverse (w, z, r) → (z + rw, z -(1 -r)w, r). This gives

where g is defined by g(w, z, r) = 1 if z + rw ∈ K and z -(1 -r)w ∈ L, and g(w, z, r) = 0 otherwise. We remark that, for (z, r) ∈ B(x K , 2h) × [0, 1], we have

The estimate (5.107) follows. Using (5.29), we deduce from (5.107) that, for all K ∈ T ,

Summing on K ∈ T , we get

58

Let us set χ(z) = K∈T 1 B(x K ,2h) (z). We have d(x K , K) ≤ h, so χ(z) = 0 if z is at a distance superior to 3h of Q. We may assume that 3h < 1, and then χ(z) = 0 if z / ∈ Q , where Q is the cube [-1, 2) d -which is contained in 3 d translates of Q 1 . By (5.29), we also have

Indeed, |z -x K | < 2h implies d(z, K) < 3h. Since the cells in T are disjoint, we have

Let K ∈ T . Similarly, we have

Summing on K ∈ T and using the fact that the cardinal of the set {K : d(K, z) ≤ h} is bounded by Cα -1 , we get the second estimate of (5.106).

Exercise 5.11 (Modulus of continuity of functions of bounded variation). Show that

for all u ∈ BV(T d ), for all 0 ≤ h ≤ 1, where ω L 1 (u; h) is the modulus of continuity defined by (5.61) and where C is a constant depending on the dimension d only.

The solution to Exercise 5.11 is here.

Contraction in L 1 . We will also need the following proposition.

Proposition 5.16 (L p -conservation). Let u, v ∈ L ∞ (T d ×(0, T )) be some weak solutions to (5.5) on (0, T ) with respective initial data u 0 , v 0 ∈ L ∞ (T d ). Assume that a is divergence free. Then, for every p ∈ [1, +∞], we have

for all t ∈ (0, T ).

Proof of Proposition 5.16. We use Theorem 5.6. By linearity, we can assume v ≡ 0. We have u(x, t) = u 0 • Φ t (x). This gives (5.109) since Φ t is a bijection of T d (case p = +∞) and preserves the measure (case p ∈ [1, +∞)), since a is divergence free.

A trivial consequence of (5.109) is that

(5.110)

We will also use Proposition 5.2, which gives (with obvious notations)

(5.111) for all t ≥ 0.

Reduction 1. Discrete time. Let t ∈ [0, T ].

There is a unique n ≥ 0 such that t n ≤ t < t n-1 .

We have then u h,∆t (t) = u h,∆t (t n ) and

Since a is divergence free, Φ t and φ t preserve the Lebesgue measure, so

by (5.108). Here,

The group property of the flow gives

where C depends on d, C 0 and a L ∞ (T d ) . This shows that it is sufficient to establish (5.82) for a time t in the discrete grid {t n ; n ≥ 0}. We proceed to this reduction to extend the analysis done in the proof of Theorem 5.5. Indeed, in the proof of Theorem 5.5, it was assumed that the test function ϕ was compactly supported in T d × [0, T ). It is easy however to extend our proof to the case where T = t N and ϕ ∈ C 1 (T d × [0, T ]). We have then an additional term for t = T to take into account, and (5.62) will be replaced by the inequality

]. Let v 0 be the L 2 -projection (see (5.102)) of u 0 on the functions which are piecewise constant with respect to the periodic mesh T 0 = L -1 (Q + Z d ). This mesh satisfies (5.29) with h 0 = L -1 and α = (2d) -1 since

for all K 0 ∈ T 0 . By Proposition 5.15, we have

where C depends on the dimension d only. In view of (5.110)-(5.111), of the second estimate in (5.106) and of (5.108), we can replace u 0 by v 0 to establish (5.82). Consequently, we may assume without loss of generality that u 0 is piecewise constant with respect to T 0 . We use this first reduction step for the following reason: let t > 0 and let A = {u 0 > t} be a super-level set of u 0 . Then A is an union of given cells of T 0 . Let ∂A L -1 denote the L -1 neighbourhood of ∂A:

We want to prove that the volume

where the constant C depends on d only. To establish (5.113), denote by T 0 [∂A] the set of cells K ⊂ A such that K ∩ ∂A is non-empty. We have

Since ∂K L -1 is included in the closure of the union of K and its 2d neighbouring cells, we obtain L -(d-1) .

(5.115)

The two estimates (5.114) and (5.115) give (5.113).

Reduction 4. Co-area formula. We apply Theorem 5.14. The equations we consider are linear: they satisfy a superposition principle. By (5.100), we may replace u 0 by the characteristic function of a super-level set A with finite perimeter. The advantage of this manipulation is the following one. Since 0 ≤ u h,∆t ≤ 1 by the comparison principle (Proposition 5.2), and

Note that ϕ (t) = ϕ (0) • Φ t , so (∂ t + a • ∇ x )ϕ = 0 in a weak sense. If we could use this ϕ as a test function in (5.112), we would get (taking (5.116) and then would have to work on the error terms. Since ϕ is not sufficiently regular to justify (5.116), we proceed differently and consider a regularized version of ϕ . Let T 1 denote the function

which truncates s when |s| > 1. Let δ denote the signed distance function

where d is the euclidean distance. We set

(5.117)

The functions T 1 and δ are Lipschitz continuous 5 , so ϕ 0 as well. This regularity is sufficient to justify, after a preliminary regularization procedure, that (5.112) is valid with ϕ as a test-function. We obtain (5.119) instead of (5.116). In the next section, we will explain how to exploit (5.119) to prove (5.82).

Remark 5.6. The step consisting in Reduction 3 is necessary in our method of proof. We can illustrate this in dimension d = 2. Indeed, assume from the start that u 0 is the characteristic function of a set A of finite perimeter, in which case the "Reduction 4" step is irrelevant. We consider

. . is the standard sequence used to define the triadic Cantor set and η > 0 will tend to 0. We take η > 0 only to get a non-trivial boundary ∂A n . To simplify the argument, let us work directly with K n . For ε = 3 -N , N ≥ 1 and n ≥ N , we have

) n , so the inequality

where C is an absolute constant, cannot be satisfied when n is too large.

Error estimate

We examine first the integral in the left-hand side of (5.119), that we would like to compare to the exact

By the conservation property (5.109) for p = 1,

We use the estimate (5.113), and the fact that

(5.120)

The first term u h,∆t (0)-u(0) L 1 (T d ) in the right-hand side of (5.119) is bounded by C|Du 0 |(T d )h as a consequence of Proposition 5.15. By (the proof of) Theorem 5.5 and (5.108), we have y,z). Taking the inf on z ∈ ∂A, we obtain d(x, ∂A) ≤ d(x, y) + d(y, ∂A). By symmetry, we also have

(5.118) Replacing A by A c shows that (5.118) holds true when x, y ∈ A c . If x ∈ A, y ∈ A c , then the segment [x, y] intersects ∂A at least at the point zτ defined by

in (5.124), let us fix n ∈ {0, . . . , N -1}. We have

where E n is the union of the cells K such that χ(K

under the CFL condition ∆t ≤ Ch. The estimate (5.125) shows that Φ tn (x) ∈ ∂A L -1 +Ch , and

Since Φ tn preserves the Lebesgue measure, we obtain the estimate

(5.126)

To get (5.126), we have used the estimate |∂A L -1 +Ch | ≤ C|∂A|(L -1 + h), which is a slight generalization of (5.113). It follows from (5.126) that S h 1/2 ≤ C|∂A|h 1/2 . We report this estimate in (5.124) (and use the bound ∆t ≤ C 0 h) to conclude that

By similar arguments, we obtain the analogous estimate

We have, indeed, by (5.122) and the bounds on ∇ x ϕ,

The first inequality in (5.59) reads

By the Cauchy-Schwarz inequality, we obtain

)S and the estimate on S given above yields (5.128). To sum up, we have shown that

(5.129)

We see here that, simply estimating D(t N ) from above by u 0 2 L 2 (T d ) will not be enough to conclude. Instead, the energy estimate (5.47) must be fully exploited. It gives, indeed (recall that t ∈ [t N , t N +1 ]) a bound on the quantity 2ξD(t N ) by the difference u 0 2

. By the conservation of the L p -norms in the continuity equation (5.5)

L 2 (T d ) . Since u(t) and u h,∆t (t) are bounded by 1 in L ∞ (T d ), we obtain

(5.130)

We report the estimate (5.130) and use the inequality 2ab ≤ ηa 2 + η -1 b 2 with a parameter η small enough (with respect to the constant C) to obtain

The error estimate (5.82) follows.

Solution to the exercises

Solution to Exercise 3.4. Since the stochastic continuity of (P t ) at s is equivalent to the weak convergence of P * t µ to P * s µ for all µ, we can use the Portmanteau Theorem and consider simply a function ϕ which is bounded and uniformly continuous. Given ε > 0, there exists δ > 0 such that d(x, y) < δ implies |ϕ(x) -ϕ(y)| < ε. We decompose then the difference

into two pieces. The first one is

which is bounded by ε. The second piece is

which can be bounded by 2 ϕ BC(E) P(d(X t , X s ) ≥ δ), which is smaller than ε for t close enough to s. Back to Exercise 3.4. Solution to Exercise 3.6.

1. That µ 0 = δ 0 means that X 0 always take the value 0 (X 0 is deterministic). We have then X 1 = ±1 with equi-probability, so

which is an example of Bernoulli's Law b( 12 ). We have then

The law of X 2 is therefore

(6.1)

3. The answer is that µ 0 is the uniform law on [-2, 2]:

where |A| is the Lebesgue measure of a Lebesgue set A ⊂ R (see the proof below for µ ∞ ). This answer can be simply guessed by examination of the evolution of the process (X n ).

An other way to find the right µ 0 is to look at µ N for large N . Indeed, a usual way to find an equilibrium for a system in evolution is to look as the behavior for large times: if there is convergence to a limit object, this will most probably be an equilibrium of the system.

Here, for example, one can look at the evolution starting from the binomial b(1/2) with values in {-2, +2}, as in Question 2. If ϕ ∈ BC(R), then

We recognize a Riemann sum, which converges to

ϕ(x)dx.

The limit law µ ∞ is an invariant measure for good. Indeed, if X 0 ∼ µ ∞ , then, by the formula of total probability,

for any Borel subsets A of R. This gives

We compute, by the invariance by translation of the Lebesgue measure and the change of variable formula,

Solution to Exercise 3.7. We will use the following result. Lemma 6.1. Let (E, d) be a complete, separable metric space. Then BC(E) is a separating class: if two probability measures ν 1 and ν 2 satisfy ν 1 , ϕ = ν 2 , ϕ for all ϕ ∈ BC(E), then ν 1 = ν 2 .

(b) The left-hand side of (4.14) is

.

By rearrangement, we obtain (4.14).

2. (a) For i = j, using independence, the event X i = X j has probability

This shows that #Π n < n with probability 0. (b) Here, the event Γ n (R d ) = n has probability 1, so

We consider the realization of the event

Drawing each random variable X i successively gives us n independent trials, where we have to test the (k + 1) outcomes X i ∈ A j , each having probability p j = ν(A j ): this is precisely the situation of a generalized Bernoulli test, described by the multinomial distribution. To be complete, let us prove this result. We use a recursion on n, starting from the trivial case n = 1. Without loss of generality, we assume that all n j , j = 0, . . . , k are strictly positive. We condition to the location of the first variable X 1 to obtain

We have P(X 1 ∈ A j ) = p j and

which gives the desired result by summation over j.

For each Borel subset

Using the notations of the previous questions, we have

which gives

There is no more n in this last expression. We explicit the summation over n 0 to obtain

We can pass to the limit in (6.11) (using monotone convergence) to extend the identity to the case where S is countable (again, discussing the case where all parameters λ n , n ∈ S are finite, or one is infinite). This yields the Superposition Principle.

5.

For each n, we can construct a Poisson process Π n with intensity µ n using some iid random variables (X n,m ) m≥1 and some independent Poisson variable N n of parameter µ n (R d ). It is always possible to ensure that the family {X n,m , N n ; n, m ≥ 1} is independent. Then we obtain independent Poisson point processes with intensity µ n . The Superposition Principle gives the result.

6. Suppose that

We can assume that the sets A n are disjoint, otherwise, we consider

Then (4.17) is realized with µ n =restriction of µ to A n .

2. We use the same kind of transformation as in (6.12) to see that

where A 1 = [0, t 1 ], A 2 = (t 1 , t 2 ], . . . , A k = (t k-1 , t k ]. Let m 1 = n 1 and m j = n j -n j-1 for j > 1. The result of the previous question shows that, conditionally to N (t k ) = n k , the event Γ(A 1 ) = m 1 , Γ(A 2 ) = m 2 . . . , Γ(A k ) = m k corresponds to the arrangement of m j among n k independent uniform variables U i on [0, t k ] in the set A j , for all j. This is the multinomial distribution (already discussed in Exercise 4.5) that gives therefore the probability: Solution to Exercise 5.2. Same proof as in the case A = A(v). This times we use the divergence-free condition (div x A)(x, v) = 0. Back to Exercise 5.2.

Solution to Exercise 5.3. We suppose that α is fixed of course. Consider a mesh with triangles only. If one triangle as a basis of length ∼ h, but a height that is almost 0, i.e. if there is an almost flat triangle in the mesh, then the first condition in (5.29) may not be satisfied.

If we consider triangles only then |∂K| ≤ 3 diam(K) ≤ 3h for any K. Now, consider a triangle with a basis of length ∼ 1, and a height ∼ h. Then fold the "arrow" of this triangle to form a polygonal set of diameter O(h) and perimeter ∼ 1. If T contains such kind of set, then the second condition in (5.29) will not be satisfied. Back to Exercise 5.3.