Nabil H Mustafa
email: mustafan@esiee.fr

Saurabh Ray
email: saurabh@mpi-inf.mpg.de

A Theorem of Bárány Revisited and Extended

Keywords: G.2 [Combinatorics]: Discrete Geometry Algorithms, Theory Discrete Geometry, Weak ǫ-nets, Caratheodory's theorem, Colorful Caratheodory theorem, Hadwiger-Debrunner (p, q)-theorem

 states that given d + 1 sets of points in R d , the convex hull of each containing the origin, there exists a simplex (called a 'rainbow simplex') with at most one point from each point set, which also contains the origin. Equivalently, either there is a hyperplane separating one of these d + 1 sets of points from the origin, or there exists a rainbow simplex containing the origin. One of our results is the following extension of the colorful Carathéodory theorem: given ⌊d/2⌋ + 1 sets of points in R d , and a convex object C, then either one set can be separated from C by a constant (depending only on d) number of hyperplanes, or there is a ⌊d/2⌋-dimensional rainbow simplex intersecting C.

INTRODUCTION

The goal of this paper is to study the behavior of low-dimensional simplices with respect to convex sets in R d . We examine a number of classical theorems in discrete geometry -Radon's theorem [START_REF] Rado | A theorem on general measure[END_REF], Carathéodory's theorem [START_REF] Matousek | Lectures in Discrete Geometry[END_REF], colorful Carathéodory theorem [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF] -and prove extensions that demonstrate the phenomenon of low-dimensional intersections.

Three classical theorems.

