Victor Kleptsyn

Aline Kurtzmann

A counter-example to the Cantelli conjecture

In this paper, we construct a counter-example to a question by Cantelli, asking whether there exists a non-constant positive measurable function ϕ such that for i.i.d. r.v. X, Y of law N (0, 1), the r.v. X + ϕ(X) • Y is also Gaussian.

For the construction that we propose, we introduce a new tool, the Brownian mass transport: the mass is transported by Brownian particles that are stopped in a specific way. This transport seems to be interesting by itself, turning out to be related to the Skorokhod and Stefan problems.

Introduction 1.A bit of history

The general thema of this paper is the following:

Cantelli conjecture (1918). Let X, Y be two real random variables, of standard Gaussian distribution law. Suppose that X and Y are independent. Let ϕ be a measurable non-negative function. Then the random variable X + ϕ(X) • Y has a Gaussian distribution law if and only if ϕ is constant.

Actually, Cantelli has originally mentioned this as a question, asking whether it is possible to have a non-constant function ϕ, in his paper [2, p.407], but later it became known as Cantelli conjecture. This conjecture has been previously studied by different authors. First, Tortorici [START_REF] Tortorici | Soluzione approssimata di un'equazione integrale di Cantelli[END_REF] has given some restriction on the function ϕ to satisfy the conjecture. To do that, he has developed ϕ in a Hermite series and has approached the solution (via a truncation of the series). Then, Tricomi [START_REF] Tricomi | Einige ungelöste Probleme der klassischen Analysis[END_REF] has used analytical tools in order to describe some properties satisfied by the function ϕ (through the characteristic function). In the same paper, he has also given a survey on this subject. Later, Dudley [START_REF] Dudley | The Gaussian Process and How to Approach It[END_REF] has exposed two unsolved problems about finite-dimensional Gaussian measures. One of them was Cantelli conjecture. Dudley said about it "The problem seems to be a mere curiosity, but that will perhaps be unclear until it is solved". Letac has also worked on this problem and has emphasized this question, in his exercise book with Malliavin [START_REF] Letac | Integration and Probability (Exercises and solutions)[END_REF]. Indeed, they have suggested an exercise, showing that the decomposition of ϕ with respect to the Hermite polynomials, that is ϕ(x) = n≥0 ϕ n Hn(x) n!

(in the L 2 (e -x 2 /2 dx √ 2π ) sense) is such that ϕ 1 = 0, -2ϕ 2 = n≥2 ϕ 2 n n! and ϕ(x) ≤ ϕ 0 + 1 almost everywhere.

Finally, this striking question has been mentionned by de Meyer, Roynette, Vallois and Yor [START_REF] Meyer | On independent times and positions for Brownian motions[END_REF]. Actually, they answered a related question, asked by Tortrat. Consider a standard (F t , t ≥ 0)-Brownian motion, denoted by (B t , t ≥ 0). Can one find an a.s. bounded random variable Z, non-constant and F 1 -measurable, such that B 1 + Z(B 2 -B 1 ) has a Gaussian distribution law? De Meyer et al. have proved the existence of a linear standard (F t , t ≥ 0)-Brownian motion (B t , t ≥ 0), and a stopping time T (w.r.t. (F t , t ≥ 0)) which is bounded by 1, non-constant and such that B T has a Gaussian distribution law. Thanks to this result, they have shown that the random variable B 1 + √ T (B 2 -B 1 ) has a Gaussian distribution law. In their example, √ T is F 1 -measurable, bounded and non-constant. However, one cannot write √ T as a function of B 1 . So this construction does not contradict the Cantelli conjecture.

Before turning to the results of this paper, we would like to mention two problems, that turn out to be closely related to the Brownian transport notion, which is an essential part of our proof: the Skorokhod embedding problem and the Stefan problem.

The Skorokhod embedding problem is the following. For a given centered probability measure µ with finite second moment and a Brownian motion B, one looks for an integrable stopping time T such that the distribution law of B T is µ. Several authors have developed different techniques to solve this problem, which has stimulated research in probability theory since the first formulation of Skorokhod [START_REF] Skorokhod | Issledovaniya po teorii sluchainykh protsessov (Stokhasticheskie differentsialnye uravneniya i predelnye teoremy dlya protsessov Markova)[END_REF]. A survey has been written by Oblój [START_REF] Oblój | The Skorokhod embedding problem and its offspring[END_REF] on this subject. Some properties of stopping times or Skorokhod stopping have also been intensively studied in the 70's and 80's (see for instance [START_REF] Fitzsimmons | Penetration time and Skorohod stopping[END_REF][START_REF] Rost | The stopping distributions of a Markov process[END_REF][START_REF] Shih | Ordered Skorokhod Stopping for a Sequence of Measures[END_REF]). In this paper, we will give a solution to a somehow similar problem, and construct (under some assumptions) a stopping time T which is a function of the Brownian motion: ∃g such that T = g(B T ).

Our problem can actually be reduced to a PDE problem of the Stefan type (see for instance Rubinstein [START_REF] Rubinstein | The Stefan Problem[END_REF]), as we will explain later. Stefan problem is an old question, first considered in 1831 by Lamé and Clapeyron. It is actually a free boundary problem, initially used to predict ice formation/melting. For a historical survey on the problem, we refer the reader to Vuik [START_REF] Vuik | Some historical notes about the Stefan problem[END_REF].

Statement of the results

Our main result will be the following Theorem 1.1. There exists a measurable non-constant function ϕ : R → R + such that for two independent standard Gaussian variables X, Y ∼ N (0, 1), the random variable X + ϕ(X) • Y is also Gaussian.

In fact, as we will see from the construction in Section 2, the function ϕ can be taken to be a "choice" between two continuous functions:

ϕ(x) = ϕ 0 (x), x ∈ K, ϕ 1 (x), x / ∈ K,
where K is a Cantor set of positive Lebesgue measure and ϕ 0 , ϕ 1 ∈ C(R).

Actually, the function ϕ we construct here is discontinuous. We believe that Cantelli conjecture is true if we impose the continuity of the function ϕ, but we have no proof for that.

In the proof of Theorem 1.1, there is a notion that naturally appears, the one of a new mass transport, that we name Brownian transport Definition 1. Let µ 0 , µ 1 be two probability measures, with the same mean and square integrable. We say that there exists a Brownian transport from µ 0 to µ 1 if, for a random process (X t , t ≥ 0) such that X 0 ∼ µ 0 and dX t = dB t (where B is a real Brownian motion independent of µ 0 ), one can find a stopping time T with finite expectation, and a function f such that i)

X T ∼ µ 1 , ii) a.s. T = f (X T ).
We say that f is the stopping funtion of this transport.

If moreover the time T is a.s. bounded, we say that there exists a bounded Brownian transport from µ 0 to µ 1 .

Its study seems highly interesting on its own (see §4.1-4.2). However, in this paper, we will prove only two existence theorems, and their assumptions are clearly far from being optimal: we prove the results that would suffice to conclude the proof of Theorem 1.1.

We point out that such a transport does not always exist. In particular, a Brownian transport cannot exist if the target measure µ 1 is atomic (unless µ 0 has atoms at the same place). Moreover, we cannot for instance transport the uniform measure on [-1, 1] to the uniform measure on [-1/2, 1/2]: the variance cannot be decreased by a Brownian transport. The bounded Brownian transport is even more restrictive: for instance, it cannot create "holes" inside the support of the measure, a necessary condition for its existence is that Supp(µ 0 ) ⊂ Supp(µ 1 ).

We will discuss the existence of a Brownian transport later, in Section 2. Nevertheless, to construct a counter-example to Cantelli conjecture, we will consider probability measures such that a bounded Brownian transport exists (and the proof of its existence is an essential step in the construction). The second main result here is the following Theorem 1.2. Let µ 0 , µ 1 be two centered probability measures, square integrable and which support is R. Suppose that, for any R large enough, the troncated probability measures μR 0 =

µ 0 | [-R,R] µ 0 ([-R,R]) and μR 1 = µ 1 | [-R,R] µ 1 ([-R,R]
) satisfy: i) μR 0 and μR 1 are absolutely continuous with respective densities ρ µ 0 and

ρ µ 1 , ii) there exist a R , b R > 0 such that for all -R ≤ x ≤ R, we have ρ µ 0 (x) ≥ a R and ρ µ 1 (x) ≤ b R , iii) there exists α R > 0 such that for any J ⊂ [-R, R], we have µ 1 (J) ≥ e -α R /|J| .
Assume also that iv) for any x ∈ R, we have

Φ µ 0 →µ 1 (x) := x -∞ (µ 0 -µ 1 )((-∞, s]) ds > 0, v) lim sup |x|→+∞ ρµ 0 (x) ρµ 1 (x) < 1.
Then, there exists a Brownian transport from µ 0 to µ 1 , with a possibly unbounded stopping time T . Moreover, this Brownian transport is given by the first intersection time with the graph of some continuous function f .

Remark. We can actually suppose in the latter theorem that the measures µ 0 , µ 1 have the same mean (instead of being centered).

An analogous question can be asked also for measures supported on an interval. This question, on one hand, turns out to be a bit simpler than the real line one (due to the compactness and lack of effects at infinity). On the other hand, it becomes one of the steps in our proof of Theorem 1.2: the function f is constructed as a limit of a subsequence of functions f R corresponding to a "cut-off" problem. The corresponding theorem is Theorem 1.3. Let µ 0 , µ 1 be two probability measures, with the same mean, square integrable and which support is an interval I ⊂ R. Suppose that they satisfy the hypotheses: i) µ 0 , µ 1 are absolutely continuous with respective densities ρ µ 0 , ρ µ 1 , ii) there exist a, b > 0 such that for all x ∈ I, we have ρ µ 0 (x) ≥ a and ρ µ 1 (x) ≤ b,

iii) there exists α > 0 such that for any interval J ⊂ I, we have µ 1 (J) ≥ e -α/|J| , iv) for all x ∈ I, we have

Φ µ 0 →µ 1 (x) := x -∞ (µ 0 -µ 1 )((-∞, s]) ds > 0, v) ρ µ 0 > ρ µ 1 in some inner neighborhood U ε (∂I) ∩ I.
Then, there exists a bounded Brownian transport from µ 0 to µ 1 , given by the first intersection time with the graph of some continuous function f . The proof of these two results will be done in several steps. First, we will do some a priori estimates and transformations, answering the question "assuming that such a transport exists, how should it look like?". The understanding coming from these steps will leave us with some kind of a PDE problem, of the Stefan type.

However we could not establish the existence theorems for this problem directly, by PDE methods (in fact, it seems to be an interesting question to us), we establish them via a discretization procedure: we solve an analogous discrete problem and pass to the limit as the mesh goes to 0. This part is rather technical and is postponed to §4.2.