One of the starting theorems in discrete geometry is the following result. For a set P ⊂ R d , let conv(P ) denote the convex hull of P . THEOREM 1 (RADON'S THEOREM). Given any set P of d + 2 points in R d , one can partition P into two sets P1 and P2 such that conv(P1) ∩ conv(P2) = ∅.

Note here that one of the two sets P1 and P2 can be large, e.g., P1 can consist of d + 1 points. So only the trivial bound |P1|, |P2| ≤ d + 1 holds. Therefore one cannot get a better upper bound on the dimension of the simplices conv(P1) or conv(P2).

We say a point p can be separated from a convex set C if there exists a hyperplane h with C and p in the interior of the two different halfspaces defined by h. THEOREM 2 (CARATHÉODORY'S THEOREM). If a convex set C intersects the convex hull of some point set P , then it also intersects a simplex spanned by P . Equivalently, either P can be separated from C with one hyperplane, or C intersects the convex hull of some (d + 1) points of P .

Here we have stated the theorem in a slightly more general form; usually it is stated where C is just a point.

A beautiful extension of Carathéodory's theorem was discovered by Imre Bárány [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF]: THEOREM 3 (COLORFUL CARATHÉODORY THEOREM). Given d + 1 sets of points P1, . . . , P d+1 in R d and a convex set C such that C ∩ conv(Pi) = ∅ for all i = 1, . . . , d + 1, there exists a set Q with C ∩ conv(Q) = ∅ and where |Q ∩ Pi| = 1 for all i. Such a Q is called a 'rainbow set'. Equivalently, either some Pi can be separated from C with one hyperplane, or C intersects the convex hull of a rainbow set of d + 1 points. This theorem is also commonly stated for the case where C is a point, but the above slight generalization follows immediately from Bárány's proof technique [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF]. Also, Carathéodory's theorem follows by applying the colorful Carathéodory theorem to d + 1 copies of the same pointset.

Our results.

The starting point of our work is the following well-known generalization of the Erdös-Szekeres theorem: THEOREM 4 (GENERALIZED ERDÖS-SZEKERES THEOREM). Given positive integers d, k, n such that ⌈d/2⌉ + 1 ≤ k ≤ d, there exists an integer n0 = ES d (n, k) such that any set of n0 points in R d contains a subset P of size n with the following property: the simplex spanned by every (d + 1)k points of P lies on the boundary of conv(P ). This statement is optimal, in the sense that this is not true for k < ⌈d/2⌉ + 1 for arbitrarily large pointsets.

The case k = d simply corresponds to the Erdös-Szekeres theorem (that any large-enough set contains a lot of points in convex position). Of course the 'large-enough' size for the above theorem increases with decreasing k; but if one pays that price, one can get more properties. For example, for d = 4, k = 3, any large-enough set of points in R 4 contains a large subset Q where every edge spanned by points of Q lies on conv(Q).

We now observe that this immediately carries over to an at-first nonobvious extension of Radon's theorem: if one is willing to increase the number of points, then a better upper-bound can be achieved on the sizes of the Radon partition:

THEOREM 1.1. Given an integer ⌊d/2⌋ + 1 ≤ k ≤ d, any set P of ES d (d + 2, k) points in R d contains two sets P1, P2 such that conv(P1) ∩ conv(P2) = ∅ and additionally, |P1|, |P2| ≤ k.
Furthermore, this is optimal in the sense that the statement does not hold for k ≤ ⌊d/2⌋. PROOF. Apply Theorem 4 to P to get a set of d + 2 points P ′ . Apply Radon's theorem to P ′ to get a partition P1, P2 ⊂ P ′ whose convex hulls intersect. Now note that if |P1| > k, then |P2| ≤ (d + 1)k. But then conv(P2) lies on the convex hull of P ′ , and so cannot intersect conv(P1), a contradiction.

Optimality is obvious as |P | ≥ d + 2 for such a partition to exist (for P in general position), and so one set has to have at least ⌊d/2⌋ + 1 points.

Our first result is to show that a similar extension is possible for Carathéodory's theorem (Section 4): THEOREM 1.2. Given a set P of n points in R d and a convex object C, either P can be separated from C by O(d 4 log d) hyperplanes (i.e., each p ∈ P is separated from C by one of the hyperplanes), or C intersects the convex hull of some ⌊d/2⌋ + 1-sized subset of P .

We show the above result by relating this problem to another well-known problem; in fact we prove that the bounds for these two problems are within a factor of d of each other, a result of independent interest.

Unfortunately the above approach does not work for proving an extension of the colorful Carathéodory theorem, for which we give a proof using a different technique (Section 5): THEOREM 1.3. For any d, there exists a constant N d such that given k = ⌊d/2⌋ + 1 sets of points P1, . . . , P k in R d and a convex object C, either one of the sets Pi can be separated from C by N d hyperplanes, or there is a rainbow set of size k whose convex hull intersects C.

Remark 1: Unlike the small polynomial bound in the extension of Carathéodory's theorem, the constant N d is exponential in d. We leave improving N d as an open problem.

Remark 2: The case where there are d + 1 sets, and a set can be separated by one hyperplane is exactly the colorful Carathéodory theorem.

Remark 3: Note also that, as before, Theorem 1.3 implies the corresponding extension for Carathéodory's theorem, although with much worse quantitative bound than that given in Theorem 1.2.

Remark 4: Theorem 1.3 implies that given C and a set of red and blue points in R 3 , either the red set or the blue set can be separated from C by a constant N3 number of planes. Or there is a red-blue edge intersecting C. In fact, for this case, a direct elementary proof with better constant exists, as follows. First, elementary considerations show that given a pointset and a convex set C, either there is a triangle ∆ spanned by the points so that each edge of ∆ intersects C or all the point can be separated from C using twelve hyperplanes. Now suppose that we have some red and blue points and a convex set C. Then applying the above result to each set of points, we conclude that either one of the sets can be separated from C with twelve planes or there is a red triangle and a blue triangle each of whose edges intersect C. For each vertex of these triangles consider the region on the boundary of C that it can see (considering C to be opaque). Since each red (resp. blue) edge intersects C, no two of the red (resp. blue) regions intersect, i.e., no three of the six regions intersect at a common point. Since the regions are pseudodisks, their intersection graph is planar. As K3,3 is not planar, there is a red region and a blue region which do not intersect. This implies that the red-blue edge defined by the points corresponding to these regions intersects C.

We conclude with some open problems and future directions of research in Section 6.

MOTIVATION & RELATED PROBLEMS

Besides building on some basic theorems of discrete geometry, there are a few other reasons why statements of the type considered in this paper are useful.

Weak ǫ-nets.

The weak ǫ-net problem asks, given a set P of n points in R d , for the existence of a small-sized set Q ⊆ R d such that any convex set containing at least ǫn points of P contains a point of Q. The current best upper-bound on the size of Q required is Õ(1/ǫ d ), while the best lower-bound is Ω(1/ǫ log d-1 1/ǫ). It is not clear what upper-bound to expect. But if one believes that "the truth is probably much smaller, maybe around O(1/ǫ ⌊d/2⌋ )" [Mat99], then consider the following natural approach from [START_REF] Mustafa | Weak ǫ-nets have a basis of size O(1/ǫ log 1/ǫ)[END_REF].

Pick a strong ǫ-net Q (with respect to the intersection of some constant k halfspaces). Now suppose a convex object C containing ǫn points of P is not hit by this strong ǫ-net. Then it must be that no set of k halfspaces separate C from points of Q; otherwise the intersection of these halfspaces contains C and so contains at least ǫn points without containing any point of Q, a contradiction. Intuitively, this means that the points of Q are 'close' to the boundary of C. It seems likely that then C must contain a large fraction of the volume (w.r.t. some measure) of some low-dimensional simplex spanned by points of Q (in which case we are done by picking weak nets of constant size within each low dimensional simplex). Unfortunately even the existence of an intersection of some lowdimensional simplex with C is not clear. The best one can hope for is a large intersection with a ⌊d/2⌋-dimensional simplex (better than this is not possible -to see this consider P to be the vertex set of a cyclic polytope and let C to be a slightly shrunk copy of the polytope). This is somewhat similar to the inductive approach in [ABFK92, CEG + 93]. Hence the above discussion provides one reason to study the separation interaction of low-dimensional simplices spanned by some set P with a convex set C.

High-depth edge.

The following is a well-known problem open for more than 20 years: given a set P of n points in the plane, show that there exist two points of P such that any disk containing them contains at least n/4 points of P . The current-best bound is n/4.73 [START_REF] Edelsbrunner | Circles through two points that always enclose many points[END_REF]. We now show a close relation to the problems we study in this paper.

Given P , map P to P ′ via a standard lifting to the paraboloid in R 3 . So each disk in R 2 corresponds to a downward-facing halfspace in R 3 . Now let C be the centerpoint region of P ′ . By definition, each plane supporting a facet of C has less than n/4 points on the side not containing C. Now our goal is to find two points, say p1, p2 of P ′ such that any downward-facing halfspace containing p1p2 must contain at least one point of C -and so contain at least n/4 points. For contradiction, assume that for every pair of points, the "slab" swept by projecting the segment p1p2 onto the xy-plane avoids C. Then one would prove the conjecture by showing that there exist 4 planes supporting facets of C that separate all the points of P ′ from C. This would yield a contradiction, as each such halfspace contains less than n/4 points. Therefore, the goal is to show that either the vertical slab for a pair intersects C, or all the points of P ′ can be separated by 4 supporting hyperplanes. Then the easier question of separating P ′ from C with any separating hyperplanes if no edge intersects is exactly the extension of Carathéodory's theorem for R 3 .

Gallai-type problems for Pseudodisks.

Danzer proved that given any set of caps of a sphere in three dimensions such that every pair of them intersect, it is possible to pierce all of them using four points. While at first sight this appears unrelated to the problems we study, it is intimately related. Consider a sphere S and a set of points in R 3 outside it. For each point p, the set of points x ∈ S such that a tangent plane to the sphere at x separates S from p is a cap of S. Two points p and q can be separated from S using a single plane iff their corresponding regions intersect. Danzer's theorem therefore implies that either the set of points can be separated from S using four planes or there is an edge spanned by the points that intersects S. If we replace this sphere in R 3 with an arbitrary convex set, then caps are replaced by regions that are pseudodisks. Danzer's result is believed to hold for pseudodisks as well but is currently known only with worse bounds. Therefore such separation problems can be seen as generalized Gallai-type problems.

PRELIMINARIES

In this section, we describe some basic results in discrete geometry that we will need.

Hadwiger-Debrunner (p,q)-theorem [START_REF] Alon | Piercing convex sets and the Hadwiger Debrunner (p; q)-problem[END_REF]. Given a set S of convex sets in R d such that out of every p ≥ d + 1 sets, there is a point common to q ≥ d+1 of them, then S has a hitting set of finite size and the minimum size of such a set is denoted by HD d (p, q) (so this is independent of |S|).

ǫ-nets w.r.t. halfspaces in R d [START_REF] Haussler | Epsilon-nets and simplex range queries[END_REF]. Given a set P of n points in R d and a parameter ǫ > 0, a set Q ⊆ P is an ǫ-net w.r.t. halfspaces if any halfspace containing at least ǫn points of P contains a point of Q. A famous theorem of Haussler-Welzl [START_REF] Haussler | Epsilon-nets and simplex range queries[END_REF] shows that ǫ-nets of size O(d/ǫ log d/ǫ) exist, independent of n. This bound was later improved in [START_REF] Komos | Almost tight bounds for epsilon nets[END_REF] to a near-optimal bound of (1 + o(1))( d ǫ log(1/ǫ)).

Centerpoint depth [START_REF] Matousek | Lectures in Discrete Geometry[END_REF]. Given any set P of n points in R d , the Tukey depth of a point q ∈ R d is the minimum number of points of P contained in any halfspace containing q. It is known that there always exists a point of Tukey depth at least n/(d + 1).

In general, the set of points of Tukey depth at least βn form a convex region called the β-deep region of P . The β-deep region is non-empty for any β ≤ 1/(d + 1). It is the intersection of all halfspaces containing more than (1β)n points of P . Each facet of this region is supported by a hyperplane that passes through d points of P . We will need the following fact:

Fact 1 [PA95]: If P is a set of n points and h is a hyperplane defining a facet of the β-deep region C of P , then the halfspace defined by h that does not intersect the interior of C contains less than βn points of P .

PROOF OF EXTENDED CARATHÉODORY'S THEOREM

We first show that this problem is related to another problem involving low-dimensional simplices.

Let f (d) be the smallest positive number such that for any set P of points in R d , there exists a ⌊d/2⌋ + 1-sized subset P ′ ⊆ P such that any halfspace containing P ′ contains at least |P |/f (d) points of P .

Let g(d) be the smallest positive number such that given any set P of points in R d and a convex set C, if P cannot be separated from C using at most g(d) hyperplanes, then C must intersect the convex hull of some ⌊d/2⌋ + 1 size subset of P .

We now show that g(d) and f (d) are related within a factor of d.

THEOREM 4.1. g(d) ≤ d•f (d) log f (d).
In other words, given a set P of points in R d and a convex set C such that P cannot be separated from C by df (d) log f (d) hyperplanes, then C must intersect the convex hull of some ⌊d/2⌋ + 1 points of P .

PROOF. Assume that no convex hull of any ⌊d/2⌋ + 1 points of P intersects C. Then we show that P can be separated from C using df (d) log f (d) hyperplanes. CLAIM 4.2. Let P be a weighted set of points in R d , with weight of the point pi ∈ P to be wi. Assume all wi's are rationals, and let W = P wi. If the convex hull of no ⌊d/2⌋ + 1 points of P intersects C, then there exists a hyperplane separating points of total weight at least W f (d) from C. PROOF. As each wi is a rational, assume wi = ŵi/D, where ŵi and D are integers. Let Q be the pointset gotten by replacing each point pi with ŵi copies of pi. Crucially, if the convex hull of no ⌊d/2⌋ + 1 subset of P intersects C, then the convex hull of no ⌊d/2⌋ + 1 subset of Q can intersect C. Take the ⌊d/2⌋ + 1-sized subset Q ′ of Q such that any halfspace containing Q ′ contains at least |Q|/f (d) points of Q. As the convex hull of Q ′ does not intersect C, there is a halfspace h which does not intersect C and contains Q ′ . Let P ′ be the set of points of P contained in h. Then h contains exactly P p i ∈P ′ ŵi points of Q, which by definition of Q ′ must be at least |Q|/f (d). Then the sum of weights of points of P contained in h is bounded by

X p i ∈P ′ wi = P p i ∈P ′ ŵi D ≥ |Q|/f (d) D = ( P ŵi)/f (d) D = P wiD Df (d) = W f (d)
Discretize the set of all combinatorially distinct hyperplanes separating some subset of P from C to get a set H = {h1, . . . , hm} of O(|P | d ) hyperplanes. Now consider assigning weights w(hi) to each halfspace such that the total weight P w(hi) is minimized, and the sum of weights of halfspaces containing any point of P is at least 1. Let W (H) denote the minimum value.

Similarly, assign weights w(pi) to each point of P such that the total weight P w(pi) is maximized, and the sum of weights of points contained in any halfspace h ∈ H is at most 1. Let W (P ) denote the maximum value. Then the above two problems are dual to each other (as linear programs), and so by the Strong Duality Theorem, W (H) = W (P ). Now note that W (P ) ≤ f (d): by Claim 4.2, there exists a halfspace in H of weight at least W (P )/f (d), which by the definition of W (P ) is at most 1.

Therefore there exists an assignment of weights to halfspaces in H such that W (H) ≤ f (d), and each point is contained in halfspaces of total weight at least 1. Now using the ǫ-net theorem for halfspaces [START_REF] Komos | Almost tight bounds for epsilon nets[END_REF], with ǫ = 1/W (H), there exists a set of

d/ǫ log 1/ǫ = dW (H) log W (H) = df (d) log f (d)
halfspaces of H containing all points of P . As all halfspaces in H were separating halfspaces, we are done.

Remark 1: The above technique is similar to the one used in the proof of Hadwiger-Debrunner (p, q) theorem [AK92], with some crucial differences. In their use, they get an exponential bound, which we are able to avoid due to three reasons: ǫ-nets for halfspaces have a near-linear bound, avoiding double-counting arguments that they use, and finally, the weighted version (Claim 4.2) gives exactly the same quantitative bound as the unweighted version.

Proof of Theorem 1.2: the paper [START_REF] Smorodinsky | On center regions and balls containing many points[END_REF] proves that f (d) ≤ O(d 3 ). And the proof is complete by using Theorem 4.1.

Similarly we now show that a bound on g(d) gives an upperbound on f (d):

THEOREM 4.3. f (d) ≤ d • g(d).
In other words, given a set P of points in R d , there always exists a subset P ′ of size ⌊d/2⌋ + 1 such that any halfspace containing P ′ contains at least |P |/dg(d) points of P .

PROOF. Consider the β-deep region C of P ; by the Centerpoint theorem, for β ≤ 1/(d + 1), such a region always exists. Now we claim that for β = 1/dg(d), there exists a ⌊d/2⌋ + 1-sized subset P ′ whose convex hull intersects C. Then any halfspace containing P ′ contains at least one point of C, and so contains at least |P |/dg(d) points by the definition of the centerpoint region.

Otherwise, for contradiction assume that the convex hull of no ⌊d/2⌋ + 1-sized subset intersects C. Then by definition of g(d), P can be separated from C using g(d) hyperplanes, say the set H.

PROOF OF EXTENDED COLORFUL CARATHÉODORY THEOREM

The goal of this section is to prove Theorem 1.3. We use a slightly different language for convenience: instead of saying that "a point set P can be separated from a convex body C using k hyperplanes", we say that "there exists a polyhedron Q with k facets such that C ⊆ Q and Q ∩ P = ∅". In such a case we also say that Q separates P from C. We re-state Theorem 1.3 in this language. THEOREM 5. For any positive d and l > ⌊d/2⌋, there exists a constant N d,l s.t. the following is true. Given any compact convex body C and l finite sets of points P1, . . . P l in R d , at least one of the following holds:

1. There exists a polyhedron Q with at most N d,l facets such that for some i, Q separates Pi from C.

2. There exists a rainbow subset P ′ ⊆ ∪ d i=1 Pi whose convex hull intersects the interior of C.

The approach of the previous section does not work for proving the extension of the colorful Carathéodory's theorem. The method gave one low-dimensional simplex intersecting C, or the existence of a hyperplane separating many points. Unfortunately with multiple sets, one needs to find many such intersecting simplices for each set Pi. Therefore one is forced to use a more Ramsey-theoretic technique, and this causes the constant to become exponential in d.

We next present some preliminary definitions and claims required to prove the above theorem.

Call a convex body C fine if it is compact and its boundary ∂C is smooth and has positive curvature everywhere. Let C be a fine convex body and let P be a finite set of points in R d . We say that a point p can see a point y if the relative interior of the segment py does not intersect C. For any p ∈ P , let Up be the set of points in ∂C that p can see.

Let hy be the tangent plane to C at the point y ∈ ∂C and let h + y be the closed halfspace defined by it that contains C. Observe that any point p ∈ P sees a point y ∈ ∂C iff p / ∈ int(h + y ), where int(S) denotes the interior of the set S.

LEMMA 5.1. For any positive numbers d and t ≥ d, there exists a constant H t,d such that given any fine convex body C and a finite set of points P such that P ∩ C = ∅, at least one of the following hold:

• There exists a set X ⊂ ∂C of size at most H t,d such that each point in P is seen by some x ∈ X.

• There is a subset P ′ ⊆ P of size at least t such that no y ∈ ∂C sees more than d -1 points in P ′ .

PROOF. Fix any point ν ∈ ∂C as a reference point. Let hν be the tangent plane to C at ν. Let h be the unique tangent hyperplane parallel to hν such that C is contained in the strip between hν and h. Let π be the continuous bijective map that maps any y ∈ ∂C \ {ν} to l (ν, y) ∩ h, where l (ν, y) denotes the line through ν and y.

For any p ∈ P that does not see ν (i.e., ν / ∈ Up), let Vp = π(Up) = {π(y) : y ∈ Up} and let V = {Vp : p ∈ P, p does not see ν}. Clearly, for each p ∈ P that does not see ν, Vp lies on the plane h, is convex and has dimension d-1. Note that if two points p, q ∈ P see a point y ∈ ∂C then y ∈ Up ∩ Uq. So π(y) ∈ Vp ∩ Vq.

Suppose that the second part of the theorem does not hold; i.e., in every subset of P of size t, there are at least d points which can be seen by a single point y ∈ ∂C. Equivalently, any subset of V of size t has at least d sets which have a common intersection. By the Hadwiger-Debrunner theorem [START_REF] Alon | Piercing convex sets and the Hadwiger Debrunner (p; q)-problem[END_REF], there exists a constant HD d-1 (t, d) of points in h that hit all the sets in V. Let X ′ be the set of these points. Let X = π -1 (X ′ ) ∪ {ν}. Each point in P is seen by at least one point in X (if Vp is hit by the point y ′ ∈ h, then p ∈ P is seen by π -1 (y ′ ) ∈ ∂C). The theorem is therefore proved by setting H t,d = HD d-1 (t, d) + 1. Now we can finish the proof of the main theorem of this section: PROOF. Let P = ∪ l i=1 Pi. We set N d,l = H t,d for some t to be fixed later.

If P ∩ C = ∅ then the second part of the theorem is trivially satisfied. We therefore assume that P ∩ C = ∅. Without loss of generality we also assume that C is fine since we can always find a fine convex body C ′ that contains C and does not intersect P and furthermore for each point y ′ ∈ C ′ , there is a point y ∈ C such that the Euclidean distance between y and y ′ is smaller than any prescribed δ > 0. Proving the theorem for such C ′ s also proves it for arbitrary closed convex bodies.

For each i, apply Lemma 5.1 to C and Pi with the parameter t. This gives us either a set Xi of at most H t,d points in ∂C such that each point in Pi is seen by at least one of these or we get a set Qi ⊆ Pi of t points so that no d of them is seen by the same point in ∂C. If the first possibility happens for some j, then

T x∈X j h + x
gives us the polyhedron Q with at most H t,d facets and where Q contains C while Pj lies outside Q. This satisfies the first part of the Theorem and we're done. We therefore assume the second possibility for each i; namely, each Pi has a subset Qi of t points such that no d points of Qi are seen by the same point of ∂C. Equivalently, the convex hull of any d points of Qi intersects C.

Let Q = ∪ l i=1 Qi. Consider any rainbow set R ⊆ Q with one point from each Qi. There are t l such sets. If the convex hull of R intersects C, then the second part of the theorem is satisfied, and we're done. Assume for contradiction that this is not the case. Then for each rainbow set R, there exists a hyperplane h separating R from C. The closed halfspace h -bounded by h and not intersecting C contains at most d -1 points from any particular Qi due to the fact that any d-sized subset of Qi intersects C. Therefore |h -∩Q| ≤ (d-1)l, and hence is a ≤ k-set of Q with k = l(d-1).

If no rainbow set intersects C, then we get such a ≤ k-set for each rainbow set R of size l. As there are t l such rainbow sets, we get t l ≤ k-sets. However each such ≤ k-set can be overcounted at most `k l ´= `l(d-1) l ´times. This implies that there are at least L(t) = t l / `l(d-1) l ´distinct ≤ k-sets. On the other hand, it is known that the number of ≤ k-sets of a set of n points in R d is at most O(n ⌊d/2⌋ (k + 1) ⌈d/2⌉ ) [START_REF] Matousek | Lectures in Discrete Geometry[END_REF]. This gives an upper bound of U (t) = O((tl) ⌊d/2⌋ ((d -1)l + 1) ⌈d/2⌉ ) on the number of ≤ ksets. Since l > ⌊d/2⌋, for some large enough t depending only on l and d, L(t) > U (t). Thus we get a contradiction implying that one of the rainbow sets must intersect C.

CONCLUSIONS

We think that the phenomenon studied in this paper is much more widely applicable. In fact, statements of this type might shed light on interactions between several classical theorems (see below). Besides improving quantitative bounds presented in this paper -for both extended Carathéodory and the extended colorful Carathéodory theorems -we end with a number of questions for which we think the answer is affirmative:

1. Extension of Kirchberger's theorem. Given a set P of n red points and n blue points in R d either there exist a constant number of hyperplanes H such that every red-blue pair is separated by a plane in H, or a ⌊d/2⌋-dimensional red simplex intersects a ⌊d/2⌋-dimensional blue simplex.

2. Extension of Tverberg's theorem. Given a set P of n points in R d , there exists a Tverberg partition on a large subset of P where two sets have size ⌊d/2⌋ + 1. It is not too hard to see that this implies a version of the extension of Carathéodory's theorem.

3. Extension of Colored Tverberg's theorem. Given (d + 2) sets P1, . . . , P d+2 , there exists a colored Tverberg partition on a large subset where two sets have size ⌊d/2⌋ + 1. Again, this version implies the extension of the colorful Carathéodory theorem.

  Now any halfspace not intersecting C contains less than d • β|P | points: each halfspace supporting a facet of C contains less than β|P | points, and any other halfspace not intersecting C is contained in the union of at most d halfspaces supported by facets of C. Therefore each halfspace of H contains less than d • β|P | points. And so the union of halfspaces in H contains less than g(d)•d•β|P | points of P , a contradiction for β = 1/dg(d).

ACKNOWLEDGEMENTS

We thank an anonymous reviewer for meticulous and very insightful comments. The first author would also like to thank Janos Pach for his support and encouragement. Part of this work was done by the first author while visiting the wonderful algorithms group at the Max-Planck Institute for Informatik in Saarbrucken.


F Comte

NONPARAMETRIC ESTIMATION FOR STOCHASTIC DIFFERENTIAL EQUATIONS WITH RANDOM EFFECTS

Keywords: Diffusion process, mixed models, nonparametric estimation, random effects. AMS Classification. 62G07-62M05

published or not. The documents may come

Nonparametric estimation for stochastic differential equations with random effects

Introduction

Random effects models are increasingly used in the biomedical field and have proved to be adequate tools for the study of repeated measurements collected on a series of subjects (see e.g. Davidian and Giltinian, 1995[START_REF] Pinheiro | Mixed-Effects Models in S and S-PLUS[END_REF][START_REF] Nie | Strong consistency of MLE in nonlinear mixed-effects models with large cluster size[END_REF][START_REF] Nie | Strong consistency of the maximum likelihood estimator in generalized linear and nonlinear mixed-effects models[END_REF][START_REF] Nie | Convergence rate of the mle in generalized linear and nonlinear mixed-effects models: Theory and applications[END_REF].

Such mixed models are defined through a hierarchical structure where, first, a distribution describes the intra-individual variability and, second, a distribution describes the inter-individual variability. In stochastic differential equations (SDEs) with random effects, the dynamics of each individual is given by a SDE with drift and/or diffusion coefficient depending on parameters, and the parameters of each SDE are random variables thus taking into account the variability between individuals. To be more precise, consider the following one-dimensional SDE modeling a continuous evolution for N subjects: [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF] dX j (t) = b(X j (t), φ j )dt + σ(X j (t), φ j )dW j (t), X j (0) = x j , j = 1, . . . , N.

Here, x 1 , . . . , x N are known values, (W 1 , . . . , W N ) are independent standard Brownian motions, φ 1 , . . . , φ N are i.i.d. random variables and (W 1 , . . . , W N ) and (φ 1 , . . . , φ N ) are independent. Each process (X j (t)) represents an individual and the random variable φ j represents the random effect of individual j. The functions b(x, ϕ), σ(x, ϕ) are supposed to be known and statistical inference is mainly concerned with the common unknown distribution of the random effects φ j . In several recent contributions, a parametric model is proposed for the latter distribution and various numerical as well as theoretical results have been obtained concerning maximum likelihood estimation (see e. Nonparametric estimation in the context of random effects models has been recently investigated for linear discrete time models (see e.g. [START_REF] Comte | Nonparametric estimation of random effects densities in linear mixedeffects model[END_REF]. To our knowledge, the problem of nonparametric estimation of the population distribution (distribution of φ j ) has not been yet investigated in the context of SDEs with random effects. In this paper, we study this topic in two special cases of [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF]. First, a multiplicative random effect in the drift: [START_REF] Comte | Penalized contrast estimator for adaptive density deconvolution[END_REF] dX j (t) = φ j b(X j (t))dt + σ(X j (t))dW j (t), X j (0) = x j , j = 1, . . . , N.

Second, an additive random effect in the drift:

(3) dX j (t) = (φ j + b(X j (t)))dt + σ(X j (t))dW j (t), X j (0) = x j , j = 1, . . . , N.

The functions b : R → R and σ : R → R are known. We assume that the random variables φ 1 , . . . , φ N have a common density f on R and that the processes (X j (t)) are continuously observed on a time interval [0, T ] with T > 0 given. We build a series of nonparametric estimators of the density f from the observations {X j (t), 0 ≤ t ≤ T, j = 1, . . . , N } which are either kernel or deconvolution estimators. We study the L 2 -risk of the proposed estimators and discuss their asymptotic properties as N tends to infinity. We distinguish the case of fixed T and the case of T = T (N ) tending to infinity with N . In view of practical implementation, the case of discrete observations (X j (kδ), 0 ≤ k ≤ n, j = 1, . . . , N ), with nδ = T is studied. Numerical simulation results using discretized sample paths for various models are given. Section 2 concerns model [START_REF] Comte | Penalized contrast estimator for adaptive density deconvolution[END_REF]. For large T , we propose a kernel estimator f

h of f . The bound of its L 2 -risk shows that T = T (N ) ≥ N 3 ensures the possibility of obtaining the usual optimal rates on Nikol'ski classes of regularity for f . Section 2.2 is devoted to the special case b = σ. Using an approach analogous to the one in [START_REF] Comte | Nonparametric estimation of random effects densities in linear mixedeffects model[END_REF], we build a deconvolution estimator f (2) m and discuss its properties for fixed and large T . Then, under the condition T = T (N ) = N 2 , a special class of deconvolution estimators ( fτ , τ ≤ N 2 ) is introduced.

We propose a data-driven selection of the parameter τ which is non standard and leads to an adaptive estimator (Theorem 1).

Section 3 concerns model [START_REF] Comte | Nonparametric estimation of random effects densities in linear mixedeffects model[END_REF]. We follow an analogous scheme. The model assumptions and the constraints on T are weaker. First, a kernel estimator f (4) h is proposed which attains usual optimal rates for T = T (N ) ≥ N 5/2 . Then, for T = T (N ) = N 2 a class of deconvolution estimators ( fτ , τ ≤ N 2 )) and a data-driven selection of τ are studied.

In view of practical implementation, we consider the case of discrete observations with small sampling interval δ and check that the estimators can be adapted to this case (Section 4). This is used indeed in Section 5, devoted to numerical simulation on various models: the kernel and the adaptive deconvolution estimators are implemented. The results are satisfactory, even when the condition T (N ) = N 2 is not fulfilled. In Section 6, model properties are investigated in the general framework of (1) or in the special cases of ( 2) and (3). Some concluding remarks are given in Section 7. Proofs are gathered in Section 8.

Multiplicative random effect in the drift

We consider in this section model [START_REF] Comte | Penalized contrast estimator for adaptive density deconvolution[END_REF] where ϕ belongs to R and b and σ are known functions satisfying:

(H1) b and σ are Lipschitz:

∃L > 0, ∀x, y ∈ R, |b(x) -b(y)| + |σ(x) -σ(y)| ≤ L|x -y|. (H2)
T 0 b 2 σ 2 (X j (s))ds < +∞, j = 1, . . . , N, a.s. The processes (W 1 , . . . , W N ) and the r.v.'s (φ 1 , . . . , φ N ) are defined on a common probability space (Ω, F, P). Consider the filtration (F t , t ≥ 0) defined by F t = σ(φ j , W j (s), s ≤ t, j = 1, . . . , N ). As F t = σ(W i (s), s ≤ t) ∨ F i t , with F i t = σ(φ i , (φ j , W j (s), s ≤ t), j = i) independent of W i , each process W i is a (F t , t ≥ 0)-Brownian motion. The random variables φ i are F 0measurable. Under (H1), equation (2) admits a strong solution adapted to the filtration (F t , t ≥ 0) (see Proposition 8). Assumption (H2) is clearly fulfilled, for instance, if σ is lower bounded. Following [START_REF] Delattre | Maximum likelihood estimation for stochastic differential equations with random effects[END_REF], we may now introduce statistics which have a central role in the estimation procedure. For j = 1, . . . , N , we denote (4)

U j (t) = t 0 b σ 2 (X j (s))dX j (s), V j (t) = t 0 b 2 σ 2 (X j (s))ds. Then, equation (2) yields: (5) U j (t) = φ j V j (t) + M j (t), j = 1, . . . , N, with M j (t) = t 0 (b/σ)(X j (s)
)dW j (s). 2.1. Large observation time. In this paragraph, we consider the asymptotic framework where both N and T tend to infinity. And, in addition to (H1)-(H2), we assume:

(H3) +∞ 0 b 2 σ 2 (X j (s))ds = +∞, j = 1, . . . , N, a.s. Let A j,T := U j (T ) V j (

T ) .

The statistic A j,T coincides with the maximum in ϕ of the conditional likelihood of (2) given φ j = ϕ. From (5), we see that A j,T = φ j + M j (T )/V j (T ) (see e.g. [START_REF] Delattre | Maximum likelihood estimation for stochastic differential equations with random effects[END_REF]). The second term is the ratio of a martingale divided by its quadratic variation, which under (H3), tends to zero a.s. when T tends to infinity. Thus, A j,T is a consistent estimator of the random variable φ j . To deal with expectations, we need the following stronger assumption implying (H3): (H4) There exist positive constants c 0 , c 1 such that

c 2 0 ≤ b 2 (x)/σ 2 (x) ≤ c 2 1
, ∀x ∈ R. As A j,T approximates φ j , we introduce a kernel estimator for the unknown density f of φ j : ( 6)

f (1) h (x) = 1 N N j=1 K h (x -A j,T ), K h (x) = 1 h K x h ,
where K is integrable with K(u)du = 1, C 1 and satisfies

(7) K 2 := K 2 (u)du < +∞, K ′ 2 = (K ′ ) 2 (u)du < +∞,
where K ′ denotes the derivative of K and . the L 2 -norm. We define f h = f ⋆ K h where ⋆ denotes the convolution product.

Proposition 1. Consider estimator f (1) h given by ( 6) under (H1), (H2), (H4) and [START_REF] Donnet | Parametric inference for mixed models defined by stochastic differential equations[END_REF]. Then

(8) E( f (1) h -f 2 ) ≤ 2 f -f h 2 + K 2 N h + 2c 2 1 K ′ 2 c 4 0 1 T h 3 .
The proof of Proposition 1, as all other proofs, is relegated to Section 8. Under weak regularity assumptions on f , ff h 2 tends to zero when h tends to zero. The estimating method is consistent, as soon as 1/(N h) + 1/(T h 3 ) tends to zero. Since N is the number of i.i.d. observed trajectories, we now look at the rate of the L 2 -risk expressed as a function of N and thus let T and h be expressed as functions of N . We recall that a kernel of order ℓ satisfies x k K(x)dx = 0 for k = 1, . . . , ℓ. For constants β > 0 and L > 0, the Nikol'ski class N (β, L) is defined by:

N (β, L) = f : R → R : f (ℓ) (x + t) -f (ℓ) (x) 2 dx 1/2 ≤ L|t| β-ℓ , ∀t ∈ R .

The following Corollary holds

Corollary 1. Assume that f belongs to N (β, L) and that the kernel K has order ℓ = ⌊β⌋ with

|x| β |K(x)|dx < +∞. Under the condition (9) h ∝ N -1/(2β+1) and T = T (N ) ≥ N (2β+3)/(2β+1) ,
we have 2β+1) . We give here the classical discussion implying Corollary 1. If f belongs to N (β, L) and if the kernel K has order ℓ, then f - [START_REF] Tsybakov | Introduction to nonparametric estimation[END_REF]. For the first two terms in the r.h.s. of [START_REF] Donnet | EM algorithm coupled with particle filter for maximum likelihood parameter estimation of stochastic differential mixed-effects models[END_REF], the classical rate-optimal compromise imposes that h ∝ N -1/(2β+1) thus implying h 2β + 1/(N h) ∝ N -2β/(2β+1) . Fitting the last term with this rate requires that 1/(T h 3 ) ≤ N -2β/(2β+1) . This holds for T ≥ N (2β+3)/(2β+1) . The conditions in (9) yield the rate [START_REF] Ikeda | Stochastic differential equations and diffusion processes[END_REF].

(10) E( f (1) h -f 2 ) N -2β/(
f h 2 ≤ C 2 h 2β with C = L |u| β |K(u)|du/ℓ! (see
The constraint on T is satisfied for any nonnegative β if T ≥ N 3 . If β ≥ β 0 for some known β 0 , we only require T ≥ N (2β 0 +3)/(2β 0 +1) . Even if β is very large, we always need T /N tends to infinity when N tends to infinity.

With T = T (N ) ≥ N 3 , an adaptive selection of the bandwidth h could be done relying on the method described in Goldenshluger and Lepski (2011).

2.2. The special case b = σ for fixed T . The following approach is inspired by the discrete time model studied in Comte and Samson, 2012. Indeed, when b = σ, the variables in (4) and equation ( 5) reduce to:

U j (t) = t 0 dX j (s) σ(X j (s)) , V j (t) = t, U j (t) = φ j t + W j (t), j = 1, . . . , N.
Assume that T is fixed and let ∆ be a sampling interval to be discussed later. For k = 1, . . . , K, t k = k∆, T = K∆, we consider the following random variables based on observations [START_REF] Karatzas | Brownian motion and stochastic calculus[END_REF] U j,k :=

U j (t k ) -U j (t k-1 ) ∆ = φ j + 1 √ ∆ W j (t k ) -W j (t k-1 ) √ ∆ .
Using a Gaussian deconvolution, we define the estimator:

(12) f (2) m (x) = 1 2π πm -πm e -iux ∆ N T N j=1 K k=1 e iuU j,k e u 2 /(2∆) du,
where m is a cutoff which should be chosen adaptively.

Recall some standard notations. For possibly complex-valued functions g, h ∈ L 2 (R) ∩ L 1 (R), we denote by g * (u) = e iux g(x)dx the Fourier transform of g, by g, h = g(x)h(x)dx the L 2 -scalar product. The Plancherel theorem yields g, h = g * , h * /2π. Let now

f m (x) = 1 2π πm -πm e -iux f * (u)du, i.e. f * m (u) = f * (u)1 I [-πm,πm] (u) so that f (2) m (x) is, for all x, an unbiased estimator of f m (x), i.e. E( f (2) m (x)) = f m (x).
We have the following result. Proposition 2. Consider the estimator f (2) m given by [START_REF] Klein | Concentration around the mean for maxima of empirical processes[END_REF]. We have

E( f -f (2) m 2 ) ≤ f -f m 2 + ∆ 2πN T πm -πm e u 2 /∆ du + m N ≤ 1 2π |u|≥πm |f * (u)| 2 du + ∆ πN T ∆e π 2 m 2 /∆ πm + e 2 √ ∆ + m N . ( 13
)
The bound of the L 2 -risk is classically split into the sum of a bias term ff m 2 and a variance term, itself the sum of two expressions (last two terms in the r.h.s. of ( 13)). Let us discuss the possible best choice of ∆ for fixed T . Do we have interest to take small ∆? The function ∆ → ∆ 2 e (πm) 2 /∆ decreases for ∆ ≤ π 2 m 2 /2, increases for ∆ ≥ π 2 m 2 /2 and thus admits a unique minimum reached at π 2 m 2 /2. As m has to be large (for the bias to be small), the choice of ∆ minimizing ∆ 2 e (πm) 2 /∆ is excluded. Consequently, with fixed T ≥ 1, the best choice of ∆ ≤ 1 is just ∆ = 1. It follows that the dominating variance term is ∝ (e (πm) 2 /m)/N . This is the standard order of variance in nonparametric deconvolution when measurement errors are Gaussian. We refer to e.g. [START_REF] Comte | Penalized contrast estimator for adaptive density deconvolution[END_REF] for defining the adequate adaptive choice of the cut-off m.

In view of the next section, let us consider the case of a large T . Then, we can choose a large

∆ if T ≥ (πm) 2 /2. With ∆ = (πm) 2 /2 and T ≥ (πm) 2 /2, ∆ 2 e (πm) 2 /∆ π 2 m N T ≤ e 2 2 m N .
The two variance terms thus have the same order m/N which is standard in density estimation without noise. For instance, for ∆ = T, K = 1, πm = √ T , the estimator ( 12) is equal to:

1 2π √ T - √ T e -iux 1 N N j=1
e iuA j,T e u 2 /(2T ) du, with here A j,T = U j (T ) T .

The variance term in its L 2 -risk bound is simply (3e/2) √ T /N + m/N . This suggests the choice T (N ) ∝ N 2 as adequate.

2.3. Estimation in the case b = σ for large T . In the case of large T , with b = σ, the previous discussion indicates that T = T (N ) should be proportional to N 2 . Let us assume, for simplicity, that T = T (N ) = N 2 . The discussion also suggests to introduce a new class of estimators defined by

fτ (x) = 1 2π √ τ - √ τ e -iux 1 N N j=1
e iuA j,τ e u 2 /(2τ ) du, based on the observed processes (14)

A j,τ = U j (τ ) τ , τ ∈ [0, N 2 ].
Then, we proceed to build an adaptive choice of τ , among the integer values {1, . . . , N 2 }. Note that the class of estimators ( fτ ) presents a non standard feature as the parameter τ appears not only as a cut-off parameter for deconvolution but also inside the integral. The following risk bound holds when τ is fixed.

Proposition 3. Assume (H1), b = σ and τ ≤ T (N ) = N 2 . Then, E( fτ -f 2 ) ≤ 1 2π |u|≥ √ τ |f * (u)| 2 du + √ τ πN 1 + 1 0 e v 2 dv . Let f τ be such that f * τ = f * 1 I [- √ τ , √ τ ] .
The bias term above is:

f -f τ 2 = 1 2π |u|≥ √ τ |f * (u)| 2 du.
Regularity spaces usually considered in deconvolution setting are Sobolev balls defined by:

(15) C(a, L) = {f ∈ (L 1 ∩ L 2 )(R), (1 + u 2 ) a |f * (u)| 2 du ≤ L}.
Clearly, if f belongs to C(a, L):

1 2π |u|≥ √ τ |f * (u)| 2 du ≤ (L/2π)τ -a .
Thus, the bias-variance compromise is obtained for τ of order N 2/(2a+1) . The resulting rate is proportional to N -2a/(2a+1) . Evidently, as a is unknown, this choice of τ cannot be done.

Therefore, we now define the data-driven selection of τ . With κ a constant to be specified later, let ( 16)

pen(k) = κ √ k N , and (17)
Γτ = max 1≤k≤N 2 fk∧τ -fk 2 -pen(k) + = max τ ≤k≤N 2 fτ -fk 2 -pen(k) + ,
where (x) + = max(x, 0). Now define

(18) τ = arg min 1≤τ ≤N 2 Γτ + pen(τ ) .
As in Goldenschluger-Lepski method (see reference [START_REF] Goldenshluger | Bandwidth selection in kernel density estimation: oracle inequalities and adaptive minimax optimality[END_REF]), Γτ is a data-driven estimation of the bias term ff τ 2 while pen(τ ) corresponds to the variance term. The choice of τ is thus done to minimise the bias-variance compromise.

Recall that f τ is defined by

f * τ = f * 1 I [- √ τ , √ τ ] . Theorem 1. Assume (H1), b = σ and T (N ) = N 2 . For κ ≥ 12 1 0 e v 2 dv/π(≃ 5.58), we get E( fτ -f 2 ≤ C inf 1≤τ ≤N 2 ( f τ -f 2 + pen(τ )) + C ′ N ,
where C is a numerical constant (C = 7) and C ′ is a constant.

Theorem 1 states that the bias-variance compromise is automatically achieved by the adaptive estimator fτ without knowledge of the regularity of f . The condition T (N ) = N 2 may appear rather strong, but can be weakened if some knowledge on the regularity of f is available. For instance, assume that f ∈ C(a, L) with a ≥ 2. Then the optimal τ has order N 2/(2a+1) ≤ N 2/5 . Therefore, the condition T (N ) = N 2 can be replaced by T (N ) = N 2/5 . 2.4. Miscellaneous remarks. The two strategies described sections 2.1 and 2.2 have links. Under (H1) and (H4), f can be as well estimated using deconvolution as follows:

(19) f (3) m (x) = 1 2π πm -πm e -iux 1 N N j=1 e iuA j,T du = 1 πN N j=1 sin(πm(A j,T -x)) A j,T -x .
This estimator corresponds to a kernel estimator as [START_REF] Ditlevsen | Mixed effects in stochastic differential equation models[END_REF] with K(x) = sin(πx)/(πx) (not fulfilling [START_REF] Donnet | Parametric inference for mixed models defined by stochastic differential equations[END_REF]) and bandwidth h = 1/m and is also a possible estimator of f in the special case b = σ. The risk is then bounded as follows.

Proposition 4. Consider the estimator given by ( 19) under (H1) and (H4). We have

(20) E( f (3) m -f 2 ) ≤ 1 2π |u|≥πm |f * (u)| 2 du + π 2 c 2 1 3c 4 0 m 3 T + m N . If b = σ, (21)
E( f (3) m -f 2 ) ≤ 1 2π |u|≥πm |f * (u)| 2 du + 1 8πT 2 πm -πm |u| 4 |f * (u)| 2 du + m N .
Compared with Proposition 1, the bound in ( 20) is analogous to [START_REF] Donnet | EM algorithm coupled with particle filter for maximum likelihood parameter estimation of stochastic differential mixed-effects models[END_REF]. In the special case b = σ, the risk bound of f (1) h is unchanged. On the contrary, the bound of f (3) m in ( 21) contains an additional bias term (middle term in the r.h.s. of ( 21)) which allows to weaken the constraints on T . For instance, if |u| 4 |f * (u)| 2 du < +∞, which is true if f ∈ C(a, L) for a ≥ 2, the new term is negligible as soon as T ≥ √ N . Thus, if the regularity index of f is larger than 2, rates of density estimation without noise can be attained. If we have no knowledge at all on the behaviour of |f * (u)| 2 , we can only use that |f * (u)| ≤ 1 and get the order m 5 /T 2 which is better than m 3 /T .

Additive random effect in the drift

We study in this section model (3), under (H1).

3.1.

Large time strategy. Relying on Equation (3), we set:

Z j,T := X j (T ) -X j (0) - T 0 b(X j (s))ds T = φ j + 1 T T 0 σ(X j (s))dW j (s),
and define the estimator

(22) f (4) h (x) = 1 N N j=1 K h (x -Z j,T ),
where

K h (x) = (1/h)K(x/h), K is C 2 , integrable, with K(u)du = 1 and (23) K 2 (u)du < +∞, (K") 2 (u)du < +∞.

The risk of f (4)

h is slightly different than the risk of f (1) h of Section 2.

Proposition 5. Consider estimator f (4) h given by ( 22) under (H1) and ( 23). Assume moreover that σ

2 (x) ≤ σ 2 1 , ∀x ∈ R. Then (24) E( f (4) h -f 2 ) ≤ 2 f -f h 2 + K 2 N h + cσ 4 1 K" 2 1 T 2 h 5 where c is a numerical constant.
The discussion of Corollary 1 can be done here. Consider that f belongs to the Nikol'ski class N (β, L) and that the kernel has order ℓ = ⌊β⌋ with |x| β |K(x)|dx < +∞. If we impose that h ∝ N -1/(2β+1) , we get a rate proportional to N -2β/(2β+1) plus a term of order N 5/(2β+1) /T 2 . If T 2 ≥ N (2β+5)/(2β+1) , then N 5/(2β+1) /T 2 ≤ N -2β/(2β+1) . This constraint holds for any nonnegative β if T ≥ N 5/2 . Note that this constraint is weaker than for f (1) h and the result holds under weaker assumptions for the model.

3.2. Fixed step strategy using increments. The method using increments with a sampling interval ∆ is possible here. Using (3) yields,

Y j,k := X j (t k ) -X j (t k-1 ) - t k t k-1 b(X j (s))ds t k -t k-1 = φ j + 1 t k -t k-1 t k t k-1 σ(X j (s))dW j (s)
where t k = k∆, k = 1, . . . , K, T = K∆. Let:

f (5) m (x) = 1 2π πm -πm e -iux ∆ N T N j=1 K k=1 e iuY j,k e u 2 2∆ 2 R t k t k-1 σ 2 (X j (s))ds du.
Note that, in the above formula, we use a "stochastic deconvolution" to build the estimator. The following risk decomposition holds.

Proposition 6. Consider estimator f (5) m given above under (H1). Assume moreover that

σ 2 (x) ≤ σ 2 1 , ∀x ∈ R. Then E( f (5) m -f 2 ) ≤ f -f m 2 + ∆ πN T πm -πm e u 2 σ 2 1 /∆ du + m N .
The same discussion as after Proposition 2 can be done here. As above, we can define another class of estimators depending on a cutoff parameter τ and build an adaptive choice of it. Let

fτ (x) = 1 2π √ τ - √ τ e -iux 1 N N j=1 e iuZ j,τ e u 2 2τ 2 R τ 0 σ 2 (X j (s))ds du, Z j,τ := X j (τ ) -X j (0) - τ 0 b(X j (s))ds τ .
We define

(25) Γτ = max 1≤k≤N 2 fk∧τ -fk 2 -pen(k) + with pen(k) = κ log(N ) √ k N , Let (26) τ = arg min 1≤τ ≤N 2 Γτ + pen(τ ) .
Theorem 2. Assume (H1) and T (N ) = N 2 . Assume moreover that σ 2 (x) ≤ σ 2 1 , ∀x ∈ R. Then there exists a numerical constant κ such that:

(27) E( fτ -f 2 ≤ C inf 1≤τ ≤N 2 ( f τ -f 2 + pen(τ )) + C ′ N ,
where C is a numerical constant and C ′ is a constant.

The additional factor log(N ) in the penalty pen is due to the fact that σ(x) is not constant. It implies a logarithmic loss in the rate. More precisely, if f ∈ C(a, L), the infimum in the right-hand-side of ( 27) is of order (N/ log(N )) -2a/(2a+1) instead of N -2a/(2a+1) .

If σ(x) is constant, this factor log(N ) in the penalty is not needed.

Remark 1. The study of Section 3 can be done under weaker assumptions on σ including the case where a random effect is present in the diffusion coefficient too, say σ(x, ψ) provided that sup t≥0 E(σ 2 (X j (t), ψ j ) = σ 2 1 < +∞.

Discretizations

In practice, only discrete time observations of (X j (t)) are available. We investigate now this context and assume that for a small sampling interval δ, the observations are (X j (kδ)) 1≤k≤n , with T = nδ. In estimators of Sections 2 and 3, we replace all ordinary and stochastic integrals based on the continuous time observations by their usual discrete approximations using the discrete data. This procedure is classical. To avoid unnecessary repetitions, we only deal with the estimators built in Section 3.

We replace the Z j,T 's by the usual approximation:

Ẑj,T = 1 T X j (T ) -X j (0) -δ n k=1 b(X j ((k -1)δ)) ,
and define the estimator based on discrete observations:

f (4) h,δ (x) = 1 N N j=1 K h x -Ẑj,T .
Analogously, for τ ≤ T , set:

Ẑj,τ = 1 τ   X j (δ[τ /δ]) -X j (0) -δ [τ /δ] k=1 b(X j ((k -1)δ))   , fτ,δ (x) = 1 2π √ τ - √ τ e -iux 1 N N j=1 e iu Ẑj,τ e u 2 2τ 2 P [τ /δ] k=1 δσ 2 (X j ((k-1)δ)) du.
The following proposition holds:

Proposition 7. Assume (H1). Assume moreover that E(φ 2 j ) < +∞, σ 2 (x) ≤ σ 2 1 for all x and sup s≥0 E[b 2 (X j (s))] < +∞.
(1) Let the kernel satisfy ( 7) and ( 23). Then,

(28) E( f (4) h,δ -f 2 ) ≤ 2 f -f h 2 + K 2 N h + c σ 4 1 K" 2 1 T 2 h 5 + C δ h 3 K ′ 2
, where c, C are constants not depending on T, h, δ.

(2) For 0 < δ < 1 ≤ τ ,

(29) E( fτ,δ -f 2 ) ≤ C( f τ -f 2 + √ τ ( 1 N + δ)),
where C is a constant not depending on τ, δ.

Let us give some comments on the assumption sup s≥0 E[b 2 (X j (s))] < +∞. It holds obviously if the drift b is bounded. Otherwise, it may be linked with the existence of a stationary distribution for model [START_REF] Comte | Nonparametric estimation of random effects densities in linear mixedeffects model[END_REF], but it will be checked directly in the examples below. Repeating all steps of Theorem 2, we can define a data-driven choice τδ of τ and prove that the corresponding estimator fτ δ ,δ satisfies an inequality analogous to (27).

Numerical simulation results.

In this section, we consider three models of multiplicative or additive form.

Model [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF]. Geometric Brownian motion:

(30) dX j (t) = X j (t)(φ j dt + σdW j (t)), X j (0) = x j > 0.
Then, X j (t) = exp(Y j (t)) with dY j (t) = (φ jσ 2 /2)dt + σdW j (t).

For this model, we use exact simulations for N = 50 and T = 300 or N = 200 and T = 300, with σ = 1, x j = 1. The distributions of the random effects are: Gamma Γ(3, 0.1), where 3 is the shape parameter and 0.1 the scale parameter, mixed gamma 0.3 Γ(3, 0.1) + 0.7 Γ(15, 0.1), and Gaussian N (1, 0.2 2 ).

The computation of the kernel estimator is fast as we only need the terminal variable U j (T ), which has an explicit form for model [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF]. The bandwidth is selected by the R-function density, first column gives 25 estimated densities with N = 50, T = 300 for the kernel estimator. In the last two columns, we have N = 200, T = 300, for the kernel (column 2) and the deconvolution (last column) estimators. Clearly, increasing N improves the result as expected. Note that the methods work well even for T /N not very large. Looking at the last two columns, we see that the deconvolution method seems less biased but with a greater variability than the kernel method. Especially, for a bimodal distribution, the deconvolution methods works well, even better than when the individual parameter φ j are directly observed (dotted line). Nevertheless, the deconvolution method is more time consuming as we need to compute all the U j (τ ) for 1 ≤ τ ≤ T .

Model [START_REF] Comte | Penalized contrast estimator for adaptive density deconvolution[END_REF]. Ornstein-Uhlenbeck process with multiplicative random effect:

(31) dX j (t) = φ j X j (t)dt + σdW j (t), X j (0) = x j .
This model satisfies (H1)-(H2) but not (H4). Nevertheless, it is a classical model. We use the explicit solution:

X j (t) = x j e φ j t + σe φ j t t 0 e -φ j s dW j (s).

We use exact simulations of the X j (kδ) with δ = 0.01, for N = 200 and T = 400, with σ = 1 and x j = 0. The distributions of the opposite of the random effect -φ j are: log-normal from normal distribution N (1, 0.1 2 ), mixed gamma 0.3 Γ(3, 0.08)+0.7 Γ(15, 0.07), and mixed Gaussian 0.5 N (0.5, 0.25 2 ) + 0.5 N (1.8, 0.25 2 ).

To compute the kernel estimator f (1) h , we replace U j (T ) and V j (T ) by their usual discrete approximations using discrete data X j (kδ). The method works well as illustrated by Figure 2 where 25 estimated densities are plotted. Indeed, the graphs are comparable to those obtained from a sample of directly observed φ j (bold dotted curves). Again, T /N need not be very large.

Model (3):

Ornstein-Uhlenbeck process with additive random effect:

(32) dX j (t) = (φ j -X j (t))dt + σdW j (t), X j (0) = x j .
log-normal mixed gamma mixed Gaussian 3), additive Ornstein-Uhlenbeck process with distribution of the random effects: log-normal (first column), mixed gamma (second column), and mixed Gaussian (third column). Estimated density for 25 independent samples in thin green: kernel estimator ( f (4) h,δ , first line) and deconvolution estimator ( fτ δ ,δ , second line). True density in bold black. Estimated density for one sample of (φ j )'s directly observed with standard kernel density estimator in bold dotted red. N = 200, T = 400.

The solution is:

X j (t) = x j e -t + φ j (1 -e -t ) + σe -t t 0 e s dW j (s).
Hence,

E(X 2 j (t)|φ j = ϕ) ≤ 3(x j ) 2 + ϕ 2 + σ 2 2t .
Provided that Eφ 2 j < +∞, E(X 2 j (t)) ≤ 3((x j ) 2 + Eφ 2 j + σ 2 ). All assumptions of Section 3 are satisfied. For this model, we use exact simulations of the X j (kδ) with δ = 1 for N = 200 and T = 400, with σ = 1 and x j = 0. The distributions of the random effects are: lognormal log N (1, 0.1 2 ), mixed gamma 0.4 Γ(3, 0.08) + 0.6 Γ(30, 0.035), and mixed Gaussian 0.5 N (0.5, 0.25 2 ) + 0.5 N (1.8, 0.25 2 ).

The computation of the kernel estimator f (4) h,δ only requires the discretized terminal variable Ẑj,T while the deconvolution-type estimator fτ δ ,δ requires all the variables Ẑj,τ for 1 ≤ τ ≤ N 2 , see Proposition 7. The deconvolution-type estimator fτ δ ,δ is computed with constant κ calibrated through preliminary simulation experiments to κ = 10.

Figure 3 (25 estimated densities) illustrates the kernel method (first line) and the deconvolution method (second line). The deconvolution method has a great variability but captures well the two modes of the bimodal distributions. On the contrary, the variability band for the kernel estimators is thiner but seems to miss the height of the two modes.

Model properties.

In this section, we detail some properties of model [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF], give some interpretations of our assumptions and look at links between model ( 2) and (3). 6.1. Existence and uniqueness of strong solutions. We consider N real valued stochastic processes (X j (t), t ≥ 0), j = 1, . . . , N , with dynamics ruled by (1) where φ j are R d -valued. Consider the assumptions (A) The functions (x, ϕ) → b(x, ϕ) and (x, ϕ) → σ(x, ϕ) are C 1 on R × R d , and such that:

∃K > 0, ∀(x, ϕ) ∈ R × R d , |b(x, ϕ)| + |σ(x, ϕ)| ≤ K(1 + |x| + |ϕ|). (B) The functions (x, ϕ) → b(x, ϕ) and (x, ϕ) → σ(x, ϕ) are C 1 on R × R d ,
and such that:

|b ′ x (x, ϕ)| + |σ ′ x (x, ϕ)| ≤ L(ϕ), |b ′ ϕ (x, ϕ)| + |σ ′ ϕ (x, ϕ)| ≤ L(ϕ)(1 + |x|),
with ϕ → L(ϕ) continuous.

Under (A) or (B), for all ϕ, and all x j ∈ R, the stochastic differential equation

(33) d X ϕ,x j j (t) = b(X ϕ,x j j (t), ϕ)dt + σ(X ϕ,x j j (t), ϕ) dW j (t), X ϕ,x j j (0) = x j
admits a unique strong solution process (X ϕ,x j j (t), t ≥ 0) adapted to the filtration (F t , t ≥ 0). Let C(R + , R) be the space of continuous functions on R + , endowed with the Borel σ-field associated with the topology of uniform convergence on compact sets. The distribution of X ϕ,x j j (.) is uniquely defined on this space. Now, we can state: Proposition 8.

• Under (A) or (B), for j = 1, . . . , N , equation (1) admits a unique solution process (X j (t), t ≥ 0), adapted to the filtration (F t = σ(φ j , W j (s), s ≤ t, j = 1, . . . , N ), t ≥ 0) such that the joint process ((X j (t), φ j ), t ≥ 0) is Markov and there exists a measurable functional

(34) (ϕ, x, w . ) ∈ (R d × R × C(R + , R)) → F . (ϕ, x, w . ) ∈ C(R + , R)
such that X j (.) = F . (φ j , x j , W j (.)).

Given that φ i = ϕ, the conditional distribution of (X j (t), t ≥ 0) is identical to the distribution of the process (X ϕ,x j j (t), t ≥ 0). The processes (X j (t), t ≥ 0), j = 1, . . . , N are independent.

• Under (A), if moreover, for k ≥ 1, E(|φ i | 2k ) < ∞, then, for all T > 0, sup t∈[0,T ] E[X j (t)] 2k < ∞.

Assumption (H4

). Let us discuss some implications of Assumption (H4). Under (H4), the function b 2 /σ 2 is non null. If we combine (H4) with the assumption that 0 < σ 2 0 ≤ σ 2 (x) ≤ σ 2 1 , ∀x ∈ R, then, we can assume that both b and σ are positive and satisfy:

(H5) (i) 0 < c 0 ≤ b(x)/σ(x) ≤ c 1 , (ii) 0 < σ 0 ≤ σ(x) ≤ σ 1 , ∀x ∈ R.
Proposition 9. Let X i be given by ( 2), X j (0) = x j , j = 1, . . . , N under (H5). Then, the process X i is transient in the sense that:

P( lim t→+∞ X i (t) = +∞) = P(φ i > 0), P( lim t→+∞ X i (t) = -∞) = P(φ i < 0).
6.3. Links between the multiplicative and the additive model. In some cases, the multiplicative model can be transformed into an additive model by a change of function.

Proposition 10. Assume that the drift function in model ( 2) is C 1 and satisfies, for some positive constant b 0 , b(x) ≥ b 0 for all x, and set

F (x) = x 0 du/b(u). Then the process Y j (t) = F (X j (t)) satisfies dY j (t) = (φ j - 1 2 b ′ • F -1 (Y j (t)) b 2 • F -1 (Y j (t)) )dt + σ • F -1 (Y j (t)) b • F -1 (Y j (t)) dW j (t)
The result follows from a standard application of the Itô formula. Consequently, (2) can be treated as (3) after the change of function when b(•) is lower bounded b y a positive constant.

Concluding remarks

In this paper, we consider N i.i.d. processes (X j (t), t ∈ [0, T ]), j = 1, . . . , N , where the dynamics of X j is described by a SDE including a random effect φ j . The nonparametric density estimation of φ j is investigated in two specific models ((2)-( 3)) where the diffusion coefficient does not contain the random effect. The drift term is either multiplicative (b(x, ϕ) = ϕb(x)) or additive (b(x, ϕ) = φ + b(x)). We build kernel and adaptive deconvolution-type estimators and study their L 2 -risk as both N and T = T (N ) tend to infinity. Under the theoretical condition that T (N )/N tends to infinity rather fast, the estimators attain the usual optimal rates. Nevertheless, numerical simulation results on several models show that, in practice, T (N )/N needs not be very large. Extensions of the present work to models with a more general drift are on going work.

E( f - f (1) h 2 ) = f -E( f (1) h ) 2 + E( f (1) h -E( f (1) h ) 2 ) ≤ 2 f -f h 2 + 2 f h -E( f (1) h ) 2 + E( f (1) h -E( f (1) h ) 2 ). (35)
The last term is the usual variance term and is bounded by

(36) E( f (1) h -E( f (1) h ) 2 ) = 1 N Var(K h (x -A 1,T ))dx ≤ K 2 N h .
The first term is a usual bias term. The specific term is the middle one. We note that f h (x) = E(K h (xφ 1 )) and we apply the Taylor Formula with integral remainder:

K h (x -A 1,T ) -K h (x -φ 1 ) = (φ 1 -A 1,T ) h 2 1 0 K ′ 1 h (x -φ 1 + u(φ 1 -A 1,T )) du which yields f h -E( f (1) h ) 2 = (E(K h (x -A 1,T ) -K h (x -φ 1 ))) 2 dx ≤ E (K h (x -A 1,T ) -K h (x -φ 1 )) 2 dx = E (K h (x -A 1,T ) -K h (x -φ 1 )) 2 dx ≤ 1 h 3 (K ′ ) 2 (y)dyE[(φ 1 -A 1,T ) 2 ] = 1 h 3 (K ′ ) 2 (y)dyE M 1 (T ) V 1 (T ) 2 ≤ 1 h 3 (K ′ ) 2 (y)dy c 2 1 T c 4 0 since under (H4), E (M 1 (T )) 2 (V 1 (T )) 2 ≤ 1 T 2 c 4 0 E[(M 1 (T )) 2 ] ≤ 1 T c 2 1 c 4 0 . 8.2. Proof of Proposition 2. Since E( f (2) m ) = f m , we have (37) E( f -f (2) m 2 ) = f -f m 2 + E( f m -f (2) m 2 ). As f m - f (2) m 2 = (2π) -1 f * m -( f (2) m ) * 2
, and the random vectors (U j,k ) 1≤k≤K are independent and identically distributed for j = 1, . . . , N (see ( 11)), we get

E( f m -f (2) m 2 ) = 1 2π πm -πm E   1 N K N j=1 K k=1
(e iuU j,k e u 2 /∆ -E(e iuU j,k e u 2 /(2∆) ))

2   du = 1 2πN πm -πm Var 1 K K k=1 e iuU 1,k e u 2 /(2∆) du = 1 2πN K 2 πm -πm K k,k ′ =1 cov(e iuU 1,k , e iuU 1,k ′ )e u 2 /∆ du. ( 38
)
Looking at [START_REF] Karatzas | Brownian motion and stochastic calculus[END_REF], we can see that, for

k = k ′ , cov(e iuU 1,k , e iuU 1,k ′ ) = 1 -|f * (u)| 2 e -u 2 /∆ and for k = k ′ , cov(e iuU 1,k , e iuU 1,k ′ ) = (1 -|f * (u)| 2 )e -u 2 /∆ .
Plugging this in (38) yields ( 39)

E( f m -f (2) m 2 ) ≤ ∆(m) N K + m n where ∆(m) = 1 2π πm -πm e u 2 /∆ du.
Plugging (39) into (37) gives [START_REF] Nie | Strong consistency of the maximum likelihood estimator in generalized linear and nonlinear mixed-effects models[END_REF].

We now bound ∆(m). First

∆(m) = √ ∆ π πm/ √ ∆ 0 e v 2 dv ≤ √ ∆ π e + πm/ √ ∆ 1 e v 2 dv .
Integrating by part and using that v → e v 2 /v 2 is nondecreasing for v ≥ 1 imply

πm/ √ ∆ 1 e v 2 dv = e v 2 2v πm/ √ ∆ 1 + 1 2 πm/ √ ∆ 1 e v 2 dv v 2 ≤ √ ∆ πm e π 2 m 2 /∆ - e 2 .
Therefore we get

∆(m) ≤ √ ∆ π √ ∆ πm e π 2 m 2 /∆ + e 2 .
As

f * m = f * 1 [-πm,πm] , f -f m 2 = (2π) -1 |u|≥πm |f * (u)| 2 du
, which ends the proof of ( 13) and thus of Proposition 2. 2 8.3. Proof of Proposition 3. The proof is close to the one of Proposition 2 and simpler. The following decomposition holds:

fτ -f 2 = fτ -f τ 2 + f τ -f 2 .
Then,

E( fτ -f τ 2 ) = 1 2πN √ τ - √ τ
Var e iuA 1,τ e u 2 /(2τ ) du, where

Var(e iuA 1,τ ) = 1 -|f * (u)| 2 e -u 2 /τ . Hence, (40)

E( fτ -f τ 2 ) = 1 2πN √ τ - √ τ (1 -|f * (u)| 2 e -u 2 /τ )e u 2 /τ du ≤ √ τ πN 1 0 e v 2 dv.
8.4. Proof of Theorem 1. We have the successive decompositions fτ -

f 2 ≤ 3( fτ -fτ∧τ 2 + fτ∧τ -fτ 2 + fτ -f 2 ) and fτ -fτ∧τ 2 = fτ -fτ 2 1 I τ ≥τ = fτ -fτ 2 -pen(τ ) 1 I τ ≥τ + pen(τ )1 I τ ≥τ ≤ Γτ + pen(τ ) fτ∧τ -fτ 2 = fτ -fτ 2 1 I τ ≤τ = fτ -fτ 2 -pen(τ ) 1 I τ ≤τ + pen(τ )1 I τ ≤τ ≤ Γτ + pen(τ ).
This yields fτf 2 ≤ 3( Γτ + pen(τ ) + Γτ + pen(τ ) + fτf 2 )

≤ 6( Γτ + pen(τ )) + 3 fτ -f 2 .
Then, for k ≥ τ :

fk -fτ 2 ≤ 3( fτ -f τ 2 + fk -f k 2 + f k -f τ 2 )
Note that

f k -f τ 2 = 1 2π f * k -f * τ 2 = 1 2π √ τ ≤|u|≤ √ k |f * (u)| 2 du ≤ 1 2π |u|≥ √ τ |f * (u)| 2 du = f -f τ 2 .
Moreover, as the Fourier transforms of fτf τ and f -

f τ have disjoint supports, fτ -f 2 = fτ -f τ 2 + f τ -f 2 . It follows that, for k ≥ τ : fk -fτ 2 ≤ 3( fk -f k 2 + fτ -f 2 ),
which in turn implies that Γτ ≤ 3 max

τ ≤k≤N 2 ( fk -f k 2 -pen(k)/3) + 3 fτ -f 2 .
Therefore, gathering inequalities, we get fτf 2 ≤ 18 max

τ ≤k≤N 2 ( fk -f k 2 -pen(k)/3) + 6 fτ -f 2 + 6pen(τ )
and

E( fτ -f 2 ) ≤ 18 N 2 k=τ E( fk -f k 2 -pen(k)/3) + 6E( fτ -f 2 ) + 6pen(τ ) ≤ 18 N 2 k=τ E( fk -f k 2 -pen(k)/3) + 6 f τ -f 2 +6 1 + 1 0 e v 2 dv π √ τ N + 6pen(τ ). Consequently E( fτ -f 2 ) ≤ 6 f τ -f 2 + 6 1 + 1 + 1 0 e v 2 dv πκ pen(τ ) + 18 N 2 k=τ E( fk -f k 2 - pen(k) 3
).

Now, we use the Talagrand Inequality to prove the Lemma Lemma 1. Under the Assumptions of Theorem 1

N 2 k=τ E( fk -f k 2 -pen(k)/3) ≤ C N .
This and Proposition 3 gives the result of Theorem 1. 2 Proof of Lemma 1. We have that fk -

f k 2 = sup t∈S √ k , t =1 |ν N (t)| 2 where S m = {t ∈ L 2 , supp(t * ) = [-m, m]} and ν N (t) = 1 2π t * , ( fk -f k ) * = 1 2πN N j=1 √ k - √ k t * (-u)(e iuA j,k e u 2 /(2k) -f * (u))du.
Note that:

ν N (t) = 1 N N j=1 (ψ t (A j,k ) -E(ψ t (A j,k ))) with ψ t (x) = 1 2π √ k - √ k t * (-u)e iux e u 2 /(2k) du.
The class of functions {ψ t , t ∈ S √ k , t = 1} is uniformly bounded as follows.

ψ t ∞ ≤ 1 √ 2π t √ k - √ k e u 2 /k du 1/2 ≤ e/π k 1/4 := M.
By inequality (40), we get that:

E sup t∈S √ k , t =1 |ν N (t)| 2 = E( fk -f k 2 ) ≤ c √ k/N := H 2 , with c = 1 0 e v 2 dv/π. At last, let us determine the bound v. 4π 2 sup t∈S √ k , t =1 Varψ t (A j,k ) ≤ sup t∈S √ k , t =1 E t * (u)t * (-v)e i(u-v)A j,k e (u 2 +v 2 )/(2k) dudv ≤ sup t∈S √ k , t =1 t * (u)t * (-v)f * (u -v)e (u 2 +v 2 +(u-v) 2 )/(2k) dudv ≤ √ k - √ k √ k - √ k |f * (u -v)| 2 e 3(u 2 +v 2 )/k dudv 1/2 ≤ 2 √ ke 6 2 √ k -2 √ k |f * (z)| 2 dz 1/2 ≤ 2 √ πe 3 k 1/4 f := 4π 2 v
Thus applying the Talagrand Inequality yields with ǫ 2 = 1/2 that:

E sup t∈S √ k , t =1 |ν N (t)| 2 -4H 2 ≤ C 1 k 1/4 N e -C 2 k 1/4 + k 1/2 N 2 e -C 3 √ N ,
where C 1 , C 2 , C 3 are positive constants. Thus for pen(k)/3 = 4H 2 , we get

N 2 k=τ E( fk -f k 2 -pen(k)/3) = N 2 k=τ E sup t∈S √ k , t =1 |ν N (t)| 2 -2H 2 ≤ C 1 N N 2 k=τ k 1/4 e -C 2 k 1/4 + e -C 3 k 1/4 ≤ C 4 N .
We can choose the constant κ such that κ ≥ 12c. 2 8.5. Proof of Proposition 4. We have

E( f (3) m -f 2 ) = E( f (3) m -E( f (3) m ) + E( f (3) m ) -f m + f m -f 2 ) = f m -f 2 + E( f (3) m ) -f m 2 + E( f (3) m -E( f (3) m ) 2 ) The term f m -f 2 = 1 2π |u|≥πm |f * (u)| 2 du is the usual bias term. The additional bias term E( f (3) m ) -f m 2 is bounded by E( f (3) m ) -f m 2 = 1 2π πm -πm | 1 N N j=1 E(e iuA j,T ) -E(e iuφ j ) | 2 du = 1 2π πm -πm | E(e iuA 1,T -e iuφ 1 ) | 2 du
By the Taylor formula,

e iuA 1,T -e iuφ 1 = e iuφ 1 iu M 1 (T ) V 1 (T ) e iuξ j,T .
Thus

E( f (3) m ) -f m 2 ≤ 1 2π πm -πm u 2 E M 1 (T ) V 1 (T ) 2 du
Then, under (H4),

E (M j (T )) 2 (V j (T )) 2 ≤ 1 T 2 c 4 0 E[(M j (T )) 2 ] ≤ 1 T c 2 1 c 4 0 .
We obtain

E( f (3) m ) -f m 2 ≤ π 2 c 2 1 3c 4
0 m 3 T Using the Parseval equality, the variance term can be bounded as follows

E( f (3) m -E( f (3) m ) 2 ) = 1 2π E   πm -πm | 1 N N j=1 (e iuA j,T -E(e iuA j,T ))| 2 du   = 1 2π πm -πm V ar   1 N N j=1 e iuA j,T   du ≤ m N
Finally, we obtain the bound [START_REF] Revuz | Continuous martingales and Brownian motion[END_REF].

If b = σ, E( f (3) m (x)) = 1 2π πm -πm e -iux f * (u)e -u 2 /(2T ) du.
The risk of the estimator, using repeatedly Parseval equality, is

E( f -f (3) m 2 ) = f -f m 2 + f m -E( f (3) m ) 2 + E( f (3) m -E( f (3) m ) 2 ) ≤ f -f m 2 + 1 2π πm -πm |f * (u)| 2 |e -u 2 /(2T ) -1| 2 du + m N ≤ 1 2π |u|≥πm |f * (u)| 2 du + 1 8πT 2 πm -πm |u| 4 |f * (u)| 2 du + m N , (
-E( f (4) h ) 2 , still considering that f h (x) = E(K h (x -φ 1 )
). We apply the Taylor Formula with integral remainder:

K h (x -Z 1,T ) -K h (x -φ 1 ) = (φ 1 -Z 1,T ) h 2 K ′ x -φ 1 h + (φ 1 -Z 1,T ) 2 h 3 1 0 (1 -u)K" 1 h (x -φ 1 + u(φ 1 -Z 1,T )) du.
Recall that φ 1 is F 0 -measurable, thus E((φ 1 -Z 1,T )K ′ ( x-φ 1 h )) = 0, and we obtain, using successively the Cauchy Schwarz and the Burkholder-Davis-Gundy inequalities,

f h -E( f (4) h ) 2 = (E(K h (x -Z 1,T ) -K (x -φ 1 ))) 2 dx ≤ E (K h (x -Z 1,T ) -K h (x -φ 1 )) 2 dx = E (K h (x -Z 1,T ) -K h (x -φ 1 )) 2 dx ≤ 1 3h 5 (K") 2 (y)dyE    T 0 σ(X 1 (s))dW (s) 4 T 4    ≤ c h 5 T 4 K" 2 E T 0 σ 2 (X 1 (s))ds 2 ≤ c h 5 T 2 K" 2 σ 4 1 .
8.7. Proof of Proposition 6. We know that exp(U t -U t /2) is a martingale if U is a martingale and E(e U t/2 ) < ∞. As σ 2 (x) ≤ σ 2 1 for all x, this implies that

exp i u ∆ k∆ (k-1)∆ σ(X j (s))dW (s) + u 2 2∆ 2 k∆ (k-1)∆ σ 2 (X j (s))ds
has conditional expectation 1 given F (k-1)∆ . Since e iuφ j is F (k-1)∆ -measurable, we obtain that

E e iuY j,k e u 2 2∆ 2 R k∆ (k-1)∆ σ 2 (X j (s))ds = E e iuφ j E e i u ∆ R k∆ (k-1)∆ σ(X j (s))dW (s)+ u 2 2∆ 2 R k∆ (k-1)∆ σ 2 (X j (s))ds |F (k-1)∆ = E(e iuφ 1 ) = f * (u).
Therefore E( f (5) m (x)) = f m (x) and we decompose the risk in the two usual terms

(42) E( f (5) m -f 2 ) = f -f m 2 + E( f (5) m -f m 2 ).
Then we have to compute

E( f (5) m -f m 2 ) = 1 2π E   πm -πm 1 N K N j=1 K k=1 (e iuY j,k e u 2 2∆ 2 R k∆ (k-1)∆ σ 2 (X j (s))ds -f * (u)) 2 du   .
Then using that the terms under expectation are centered, we compute a variance with independent variables with respect to the index j:

E( f (5) m -f m 2 ) = 1 2πN πm -πm E   1 K K k=1 (e iuY 1,k e u 2 2∆ 2 R k∆ (k-1)∆ σ 2 (X 1 (s))ds -f * (u)) 2   du.
Let us denote by M k = k∆ (k-1)∆ σ(X 1 (s))dW (s) and M k = k∆ (k-1)∆ σ 2 (X 1 (s))ds. Now, for k < ℓ, by conditioning as follows:

cov e iu(φ 1 +M k )+u 2 M k /2 , e iu(φ 1 +M ℓ )+u 2 M ℓ /2 = E e iuM k +u 2 M k /2 E(e iuM ℓ +u 2 M ℓ /2 |F (ℓ-1)∆ ) -|f * (u)| 2 we get that cov e iu(φ 1 +M k )+u 2 M k /2 , e iu(φ 1 +M ℓ )+u 2 M ℓ /2 = 1 -|f * (u)| 2 .
We obtain

E( f (5) m -f m 2 ) = 1 2πN πm -πm 1 K 2   K k=1 (e u 2 ∆ 2 R k∆ (k-1)∆ σ 2 (X 1 (s))ds -|f * (u)| 2 ) + k =ℓ (1 -|f * (u)| 2 )   du ≤ 1 2πN K πm -πm e u 2 σ 2 1 ∆ 2 du + m N .
Gathering the last inequality and (42) gives the result of Proposition 6. 2 8.8. Proof of Theorem 2. The proof follows the steps of Theorem 1. We prove that

E( fτ -f 2 ) ≤ f -f τ 2 + √ τ πN 1 0 e σ 2 1 v 2 dv.
Then we obtain

E( fτ -f 2 ) ≤ 6 f τ -f 2 + 6 1 + 1 + 1 0 e σ 2 1 v 2 dv πκ pen(τ ) + 18 N 2 k=τ E( fk -f k 2 - pen(k) 3
).

Then we have to prove

E   N 2 k=τ E( fk -f k 2 - pen(k) 3 )   ≤ C ′ N .
To this end, we define

νN (t) = 1 N N j=1 (ψ t ( Ãj,k ) -E(ψ t ( Ãj,k ))) with Ãj,k = (Z j,k , k 0 σ 2 (X j (s))ds)
and

ψ t (x, y) = 1 2π √ k - √ k t * (-u)e iux+ u 2 2k 2 y du 1 I 0≤y≤σ 2 1 k . We find ψ t ∞ ≤ M := e σ 2 1 /πk 1/4 , sup t∈S √ k , t =1 |ν N (t)| 2 ≤ c√ k/N := H2 with c = 1 0 e σ 2 1 v 2 dv/π.
The difference with the proof of Theorem 1 is that, here, we get nothing better than ṽ := N H2 . This is why we take ǫ 2 = 3 log(N )/K 1 in the Talagrand Inequality. Then, choosing pen(k)/3 ≥ (1 + 2ǫ 2 ) H2 gives the result and the value of the constant κ. 2 8.9. Proof of Proposition 7. For the fisrt point, the proof is very close to the one of Proposition 5. The only difference is that the bias term includes an additional term due to the approximation of Z j,T by Ẑj,T . We have:

K h (x -Ẑj,T ) -K h (x -Z j,T ) = Z j,T -Ẑj,T h 2 1 0 K ′ ( x -Ẑj,T + u(Z j,T -Ẑj,T ) h )du.
Using the Cauchy-Schwarz inequality, we get:

dx E(K h (x -Ẑj,T ) -K h (x -Z j,T )) 2 ≤ E(Z j,T -Ẑj,T ) 2 h 3 (K ′ (y)) 2 dy.
It remains to study

Z j,T -Ẑj,T = 1 T n k=1 kδ (k-1)δ (b(X j (s)) -b(X j ((k -1)δ)))ds.
Using again the Cauchy-Schwarz inequality and the fact that b is Lipschitz, say with constant L, yields:

E(Z j,T -Ẑj,T ) 2 ≤ L 2 T n k=1 kδ (k-1)δ (X j (s) -X j ((k -1)δ)) 2 ds. As X j (s) -X j ((k -1)δ) = s (k-1)δ (φ j + b(X j (u)) du + s (k-1)δ σ(X j (u))dW j (u), we obtain: E (X j (s) -X j ((k -1)δ)) 2 ≤ 4δ 2 (Eφ 2 j + sup s≥0 E[b 2 (X j (s))] + 2δσ 2 1 .
Thus, E(Z j,T -Ẑj,T ) 2 ≤ Cδ for some constant C which depends neither on T nor on δ.

Second, we have:

E( fτ,δ -f 2 ) ≤ 2E( fτ,δ -fτ 2 ) + 2E( fτ -f 2 ).
Thus, we only deal with the additional term:

E( fτ,δ -fτ 2 ) ≤ 1 2π √ τ - √ τ E|e iu Ẑ1,τ + u 2 2τ 2 P [τ /δ] k=1 δσ 2 (X 1 ((k-1)δ)) -e iuZ 1,τ + u 2 2τ 2 R τ 0 σ 2 (X 1 (s)ds | 2 du.
For δ < 1 ≤ τ , we can prove as above:

E(Z 1,τ -Ẑ1,τ ) 2 + 1 τ 2 E( [τ /δ] k=1 δσ 2 (X 1 ((k -1)δ)) - τ 0 σ 2 (X 1 (s))ds) 2 ≤ Cδ
for some constant C which depends neither on τ nor on δ. Therefore,

E|e iu Ẑ1,τ + u 2 2τ 2 P [τ /δ] k=1 δσ 2 (X 1 ((k-1)δ))) -e iuZ 1,τ + u 2 2τ 2 R τ 0 σ 2 (X 1 (s))ds | 2 ≤ Cδ(e u 2 σ 2 1 /τ + u 4 4τ 2 e 2u 2 σ 2 1 /τ ),
which, integrating with respect to u, gives the result. 2 8.10. Proof of Proposition 8. . Consider the two-dimensional SDE:

dX j (t) = b(X j (t), φ j (t))dt + σ(X j (t), φ j (t))dW i (t), X j (0) = x j , dφ j (t) = 0, φ i (0) = φ j .
This clarifies the Markov property of the joint process (X j (t), φ j ) once we have proved existence and unicity of a strong solution. Moreover, the random effect φ j thus appears as an unobserved initial condition.

• Assumption (A) standardly implies that the above two-dimensional SDE admits a unique strong solution and that there exists a functional F such that X j (.) = F . (φ j , x j , W j (.))

where

F . : R d × R × C(R + , R) → C(R + , R
) is measurable (see e.g. Karatzas and Shreve (1997) p.310). The joint process ((X j (t), φ j (t) ≡ φ j ), t ≥ 0) is Markov. By the Markov property, for all ϕ, x j , the conditional distribution of (X j (t), φ j ), t ≥ 0) given φ j = ϕ is the distribution of X ϕ,x j j (.) = F . (ϕ, x j , W j (.)).

As (φ j , W j (.)) are independent, the processes (X j (.)) are independent. As (φ j , x j ) is the initial condition, the moment result follows.

• Assumption (A) does not cover the case of (2). This is why we also consider (B). Under (B), we proceed in several steps which are classically used to prove regularity w.r.t. an initial condition. Under (B), for all ϕ, equation (33) admits a unique strong solution. Therefore, there exists a measurable functional

(43) (x, w . ) ∈ R × C(R + , R) → F . (ϕ, x, w . ) ∈ C(R + , R)
such that X ϕ,x j j (.) = F . (ϕ, x j , W j ) is the unique strong solution of (33). Moreover, as the initial condition x j is deterministic, it holds that, for all integer k ≥ 1 and all T > 0,

E sup t∈[0,T ] (X ϕ,x j j (t)) 2k < +∞.
We now prove that (43) is measurable as a function of (ϕ, x, w.).

Step 1 Let H be a compact subset of R d , we prove that for all x j ∈ R and all T > 0, where ϕ → L(k, ϕ) is continuous. To ease notations, let us set, X(t) = X ϕ,x j j (t), x = x j . We proceed as in Ikeda and Watanabe (1981,Theorem 2.4, p.163). Using the Hölder inequality, the Burholder-Davis-Gundy inequality, we get We have: For the proof, we omit the index j in the notations. Consider a fixed value ϕ > 0 and introduce the process Y 0 (t) given by: dY 0 (t) = ϕσ 0 c 0 dt + σ(Y 0 (t))dW (t), Y 0 (0) = x.

X ϕ,x j j (t) -X ϕ ′ ,x j
As ϕ > 0, ϕb(x) ≥ ϕσ 0 c 0 for all x. By the comparison theorem for one-dimensional SDEs (see e.g. Ikeda and Watanabe 1981, p.352), it holds that X ϕ,x (t) ≥ Y 0 (t) for all t ≥ 0. Thus, ≥ ϕσ 0 c 0 , hence lim t→+∞ X ϕ,x (t) = +∞. Analogously, for ϕ < 0, P(lim t→+∞ X ϕ,x (t) = -∞) = 1. For ϕ = 0, X 0,x (.) is a martingale such that < X 0,x > +∞ = +∞ 0 σ(X 0,x (s))ds = +∞ a.s.. Hence, P(lim inf t→+∞ X 0,x (t) = -∞, lim sup t→+∞ X 0,x (t) = +∞) = 1. Noting that By standard density arguments, this result can be extended to the case where F is a unit ball of a linear normed space, after checking that f → ν n (ψ) is continuous and F contains a countable dense family.

X

  g. Ditlevsen and De Gaetano, 2005, Overgaard et al., 2005, Donnet and Samson, 2008, Picchini et al., 2010, Picchini and Ditlevsen, 2011, Donnet and Samson, 2010, Delattre et al., 2012).

Figure 1 .Figure 2 .

 12 Figure 1. Model (1), Geometric Brownian Motion with distribution of the random effects: Gamma (first line), mixed gamma (second line), and Gaussian (third line). Estimated density for 25 independent samples in thin green: kernel estimator (first two columns) and deconvolution estimator (last column). True density in bold black. Estimated density for one sample of (φ j )'s directly observed with standard kernel density estimator in bold dotted red.

Figure 3 .

 3 Figure 3. Model (3), additive Ornstein-Uhlenbeck process with distribution of the random effects: log-normal (first column), mixed gamma (second column), and mixed Gaussian (third column). Estimated density for 25 independent samples in thin green: kernel estimator ( f (4) h,δ , first line) and deconvolution estimator ( fτ δ ,δ , second line). True density in bold black. Estimated density for one sample of (φ j )'s directly observed with standard kernel density estimator in bold dotted red. N = 200, T = 400.

8 . Proofs 8 . 1 .

 881 Proof of Proposition 1. Classically,

  ) 2k := C(T, H) < +∞.By equation (33), for all ϕ ∈ H and t ≤ T , , ϕ)dW j (s) By (B), we have, for all ϕ, x and k ≥ 1,b 2k (x, ϕ) + σ 2k (x, ϕ) ≤ L(k, ϕ) (1 + x 2k ),

E 0 ( 1 +

 01 sup u≤t (X(u)) 2k ≤ C(k)(x 2k + L T (k, ϕ) t E sup u≤s (X(u)) 2k )ds,where C(k) is a constant and ϕ → L T (k, ϕ) is continuous. We conclude by the Gronwall lemma that, for all t ≤ T ,E sup u≤t (X(u)) 2k ≤ C T (k, ϕ),where ϕ → C T (k, ϕ) is continuous. Thus, we get (44).Step 2 We prove that (45) ϕ → X ϕ,x j j (.)is continuous as a function R d → C(R + , R).Let H be a compact convex subset of R d and set, for ϕ, ϕ ′ ∈ H,S t (ϕ, ϕ ′ ) = E sup u≤t X ϕ,x j j (u) -X ϕ ′ ,x j j (u)2k.

8 . 11 .

 811 , ϕ)b(X ϕ ′ ,x j j (s), ϕ ′ ) ds + t 0 σ(X ϕ,x j j (s), ϕ)σ(X ϕ ′ ,x j j (s), ϕ ′ ) dW j (s).By (B), we have fors ≤ T , |b(X ϕ,x j j (s), ϕ)b(X ϕ ′ ,x j j (s), ϕ ′ )| + |σ(X ϕ,x j j (s), ϕ)σ(X ϕ ′ ,x j j (s), ϕ ′ )| ≤ L(ϕ) |X ϕ,x j j (s) -X ϕ ′ ,x j j (s)| + |ϕϕ ′ |(1 + sup u≤T |X ϕ ′ ,x j j (u)|)Now, we proceed as in Step 1. We use the Hölder inequality, the Burkholder-Davis-Gundy inequality, the result (44) of Step 1 and finally the Gronwall lemma to obtain that, for all t ≤ T ,S t (ϕ, ϕ ′ ) ≤ |ϕϕ ′ | 2k C T (k, H),for (another) constant C T (k, H). Now, choosing 2k > d, we can conclude by the Kolmogorov continuity of sample paths theorems (see e.g. Revuz and Yor, 1991, Theorem 2.1, p.25), thatω T (δ) = sup ϕ,ϕ ′ ∈H sup t≤T |X ϕ,x j j (t) -X ϕ ′ ,x j j (t)|tends to 0 a.s. as δ tends to 0. This gives (45).Step 3 As (43) is measurable for all ϕ, Step 2 standardly implies that(ϕ, x, w . ) ∈ R d × R × C(R + , R) → F . (ϕ, x, w . ) ∈ C(R + , R)is measurable. The conclusion of Proposition 8 follows. Proof of Proposition 9.

2 8. 12 .ǫ 2 - 1 ,

 21221 ) = +∞|φ = ϕ) = P( lim t→+∞ X ϕ,x (t) = +∞) = 1 (ϕ>0) , we get that P( lim t→+∞ X(t) = +∞) = P(φ > 0). The other property follows analogously. Talagrand Inequality. The following result follows from the Talagrand concentration inequality given in Klein and Rio (2005) and arguments in Birgé and Massart (1998) (see the proof of their Corollary 2 page 354). Lemma 2. (Talagrand Inequality) Let Y 1 , . . . , Y n be independent random variables, let ν n,Y(ψ) = (1/n) n i=1 [ψ(Y i ) -E(ψ(Y i ))] and let F be a countable class of uniformly bounded measurable functions. Then for ǫ 2 > 0E sup ψ∈F |ν n,Y (ψ)| 2 -2(1 + 2ǫ 2 )K 1 = 1/6,and sup ψ∈F ψ ∞ ≤ M, E sup ψ∈F |ν n,Y (ψ)| ≤ H, sup ψ∈F 1 n n k=1 Var(ψ(Y k )) ≤ v.

  41) which gives the second bound of Proposition 4. 2 8.6. Proof of Proposition 5. Equations (35) and (36) hold with f (4) h instead of f (1) h and Z 1,T instead of A 1,T . Now we study f h