Remark. Some assumptions of Theorems 1.2 and 1.3 seem non restrictive, such as the positivity of Φ µ 0 →µ 1 inside I for Theorem 1.3. Indeed, a necessary condition is that the function Φ is non-negative (see Corollary 3.2). Though, in the case of a non-negative function Φ that is not positive everywhere inside I, one can simply split the interval I into the intervals of positivity of Φ (see Lemma 3.4). Other assumptions, such as (iii), seem unavoidable in order to assure the uniform boundedness of the stopping time. Indeed, otherwise, the first intersection measure of the Brownian motion with the graph of an unbounded function f , say f (x) = 1 |x| , would satisfy the assumptions of the theorem. But it is very likely that it cannot be obtained by means of a bounded Brownian transport. Finally, some assumptions (such as the absolute continuity of µ 0 or the lower bound for its density) surely can be weakened. It is highly interesting to study what are the "correct assumptions" for the existence of a Brownian transport. But we are not doing it in the present work: the statement of Theorem 1.3 suffices for our construction.

Outline

Let us indicate how the rest of the paper is organized. In Section 2, we present a construction of a counter-example to the Cantelli conjecture, based upon the existence of a certain bounded Brownian transport.

Next, in Section 3, we are doing some a priori estimates: assuming that a Brownian transport exists, we deduce some conclusions describing it. In particular here, the function Φ defined in Theorem 1.2 naturally appears (and becomes one of the main objects of our consideration). We will also explain how it is naturally related to a PDE of the Stefan type. In §3.2, using these estimates, we deduce from Theorem 1.2 that the Brownian transport (that we refer to in our counter-example construction) is indeed a bounded one (checking the behaviour of the corresponding function f at the infinity). This completes the construction of our counter-example (modulo Theorem 1.2).

In Section 4, we are proving Theorems 1.2 and 1.3. First, in §4.1, considering the restriction on the intervals [-R, R] and passing to the limit, we prove the existence of a Brownian transport for measures on the real line, deducing Theorem 1.2 from Theorem 1.3. Then, in §4.2, by means of the discretization technique, we establish the existence of a Brownian transport on an interval, proving Theorem 1.3.

Construction

The first step in the proof of Theorem 1.1 is the following idea, close to [START_REF] Meyer | On independent times and positions for Brownian motions[END_REF]. Consider the standard Brownian motion (B t , t ≥ 0), and let T = T (ω) be a stopping time (w.r.t. the standard family (F t , t ≥ 0) of σ-algebras), such that T < C almost surely for some constant C. Then, ( 1)

B C = B T + (B C -B T ) = B T + √ C -T • ξ,
where the random variable ξ := B C -B T √ C-T is a standard Gaussian variable N (0, 1) and is independent from B T due to the Markov property. Now note that B C is a Gaussian random variable, so

B T + √ C -T • ξ ∼ N (0, C), B T ⊥ ⊥ ξ, ξ ∼ N (0, 1). (2)
Compare it to what we need to prove Theorem 1.1 (and hence to disprove the Cantelli conjecture):

(3)

X + ϕ(X) • Y ∼ N (0, •), X ⊥ ⊥ Y, X, Y ∼ N (0, 1).
This comparison immediately gives us the following conclusion:

Proposition 2.1. Let T = T (ω) be a non-constant stopping time for the standard Brownian motion (B t , t ≥ 0), and assume that the following holds:

i) ∃C : ∀ω T (ω) < C;
ii) The law of B T is the standard Gaussian law: B T ∼ N (0, 1);

iii) There exists a measurable function f : R → R + , such that almost surely

T = f (B T ).
Then, the function ϕ(x) = C -f (x) provides us a counter-example to the Cantelli conjecture.

Remark. There is one subtlety with the property iii) that we would like to emphasize. While this property says that the stopping moment T should be equal to a function of the place B T where the process was stopped, it does not say that we should stop the process immediately once the equality t = f (B t ) is satisfied. Moreover, for the construction in the proof of Theorem 1.1, it is not true that T = min{t :

t = f (B t )}.
This is where the Brownian transport notion naturally appears. The assumption of this proposition can be rephrased as the existence of a Brownian transport from the Dirac measure δ 0 to the Gaussian measure N (0, 1), with a non-constant bounded stopping time T . In fact, the Brownian transport notion will appear further in even more "clear" way, see Problem 1 below.

We can now describe how the stopping time T , satisfying the assumptions of Proposition 2.1, will be constructed. We will fix a moment t 0 ∈ (0, 1) and choose in a small neighborhood of the origin a Cantor set K ⊂ R of positive Lebesgue measure (with some restrictions on its geometry), such that on this set the density of the law N (0, 1) is everywhere upper bounded by the density of the law N (0, t 0 ):

ρ N (0,t 0 ) (x) > ρ N (0,1) (x) ∀x ∈ K.
Then, at the moment t 0 , for any x ∈ K, we stop

ρ N (0,1) (x)
ρ N (0,t 0 ) (x) 's part of all the trajectories passing through x at this moment. To do so, one can either use a probabilistic Markov time, modifying the initial probability space of the Brownian motion by multiplying it by [0,1], or note that the random variable S t 0 (ω) := sup 0≤t≤t 0 |B t (ω)| has a continuous conditional distribution w.r.t. any condition B t 0 = x, and hence, denoting by κ(α, x) the α-quantile of the corresponding conditional distribution, we can put ( 4)

T (ω) = t 0 if x := B t 0 (ω) ∈ K and S t 0 (ω) ≤ κ ρ N (0,1) (x) ρ N (0,t 0 ) (x) , x .
This stopping ensures that the transport time T and the corresponding function f are non-constant: there is something left to transport.

The following problem now remains. At the moment t 0 , there is a conditional distribution of not yet stopped trajectories, with the density:

(5) ρ 0 (x) = c -1 ρ N (0,t 0 ) (x), x / ∈ K, c -1 ρ N (0,t 0 ) (x) -ρ N (0,1) (x) , x ∈ K,
where c = P(N (0, 1) / ∈ K). Now, we are left with the following problem. We want to stop these trajectories at a bounded stopping time T , such that

i) T = f (B T ), ii) the law of B T conditionally to T > t 0 is the restriction (to R \ K) of the standard Gaussian law N (0, 1)| R\K .
In other words, we are looking for a solution of the following Problem 1. Find a bounded Brownian transport from µ 0 = ρ 0 dx, given by (5), to µ 1 which is the conditional distribution of N (0, 1) on R \ K.

Indeed, once Problem 1 is solved with the bounded stopping time T 1 such that T 1 = f 1 (B T 1 ), we can take for the original problem

(6) T (ω) = t 0 , if x := B t 0 (ω) ∈ K and S t 0 (ω) ≤ κ( ρ N (0,1) (x) ρ N (0,t 0 ) (x) , x), t 0 + T 1 , otherwise.
where T 1 is evaluated on the trajectory X t = B t 0 +t . We then have ( 7)

f (x) = t 0 , if x ∈ K, t 0 + f 1 (x), if x / ∈ K.
Remark. It is important to note that, due to the choice of the "target measure" µ 1 , the stopping point of the process (X t , t ≥ 0) a.s. does not belong to K. Hence, even though in [START_REF] Oblój | The Skorokhod embedding problem and its offspring[END_REF], the function f on K does not coincide with t 0 + f 1 (x), the equality T = f (B T ) still a.s. holds for the trajectories not yet stopped at time t 0 .

Actually, Problem 1 is a particular case of a wider question, closely related to the Skorokhod embedding problem, that we state below. This question seems very interesting to us, but, at the best of our knowledge, it has not been studied until now. Problem 2. Let two probability measures µ 0 and µ 1 , with the same mean and finite second moment and which support is R, be given. Find a bounded Brownian transport from µ 0 to µ 1 .

It is obvious that such a Brownian transport does not always exist. Evidently, one has to ask E(µ 0 ) = E(µ 1 ) and Var(µ 0 ) ≤ Var(µ 1 ). However, these two hypotheses are clearly insufficient. We will study this question in the next section and find a stronger necessary condition, and, what is more important, a sufficient one. Moreover, under this sufficient condition, the function f can be taken to be continuous, with the moment T being the first intersection time of the trajectory (X t , t ≥ 0) with the graph of f :

T (ω) = inf{t ≥ 0 : t = f (X t )}.
Problem 1 will then be deduced as a result of an application of this sufficient condition. It will be done below, in Section 3. Namely, we have the following result Theorem 2.2. Assume that K ⊂ [-1, 1] and that there exists α > 0 such that, for any interval I ⊂ [-1, 1], one has Leb(I \ K) ≥ exp{-α/|I|}. Then, there exists a solution T 1 to Problem 1 and the corresponding function f 1 is continuous. Moreover, T 1 can be represented as a "first intersection" moment It is not difficult to construct a compact set K satisfying the assumptions of Theorem 2.2. Actually, if in the standard construction of the Cantor set, one chooses to remove on the n-th step an 1 (n+1) 2 -th part around the middle of the previously constructed intervals, the obtained Cantor set K satisfies the assumptions of Theorem 2.2. Moreover, for this Cantor set, an even stronger estimate holds: Leb(I \ K) ≥ α|I| 2 for some universal constant α.

T 1 (ω) = inf{t ≥ 0 : t = f 1 (X t )}.
Once such a set K is constructed, the above arguments allow us to deduce Theorem 1.1 from Theorem 2.2. So the task of disproving the Cantelli conjecture is reduced to proving Theorem 2.2.

3 Ideas: the function Φ and some a priori arguments

In the following, for a regular time-space function Φ : R + × R → R, (t, x) → Φ t (x), we denote by Φt (x) = ∂ t Φ t (x) its time-derivative. Moreover, for an absolutely continuous measure µ, we denote by ρ µ its density distribution function. The ε-neighborhood of a set I is denoted by U ε (I). As all the objects we consider in this section are invariant by a translation, we will suppose that the measures µ 0 , µ 1 are centered.

The transport function Φ and Stefan-type problem

Before going deeper into the proof of the existence theorems (Theorems 2.2, 1.2 and 1.3), let us first do some a priori arguments: assuming that a Brownian transport from some centered measure µ 0 to some other centered measure µ 1 exists (both µ 0 , µ 1 having a finite second moment), what could be its properties and how could it be described?

The tool that is very useful for such a description is the following notion Definition 2. Let µ be a measure on R, with finite second moment. Then, we denote by Φ µ the primitive of its repartition function F µ (x) := µ((-∞, x]):

(8) Φ µ (x) := x -∞ µ((-∞, s]) ds.
An easy computation then shows that

Φ µ (x) = x -∞ (x -y) dµ(y) = xµ((-∞, x]) - x -∞ y dµ(y) = x -xµ([x, +∞)) + E(µ) - +∞ x y dµ(y) = x -E(µ) + +∞ x µ([s, +∞)) ds. ( 9
)
In particular, for any two such measures µ 0 , µ 1 , the difference between the corresponding functions [START_REF] Shih | Ordered Skorokhod Stopping for a Sequence of Measures[END_REF] Φ µ 0 →µ 1 (x) := Φ µ 1 (x) -Φ µ 0 (x) converges to 0 as x tends to -∞ and as x → +∞. The role of Φ is then given by the following result. Let (X t , T ) be a Brownian transport from µ 0 to µ 1 . Denote by Xt := X t∧T the "stopped" process, by νt its distribution law at time t, and by ν t the (non-probability) measure given by the "not yet stopped" particles: for any Borel set A, we have ν t (A) = P(X t ∈ A, t < T ).

Lemma 3.1. Φνt = 1 2 ρ νt .

Proof. Indeed, we have d Xt = 1 t<T dB t and hence by the heat equation, we have Φνt = 1 2 ρ νt . An immediate corollary to this lemma is the following Corollary 3.2. Let µ 0 , µ 1 be two centered absolutely continuous probability measures, with finite second moment. Suppose that there exists a Brownian transport from µ 0 to µ 1 . Then, for any x ∈ R, we have Φ µ 0 →µ 1 (x) ≥ 0.

Proof. It is obvious from Lemma 3.1 that the functions Φ t (x) := Φ νt→µ1 (x) = Φ µ 1 (x)-Φ νt (x) are monotonically decreasing with t for any fixed x. The only thing we have to check is that Φ t (x) converges pointwise to 0 (what is evident in the case of a bounded Brownian transport, but needs to be justified in general). Indeed, Xt is a martingale and its variation

Var( Xt ) = Var( X0 ) + E(t ∧ T ) ≤ Var(µ 0 ) + ET < ∞
is uniformly bounded. Hence (see for instance Thm 4.3.3 in [START_REF] Benaïm | Promenade aléatoire[END_REF]), we have that Xt converges in L 2 to X∞ (ω) := lim t→∞ X t (ω) and thus

Φ νt (x) = x -∞ P( Xt ≤ s) ds = Ω | Xt (ω) -s| -dP(ω) ---→ t→∞ Ω | X∞ (ω) -s| -dP(ω) = Φ µ 1 (x),
where we have denoted |a| -:= |a| • 1 a≤0 .

These proofs, in fact, suggest us a way of constructing the stopping time T . Namely, together with the process (X t , t ≥ 0), we consider an increasing family of closed sets K t = {Φ t = 0} (that will be in fact sections of the supergraph of f : K t = {x ∈ R : t ≥ f (x)}, as shown in Figure 2 below). We stop the process once it reaches this family:

T = inf{t ≥ 0 : X t ∈ K t }.
The function f will then be defined as

f (x) = inf{t ≥ 0 : x ∈ K t } = inf{t ≥ 0 : Φ t (x) = 0}.
Roughly speaking, we let the function Φ t = Φ νt→µ1 decrease (as Φt ≤ 0), and once it vanishes somewhere, we add this place to the set K t of "stopped motion". Due to this description, we will call in the future Φ µ 0 →µ 1 the cost function of the Brownian transport from µ 0 to µ 1 .

Φ t = 0 K t K t x t Figure 2: Construction of K t
We wish to emphasize that the above description is absolutely unrigorous. It cannot be used without proving the corresponding existence theorems that do not seem to have an obvious direct proof. So, we will prove them in Section 4, via the discretization procedure. However, it gives an explanation why Theorems 1.2 and 1.3 should hold.

Moreover, this description can be (for the case of an absolutely continuous measure µ 0 ) rephrased in terms of Stefan-type problem. Namely, the density ρ t = ρ νt obeys the heat equation ρt = 1 2 ∆ρ t with the (moving) Dirichlet boundary condition ρ t | Kt = 0. So, the couple (Φ t , ρ t ) and the function f (x) obey the system (11)

         Φt = -1 2 ρ t , ρt = 1 2 ∆ρ t if t < f (x), Φ f (x) (x) = 0, ρ f (x) (x) = 0,
where the third equation defines the function f , while the last one is considered as a boundary condition on ρ.

We will not go deeper into giving fully formal sense to the system (11) (for instance, note that on the graph of f , the derivative Φt can be discontinuous and if f is constant on some interval, then at the corresponding points, the density ρ will abruptly go to 0). As we have already mentioned in the Introduction, we could not prove the existence theorem here by PDE methods (though it would be interesting to find such a direct proof). However, we would like to emphasize here that the system (11) seems analogous to the Stefan problem of melting ice (see [START_REF] Rubinstein | The Stefan Problem[END_REF], [START_REF] Vuik | Some historical notes about the Stefan problem[END_REF]).

Even though we have not yet established the existence of the process described by the above rules, for the rest of this paragraph, we will -in order to understand the ideas before passing to the technical part-assume that it exists, and will study its behaviour. Note that one of the questions appearing (and that will be answered below) is the following one: does Φ t vanish everywhere in finite time? To answer this question, it is natural to consider the connected components of R \ K t and to study their evolution. In fact, to prove Theorem 2.2, we have to show that any of them disappears in a finite time. This will be done in Lemma 3.4. The next result deals with "disconnecting" different intervals from each other, allowing us to study their evolution separately. Lemma 3.3. Let µ, ν be two centered absolutely continuous probability measures on R, with finite second moment, such that Φ ν→µ is non-negative. Let x ∈ R be such that Φ ν→µ (x) = 0. Then, the measures µ and ν of the interval (-∞, x] coincide, as well as the expectations of the conditional measures

ν| (-∞,x] ν((-∞,x]) and µ| (-∞,x] µ((-∞,x]) .
The same holds for the restrictions on the interval [x, +∞) and on any interval [x, y] provided that Φ ν→µ vanishes at both of its endpoints.

Proof. As the measures ν and µ are non-atomic, the function Φ ν→µ is of class C 1 . But, as Φ ν→µ is non-negative and Φ ν→µ (x) = 0, the point x is a minimum of the function Φ ν→µ . Hence ∂ x Φ ν→µ (x) = 0. Noting that ∂ x Φ ν→µ (x) = -µ((-∞, x]) + ν((-∞, x]), we obtain the first conclusion of the lemma. Now, remember the identity (9):

Φ µ (x) = x -∞ (x -y) dµ(y) = xµ((-∞, x]) - x -∞ y dµ(y).
As Φ ν→µ (x) = 0, and thus Φ µ (x) = Φ ν (x), we have [START_REF] Tortorici | Soluzione approssimata di un'equazione integrale di Cantelli[END_REF] xµ((-∞, x]) -

x -∞ y dµ(y) = xν((-∞, x]) - x -∞ y dν(y).
The equality between the first terms in the left and right hand sides of ( 12) is already established and thus implies the equality between the last terms.

The other issues of the lemma are direct corollaries of the proved ones.

Some a priori arguments and proof of Theorem 2.2

We are now ready to deduce Theorem 2.2 from Theorem 1.2. In other words, still assuming that the description in §3.1 defines us the desired process, we conclude the construction of the counter-example to the Cantelli conjecture. This deduction will be split in several lemmas. A natural notion that has already inexplicitely appeared is the following Definition 3. Let µ 0 , µ 1 be two centered measures, with finite second moment. We say that there exists a continuous Brownian transport from µ 0 to µ 1 if there exists a Brownian transport (X t , T ) from µ 0 to µ 1 such that T = f (X T ) where f is continuous and T is a first intersection time with the graph of f .

The transport we have constructed in Section 2 is actually a continuous one: the transports of Theorems 1.2 and 1.3 are continuous.

A first tool that we need is the following general lemma, that allows to estimate from above the time in which a connected component of R \ K t "disappears". Lemma 3.4. Let ( Xt , K t ) be constructed as described above ( §3.1) for some probability measures µ 0 , µ 1 with the same mean and finite second moment (but perhaps with no time t such that Kt = R). Let I be an interval which is a connected component of R \ K t (at some time t). Assume that for any interval J ⊂ I, we have µ 1 (J) ≥ exp{-α/|J|}. Then, there exists a constant θ (which does not depend on I) such that I ⊂ K t+θα|I| .

Proof. We will first prove the following auxiliary statement: there exists a constant θ 0 such that, at the moment t := t + θ 0 α|I|, any connected component of I \ K t is of length less than |I|/2. This statement will imply the conclusion of the lemma. Indeed, applying it again to the connected components of I \K t+θ 0 α|I| , we see that, at the moment t = t+θ 0 α|I|+ θ 0 2 α|I|, the lengths of connected components of I \K t do not exceed α |I| 4 . We repeat this procedure. Thus, at the moment t + 2θ 0 α|I|, we have I ⊂ K t+2θ 0 α|I| . This concludes the proof.

Let us now prove the latter statement. Indeed, note that for any interval of complement J ⊂ R \ K t , the Wiener measure of the trajectories that are still moving inside J at the time t is equal to µ 1 (J). Indeed, as J is a connected component of R \ K t , we have Φ t | ∂J = 0 and hence Lemma 3.3 can be applied. So to prove that at some moment t > t, the length of any connected component J ⊂ I \ K t is less than |I|/2, it suffices to show that, at this moment, the proportion of trajectories that have not yet intersected the graph of f is at most exp(-α |I|/2 ). To do this, we consider a weaker stopping condition: the trajectory is stopped once it reaches the boundary of I. The density of such a process is given by the heat equation with the Dirichlet boundary conditions on I. The measure of not yet stopped trajectories at the moment t + τ is then given by the scalar product ϕ τ , 1/|I| , where

φτ = 1 2 ∆ϕ τ , ϕ τ | ∂I = 0, ϕ 0 = ρ t .
As the Laplace operator is self-adjoint, this scalar product is equal to ψ τ , ϕ 0 ,

where ψτ = 1 2 ∆ψ τ , ψ τ | ∂I = 0, ψ 0 = 1 |I| .
Thus, this scalar product doesn't exceed |I| • sup I ψ τ . Re-scaling the interval I to [0, 1] and accordingly multiplying the time by 1/|I| 2 and the initial function by |I|, we obtain an upper bound by [START_REF] Tricomi | Einige ungelöste Probleme der klassischen Analysis[END_REF] sup

[0,1] n c 2n+1 exp - π 2 (2n + 1) 2 2|I| 2 τ sin(π(2n + 1)x),
where c 2n+1 = 2 2n+1 are the nonzero Fourier coefficients of the function 1 with respect to the eigenfunctions sin(π(2n+1)x) of the Laplace operator on [0, 1].

Estimating c n by 1 in [START_REF] Tricomi | Einige ungelöste Probleme der klassischen Analysis[END_REF] and the exponents by a geometric series, we see that this supremum does not exceed exp{-

π 2 2|I| 2 τ } • 1 1 -exp{-π 2 |I| 2 τ } . Now, note that for τ = 8 π 2 α|I|, the first factor is exp{-4 α |I| } = exp{-α |I|/2 } 2 .
Thus, the product is at most [START_REF] Vuik | Some historical notes about the Stefan problem[END_REF] exp{-

α |I|/2 } • exp{-α |I|/2 } 1 -exp{-α |I|/2 } .
Note finally that exp{-α |I|/2 } is at most 1/2, as otherwise the µ 1 -measures of both left and right halves of I would be greater than 1/2. Hence, the second factor in ( 14) is not greater than 1 and we have obtained the desired estimate by exp{-α |I|/2 }. The next results are for the particular case of the transport in Theorem 2.2, based essentially on the specifics of Gaussian distributions. Namely, let µ 0 and µ 1 be as in Theorem 2.2. Lemma 3.5. µ 0 and µ 1 satisfy the assumptions of Theorem 1.2.

Proof. The conditions i) and v) are obvious and the fact that the measures µ 0 , µ 1 have the same mean comes from the fact that we are removing the same part from N (0, t 0 ) and N (0, 1). Conditions ii) and iii) are due to the assumptions on K. We only have to prove iv). Indeed, the function Φ µ depends linearly on µ: Φ αµ+βν = αΦ µ + βΦ ν . Due to the definition of µ 0 and µ 1 , we have that

Law(N (0, t 0 )) = cµ 0 + (1 -c)µ , Law(N (0, 1)) = cµ 1 + (1 -c)µ
where µ is the conditional distribution law of N (0, 1) on K. Hence,

Φ µ 0 →µ 1 (x) = c -1 Φ N (0,t 0 )→N (0,1) (x) = c -1 1 t 0 1 √ 2πt exp{- x 2 2t } dt > 0.
Now, let the Brownian transport (X t , T 1 ), where T 1 = f 1 (X T 1 ), be a continuous Brownian transport of Theorem 1.2. We have to show that the (continuous) function f 1 is bounded. In other words, we have to estimate its behaviour at infinity. Actually, we will prove the stronger statement Proposition 3.6. lim x→∞ f 1 (x) = 1 -t 0 . Moreover, there exists a constant β > 0 such that for all |x| large enough, one has

1-t 0 ≤ f 1 (x) ≤ 1-t 0 +e -βx 2 .
A first step in proving this proposition is the following

Lemma 3.7. ∀x ∈ R, f 1 (x) ≥ 1 -t 0 .
Proof. It is here easier to work with the non-normalized measures μ0 = cµ 0 and μ1 = cµ 1 , and with the corresponding non-normalized cost function

Φ μ0 →μ 1 = cΦ µ 0 →µ 1 = Φ N (0,t 0 )→N (0,1) .
It is clear that they satisfy the system [START_REF] Skorokhod | Issledovaniya po teorii sluchainykh protsessov (Stokhasticheskie differentsialnye uravneniya i predelnye teoremy dlya protsessov Markova)[END_REF]. In fact, one can simply divide everything by c, to pass to the normalized case, but it seems to us that the explanation would be less clear.

If we had not removed, at the initial moment from N (0, t 0 ), the particles corresponding to (1 -c)µ = N (0, 1)| K , we would have had

1-t 0 0 ρ N (0,t+t 0 ) (x) dt = Φ μ0 →μ 1 (x).
As our initial condition is only a part of N (0, t 0 ), we have ∀t > 0 ∀x ∈ R ρ t (x) < ρ N (0,t 0 ) (x), where ρ t is the density of the process started with μ0 and stopped at the moment of touching the graph of f 1 . Hence, we have

∀x ∈ R t 0 0 ρ t (x) dt < Φ μ0 →μ 1 (x),
and as

f 1 (x) 0 ρ t dt = Φ μ0 →μ 1 ,
we have proved the result. Now, let us consider the density that we obtain at the time 1 -t 0 . The next lemma estimates its behaviour at infinity: Lemma 3.8. There exists a constant β 0 > 0 such that for all |x| large enough, one has

ρ N (0,1) (x) • (1 -e -β 0 x 2 ) ≤ ρ 1-t 0 (x) ≤ ρ N (0,1) (x).
Proof. The measure ν 1-t 0 is the convolution of the initial measure μ0 with N (0, 1 -t 0 ). If, instead of μ0 , we had N (0, t 0 ), we would obtain exactly N (0, 1). But as μ0 is only a part of N (0, 1 -t 0 ), we immediately have

ρ 1-t 0 (x) ≤ ρ N (0,1) (x).
The difference ρ N (0,1) (x) -ρ 1-t 0 (x) is the part of the density that comes from the removed part N (0, 1)| K of the initial condition. This part is supported by [-1, 1]. Hence, the difference

ρ N (0,1) (x) -ρ 1-t 0 (x) = ρ N (0,1)| K * N (0,1-t 0 ) (x)
can be estimated from above as u • e

- (x-1) 2 2(1-t 0 )
, where u > 0 is a constant. This is asymptotically less that e -β 0 x 2 • ρ N (0,1) (x) for any

β 0 < 1 2 1 1-t 0 -1 .
From now on, let us fix β 0 as in Lemma 3.8. We can estimate the behaviour of the function Φ at the same moment 1 -t 0 Lemma 3.9. For all |x| large enough, we have Φ 1-t 0 (x) ≤ e -β 0 x 2 ρ N (0,1) .

Proof. From the definition of Φ, we indeed have

Φ 1-t 0 (x) = x -∞ (µ 1 ((-∞, s]) -ν1-t 0 ((-∞, s])) ds = x -∞ (x -s)(ρ µ 1 -ρ ν1-t 0 )(s) ds = x -∞ (x -s)(ρ N (0,1) -ρ ν 1-t 0 )(s) ds. Applying Lemma 3.8, we have as x → -∞ Φ 1-t 0 (x) = x -∞ (x -s) • e -β 0 s 2 • ρ N (0,1) (s) ds ≤ 1 √ 2π x -∞ |s|e -(β 0 +1/2)s 2 ds = 1 √ 2π ∞ x e -(β 0 +1/2)v 2 d(v 2 /2) ≤ 1 √ 2π e -(β 0 +1/2)x 2 = e -β 0 x 2 • ρ N (0,1) (x).
In the same way, using the integral representation of Φ µ→ν via the integral (9), one can estimate Φ 1-t 0 (x) for any large positive x.

Having obtained this estimate, we can conclude that the inequality f 1 (x) ≤ 1 -t 0 + e -β 0 x 2 /2 will be satisfied for a "very dense" at infinity set of points x. Namely, denote (x) := e -β 0 x 2 /2 . Lemma 3.10. For any |x| large enough, there exist two points y

+ ∈ [x, x + (x)] and y -∈ [x -(x), x] such that f 1 (y + ) ≤ 1 -t 0 + (x) and f 1 (y -) ≤ 1 -t 0 + (x).
Proof. Assume the contrary: for instance, that ∀y ∈

[x, x + (x)], f 1 (y) > (1 -t 0 ) + (x)
. This implies that the set K t does not intersect the rectangle

[x, x + (x)] × [1 -t 0 , 1 -t 0 + (x)],
and for any point of this rectangle, the density ρ t (y) can be estimated from below via the solution of the heat equation u = 1 2 ∆u on [x, x + (x)] with the initial conditions u 1-t 0 = ρ 1-t 0 . For all |x| large enough, ρ N (0,1) varies on [x, x + (x)] at most 2 times, and hence we have a lower bound for the initial condition ∀y ∈ [x, x + (x)]

ρ 1-t 0 (y) ≥ 1 3 ρ N (0,1) (m) ≥ 1 3 sin π (x) • (y -x) • ρ N (0,1) (m)
,

where m = x + 1 2 (x) is the middle of the interval [x, x + (x)]. The func- tion sin π (x) • (y -x
) is an eignefunction of the Laplace operator with the eigenvalue λ = π 2 (x) 2 and hence for all t ∈ [1 -t 0 , 1 -t 0 + (x)], we have a lower bound

ρ t (y) ≥ 1 3 exp{- t -(1 -t 0 ) 2 • π 2 (x) 2 } • sin π (x) • (y -x) • ρ N (0,1) (m) ≥ 1 4 sin π (x) • (y -x) • ρ N (0,1) (m).
In particular, for the middle point m of the interval, we have

ρ t (m) ≥ 1 4 ρ N (0,1) (m).
Thus, (15)

1-t 0 + (x) 1-t 0 ρ t (m) dt ≥ (x) 4 • ρ N (0,1) (m).
As (x) = e -β 0 x 2 /2 , we have due to Lemma 3.9

Φ 1-t 0 (m) ≤ e -β 0 (x+ (x)) 2 • ρ N (0,1) (m).
So we have

1-t 0 + (x) 1-t 0 ρ t (m) dt > Φ 1-t 0 (m).
The obtained contradiction proves the lemma.

We can now conclude the proof of Proposition 3.6.

Proof of Proposition 3.6. Lemma 3.10 implies that for any |x| large enough, either

f 1 (x) ≤ 1 -t 0 + (x) or the connected component I of R \ K t that contains x is a subset of [x -(x), x + (x)].
We are now going to show that then f 1 (x) ≤ (1-t 0 )+ (x)+θ 1 (x) 2 , where the constant θ 1 can be chosen not depending on x. Indeed, due to Lemma 3. The density of the new probability measure μ1 on Ĩ = [0, 1] takes value on [1/2, 2] (as ρ N (0,1) varies at most two times on I). Hence, it satisfies the assumptions of Lemma 3.4 with some uniform (not depending on x) constant α. Thus, the rescaled time in which the interval "disappears" is uniformly (for |x| large enough) bounded by some constant θ 3 and hence x ∈ I ⊂ K (1-t 0 )+ (x)+θ 3 (x) 2 . As (x) 1, the latter statement implies the desired upper bound for f 1 (x). This concludes the proof of Theorem 2.2: the function f 1 is bounded on R.

Existence of a Brownian transport 4.1 Brownian transport on the real line

In this paragraph, we will deduce Theorem 1.2 from Theorem 1.3 (which will be proved in the next paragraph). To do so, assume that the measures µ 0 , µ 1 satisfy the assumptions of Theorem 1.2. Naturally, the idea here will be to find a family of compactly supported measures µ R 0 and µ R 1 that approximate µ 0 and µ 1 and for which there exist continous Brownian transports. The simplest case is when the measures µ 0 , µ 1 , in addition to be centered, are symmetric.

(16) δ f | I (ε) ≥ επ • a 2δ 0 • b exp{- π 2 C δ 2 0 }.
Proof of Lemma 4.3. We will first prove that the functions f R "take small values somewhere". Namely, that there exist some constants 1 , C such that By continuity, (17) holds also in the case of the density ρ of the process starting with an initial measure µ R

∀R ≥ R 0 , ∃x ∈ [-1 , 1 ]: f R (x) ≤ C . Indeed,
0 | [-1,1] > µ 0 | [-1,1]
, and which trajectories are stopped outside a large enough interval [-1 , 1 ]. Hence, for any R large enough (so that µ R

0 | [-1,1] is close enough to µ 0 | [-1,1]
), there exists x ∈ [-1 , 1 ] such that f (x) ≤ C . Indeed, otherwise, we would have an inequality

C 0 ρ R t (0) dt > Φ µ R 0 →µ R 1 (0),
which would be a contradiction. Now, for the Brownian transport from µ R 0 to µ R 1 , let us consider the total measure ν t (R \ K t ) of the not yet stopped trajectories at some time t. Note that, due to the recurrence of the Brownian motion on R: ∀ε > 0, ∀ 2 , there exists a time t = t(ε, 2 ) such that for any x ∈ [-2 , 2 ], a Brownian trajectory, starting at x, crosses the rectangle [-1 , 1 ] × [C , t] left to right with probability at least 1 -ε.

Choose now 2 large enough so that ∀R ≥ R 0 , µ R 0 ([-2 , 2 ]) ≥ 1 -ε. Then, for any R ≥ R 0 , the total measure νt(R \ Kt) of the not yet stopped trajectories at time t will be at most 2ε, as crossing the rectangle implies stopping due to the choice of 1 and C . In particular, taking

ε := 1 4 min(µ 0 (--1, -), µ 0 ( , + 1)),
we see that

νt(R \ K t ) ≤ 1 2 µ 0 (--1, -) ≤ µ R 0 (--1, -) νt(R \ K t ) ≤ 1 2 µ 0 ( , + 1) ≤ µ R 0 ( , + 1).
Hence, any connected component of R \ Kt that intersects I = (-, ) is contained in (--1, + 1). Applying now Lemma 3.4 for all the connected components of R \ Kt that intersect I, we conclude that all of them disappear in at most time θ

• α +1 • |[--1, + 1]|. Hence ∀R ≥ R 0 , f R | [-, ] ≤ t + θ • α +1 • (2 +
2) and we have the desired upper bound.

We are now ready to prove the uniform continuity for the family f R , that is Proposition 4.4. A basic idea here is the following one: assume that the function f is smooth and (piecewise) monotonic. Then, considering a point x in a neighborhood of which f is monotonically increasing, we see that between the moments t = f (x) and t + ∆t = f (x + ∆x), the left end of the interval of complement to K t absorbs approximatively the mass ∆t • ρ t (x) of Brownian particles and this should be equal to the mass µ 1 of the interval

[x, x + ∆x]. Hence, ∆t ≈ µ 1 ([x, x + ∆x]) ρ t (x) ≈ ρ µ 1 (x) ρ t (x) • ∆x.
Estimating from above the numerator by b, and from below the denominator (by a comparison with the heat equation on an interval), we obtain the desired bound for f = ∆t ∆x . Let us now make these computations rigorous. Proof of Proposition 4.4. Note first that Lemma 3.4 guarantees that the functions f | I cannot have "high thin peaks": if y, z ∈ U 1 (I ) ∩ I and f (y) = f (z), then max

x∈[y,z] f (x) ≤ f (y) + θα • |[y, z]|.
Now, take δ = δ 0 = min ε θ 0 α , 1 2 and let us show the estimate (16). Namely, assume first that x, y ∈ I with the distance between x and y less than the right hand-side of (16). We want to show that |f (x) -f (y)| ≤ ε. Without any loss of generality, we can assume that f (x) < f (y). We can also assume that ∀x ∈ [x, y], f (x ) > f (x) (as otherwise, we can replace x with the rightmost point x of the level set f -1 (f (x)) ∩ [x, y]).

Consider now the behaviour of f on [x, x + δ 0 ]. Denote t 1 = f (x) and t 2 = min [y,x+δ 0 ] f . Due to Lemma 3.4 and the choice of δ 0 , we have

f (y) ≤ max(t 1 , t 2 ) + θα δ 0 ≤ max(t 1 , t 2 ) + ε 2 .
Thus, if t 2 ≤ t 1 + ε 2 , everything is proven. (In particular, this rules out the case of x + δ 0 falling outside I: the lower limit of f at an endpoint of I is zero.) Thus, we can assume that t 2 > t 1 + ε 2 . Consider now the Brownian paths of the process X t that were not stopped. Note that any such path, starting anywhere in [x, x + δ 0 ], stays in this interval till the moment t 1 and then leaves it through the left end before the moment t 2 , as shown in Figure 3 below. The first intersection point of such a path with the graph of f is somewhere above [x, y]. Hence, the measure µ 1 ([x, y]) is greater or equal to the measure of such paths. . Hence, the density of the trajectories that have never left [x, x + δ] up to time t is greater than e -λt • a sin π(z-x) δ 0 , and thus the density of those who are first-leaving the interval through its left end is at least a π δ 0 e -λt . The total mass of the trajectories leaving between the moments t 1 and t 2 is

x x y y x + δ 0 x + δ 0 t 1 t 1 t 2 t 2 x t
t 2 t 1 a π δ 0 e -λt dt ≥ a π δ 0 (t 2 -t 1 )e -λt 2 .
As we have t 2 -t 1 ≥ ε 2 and t 2 ≤ C , we finally have obtained a lower bound for the total mass of such trajectories and thus for µ 1 ([x, y]). This lower bound is given by a

π • ε δ 0 • 2 e -C π 2 /δ 2 0 .
Though, due to our assumption, µ 1 ([x, y]) ≤ b (y -x), and due to our choice of δ(ε), this gives us a contradiction.

Having proved both Lemma 4.3 and Proposition 4.4, we have thus proved Proposition 4.2. We are now ready start concluding the proof of Theorem 1.2. Namely, as the family (f R ) is precompact, there exists a convergent subsequence f R k ---→ k→∞ f . A natural conclusion would then be that the first intersection measure with the graph of f for the initial measure µ

0 = lim µ R k 0 is exactly µ 1 = lim µ R k 1 .
To make this argument work rigorously, we will need the following Definition 4. Let f ∈ C(R, R + ) be a continuous positive function and x ∈ R. The first intersection measure m x,f is defined as the law of the x-coordinate of the first intersection between the graph of f and the trajectory of the Brownian motion started from the point x: X t = x + B t , T = inf{t ≥ 0 : t = f (X t )} and m x,f = Law(X T ). Similarly, we denote by m µ,f the first intersection measure between the process started from the distribution µ and the graph of the stopping function f . Proposition 4.5. The first intersection measure m x,f depends continuously (in the sense of the weak* convergence) on x ∈ R and f ∈ C(R, R + ) (where C(R, R + ) is equipped with the topology of uniform convergence on compact sets).

The following lemma is an easy exercise Lemma 4.6. Denote by (X t , t ≥ 0) the standard Brownian motion. For all ε > 0, there exists δ > 0 such that, with probability at least 1 -ε, there exist t + , t -∈ [δ, ε] such that X t + = δ, X t -= -δ and sup 0≤t≤max(t + ,t -) |X t | ≤ ε. In other words, the Brownian motion crosses horizontally the rectangle [-δ, δ] × [δ, ε], and before this crossing, it stays inside the strip [-ε, ε] × R + (see Figure 4 below). Proof of Proposition 4.5. Let f 1 ∈ C(R, R + ) and x 1 ∈ R be given. Take an arbitrary ε > 0 and let δ > 0 be defined by Lemma 4.6. It is easy to see that, for some R > 0, for any initial point x ∈ U 1 (x 1 ) and for any f such that |f (x 1 ) -f 1 (x 1 )| ≤ 1, the Brownian motion started at x intersects f before leaving the strip [-R, R] × R + with probability at least 1 -ε.

Consider now x 2 ∈ U δ (x 1 ) and f 2 -f 1 C([-R-δ,R+δ]) ≤ δ. We will estimate the difference between m x 1 ,f 1 and m x 2 ,f 2 . To do this, take the trajectory of the same Brownian motion B t shifted to the initial points x 1 and x 2 : X 1 t = x 1 +B t and X 2 t = x 2 + B t . Consider the moment of the first intersection of these processes with the corresponding graphs. Let T j := inf{t ≥ 0 : t = f j (X j t )} for j = 1, 2 and T := min(T 1 , T 2 ). Note that T 1 and T 2 are two Markov hitting times and hence, the conditional behaviour of X j t under any condition T = T 0 and X j T 0 = xj is simply the Brownian motion shifted to the initial point (T 0 , xj ). See Figure 5 below. Now, let us prove that we have |X 1 T 1 -X 2 T 2 | ≤ ε with probability at least (1 -ε) 2 . To show this, we first note that, due to the choice of R, we

f 1 f 1 + δ x t T 1 T 1 δ ε X 1 t X 2 t x1 x1 x 1 x 1 x 2 x 2
Figure 5: First intersection of X 1 , X 2 with the graphs of f 1 and f 1 + δ respectively have X j T ∈ U R+δ (x 1 ) with probability at least 1 -ε. Now, under any "first intersection condition" T 2 ≥ T 1 = t, X 1 t = x1 ∈ U R (x 1 ), the trajectory of X 2 t intersects the graph of f 2 inside U ε+δ (x 1 ) × [ t, t + ε] with probability at least 1 -ε. Indeed, under this condition, the trajectory of X 2 t is the trajectory of the Brownian motion started from the point ( t, X 2 t ). Meanwhile, we have |X 2 t -X 1 t | = |x 2 -x 1 | ≤ δ. Also, we have f 2 (x 1 ) ≤ f 1 (x 1 ) + δ. Recalling the definition of δ, we obtain the desired estimate on the conditional probability.

In the same way, under any condition T 1 ≥ T 2 = t and X 2 t = x2 ∈ U R (x 1 ), we have |X 1 T 1 -X 2 T 2 | ≤ ε + δ with probability at least 1 -ε. Considering the first intersection moment, we see that, with probability at least (1 -ε), the corresponding point belongs to U R (x 1 ), and conditionally to it we have |X 1

T 1 -X 2 T 2 | ≤ ε + δ with probability at least 1 -ε. Hence, we have finally (18)

P(|X 1 T 1 -X 2 T 2 | ≤ ε + δ) ≥ (1 -ε) 2 .
As m x 1 ,f 1 = Law(X 1 T 1 ) and m x 2 ,f 2 = Law(X 2 T 2 ), (18) gives us the desired comparison between these two measures.

As it can be easily seen from the latter proof, the continuity in Proposition 4.5 is uniform for x belonging to any compact set in R.

For further arguments, it will be useful to consider the following distance between probability measures

Figure 1

 1 Figure 1 below shows a simulation of the functions f 1 and ϕ (that one can do thanks to an almost explicite nature of our construction).

Figure 1 :

 1 Figure 1: On the left: the graph of the function f 1 . On the right: the graph of the resulting function ϕ

i) µ 0

 0 , µ 1 satisfy the hypotheses of Theorem 1.3 on U 1 (I ) ∩ I. ii) f | U 1 (I )∩I ≤ C . iii) µ 0 | I and µ 1 | I satisfy the hypotheses of Theorem 1.3 for some constants a , b , α . Let δ 0 := min{ ε 3θ 0 α , 1 2 }. Then the inverse of the modulus of continuity of f | I , denoted by δ f | I (ε), is lower bounded by:

0 ρ

 0 as we have already mentioned, the functions Φ R := Φ µ R 0 →µ R 1 converge to the function Φ := Φ µ 0 →µ 1 . In particular, the values Φ R (0) are uniformly bounded by some constant C 1 . Now, let us consider a Brownian motion started from µ 0 | [-1,1] . Its density ρ BM at 0 has an asymptotics of 1 √ t and thus, its integral diverges. Hence, there exists C such that (17) C BM (t) dt > C 1 .

Figure 3 :

 3 Figure 3: Two Brownian paths crossing the graph of f

Figure 4 :

 4 Figure 4: A Brownian path crossing the strip

  3, we can consider the continuous Brownian transport problem from ν 1-t 0 + (x) | I to μ1 | I independently of the rest of the real line. Let us then rescale I to [0, 1], normalizing the measures ν 1-t 0 + (x) | I and μ1 | I to probability ones, and rescaling the time by the factor

1 |I| 2 .

Acknowledgement: V.K. thanks S. Pirogov, A. Sobolevski, B. Gurevich, A. Rybko and S. Shlosman for interesting discussions. A.K. thanks Bernard Roynette for telling her the Cantelli conjecture.

We will then consider the sequence of conditional normalized measures μR 0 :=

, and μR

.

For the case of general centered measures µ 0 and µ 1 , we will have to modify this construction, as their restrictions on [-R, R] are no longer forced to have the same mean. Namely, denote for any measure µ such that µ((-∞, 0)) > 0 and µ((0, ∞)) > 0 by γ(µ) the measure

where (c(µ), d(µ)) is the unique solution to the system

It is then easy to see that γ(µ) is always a centered measure and we have c(μ R j ) ---→ ). Now we would like to consider continuous Brownian transports from µ R 0 to µ R 1 , then extract a convergent subsequence from the sequence of corresponding functions f R , and finally show that the limit function f indeed defines a continuous Brownian transport from µ 0 to µ 1 . So, a first step in the realization of this scheme is to check that for all R large enough, Theorem 1.3 is indeed applicable for finding a continuous Brownian transport from µ R 0 to µ R 1 . Lemma 4.1. For any R large enough, there exists a continuous Brownian transport from µ R 0 to µ R 1 . Proof. We have to check that the assumptions of Theorem 1.3 are satisfied for all R large enough. As the conditions i)-iii) are the same in Theorems 1.2 and 1.3, we only have to check the two last ones.

Recall that we have λ := lim sup x→∞ ρµ 0 (x) ρµ 1 (x) < 1. Hence, for some constant M , we have

• 1 x≥0 .

Note that the second factor in the right hand side tends (uniformly) to 1 as R → ∞. Thus, for any R large enough, it is less than 2 1+λ and hence ∃M : ∀|x| > M,

This proves the desired condition v). Moreover, note that due to the finiteness of the first moment of µ 0 and

Next, for all R > M and x ∈ (-R, -M ], we have

Thus, for all R large enough and all x ∈ (-R, R), we have Φ µ R 0 →µ R 1 (x) > 0. This proves iv) and thus concludes the proof.

We will choose and fix a value R 0 ≥ 1 such that for any R > R 0 , there exists a continuous Brownian transport from µ R 0 to µ R 1 , and we will consider the corresponding family of stopping functions f R .

A next step is to assure the possibility of extracting a convergent subsequence from the family of functions f R .

Proposition 4.2. The family (f R ) is precompact in the topology of uniform convergence on the compact sets. This proposition, due to the Arzelà-Ascoli theorem, is equivalent to the union of the following two results.

Proposition 4.4. Let µ 0 , µ 1 be two probability measures, supported on a finite or infinite interval I ⊂ R, for which there exists a continuous Brownian transport from µ 0 to µ 1 with some stopping function f . Assume that, for an interval I ⊂ I and a constant C > 0, the following holds: Definition 5. Let µ, µ be two probability measures. We define the distance between them as d(µ, µ

It is easy to see that this distance defines on the space of probability measures precisely the weak* convergence. In fact, in the proof of Proposition 4.5, we obtain the estimate → µ 0 be a weak* convergent sequence of measures, and

If additionally, the corresponding expectations of the first intersection times T (k) are uniformly bounded by some constant C, then the expectation of the first intersection time T is also finite and does not exceed C.

Proof. Indeed, for any ε > 0, there exist

(The second conclusion comes from the uniform version of Proposition 4.5).

For any k large enough, we have d(µ 0 , µ (k) 0 ) < δ. Hence, for any such k, we can choose the processes X 1 , X 2 such that Law(X

Due to the property ii), the conditional probability of

t )} are first intersection stopping times. Hence, with probability at least 1 -δ -2ε, we have

As ε is arbitrarily chosen, we have m µ (k)

Now, let us prove the second statement of the lemma. Actually, for any k large enough, and any realization as before, we have |T -T (k) | ≤ ε with probability at least 1-δ -2ε ≥ 1-3ε. Thus, we have obtained a lower bound for the integral of T over a set of probability 1-3ε, which is ET (k) +ε ≤ C +ε. As ε > 0 is arbitrary, this implies that ET ≤ C.

We can now conclude the proof of Theorem 1.2.

Proof of Theorem 1.2. We have now constructed continuous Brownian transports from µ R k 0 to µ R k 1 with stopping functions f R k converging uniformly on compact sets to some continuous function f . Then, due to the first part of Lemma 4.7, we have

The expectations of the corresponding passage times T (k) are also equal to

and thus, due to the choice of µ R k 0 , µ R k 1 , the latter difference converges to Var µ 1 -Var µ 0 < ∞. Hence, these expectations are uniformly bounded and due to the second part of Lemma 4.7, we have ET < ∞. We have finally constructed a continuous Brownian transport from µ 0 to µ 1 .

Brownian transport on an interval: discretization 4.2.1 Discretization

We are now going prove Theorem 1.3. As we have already mentioned, we will do it by means of a discretization procedure, replacing the Brownian motion by a discrete random walk, and then passing to the limit as the mesh of the lattice goes to zero.

We will first study a discretized version of our problem. Namely, instead of a Brownian motion on R, we consider a random walk on Z:

We have to modify the setting of a continuous Brownian transport in the following way. The stopping time T is now a probabilistic Markov moment, that is related to the new function g in the following way:

(20) if t > g(Y t ), then the process is stopped, if t = g(Y t ), then the process is stopped with probability q(Y t ),

where q : Z → [0, 1] is a new auxiliary function. A Brownian transport in this setting will be called a discrete Brownian transport.

The new discrete functions corresponding to Φ are defined as

and

It is then easy to check that for a centered measure µ on Z and for an integer x, one has Φ µ (x) = Φ Z µ (x). So, we will in further mostly omit the upper index "Z". The discrete function Φ works in the same way as its continuous analogue: an easy computation shows that Φ ...00100...→...0

Hence, we have for any displacement defined by (20)

This allows us, for two centered measures µ 0 , µ 1 , to define recursively the transport process in the following way: i) Initial state:

, where ν t is the occupation measure at time t, there is nothing to be done. Otherwise, take g(x) := t with q(x) = 2

Due to (21), we then have

In particular, we can easily see by induction that all the functions Φ t := Φ νt→µ 1 are non-negative, and the procedure is thus well-defined for all t. Also the latter construction implies the following: i) if at some time t, at cell x, we have Φ νt→µ 1 (x) = 0, then the cell (t, x) is frozen and any particle coming to it at this moment (or afterwards) is stopped,

, then the cell (t, x) is "partially frozen", meaning that a part of the particles of total measure 2Φ νt→µ 1 (x) is diffused, whereas the others are frozen. In this case, Φ ν t+1 →µ 1 (x) = 0, so that, starting from the moment t + 1, the cell x becomes fully frozen.

We have the following Proposition 4.8. Let µ 0 , µ 1 be two centered measures on Z, both with finite support. Suppose that µ 1 is everywhere positive on the interval I := [min Supp(µ 0 ), max Supp(µ 0 )] and Φ µ 0 →µ 1 ≥ 0. Then, the procedure (20) provides us with everywhere defined functions g, q that define a discrete bounded Brownian transport from µ 0 to µ 1 .

To prove this result, we will first need the following lemma, which is a discrete analogue of Lemma 3.3. Lemma 4.9. Let µ, ν be two centered (discrete) measures of finite support. Suppose that Φ ν→µ ≥ 0 and Φ ν→µ (x) = Φ ν→µ (y) = 0 for some x < y. Then, we have µ(

Taking the difference between such representations for µ(z) and ν(z), and summing up on z ∈ [x + 1, y -1], we have

Hence, we get

On the other hand, summing on z ∈ [x, y], we have

Thus, we conclude that

Proof of Proposition 4.8. Consider the value m t := ν t ({x : Φ νt→µ 1 (x) > 0}). On one hand, the sequence (m t ) converges to 0. Indeed, ν t is a part of the occupation measure of a random walk on Z with the initial distribution µ 0 , that is in particular conditioned to never exit the interval I := Supp(µ 1 ). The probability of staying inside I during t steps converges to 0, and thus, so does m t . On the other hand, Lemma 4.9 implies that

and thus m t ≥ {x : Φ νt→µ 1 (x) > 0} • min z∈I µ 1 (z).

As b := min z∈I µ 1 (z) > 0 due to the hypothesis of the proposition, once m t < b, we have Φ t ≡ 0 and hence ν t = µ 1 .

Proof of Theorem 1.3

We are now ready to prove Theorem 1.3. Let two centered measures µ 0 and µ 1 , supported on some interval I ⊂ R, be given and assume that, for these measures, the hypotheses i)-v) of the theorem are satisfied. Up to a rescaling of space and time, we can assume that I = [-1, 1]. For any natural n, one can consider the discretized measures µ

Note that the measures µ Consider now the corresponding random walks (with the elementary time step 1 n 2 ) and the corresponding functions

which, as earlier for Z, are the restrictions on 1 n Z of the continuous functions Φ µ (n) i (x). A first step in applying the discretization technique is a check that there exists a discrete Brownian transport from µ is positive everywhere on I once n is large enough.

Consider now the corresponding discrete transport functions g (n) (x) that we extend to [-1, 1] piecewise linearly. Note that, for these functions, we still have the (uniform in n) estimates, analogous to Lemma 3.4 and Proposition 4.5 (proven by the same methods). Hence, the family of functions g (n) is precompact and we can extract a convergent subsequence g (n k ) → f . On the other hand, discrete random walks tend, as n → ∞, to the Brownian motion. Hence, the same arguments as in Proposition 4.5 and Lemma 4.7 imply that the first intersection measure for the initial distribution µ 0 = lim k→∞ µ (n k ) 0 with the stopping function f = lim k→∞ g (n k ) will be lim k→∞ µ (n k ) 1 = µ 1 . This concludes the proof of Theorem 1.3.


Mani Ezzat
email: mani.ezzat@gmail.com

Thierry Poibeau
email: thierry.poibeau@ens.fr

A New Scheme for Annotating Semantic Relations between Named Entities in Corpora

Although several studies have developed models and type hierarchies for named entity annotation, no such resource is available for semantic relation annotation, despite its utility for various applications (e.g. question answering, information extraction). In this paper, we show that there are two issues in semantic relation description, one concerning knowledge engineering (what to annotate?) and the other concerning language engineering (how to deal with modality and modifiers?). We propose a new annotation scheme, making it possible to have both a precise and tractable annotation. A practical experiment shows that annotators using our scheme were able to quickly annotate a large number of sentences with very high inter-annotator agreement.

Introduction

A large number of natural language applications (e.g. information extraction, question answering, automatic summarization) require a precise analysis of the linguistic content of the text. Since the Message Understanding Conferences in the 1990s, there is a general agreement on the different steps required to perform this analysis: i) relevant elements (mostly named entities) are first recognized and tagged, then ii) relations between these elements are extracted. This generic schema does not preclude the existence of other steps in the analysis (e.g. anaphora resolution, discourse structure recognition), but the recognition of basic elements and relations between them is nevertheless a shared basis among a large number of systems [START_REF] Jurafsky | Speech and Language Processing: An Introduction to Natural Language Processing[END_REF].

This of course explains why there has been an increasing amount of research both on named entity recognition and on relation analysis in the last 20 years (MUC6, 1995;[START_REF] Appelt | Named Entity Extraction from Speech: Approach and Results Using the TextPro System[END_REF]. However, the maturity of these two tasks differs to a large extent. As for named entity recognition, a large number of tools, data and gold standard are available for very different languages. The success rate is often above .9 or even .95 F-measure for major categories (person's names, location's names) in newspapers [START_REF] Collins | Unsupervised models for named entity classification[END_REF]. Entity types are to a certain extent normalized and formalized in large hierarchies (see for example the hierarchy proposed by Sekine which is now a de facto standard [START_REF] Sekine | Extended Named Entity Hierarchy[END_REF]).

In comparison, it is interesting to observe that only a few annotated corpora and no real gold standard exist for semantic relations 1 . A first explanation is that relation analysis largely depends on the task and on the kind of corpora being analyzed. However, we do not think that this is enough to explain the current situation: for example question-answering systems are supposed to address any kinds of questions and thus require a generic approach for relation analysis.

It is of course difficult to normalize the set of all possible relations. The clusters of verbs described in Wordnet (synsets, clusters of near-synonym verbs) (Fellbaum, 1998) or Framenet (clusters of verbs sharing the same argument structure) [START_REF] Fillmore | Background to Framenet[END_REF] are a good basis and our goal is not to propose a new classification of verbs and/or events. Nevertheless, annotation schemes proposed so far do not go beyond simple events themselves. From this perspective, they are inadequate in that they do not provide enough room between a yes or no option (the relation can be identified or not), whereas texts constantly report relations along with modalities, negations, etc. This is the reason why, in this paper, we propose a tractable annotation scheme allowing one to annotate relations more accurately, with a level of generality that makes our scheme both tractable and extensible. We do not focus on event them-1 One of our reviewers suggested previous studies (like [START_REF] Carlson | Building a discourse-tagged corpus in the framework of rhetorical structure theory[END_REF][START_REF] Poesio | Anaphoric Annotation in the ARRAU Corpus[END_REF], among several others). However, none of these propose a general scheme for semantic relation annotation. They generally deal with a specific theory (e.g. Rhetorical Structure Theory [START_REF] Carlson | Building a discourse-tagged corpus in the framework of rhetorical structure theory[END_REF]) or a specific phenomenon (e.g. anaphora resolution [START_REF] Poesio | Anaphoric Annotation in the ARRAU Corpus[END_REF]). Recent frameworks like ACE take profits of all these studies but a large number of problems remains unsolved, see (ACE, 2008a).

selves, but we propose to annotate contextual information for a more thorough analysis of relations expressed in texts. Contextual information includes negations, modalities and reported speech, which are surprisingly poorly represented in most schemes.

We first show why semantic relation annotation is difficult. We then present previous schemes that have been proposed in different frameworks, esp. the Message Understanding Conferences (MUC) [START_REF] Grishman | Message understanding conference 6 -A brief history[END_REF] and the Automatic Content Extraction (ACE) conferences, as well as their limitations. We then propose our own scheme and present two experiments showing that annotators using our scheme were able to quickly annotate a large number of sentences with a very high accuracy.

2 Why is Relation Annotation a Difficult Task?

We consider different issues related to semantic relation analysis for event detection. Note that we do not focus on the analysis of lexical relations themselves (e.g. synonymy, meronymy, hyponymy, etc.) since there has been a huge body of research on this topic so far [START_REF] Cruse | Lexical semantics[END_REF]. We consider that lexical semantics is outside the scope of this study, even if this kind of knowledge plays a prominent role in relation analysis (and therefore, in various tasks like information extraction or question answering). In our view, there are two main issues in relation annotation. The first one is a knowledge engineering problem, the second one a linguistic representation problem.

A Knowledge Engineering Problem

In most annotation schemes, one has to take a binary decision, i.e. whether to annotate or not the relation. There are of course some clear cases. For example, if one is interested in companies acquiring other companies, the following sentences should obviously be considered as positive examples:

• Google has bought Irish company Green Parrot

Pictures in an attempt to improve the quality of video uploaded to YouTube.

• Google Buys Mobile Ad Company for $750M

• Google buys YouTube for $1.65 billion However, most cases are not that clear. Since relations refer to semantic concepts and since those concepts can be difficult to grasp, some examples cannot be tagged accurately without a proper representation of the domain. Some examples are impossible to classify, since the text does not provide enough information to decide if the event (the purchase) has been completed or not:

• Under the Note Purchase Agreement: (a) Dolphin Fund II acquired convertible notes of the Issuer in the aggregate principal amount of $988,900, which convertible notes were convertible, as of January 15, 2003 into 3,826,270 shares of Common Stock In this example, the text is complex, refers to domain specific concepts and does not even give the key to the annotator: it is not explicitly said if the result of the transaction means a transfer of the control of the company or not. All these refer to knowledge engineering problems: most of the time, a good command of domain knowledge is necessary to be able to annotate accurately the different examples in the text. As seen above, this knowledge is not enough when some information is missing or when the text is underspecified.

A linguistic engineering problem

The linguistic side of the problem is of course not completely disconnected from the knowledge engineering point of view. Let's consider the following examples:

• Rumors Swirling Around A Google Acquisition of Groupon...

• Is Google Buying Groupon For Several Billion Dollars?

One can see that the first sentence does not refer to a pure fact since the main information is introduced by the phrase "Rumors Swirling Around".

In the second example, it is the fact that information appears with a question mark that makes it uncertain. More generally, relation annotation is inseparable from the analysis of hedge expressions. According to J. Watts [START_REF] Watts | Politeness[END_REF], hedge expressions are "linguistic expressions which weaken the illocutionary force of a statement: by means of attitudinal predicates (I think, I don't think, I mean) or by means of adverbs such as actually, etc.". Modal auxiliaries (may, would...) should also be include in this list.

• Google May Acquire Groupon for $6 Billion

• If Google would acquire Salesforce.com, it wouldn't be about CRM only.

In the previous examples, modal auxiliaries make it clear that these sentences are not about facts but possibilities.

For some kinds of events, one can easily find speculations (e.g. rumors in the financial domain). Speculations can also use the negative form:

• Google will NOT acquire Twitter in 2011.

• Why Google Will Not Acquire Twitter

All these examples show that texts are not just about facts but include a lot of other phenomena (modals, negation, etc.) that make annotation a difficult task. This is of course not new, and a lot of studies have tried to address some of these complex linguistic questions (e.g. analyzing the scope of modalities or negations). However, these questions are not directly addressed by most existing annotation schemes, especially the most popular ones.

Existing Schemes for Semantic Relation Annotation

Semantic relation analysis is a traditional task for the language understanding community. Despite the lack of generic resources (as seen in the introduction), a large number of works involve relation annotation. As a consequence, relation annotation has been identified as a separable and re-usable task from the Message Understanding Conferences on.

Early Work in Relation Annotation

Text understanding has been explored since the beginning of natural language processing, and involves since the beginning the recognition of semantic relations between textual entities.

During the 1970s, a number of applications tried to establish a link between texts and databases. This kind of analysis typically requires to be able to connect together different pieces of information. Ad hoc relations were defined and recognized in texts in order to fill databases and subsequently be able to access these databases with natural language queries (see for example the LUNAR system developed by Woods to access databases on materials collected on the moon [START_REF] Woods | Progress in natural language understanding: an application to lunar geology[END_REF]).

Semantic networks (e.g. conceptual graphs [START_REF] Sowa | Implementing a semantic interpreter using conceptual graphs[END_REF])) provided a framework to standardize the representation of this kind of information, but did not normalize the annotation itself.

The Message Understanding Conferences (MUC)

The Message Understanding Conferences refer to a series of evaluation campaigns organized by DARPA from 1987[START_REF] Freitag | Multistrategy learning for information extraction[END_REF](MUC6, 1995;MUC7, 1998). The goal was for DARPA and other funding institutions to be able to track the progress of different strategies for information extraction (i.e. the extraction of structured knowledge from unstructured texts). We will not detail here the evolution of MUC during these 12 years, since good overviews are available elsewhere [START_REF] Grishman | Message understanding conference 6 -A brief history[END_REF].

What is interesting from our perspective is the fact that for MUC-6, in 1995, named entity recognition was recognized as an independent task. Three other tasks ("co-reference annotation", "template element" and "scenario template") were proposed for evaluation, and these were mainly based on the identification of relevant relations between named entities, and between named entities and their attributes.

Here, the evaluation was clearly task-oriented: a limited number of texts from the targeted domain were carefully selected for evaluation. Modifiers, negations and other hedge expressions were only marginally represented and not really integrated in the annotation framework. Most systems did not take these elements into account, with no major penalty. Of course, this kind of strategy can lead to major errors, which can be a serious problem when the system is used in the real world.

Automatic Content Extraction (ACE)

Automatic Content Extraction refers to a series of evaluation campaigns held between 2000 and 2008 and organized by the Linguistic Data Consortium (LDC). Contrary to what was done in the framework of MUC, the evaluation is not task-oriented but technology-oriented, in that it is supposed to provide general guidelines that are not limited to a given domain [START_REF] Doddington | Automatic Content Extraction (ACE) Program[END_REF][START_REF] Ace | Automatic Content Extraction 2008 Evaluation Plan (ACE08) -Assessment of Detection and Recognition of Entities and Relations Within and Across Documents[END_REF].

ACE considers for example issues related to modality [START_REF] Ace | Automatic Content Extraction 2008 Evaluation Plan (ACE08) -Assessment of Detection and Recognition of Entities and Relations Within and Across Documents[END_REF]. A fact can be tagged as ASSERTED or as OTHER (all other cases). As we have seen in the previous section, there are far more than two cases to consider in order to be able to accurately tag texts. Moreover, the guidelines provide rather unclear rules like "If we think of the situations described by sentences as pertaining to possible descriptions of the world (or as 'possible worlds') then we can think of ASSERTED Relations as pertaining to situations in 'the real world', and we can think of OTHER Relations as pertaining to situations in 'some other world defined by counterfactual constraints elsewhere in the context'" (ACE, 2008a).

The authors give the following example: "We are afraid Al-Qaeda terrorists will be in Baghdad ". Since "The presence of Al-Qaeda terrorists in Baghdad is a situation being described as holding in the counterfactual world defined by 'our' fears", the example should be consider as being ASSERTED. They also give an example that should not be considered as being ASSERTED: "If the inspectors can get plane tickets today, then they will be in Baghdad on Tuesday". This sentence is not ASSERTED because "the inspectors (they) are in Baghdad only in the worlds where they get plane tickets today" (ACE, 2008a). So a fact is asserted when it is "interpreted relative to the 'Real' world" and not asserted (OTHER) when the fact "is taken to hold in a particular counterfactual world". Finally, "negatively defined relations (e.g. "John is not in the house") [should] not be annotated" following the ACE proposal.

In our view, there are several problems with this scheme:

1. there are more than two values to be considered. The distinction between ASSERTED and OTHER is not enough to get a fine grained description of relations in texts (for example, this annotation does not say if the event is completed or ongoing, if it is sure, probable or just possible) . Moreover, it seems important to annotate the source of the assertion when possible;

2. there is no reason to exclude negative events. Moreover, from an applicative point of view, this knowledge is often of paramount importance for the domain (e.g. knowing/speculating that Google will not buy Twitter in 2011 may have a major impact on investment people); 3. the notion of real world vs counterfactual world is not really operational for the task. It does not provide enough evidence for the annotator to make her decision.

Most recent frameworks do not seem to answer these issues, even for the "event detection" task; they often contain domain specific annotation [START_REF] Aitken | Learning information extraction rules : An inductive logic programming approach[END_REF][START_REF] Daniel | Extracting gene pathway relations using a hybrid grammar: the arizona relation parser[END_REF][START_REF] Jayram | Avatar information extraction system[END_REF][START_REF] Shen | Declarative information extraction using datalog with embedded extraction predicates[END_REF][START_REF] Kim | Corpus annotation for mining biomedical events from literature[END_REF] or focus on a certain type of information [START_REF] Morante | Learning the scope of hedge cues in biomedical texts[END_REF]. So we need to build on the ACE scheme in order to overcome some of its shortcomings.

A New Relation Annotation Scheme

Semantic relations correspond to a core event with most of time additional information related to the event. These additional pieces of information are most of the time encoded through negations, modalities and higher level clauses (for reported speech for example). Our contribution addresses these elements.

Basic Event Encoding

We consider that a semantic relation is part of the linguistic expression of an event. This relation is most of the time expressed by a predicate, either a verb (Google buys YouTube) or a noun (the purchase of Youtube by Google...). The predicate governs some arguments (Google, Youtube)

that can be tagged more or less precisely (arg1, arg2; agent, patient; buyer, target; etc.). Linguistic descriptions of verb hierarchies provide an accurate basis for this kind of analysis (see Wordnet (Fellbaum, 1998) or Framenet [START_REF] Fillmore | Background to Framenet[END_REF], as detailed above). These hierarchies must be adapted with respect to the domain but they are anyway as far as it can be re-usable.

Existing frameworks like MUC or ACE provided precise guidelines for this kind of information. We build on these guidelines for our experiments.

Enunciative Modalities

The description of basic events must be completed in order to take into account the different issues we have described above (knowledge engineering as well as linguistic engineering issues). We consider three basic attributes directly associated with relations in order to express the degree of completeness of the event: COMPLETED, ONGOING, POSSI-BLE.

• if the process is done and over, it is COM-PLETED;

• if the process has begun is not yet accomplished, it is ONGOING;

• if the process has not begun, it is POSSIBLE.

Moreover, the event can be NEGATED (e.g. see Google will NOT acquire Twitter in 2011 ).

The event can also be reported directly or by different sources, which means we have to annotate the relation as being DIRECT (Google Buys Mobile Ad Company for $750M ) or INDIRECT and, for the latter, we also have to annotate the SOURCE when possible (see for example "Rumors Swirling Around A Google Acquisition of Groupon" where the PROCESS is reported, therefore INDIRECT and the "rumors" are the source). Table 1 gives some examples along with their annotation.

More detailed annotation schemes are possible, especially to deal with different kinds of modalities (epistemic, deontic, etc.). We do not think it is appropriate to have a so fine grained description as these categories will be inappropriate for most language understanding applications. Note that this more fine grained categorization is not incompatible with our scheme. It just requires that some of the categories are refined.

Experiments

We present here a method to quickly extract potential relevant sentences from corpora using collocations. These sentences are then manually annotated in order to check the operability of our scheme. 1: English examples with annotations.

Sentence Annotation

Extracting Potentially Relevant Sentences from Corpora

The extraction of relevant sentences from corpora is a long and labour intensive task. Most of the time, one must read a large number of texts in order to find only a few relevant sentences. This is both inefficient and time-consuming. In order to reduce the time spent on this step, we have developed a series of tools allowing one to retrieve relevant documents and then identify potentially relevant sentences. Our approach is simple and easy to reproduce: the idea is to use collocations as a basis for filtering sentences from corpora. The approach can be compared to previous experiments described for example by Riloff with the Au-toSlog system [START_REF] Riloff | Automatically Constructing a Dictionary for Information Extraction Tasks[END_REF]. Information extraction patterns involve arguments that can be used to find relevant predicates and, in turn, relevant predicates can be used to find relevant arguments. The same strategy can be used to identify relevant sentences.

We reproduced this idea by first fixing named entity types. Sentences containing these types are then retrieved if named entities appear within a certain distance (in most experiments we used a sliding window with a distance inferior to 10 between the two named entities) [START_REF] Freitag | Multistrategy learning for information extraction[END_REF]. This technique makes it possible to retrieve a certain number of sentences (the method can be parametrized to adjust the number of retrieved sentences). User studies (made with a representative sample of potential end-users who are not trained linguists) have proven that experts can describe the kind of relations they are looking for and the kind of entities these relations involve. They are practically able to use the tools we have developed and are able to perform their analysis a lot quicker with this approach.

For example, in the case of companies buying other companies, only sentences that contain at least two company names are extracted. This of course eliminates relevant sentences containing less than two company names (esp. sentences containing anaphora) but, after manual inspection, we as-sume we get a representative set of sentences anyway, since anaphora do not fundamentally change the deep semantic structure. So, even if anaphora are not taken into consideration here, they can be analyzed and integrated in subsequent steps without any problem.

For the company buyout task, the system provided more than 1000 potentially relevant sentences in a few minutes (extracted from a 2.9 million word corpus). It then took less than one hour for an expert to manually check these sentences and discard non relevant ones. More than 50% of the extracted sentences were relevant but this represents less than 5% of the corpus (and always less than 10% of the corpus, even with other domains and relations). This proves that the approach is both efficient and accurate.

Corpus annotation

Our experiment is based on the previous set of sentences extracted from different sources, mainly from financial newswires and newspapers (see table 2 for some examples). A reduced experiment has been done on English texts (see examples in table 1 and in section 2) but a larger experiment has been done on French, using texts from the same domain. This ensures that our annotation scheme is largely language independent. This corpus is automatically analyzed using a state-of-the art named entity tagger2 . Sentences containing two company names are extracted. As a result, one hundred sentences are extracted and these sentences are annotated according to the above scheme by two human annotators.

Inter-annotator agreement

Interannotator agreement is relatively straightforward to calculate, although there are dependencies between tags (e.g. SOURCE is relevant only in case of INDIRECT speech). For each sentence, we compare the set of tags added by annotator A and by annotator B. If the tags do not fully correspond,

COMPLETED, INDI-RECT, SOURCE='les porte-parole des deux groupes'

Selon Apple4us, un des plus gros blogs chinois au sujet d'Apple, la firme de Cupertino aurait racheté EditGrid, un service de tableurs en ligne basé à Hong Kong, pour une somme comprise entre 10 et 30 millions de dollars.

COMPLETED, INDIRECT, SOURCE='Apple4us'

Amazon aurait racheté la jeune pousse américaine Touchco basée à New York pour développer son offre de lecteurs de livres numériques Kindle.

POSSIBLE, DIRECT

Le possible rachat du Parisien-Aujourd'hui en France par le groupe Dassault inquiète.

POSSIBLE, DIRECT

La société Acom27 dirigée par Monsieur et Madame Garnot n'a absolument pas été rachetée par les éts Cochet. we consider that there is a disagreement. Dependencies between tags are not taken into account. This is not a problem as it penalizes the evaluation, rather that the other way round (i.e. results are lower than they would be if we were taking into account these dependencies).

NEGATED, DIRECT

We then computed Cohen's kappa [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF]) and obtained 0.94, which means a near perfect agreement, according to the usual interpretation of Cohen's kappa results [START_REF] Fleiss | Statistical methods for rates and proportions[END_REF]. This proves that our method is both efficient and accurate. Some sentences are hard to classify between DI-RECT and INDIRECT, especially when the event is negated, for example when a company denies rumors (Twitter dément la rumeur de rachat par Apple -Twitter denies the rumor of a buyout by Apple). In this case, the experts agreed on NEGATED and INDIRECT. The cases of disagreement are rare and affect quite specific sentences (with negation or with a complex structure); they can all be solved after discussion between domain experts.

However, this scheme does not cover all possible cases and should be extended for specific needs.

Since it is open (and built upon existing schemes) it can easily be extended to cover new cases and new applications.

Conclusion

In this paper, we have presented an annotation scheme that is more precise that what has been proposed for the MUC and the ACE conferences.

Our scheme allows one to quickly annotate relations in texts without sacrificing accuracy.

We have proven this result through an experiment on texts from the financial domain, both in English and in French. Additionally, we have shown that it is possible to quickly retrieve relevant examples just by accessing the corpus with key collocations.

The perspectives are twofold. First, we need to annotate a larger number of texts from different domains to ensure the utility of our scheme. Second, we need to explore different specializations of this scheme, as different needs will probably be expressed in the future to get a more precise annotation, concerning modalities for example.

Table

	Rumors Swirling Around A Google Acquisition of	POSSIBLE,	INDIRECT,
	Groupon	SOURCE='rumors'
	Google will NOT acquire Twitter in 2011	POSSIBLE,	DIRECT,
		NEGATED
	Google Buys Mobile Ad Company for $750M	COMPLETED, DIRECT
	Is Google Buying Groupon For Several Billion	POSSIBLE, DIRECT
	Dollars?
	Google announced on Friday that it has entered	ONGOING,	INDIRECT,
	into an agreement to acquire Widevine	SOURCE='Google'

  Areva a racheté pour 1,62 milliard d'euros la part de Siemens dans la co-entreprise Areva NP, ouvrant la voie à un rapprochement entre Siemens et le russe Rosatom, selon le journal allemand Die Welt, qui cite les porte-parole des deux groupes, s'exprimant dans un document qui sera publié lundi.

	Twitter dément la rumeur de rachat par Apple	NEGATED, INDIRECT,
		SOURCE='rumeur'

Table 2 :

 2 French examples used for evaluation.

Tha ARISEM named entity recognizer.