Fadoua Balabdaoui

Cécile Durot
email: cecile.durot@gmail.com

Francois ¸koladjo

March

On asymptotics of the discrete convex LSE of a pmf

Keywords: convex, least squares, nonparametric estimation, pmf, shape-constraints

In this article, we derive the weak limiting distribution of the least squares estimator (LSE) of a convex probability mass function (pmf) with a finite support. We show that it can be defined via a certain convex projection of a Gaussian vector. Furthermore, samples of any given size from this limit distribution can be generated using an efficient Dykstra-like algorithm.

Introduction

Non-parametric estimation under a shape constraint of a density on a given sub-interval of R, has attracted considerable attention over the past decades. Typical shape constraints are monotonicity, convexity, log-concavity. Typical estimators are the maximum likelihood estimator (MLE) and the least-squares estimator (LSE). Both of them are obtained by minimization of a given criterion over the set of all densities that satisfy the considered shape constraint. Even if the MLE and LSE uniquely exist, no closed form is available for these estimators so a key step is to provide a precise characterization of the estimators as well as an algorithm for practical implementation. [START_REF] Grenander | On the theory of mortality measurement[END_REF] first gives such a characterization for the MLE of a monotone density, and the pointwise weak convergence of the MLE is derived in Prakasa [START_REF] Rao | Estimation of a unimodal density[END_REF]. The estimator can easily be implemented using the Pool Adjacent Violators Algorithm as described in [START_REF] Barlow | Statistical inference under order restrictions: The theory and application of isotonic regression[END_REF]. Both characterization and pointwise weak convergence of a convex density estimator on the half-real line are investigated in [START_REF] Groeneboom | Estimation of a convex function: characterizations and asymptotic theory[END_REF], and practical implementation is discussed in [START_REF] Groeneboom | The support reduction algorithm for computing non-parametric function estimates in mixture models[END_REF]. The MLE of a log-concave density is characterized in [START_REF] Dümbgen | Maximum likelihood estimation of a logconcave density and its distribution function: Basic properties and uniform consistency[END_REF] while its pointwise weak convergence is studied in [START_REF] Balabdaoui | Limit distribution theory for maximum likelihood estimation of a log-concave density[END_REF]. Algorithmic aspects are treated in [START_REF] Dümbgen | logcondens: Computations related to univariate log-concave density estimation[END_REF]. In the aforementioned continuous case of estimating a density under a shape constraint over a given sub-interval of R, the limit behavior of global distances between the estimator and the true density has been investigated. We refer to [START_REF] Kulikov | Asymptotic normality of the lk-error of the grenander estimator[END_REF] and [START_REF] Durot | The limit distribution of the l ∞ -error of grenander-type estimators[END_REF] for the limit distribution of the L pdistance and the supremum-distance respectively, in the case of a monotone density. The rate of uniform convergence of the log-concave MLE on compacts is given in [START_REF] Dümbgen | Maximum likelihood estimation of a logconcave density and its distribution function: Basic properties and uniform consistency[END_REF].

More recently, attention has been given to estimation of a discrete probability mass function (pmf) under a shape constraint. Similar to the continuous case, no closed form is available for shape constrained estimators of a pmf so one needs a precise characterization. Such characterizations are given in [START_REF] Jankowski | Estimation of a discrete monotone distribution[END_REF], [START_REF] Balabdaoui | Asymoptic distribution of the discrete log-concave mle and some applications[END_REF] and [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] for the monotone, log-concave and convex cases respectively. In the convex case, [START_REF] Balabdaoui | Marshall lemma in discrete convex estimation[END_REF] show that the same Marshall Lemma proved in the continuous case by [START_REF] Dümbgen | Marshalls lemma for convex density estimation[END_REF] continues to hold in the discrete case, that is, we have F n -F ∞ ≤ 2 F n -F ∞ for any distribution function F on N with a convex pmf, and F n and F n are the cumulative distribution function of the LSE and the empirical distribution function respectively. In contrast to the continuous case, the natural way to investigate the global limit behavior of the estimator is to compute the limit distribution of the whole process p n -p 0 , where p n is the considered estimator and p 0 is the true pmf. This approach was first considered by [START_REF] Jankowski | Estimation of a discrete monotone distribution[END_REF] in the case of a monotone pmf on N, and by [START_REF] Balabdaoui | Asymoptic distribution of the discrete log-concave mle and some applications[END_REF] in the case of a log-concave pmf. The discrete case totally differs from the continuous case. In particular, the rate of convergence is typically √ n (where n denotes the sample size) in the discrete case whereas it is of smaller order in the continuous case. Characterization and rate of convergence of the LSE of a convex pmf are given in [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] together with an algorithm, but the limit distribution of the LSE remains unknown. One of the aims of this paper is to fill this gap.

To be more precise, let X 1 , . . . , X n be i.i.d. from an unknown discrete pmf p 0 whose support takes the form N ∩ [κ, ∞) = {κ, κ + 1, . . . , } or N ∩ [κ, S] = {κ, κ + 1, . . . , S} for some integers S > κ ≥ 0. Here, κ is assumed to be known whereas S is unknown. Assuming that p 0 is convex on N ∩ [κ, ∞), we are interested in the limiting behavior of the LSE of p 0 . The case κ = 1 is of a particular interest in [START_REF] Durot | Nonparametric species richness estimation under convexity constraint[END_REF], where the problem of estimating the total number N of species in a given area is investigated under the convexity constraint. Note that we focus here on the LSE. Studying the limit behavior of the MLE is out of the scope of the article: it would require specific arguments since the MLE may differ from the LSE in our setup, see Section 2.2 below.

The limiting distribution of the LSE is described as a piecewise convex projection of a Gaussian process, where the pieces are connected to the points of strict convexity of p 0 . The Gaussian process involved in the limiting distribution depends on p 0 as well. Hence, we provide an estimator of the limiting distribution that involves consistent estimators of the points of strict convexity of p 0 . We provide an algorithm for simulating the limiting distribution of the LSE as well as the approximating distribution. This amounts to simulating (many times) a Gaussian process and its piecewise convex projection, which is obtained by minimizing the least-squares criterion over the intersection of closed convex cones. Our algorithm combines two previous algorithms. The first one is implemented in the function conreg of the package cobs for R; see Ng and Maechler (2007) for a full description. It is used to minimize the least squares criterion over the closed convex cone of discrete convex functions on a given interval. Then, the iterative algorithm by [START_REF] Dykstra | An algorithm for restricted least squares regression[END_REF] is used to minimize the criterion over the intersection of closed convex cones. We use our algorithm to illustrate our main results via a simulation study.

The paper is organized as follows. In Section 2, we recall the characterization of the LSE obtained in [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] and we derive the √ n-rate of convergence. We show that the MLE and the LSE may differ, and that the MLE may be non unique. In addition, we prove that any knot (that is, a point of strict convexity) of the true pmf is also (almost surely, for large enough n) a knot of the LSE. This allows us to characterize the support of the LSE in the case when the true pmf has a finite support. Section 3 is devoted to the weak convergence of the LSE. The limit distribution is computed in the general case and we investigate how the limit distribution simplifies in some specific cases, such as pmf having consecutive knots. Simulations are reported in Section 4. We first investigate on a few examples whether the knots of the estimator include all true knots when the sample size is finite. Then, we illustrate the convergence of the distribution of the estimator to the limit distribution. All proofs are postponed to Section 5.

Basic properties of the convex LSE

Let X 1 , . . . , X n be i.i.d. from a pmf p 0 with support included in N. Denoting by κ the left end-point of the support, we assume that p 0 is convex on N ∩ [κ, ∞). This means that the support of p 0 takes either the form N ∩ [κ, ∞) = {κ, κ + 1, . . . , } or N ∩ [κ, S] = {κ, κ + 1, . . . , S} for some integers S > κ ≥ 0, and that ∆p 0 (k) ≥ 0 for all integers k > κ, where for a sequence p = {p(k), k ∈ N},

∆p(k) = p(k + 1) -2p(k) + p(k -1), k ∈ N\{0} (2.1)
denotes the corresponding discrete Laplacian. Here, κ is assumed to be known whereas S is unknown. The assumption S > κ is made in order to avoid the uninteresting situation of having to deal with a Dirac distribution. Since convexity is preserved under translation, we can assume without loss of generality that κ = 0: in case κ > 0, the characterization as well as the asymptotic results for the LSE of the true convex pmf can be easily deduced from the ones established below using the simple fact that the support pmf of X i -κ admits 0 as its left endpoint. Thus, in the sequel we restrict our attention to the case of a convex pmf p 0 on N with an unknown support.

Based on the sample X 1 , . . . , X n , we consider the empirical pmf p n , that is

p n (j) = 1 n n i=1 1 {X i =j} , j ∈ N.
(2.2)

Characterization of the convex LSE

We are mainly interested in the asymptotics of p n , the LSE of p 0 defined as the unique minimizer of the criterion

Φ n (p) = 1 2 j∈N (p n (j) -p(j)) 2
over p ∈ C, the set of all convex sequences p on N with a finite 2 -norm, that is, the set of all sequences p = {p(k), k ∈ N} satisfying

∞ k=0 |p(k)| 2 < ∞ and ∆p(k) ≥ 0 for all integers k ≥ 1. (2.3)
Note that any p ∈ C is non-negative and non-increasing. Existence and uniqueness of p n follows from the Hilbert projection Theorem, see [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF], Section 2.1.

It follows from Theorem 1 of [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] that p n also minimizes Φ n over the set of pmf's in C. In particular, p n is a proper pmf.This fact is rather convenient because it means that in order to compute the estimator, we can minimize the criterion Φ n over C rather than over the more constrained set of pmf's in C. This also allows us to use simpler algorithms and has the advantage of giving more flexibility when deriving the characterizing Fenchel conditions for p n . As it is the case in many shape constrained problems, such characterization proves to be crucial in understanding the limiting behavior of the relevant estimator; see for example [START_REF] Groeneboom | Estimation of a convex function: characterizations and asymptotic theory[END_REF], [START_REF] Jankowski | Estimation of a discrete monotone distribution[END_REF] and [START_REF] Balabdaoui | Asymoptic distribution of the discrete log-concave mle and some applications[END_REF]. Thus, for the sake of completeness, we give in Proposition 2.1 below the Fenchel characterization proved in [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF], Lemma 2. For an arbitrary sequence p = {p(k), k ∈ N}, we denote

F p (k) = k j=0 p(j) (2.4)
for all k ∈ N with F p (-1) = 0, and we define

H p (z) = z-1 k=0 F p (k) (2.5) for all z ∈ N with the convention H p (0) = 0. Moreover, a point k ≥ 1 in the support of a convex p ∈ C is called a knot of p if ∆p(k) > 0.
Proposition 2.1. The convex pmf p n is the LSE if and only if

H pn (z) ≥ H pn (z), for all z ∈ N = H pn (z), if z is a knot of p n . (2.6)
Note that a typographical error occurring in [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF], Lemma 2, is now corrected. More precisely, if p ∈ C satisfies H p (z) ≥ H pn (z) with equality at any knot of p (instead of p n as stated in [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF]) then p = p n . Some remarks are in order. The characterization above can be seen as the discrete version of the one given by [START_REF] Groeneboom | Estimation of a convex function: characterizations and asymptotic theory[END_REF] for the LSE of a convex density with respect to Lebesgue measure. However, some of the consequences implied by the characterization of the continuous LSE do not hold true in our discrete case, due to the lack of the notion of differentiability in the discrete case. For instance, if F pn and F pn denote the continuous versions of the quantities defined above then F pn (s) = F pn (s) at any knot s of the estimator; see Corollary 2.1 of [START_REF] Groeneboom | Estimation of a convex function: characterizations and asymptotic theory[END_REF]. This equality cannot be expected to hold true for the discrete convex LSE in the general case. In fact, by definition of H pn and H pn in the discrete case,

F pn (z) = H pn (z + 1) -H pn (z) and F pn (z) = H pn (z + 1) -H pn (z)
for all z ∈ N, so it follows from (2.6) that the equality is replaced instead by the two inequalities F pn (s) ≥ F pn (s) and F pn (s -1) ≤ F pn (s -1). The equality F pn (s) = F pn (s) can only hold if, in addition to the equality H pn (s) = H pn (s), one also has H pn (s + 1) = H pn (s + 1). This happens for instance in situations where p n has two consecutive knots at s and s + 1.

The convex MLE compared to the LSE

Recall that the MLE of p 0 is defined as the maximizer (if it exists) of the criterion

n (p) = i≥0 p n (i) log[p(i)]
over the set of all convex pmf's p on N, where p n denotes the empirical pmf. The following proposition shows that the LSE of a convex pmf may differ from the MLE. Moreover it proves that the MLE may be non unique in this discrete setting. To see this, we consider a sample of only one observation X 1 from a convex pmf p 0 . We describe the LSE and the MLE in terms of the triangular distributions defined as follows. Given j ∈ N \ {0}, consider the triangular pmf with support on {0, . . . , j -1} given by

T j (i) = 2(j -i) + j(j + 1) , (2.7)
where as usual, x + = max{x, 0} for all real numbers x.

Proposition 2.2. The convex LSE of p 0 based on the single observation X 1 > 0 is uniquely defined by T 3X 1 +1 whereas the MLE exists but is non unique: the log-likelihood 1 is maximized at T 2X 1 , T 2X 1 +1 and at every mixture of those two triangular distributions.

These results differ from those obtained by Groeneboom et al. (2001a) in the continuous case. In that case, the MLE is uniquely defined.

Tightness of the convex LSE

Next we consider almost sure consistency of p n in all distances r . Here as usual, p r denotes the r -norm of a sequence p = {p(k), k ∈ N}:

p r = ( ∞ k=0 |p(k)| r ) 1/r if r ∈ N\{0} sup k∈N |p(k)| if r = ∞.
Proposition 2.3. For any integer r ∈ [2, ∞], with probability one we have that

lim n→∞ p n -p 0 r = 0.
The following proposition is an easy consequence of Proposition 2.3.

Proposition 2.4. If s > 0 is a knot of p 0 , then with probability one, there exists n 0 such that for all n ≥ n 0 , s is a knot of p n .

We finish this section by recalling boundedness in probability of √ n( p n -p 0 ) and the implied boundedness for the associated "integral " processes. Note that boundedness in probability of √ n( p n -p 0 ) is much weaker than tightness. However, these properties are equivalent in the case where √ n( p n -p 0 ) is identically equal to zero after a certain range. We will use this equivalence later on under the assumption that the true convex pmf has a finite support.

Theorem 2.5. If p n is the convex LSE of the true pmf p 0 , then

√ n p n -p 0 ∞ = O p (1). (2.8) Furthermore, if p 0 has a finite support, then √ n F pn -F p 0 ∞ = O p (1), and √ n H pn -H p 0 ∞ = O p (1).
(2.9)

The support of the convex LSE

In the sequel, we will assume that p 0 has a finite support and we denote the support by {0, 1, . . . , S}. Note that S + 1 is the last knot of p 0 in the sense that ∆p 0 (S + 1) = p 0 (S) > 0 and ∆p 0 (k) = 0 for all integers k > S + 1. Under this assumption, it is natural to ask whether the support of p n is also finite. It turns out that the answer is affirmative as we now show in the following proposition.

Proposition 2.6. If p 0 is supported on {0, . . . , S} with S ∈ N\{0}, then with probability one there exists n 0 such that for all n ≥ n 0 , the support of the LSE p n is either {0, . . . , S} or {0, . . . , S + 1}.

Asymptotics of the convex LSE

In this section, we derive the weak limit of the LSE when the true distribution is supported on a finite set. The limit distribution is given in Section 3.1 in the most general setting where we do not make any additional assumption on the structure of the knots of the true pmf p 0 . It turns out that the limit distribution of the estimator involves all knots of p 0 , see Theorem 3.2 below. This seems to contrast with the continuous case, where the limiting distribution of the LSE at a point depends only on the density (and its derivatives) of the observations at this point, so that the limit distribution is "localized". Moreover, the limit distribution of the MLE of a discrete log-concave pmf given in [START_REF] Balabdaoui | Asymoptic distribution of the discrete log-concave mle and some applications[END_REF] is localized in some sense. For these reasons, we provide in Section 3.3 below general characterizing conditions for such localizations to occur for the LSE of a discrete convex pmf. This comprehensive study of possible localization led us to find an error in the proof of Proposition 3 in [START_REF] Balabdaoui | Asymoptic distribution of the discrete log-concave mle and some applications[END_REF], and to conclude that the limit distribution given in Theorem 5 of that paper is not correct.

The general setting

Assume that p 0 is supported on {0, . . . , S} with an unknown integer S > 0. From Proposition 2.6, it follows that with probability one, p n is supported on {0, . . . , S + 1} provided that n is sufficiently large. Therefore, we consider the weak limit of p n on {0, . . . , S + 1}. To this end, first consider the weak limit of the empirical pmf p n . By standard results, the empirical process √ n(F pn -F p 0 ) weakly converges to U(F p 0 ) on {0, . . . , S + 1}, where U denotes a standard Brownian bridge from (0, 0) to (1, 0). With

W(k) = U(F p 0 (k)) -U(F p 0 (k -1)) (3.10)
for all integers k = 0, . . . , S + 1, we conclude that √ n(p n -p 0 ) weakly converges to W on {0, . . . , S + 1}. Since p n is the minimizer of a criterion that involves p n , its weak limit depends on W. Theorem 3.2 below proves that the limiting distribution of the LSE is that of the minimizer (whose existence is proved in Theorem 3.1 below) of the criterion

Φ(g) = 1 2 S+1 k=0 (g(k) -W(k)) 2 (3.11)
over the set C(K) that we define now. Let K be the set of all interior knots of p 0 , that is all knots of p 0 in {1, . . . , S}. If p 0 does not have any interior knot (which means that p 0 is triangular pmf) then K = ∅. Associated with K is the following class of functions

C(K) = g = (g(0), . . . , g(S +1)) ∈ R S+2 such that ∆g(k) ≥ 0 for all k ∈ {1, . . . , S}\K
This means that g ∈ C(K) is convex between two successive knots of p 0 . Define

H(z) = z-1 k=0 U(F p 0 (k)) = z-1 k=0 k j=0 W(j) (3.12)
for all z ∈ N, with H(0) = 0. Then, we have the following theorem.

Theorem 3.1. The criterion (3.11) admits a unique minimizer g over C(K). Furthermore, with probability one, an element g ∈ C(K) is the minimizer if and only if the process H defined on {0, . . . , S + 2} by

H(x) = x-1 k=0 k j=0 g(j) (3.13)
with the convention that H(0) = 0, satisfies

H(x)      ≥ H(x), for all x ∈ {0, . . . , S + 2} = H(x), if x ∈ K ∪ {0, S + 1, S + 2} or x ∈ {1, . . . , S}\K satisfies ∆ g(x) > 0.
(3.14)

In the above theorem, note that it is implicit that the minimizer g is actually g(ω). We are now ready to establish the weak convergence of p n . For x ∈ {0, . . . , S + 1} define

G(x) = x k=0 g(k) = H(x + 1) -H(x).
(3.15)

Theorem 3.2. If p n is the convex LSE of the true pmf p 0 with support {0, . . . , S}, then we have the joint weak convergence on {0, . . . , S + 1} as n → ∞:

  √ n(H pn -H p 0 ) √ n(F pn -F p 0 ) √ n( p n -p 0 )   ⇒   H G g   .

Estimating the limiting distribution

The asymptotic distribution g derived in Theorem 3.2 depends on the projection of a Gaussian vector, whose dispersion matrix depends on p 0 , onto a set C(K) that depends on the interior knots of p 0 . Since those knots are typically unknown, the asymptotic distribution cannot be directly used to build confidence intervals. Below, we fill the gap between the theoretical result of Theorem 3.2 and the practical problem of building such intervals. This is achieved via the construction of a random vector g n that weakly converges to g without depending on some unknown parameter. The distribution of g n can easily be approximated via Monte-Carlo simulations, and can therefore be used to approximate the distribution of √ n( p n -p 0 ).

To define g n , let S n = max{X 1 , . . . , X n }, and g n be the centered Gaussian vector of dimension S n + 2 and whose dispersion matrix is given by Γ n , the (S n + 2) × (S n + 2) matrix with component (i+1, j +1) equal to p n (i)(1-p n (i)) for all i = j and -p n (i)p n (j) for all i = j, with i, j = 0, . . . , S n + 1. Since g n converges weakly to W, by analogy to how g was defined, it is natural to define g n as the minimizer of

Φ n (g) = 1 2 Sn+1 k=0 (g(k) -g n (k)) 2 (3.16) over a set C n that approaches C(K) as n → ∞.
We feel it is useful to point out that defining C n as the set of all functions (g(0), . . . , g(S n + 1)) ∈ R Sn+2 such that ∆g(k) ≥ 0 for all k ∈ {1, . . . , S n } with possible exception at the knots of p n does not work. Indeed, due to the fact that (with probability one, asymptotically) the set of all knots of p n contains the set of all knots of p 0 with typically a strict inclusion, the proposed set does not approaches C(K) as n → ∞. An appropriate choice for C n is given in the following theorem. In dealing with convergences, we view X 1 , . . . , X n as the first n terms of an infinite sequence (X i ) i∈N of i.i.d. random variables.

Theorem 3.3. Let (v n ) n∈N be a sequence of positive numbers that satisfy

lim n→∞ v n = 0 and lim n→∞ √ nv n = ∞.
(3.17)

Define g n as above and let g n be the minimizer of (3.16) over the set C n of all functions g = (g(0), . . . , g(S n + 1)) ∈ R Sn+2 such that ∆g(x) ≥ 0 for all x ∈ {1, . . . , S n } with possible exceptions at the points x that satisfy ∆ p n (x) > v n . Then, conditionally on (X i ) i∈N , the random vector g n converges in distribution to g in probability as n → ∞.

Remark 3.4. The meaning of the above convergence should be clarified: g n is a random vector in R Sn+2 whereas g is in R S+2 . But since P (S n ≤ S) = 1, the convergence in distribution has a full meaning once g n is identified with the (S + 2)-dimensional vector ( g n , 0, . . . , 0), where the number of null entries is exactly S -S n .

Remark 3.5. Note that in the inequality ∆ p n (x) > v n , p n can be replaced by p n . The arguments used to show Theorem 3.3 will remain almost unchanged since we can use the Central Limit Theorem. The same thing applies for the estimator Σ n , which can be defined by taking any consistent estimator of p 0 for the purpose of approaching the Gaussian distribution of W.

In practice, Theorem 3.3 can be used to simulate an approximation of the distribution of √ n( p n -p 0 ) as follows: once the empirical estimator has been computed from the observations X 1 , . . . , X n , compute Γ n and simulate B (a large positive integer) independent copies g n,1 , . . . , g n,B from a centered multivariate Gaussian distribution with dispersion matrix Γ n . Then, for j = 1, . . . , B, compute g n,j as the minimizer of the criterion (3.16) where g n is replaced by g n,j over the set C n as defined in Theorem 3.3. From Theorem 3.3, it follows that the empirical distribution of g n,j , j = 1, . . . , B approaches the limit distribution g of √ n( p n -p 0 ). As a consequence of Theorem 3.3, g n converges in distribution to g unconditionally. This fact is less useful for practical applications but easier to illustrate with simulations as shown below in Section 4.

Localization

It follows from Theorem 3.2 above that the limiting distribution of p n at a fixed point involves all knots of p 0 in the general case. This seems to contrast with the continuous case where the limiting distribution of the LSE is localized in the sense that it depends only on the true density (and its derivatives) at the fixed point. Hence, a natural question is whether the convex LSE could be also localized in the discrete case.

To draw a correct comparison between what happens in the discrete and continuous cases, one has to go back to the working assumptions under which the limiting distribution has been derived in the latter case. In [START_REF] Groeneboom | Estimation of a convex function: characterizations and asymptotic theory[END_REF] it is assumed that the true convex density f defined on [0, ∞) is twice continuously differentiable in a small neighborhood of a fixed point x 0 > 0 such that f (x 0 ) > 0. In particular, the density is strictly convex at x 0 . Under this assumption, the limiting distribution only depends on f (x 0 ) and f (x 0 ). In our Theorem 3.2 we do not consider any particular configuration for the knots of p 0 . For the sake of comparison, and if we translate for the moment strict convexity at a point s in the support of p 0 as having s to be a triple knot, that is s -1, s and s + 1 are successive knots of p 0 , then it follows from Proposition 2.4 and Proposition 2.1 that with probability one there exists n 0 large enough such that for all n ≥ n 0 H pn (s -1) = H pn (s -1), H pn (s) = H pn (s), and H pn (s + 1) = H pn (s + 1). This implies that p n (s) = p n (s) and the limiting distribution is simply that of the Gaussian random variable N (0, p 0 (s)(1 -p 0 (s))). In this case, the limit of the LSE at the point s is completely localized in the sense that it is not influenced by the remaining knots of p 0 . The identity p n (s) = p n (s) shows even the stronger fact that the localization is actually happening at the level of the estimator itself.

It is conceivable that other configurations lead to some form of localization of the weak limit. We provide below general characterizing conditions for such localizations to occur. In fact, the LSE and its weak limit get localized either to the left or right at any knot of p 0 that is either followed or preceded by another knot of p 0 . In such cases, the limit of the LSE can be described only in terms of knots of p 0 that are either to the left or right of that knot; see comments after Theorem 3.6 and Theorem 3.7. In the sequel, we shall use the same notation as in Section 3.1.

First, we consider the question of localizing "to the left" of a knot. This means that given an interior knot s of p 0 , we wonder whether the restriction to {0, . . . , s} of the limiting g is distributed as the minimizer of the left-localized criterion

Φ ≤s (g) = 1 2 s k=0 (g(k) -W(k)) 2
over the set

C ≤s (K) = g = (g(0), . . . , g(s)) ∈ R s+1 such that ∆g(k) ≥ 0 for all k ∈ {1, . . . , s -1}\K .
The following theorem provides a necessary and sufficient condition for the answer to be positive. It also gives a necessary and sufficient condition for the restriction of √ n( p n -p 0 ) to (0, . . . , s) to converge to the left-localized minimizer.

Theorem 3.6. Assume that the support of p 0 is finite. Then for an arbitrary interior knot s of p 0 , there exists a unique minimizer of Φ ≤s over C ≤s (K). The minimizer is equal to ( g(0), . . . , g(s)) if, and only if,

G(s) = U(F p 0 (s)).
(3.18)

Moreover, √ n( p n (0)-p 0 (0), . . . , p n (s)-p 0 (s)) converges in distribution to the minimizer of Φ ≤s over C ≤s (K) if, and only if,

F pn (s) = F pn (s) + o p (n -1/2 ). (3.19)
Consider the case where s is a double knot, in the sense that both s and s+1 are knots of p 0 . It follows from Proposition 2.4 together with the characterization in Proposition 2.1, that with probability one, both H pn (s) = H pn (s) and H pn (s + 1) = H pn (s + 1) hold true for sufficiently large n. Therefore, F pn (s) = F pn (s) with probability one for sufficiently large n, so that (3.19) holds and the limiting distribution is left-localized. Now, we consider the question of localizing "to the right" of a knot. This means that given an interior knot s of p 0 , we wonder whether the restriction to {s, . . . , S + 1} of the limiting g is distributed as the minimizer of the right-localized criterion

Φ ≥s (g) = 1 2 S+1 k=s (g(k) -W(k)) 2
over the set C ≥s (K) of all g = (g(s), . . . , g(S + 1)) ∈ R S-s such that ∆g(k) ≥ 0 for all k ∈ {s + 1, . . . , S}\K. A necessary and sufficient condition for the answer to be positive, is given below.

Theorem 3.7. Assume that the support of p 0 is finite. Then for an arbitrary interior knot s of p 0 , there exists a unique minimizer of Φ ≥s over C ≥s (K). The minimizer is equal to ( g(s), . . . , g(S + 1)) if, and only if,

G(s -1) = U(F p 0 (s -1)). (3.20)
Moreover, √ n( p n (s) -p 0 (s), . . . , p n (S + 1) -p 0 (S + 1)) converges in distribution to the minimizer of Φ ≥s over C ≥s (K) if, and only if,

F pn (s -1) = F pn (s -1) + o p (n -1/2 ).
(3.21)

Similar as above, (3.21) holds in the specific case where both s -1 and s are knots of p 0 .

4 Numerical aspects 4.1 A Dysktra algorithm for computing the asymptotic distribution

In monotone or concave/convex regression, active set methods are often proposed to compute the estimators; see for example [START_REF] Holm | Nonparametric regression with simple curve characteristics[END_REF] or Groeneboom et al. (2008a) for more recent work. One may also refer to [START_REF] Mammen | Nonparametric regression under qualitative smoothness assumptions[END_REF] for a more general method of non parametric regression under a shape constraint.

Here, we describe a simple algorithm that enables us to simulate a sample of any size from the asymptotic distribution g of √ n( p n -p 0 ) in the case where p 0 has a finite unknown support {0, . . . , S}, see Theorem 3.2. The algorithm also enables us to simulate a sample of any size from the conditional distribution of g n given in Theorem 3.3, see Remark 4.1 below. Let s 1 < . . . < s m be the interior knots of p 0 , and put s 0 = 0 and s m+1 = S + 1. Then, define C j = g = (g(0), . . . , g(S + 1)) ∈ R S+2 such that ∆g(k) ≥ 0 for all k ∈ {s j , . . . , s j+1 } for j = 0, . . . , m. By definition (see Theorem 3.1), g is the unique minimizer of the criterion Φ in (3.11) over C(K), which means that g can be viewed as the projection of W onto m j=0 C j . Since the C j 's are closed convex cones, the solution can be found using the algorithm of [START_REF] Dykstra | An algorithm for restricted least squares regression[END_REF] which proceeds by performing cyclic projections onto the convex cones C 0 , . . . , C m . Although details of the algorithm are given in [START_REF] Dykstra | An algorithm for restricted least squares regression[END_REF], we describe here how these projections are performed.

Set g (0) ≡ (W(0), W(1), . . . , W(S + 1)) and u (0) j = 0 for j = 0, ..., m. Then, for i ≥ 1, iterate the three following steps.

(1) Compute g (i) j , the projection of g

(i) j-1 -u (i-1) j onto C j for j = 0, . . . , m. (2) Set u (i) j ≡ g (i) j -g (i) j-1 -u (i-1) j .
(3) Set i = i + 1 and go to (1).

Granted that we know how to obtain the convex projections g (n) j , convergence of the above algorithm is a consequence of Theorem 3.1 of [START_REF] Dykstra | An algorithm for restricted least squares regression[END_REF]. The projection onto each cone C j , j = 0, . . . , m can be efficiently computed using the R function conreg available in the R package COBS; see NG and Maechler (2007) for more details. Now, for any fixed integer N ≥ 1, a sample of size N from the same distribution as ( g(0), . . . , g(S + 1)) can be done as follows: we generate a centered Gaussian vector (W 0 , . . . , W S ) whose dispersion matrix is given by Γ 0 , the (S + 1) × (S + 1) matrix with component (i + 1, j + 1) equal to p 0 (i)(1 -p 0 (i)) for all i = j and -p 0 (i)p 0 (j) for all i = j, with i, j = 0, . . . , S. This can be done using the R function rmvnorm available from the mvtnorm package. In the second step, we compute the piecewise convex projection of (W 0 , . . . , W S , 0) as described above, and the two steps are then repeated N times.

Remark 4.1. Let (v n ) be a sequence satisfying (3.17). Once X 1 , . . . , X n have been observed, a sample from the conditional distribution of g n given in Theorem 3.3 can be simulated by using the above algorithm with s 1 , . . . , s m replaced by the points x that satisfy ∆ p n (x) > v n , s m+1 = S n + 1 where we recall that S n = max{X 1 , . . . , X n }, and g (0) replaced by a centered Gaussian vector in R Sn+2 with dispersion matrix Γ n . Alternatively, according to Remark 3.5, the points s 1 , . . . , s m might be replaced by the points x that satisfy ∆p n (x) > v n .

How well the true knots are captured

Recall that Proposition 2.4 implies that with probability one, having enough large sample sizes ensures that a knot of the true pmf p 0 is also a knot of the LSE p n . However, the proposition does not indicate how large n should be. To gain some insight into the relationship between the size of the sample at hand and whether the knots of the estimator include all true knots, we have carried out a simulation study with samples of size n ∈ {50, 200, 800, 3200, 12800, 51200}. Given a simulated sample of size n from a distribution p 0 , the convex LSE p n was computed using the algorithm described in [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF].

To define the convex pmf's under which the samples were generated, we use the fact that a pmf p 0 is convex if and only if p 0 admits the mixture representation

p 0 = j≥1 π j T j (4.22)
where T j is the triangular distribution defined by (2.7), 0 ≤ π j ≤ 1 and j≥1 π j = 1, see Theorem 7 in [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF]. The representation is unique and the mixing weights are given by π j = j(j + 1) 2 ∆p(j)

for j ≥ 1. Note that in particular, j is a knot of p 0 if and only if π j > 0, and if the support of p 0 takes the form {0, . . . , S}, then π S+1 > 0 whereas π j = 0 for all j > S + 1.

In our simulations, the samples were generated from four convex pmf's that are all supported on {0, . . . , 10}. We give in Table 1 the values of the mixing weights π j , 1 ≤ j ≤ 11 for various pmf's p 0 that are denoted by p 1 , p 2 , p 3 and p 4 .

Figure 1 shows the process √ n(H pn -H pn ) together with the knots of the LSE p n and the true knots, for a sample of size n ∈ {50, 200} generated from p 3 . In these examples, it can be seen that in accordance with Proposition 2.1, H pn (z) ≥ H pn (z) with an equality at all knots z of p n . However, the sample sizes are not large enough to ensure that the knots of p n include all knots of the true pmf p 3 . Neither they are large enough to ensure that the support of p n is included in {0, . . . , S + 1} where S = 10 denotes the greatest point in the support of the true pmf; see Proposition 2.6. Figure 2 1. The diamond symbols depict the knots of the LSE p n computed based on the samples, whereas the bullets show the locations of the true knots. the mixing probabilities are π 11 = 1 and π j = 0 for all j = 11. Again, we observe that H pn (z) ≥ H pn (z) with an equality at all knots z of p n . In the case of a sample size n = 50, the knots of p n do not include the only true knot 11 and the support of p n is not included in {0, . . . , 11}. On the other hand, in the case of a larger sample size n = 200, the knots of p n include the only true knot 11 and p n is supported on {0, . . . , 11}.

Figures 1 and2 are not sufficient to gain full insight into the connection between the knots of p n and the true knots since only one sample is considered in each situation. Thus, for each considered sample size and distribution, we simulated independently 1000 samples to evaluate the probability that the knots of p n include all true knots. The probabilities are estimated by empirical frequencies. Results are reported in Table 2. As expected, the empirical frequency increases as n increases. It is typically larger in cases of true distributions with only few knots than in cases of true distributions with many knots.

Assessing the convergence of the convex LSE to the weak limit

To assess convergence of the estimation error to the right weak limit, consider F M to be respectively the empirical distributions of √ n( p n (j) -p 0 (j)) and g(j) for j ∈ {0, . . . , S + 1} based on M and M independent replications. Here, M and M will be chosen to be large. More explicitly, a sample of n independent random variables

X (i) 1 , . . . , X (i)
n is drawn from p 0 for each i = 0, . . . , M to form a sample of size M from the distribution of the estimation error. Note that this sample is multidimensional of dimension S + 1 hence our need to consider the marginal components of its distribution. Similarly, we draw a sample of size M from the distribution of weak limit using the algorithm described in Section 4.1. Define now

D n,M,M = sup 0≤j≤S+1 F (j) n,M -F (j) M ∞ .
We will use this random variable to assess the established convergence. This is based on the fact that it is expected to become small for large n. Since the "target " distributions are F (j) M , j = 0, . . . , S + 1, we choose M > M . Also, we store those obtained empirical distributions and re-use them while sampling many times from the estimation error. This enables us to obtain independent realizations from F (j) n,M while F (j) M , j = 0, . . . , S + 1 are fixed. To visualize the statistical summary of D n,M,M , the obtained outcomes are represented in the form of boxplots. Those were based on 100 replications of F (j) n,M , j = 0, . . . , S + 1. Here, M = 1000, M = 5000 and n ∈ {50, 100, 500, 1000, 5000, 10000, 50000}. In the simulations, we have taken the following true convex pmf's which are all supported on {0, . . . , 10}:

• The triangular pmf p 0 given by p 0 (i) = (11 -i) + /66 for i ∈ N.

• The convex pmf's p 1 , p 2 , p 3 , p 4 , p 5 , p 6 considered above in Section 4.2.

• The pmf, p 7 , of a truncated Geometric pmf with success probability equal to 1/2, given by p 7 (i) = (1 -2 -11 ) -1 2 -(i+1) for i ∈ {0, . . . , 10} and p 7 (i) = 0 otherwise.

Note that if a geometric pmf is always convex on N, this is not the case anymore after truncation. Indeed, convexity of the latter version holds true if and only if the waiting probability is ≤ 1/2. A simple proof of this fact can be found in Section 5.

Lemma 4.2. Let S be a positive integer and q ∈ (0, 1). The truncated Geometric distribution, defined by

p(i) = q i (1 -q) 1 -q S+1 , i ∈ {0, . . . , S}
and p(i) = 0 for all integers i ≥ S + 1, is convex if and anly if q ≤ 1/2.

To compute the uniform distance between F (j)

n,M and F (j)

M , we computed the maximal value of the absolute difference on a discretized grid {-4, -3.99, . . . , 3.99, 4} with a regular step equal to 0.01. The boxplots shown in Figures 3456give support to the asymptotic theory of the estimation error of the LSE in case the true pmf is one of the selected convex pmf's p 0 , p 1 , . . . , p 7 . Interestingly, weak convergence seems not to happen at the same speed. For the triangular pmf p 0 , the boxplots appear to stabilize for n ≥ 1000 whereas the obtained boxplots for the other distributions seem to indicate that convergence has not been yet attained. According to our numerical findings in Section 4.2, large sample sizes could be required for the estimator to be able to capture these knots. Thus, the slow convergence to the true limit for p i , 1 ≤ i ≤ 7 could be partially explained by the fact that those pmf's have all interior knots, as opposed the relatively fast convergence in the case of the triangular pmf p 0 which has none. We would like to note that all points in {1, . . . , 10} are interior knots of the truncated geometric pmf p 7 since it is strictly convex of its support. Hence, it is the pmf with the largest number of interior knots and also the one for which the convergence seems to be the slowest. Also, the limit g reduces in this particular case to W. Indeed, the empirical pmf p n is convex for large sample sizes (see Proposition 2.4) so that p n = p n , and hence √ n( p n -p 7 ) has the same limit distribution W as √ n(p n -p 7 ). Another way of viewing this is to note that the required convexity of the minimizer g between the knots becomes a superfluous constraint since it is always satisfied by the straight line connecting W at two given knots. This is true only in this case because all knots are consecutive.

We would like to finish this section by adding that it is of course impossible to have a precise statement about the speed of convergence in case the true convex pmf is known to be finitely supported. However, our numerical findings indicate that in applications such as construction of asymptotic confidence bands, one has to keep in mind that moderate sample sizes may not be enough to obtain good coverage. Finally, note that in our assessment we have assumed that the distribution of g is continuous. We believe this is true but we do not intend to prove it here as it is beyond the scope of this work.

Assessing how well the weak limit is estimated

We finish this numerical section by a small simulation study which aims at assessing how well the weak limit is estimated using out Theorem 3.3 above. Choosing the appropriate sequence (v n ) n among the infinitely many possibilities is not an easy task. One can easily see that if √ nv n converges too quickly or too slowly to ∞, then one may need very big sample sizes to be able to finally observe knots at all or to extract the true knots from the total set of knots of the estimator (we know that this set will include random ones). To see how the theory works in practice, we have carried out a simulation study with the four different convex pmf's, p 0 , p 1 , p 2 and p 3 , which were already defined above. We recall that these pmf's are all supported on {0, 1, . . . , 10} and have 0, 1, 2 and 3 interior knots respectively. To assess how well the (true) weak limit is estimated, we have computed the maximal value of the uniform distance between the marginal empirical distribution functions of the estimated weak limit as defined in 3.3 and that of the true weak limit based on M = 1000 and M = 5000 replications respectively. As in the section above, the uniform distance was approximated by computing the maximal value of the absolute difference on a discretized grid {-4, -3.99, . . . , 3.99, 4} with a regular step equal to 0.01. The sequence v n was chosen to be equal to worse that the selected v n in the sense that larger samples sizes were needed before good convergence to the true weak limit was observed. Based on 100 replications and for each sample size n ∈ {500, 1000, 5000, 10000, 50000}, we have computed the boxplots of the approximated uniform distance between the empirical distributions. The results are shown in Figure 7 for the considered pmf's p i , i = 0, 1, 2, 3. As expected, bigger sample sizes are needed to observe convergence to the true weak limit for pmf's with larger number of knots. It remains to know how the sequence (v n ) n , which somehow plays a role similar to bandwidth in the context of kernel estimation, should be chosen. Ideally, such a choice should be data-based, but we do not tackle this question in this present work and leave it to a future investigation.

Proofs

Proof of Proposition 2.2. Assume we observe only X 1 > 0. We will show that the likelihood is maximized at a triangular pmf. To see this, define the function f (x) = 2(x -X 1 )/(x(x + 1)) for x ∈ (X 1 , ∞). Then, the first derivative of f is given by f (x) = 2g(x)/(x 2 (x + 1) 2 ) where g(x) = -x 2 + 2xX 1 + X 1 . The function g is strictly concave on R with g(X 1 + 1) > 0 and g(x) → -∞ as x → ∞. This means that there exists a unique x 0 ∈ (X 1 + 1, ∞) such that g(x 0 ) = 0, g(x) > 0 for all x ∈ (X 1 + 1, x 0 ) and g(x) < 0 for all x ∈ (x 0 , ∞). Hence, f achieves its maximum over (X 1 + 1, ∞) at the unique point x 0 . This in turn implies that there exists an integer j 0 ≥ X 1 + 1 such that f (j 0 ) ≥ f (j) for all integers j ≥ X 1 + 1. Now, consider an arbitrary convex pmf p on N and recall that p admits the mixture representation (4.22) where T j is the triangular distribution defined by (2.7), 0 ≤ π j ≤ 1 and j≥1 π j = 1. Since

T j (X 1 ) = 0, for j ≤ X 1 f (j), for j ≥ X 1 + 1
where f was defined above, we conclude that for all convex pmf p on N, we have

T j 0 (X 1 ) ≥ j≥1 π j T j (X 1 ) = p(X 1 ).
(5.23)

Note now that in the case of a single observation X 1 , the log-likelihood criterion reduces to

Combining the identities in (5.23) and (5.24) ensures existence of the MLE. Furthermore, the calculations above imply that there exists some integer j 0 ≥ X 1 + 1 such that T j 0 is a solution. However, we shall see that it is not the only one when X 1 > 1.

To be able to exhibit an explicit value of j 0 , we seek integers j ≥ X 1 + 1 such that 1 (T j+1 ) -1 (T j ) ≤ 0 and 1 (T j ) -1 (T j-1 ) ≥ 0 or equivalently (using again (5.24) and monotonicity of the logarithm), such that

T j+1 (X 1 ) -T j (X 1 ) ≤ 0 and T j (X 1 ) -T j-1 (X 1 ) ≥ 0.
This is in turn equivalent to

j(j + 1 -X 1 ) ≤ (j + 2)(j -X 1 ) and (j -1)(j -X 1 ) ≥ (j + 1)(j -1 -X 1 )
for j ≥ X 1 + 1. These conditions are fulfilled if and only if 2X

1 ≤ j ≤ 2X 1 + 1 with j ≥ X 1 + 1. This implies that j 0 ∈ {2X 1 , 2X 1 + 1} ∩ [X 1 + 1, ∞)
where we recall that j 0 is such that 1 (p) achieves its maximum over all convex pmf's p on N at T j 0 . Note that if j 0 = X 1 + 1, then we necessarily have X 1 = 1 (since X 1 = 0 was excluded). In this case, j 0 = 2X 1 = 2. If X 1 > 1, then j 0 > X 1 + 1 and the above calculations imply that j 0 ∈ {2X 1 , 2X 1 + 1}. In this case, one can easily verify that

1 (T 2X 1 ) = 1 (T 2X 1 +1 ) = -log(2X 1 + 1),
which is the maximal value of the log-likelihood. This also implies that the same maximal value is attained at any mixture πT 2X 1 + (1 -π)T 2X 1 +1 with π ∈ (0, 1), giving rise to an infinite numbers of solutions.

We now prove that the LSE (which uniquely exists by strict convexity of the 2 norm) takes the form T j for some j. The least squares criterion defined for one observation

X 1 is Φ 1 (T j ) = 1 2 j-1 i=0 T j (i) 2 -T j (X 1 ) + 1 2 , = 2j + 1 3j(j + 1) - 2(j -X 1 ) + j(j + 1) + 1 2 .
It follows from Theorem 1 in [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] that the greatest support point of the LSE is greater than or equal X 1 . Since the greatest support point of T j is j -1, we restrict attention to integers j ≥ X 1 + 1 such that the following conditions hold Φ 1 (T j+1 ) -Φ 1 (T j ) ≥ 0 and Φ 1 (T j ) -Φ 1 (T j-1 ) ≤ 0.

(5.25)

A straightforward calculation shows that

Φ 1 (T j+1 ) -Φ 1 (T j ) = 4j -2 -12X 1 3j(j + 1)(j + 2)
and Φ 1 (T j ) -Φ 1 (T j-1 ) = 4j -6 -12X 1 3j(j -1)(j + 1) .

Then, conditions in (5.25) hold if and only if 4j -2 -12X 1 ≥ 0 and 4j -6 -12X 1 ≤ 0, which is equivalent to 1 2 + 3X 1 ≤ j ≤ 3 2 + 3X 1 with j ∈ N. Then the unique integer j ≥ X 1 + 1 satisfying (5.25) is 3X 1 + 1. Now, using the notation in (2.4) and (2.5), we have for all i ≥ 0 and j ≥ 1

F pn (i) = 0 if i < X 1 1 if i ≥ X 1 ; H pn (i) = 0 if i < X 1 + 1 i -X 1 if i ≥ X 1 + 1 ;
and

F T j (i) = (2j-1)i-i 2 +2j j(j+1) if i ≤ j -1 1 if i ≥ j ; H T j (i) = i(i-1) 6j(j+1) (6j -2i -2 + 12j i-1 ) if i ≤ j 1 3 (2j + 1) + (i -j) if i ≥ j + 1 .
It is not difficult to check that H T j (j) = H pn (j) if and only if j = 3X 1 + 1. Moreover, we have H T 3X 1 +1 (i) ≥ H pn (i) for all i ≥ 0. The later holds because H pn (i) = 0 for i < X 1 +1, H T 3X 1 +1 (i) = H pn (i) for all integers i such that i > 3X 1 + 1 and the inequality also holds for X 1 + 1 ≤ i ≤ 3X 1 + 1 since the sequence h(i) = H T 3X 1 +1 (i) -H pn (i) decreases on set {X 1 + 1, . . . , 3X 1 + 1} with h(3X 1 + 1) = 0. Since j is the only knot of T j , it then follows from the characterization of the LSE proved in Proposition 2.1 that the LSE is equal to

T 3X 1 +1 .
Proof of Proposition 2.3. For all sequences q we have that q 2 ≤ q

1/2 ∞ q 1/2 1 whence p n -p 0 2 ≤ p n -p 0 1/2 ∞ p n -p 0 1/2 1 ≤ p n -p 0 1/2 ∞ → 0
almost surely by the Glivenko-Cantelli Theorem. Now, for all sequences q and r ∈ [2, ∞], one has q r ≤ q 2 , so it follows from Theorem 4 of [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] that

p n -p 0 r ≤ p n -p 0 2 ≤ p n -p 0 2 → 0, a.s.
which completes the proof.

Proof of Theorem 2.5. Theorem 6 of Durot et al. (2013) implies (2.8). Let {0, . . . , S} denote again the support of p 0 . Since p n is a proper pmf, it follows from Proposition 2.6 that F pn (z) -F p 0 (z) = 0 for z ≥ S + 1. Hence, for all z ∈ N we have that

√ n|F pn (z) -F p 0 (z)| ≤ √ n z∧S x=0 | p n (x) -p 0 (x)| ≤ (S + 1) √ n p n -p 0 ∞ = O p (1).
Also, the definition of H pn and H p 0 and Proposition 2.6 imply that for all z ∈ N

√ n|H pn (z) -H p 0 (z)| ≤ √ n z∧(S+1)-1 x=0 |F pn (x) -F p 0 (x)| ≤ (S + 1) 2 √ n p n -p 0 ∞ = O p (1)
and the result follows.

Proof of Proposition 2.6. First, note that the maximal point of the support of the empirical pmf p n is X (n) = max 1≤i≤n X i , and that with probability one, X (n) = S provided that n is sufficiently large. Now, by Theorem 1 of [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] we know that p n admits a finite support whose maximal point s n ≥ X (n) . Therefore, with probability one we have s n ≥ S for n large enough. We show now by contradiction that with probability one there exists n * such that if n ≥ n * then s n ∈ {S, S + 1}. Suppose that s n ≥ S + 2. By Proposition 1 of [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] we know that with probability one there exists n 0 such that for n ≥ n 0 , p n has to be linear on the set {S -1, S, S + 1, . . . , s n }. But S + 1 is a knot of p 0 which implies by Proposition 2.4 above that with probability one there exits n * ≥ n 0 such that for n ≥ n * , S + 1 is also a knot of p n . This yields a contradiction.

Proof of Theorem 3.1. First note that C(K) is a non-empty closed convex cone of R S+2 , so there exists a unique minimizer of Φ over C(K).

Now suppose that g is the minimizer of Φ over C(K). Let x ∈ {1, . . . , S + 2}. Then, for > 0 the function k → g(k) + T x (k), where

T x (k) = (x -k) + , is clearly in C(K). Hence, 0 ≤ lim 0 Φ( g + T x ) -Φ( g) = S+1 k=0 g(k)T x (k) - S+1 k=0 W(k)T x (k).
Recall that G is the function defined by (3.15) for k ∈ {0, . . . , S + 1}, and W is given in (3.10). Setting G(-1) = 0 for notational convenience, and noting that F p 0 (-1) = 0 implies that with probability one, U(F p 0 (-1)) = 0, we can rewrite the last inequality as

0 ≤ S+1 k=0 G(k) -G(k -1) (x -k) + - S+1 k=0 {U(F p 0 (k)) -U(F p 0 (k -1))} (x -k) + = S k=0 G(k) ((x -k) + -(x -(k + 1)) + ) + G(S + 1) (x -S -1) + - S k=0 U(F p 0 (k)) ((x -k) + -(x -(k + 1)) + ) -U(F p 0 (S + 1)) (x -S -1) + = x-1 k=0 G(k) - x-1 k=0 U(F p 0 (k)),
where the last inequality follows from the fact that

(x -k) + -(x -k -1) + = 1, if k ≤ x -1 0, if k ≥ x
together with the fact that (x -S -1) + = 0 for x ∈ {1, . . . , S + 1}, and (x -S -1) + = 1 for x = S + 2. Thus with probability one,

H(x) = x-1 k=0 G(k) ≥ x-1 k=0 U(F p 0 (k)) = H(x)
for all x ∈ {1, . . . , S + 2}. Note that at x = 0, equality of H and H is guaranteed by the chosen convention. Proof of equality in case ∆ g(x) > 0 uses the fact that the perturbation function

T x satisfies that g + T x is in C(K) for | | small enough yielding lim →0 1 (Φ( g + T x ) -Φ( g)) = 0.
We also have equality of H and H at the points in K ∪ {S + 1, S + 2} since at these points there is no constraint. Therefore, if g is the minimizer of Φ, we have shown that the process H defined on {0, . . . , S + 2} as in (3.13) satisfies (3.14). Conversely, consider g ∈ C(K) such that the process H in (3.13) satisfies (3.14). Let g ∈ C(K). We will show now that Φ(g) ≥ Φ( g). We have

Φ(g) -Φ( g) = 1 2 S+1 k=0 (g(k) -g(k)) 2 + S+1 k=0 (g(k) -g(k))( g(k) -W(k)) ≥ S+1 k=0 (g(k) -g(k))( g(k) -W(k)) = S+1 k=0 (g(k) -g(k))( D(k) -D(k -1)),
where D(k) = G(k) -U(F p 0 (k)). Now, similar as above, for all x ∈ {1, . . . , S + 2} we have (5.26) with equality if ∆ g(x) > 0, or a point in K ∪ {0, S + 1, S + 2}. To conclude, we will use the fact that an arbitrary element g ∈ C(K) can be written as

S+1 k=0 ( D(k) -D(k -1))(x -k) + = x-1 k=0 D(k) = H(x) -H(x) ≥ 0,
g(k) = α + m+1 j=1 c j (s j -k) + + m+1 j=1 J j i=1 c j,i (z j,i -k) + (5.27)
for all k = 0, . . . , S + 1, with s 1 < • • • < s m the interior knots of p 0 , s m+1 = S + 1, z j,1 , . . . , z j,J j the knots of g in {s j-1 + 1, . . . , s j -1} for j = 1, . . . , m + 1, and where α, c 1 , c 2 , . . . , c m+1 are real numbers, and c j,i > 0 for j = 1, . . . , m + 1 and i = 1, . . . , J j . This comes from the fact that any finite convex sequence p = {p(0), . . . , p(K)} for some K > 0, admits the (spline) representation

p(k) = a + γ 1 (s 1 -k) + + . . . + γ p (s p -k) + + γ p+1 (K -k) + (5.28)
where a is a real number, γ i > 0 and 0 < s 1 < . . . < s p < K are the interior knots of p.

Using the spline representation in (5.27) together with (5.26), where we recall that we have an equality for x = s 1 , . . . , s m+1 , it follows that

S+1 k=0 ( D(k) -D(k -1))g(k) = α D(S + 1) + m+1 j=1 J j i=1 c j,i S+1 k=0 ( D(k) -D(k -1))(z j,i -k) + ≥ α D(S + 1),
where in the last inequality we used the fact that c j,i ≥ 0 for all j, i. Now, the boundary conditions H(S + 1) = H(S + 1) and H(S + 2) = H(S + 2) in (3.14) imply that

D(S + 1) = G(S + 1) -U(F p 0 (S + 1)) = H(S + 2) -H(S + 1) -U(F p 0 (S + 1)) = H(S + 2) -H(S + 1) -U(F p 0 (S + 1)) = 0.
We arrive at It follows that Φ(g) ≥ Φ( g) and that g is the minimizer of Φ.

Proof of Theorem 3.2. For z ∈ N define

Y n (z) =: z-1 k=0 √ n (F pn (k) -F p 0 (k)) = z-1 k=0 U n (F p 0 (k)), Y n (z) =: z-1 k=0 √ n F pn (k) -F p 0 (k) ,
and recall that H is given by (3.12) with

Y n (0) = Y n (0) = H(0) = 0. It
= L(x + 1) + L(x -1) -2L(x)
for x ∈ {0, . . . , S + 1} with L(-1) = 0. Note that we have that L(S + 2) = L(S + 1) = H(S + 1) = H(S + 2).

(5.30) Indeed, it follows from Proposition 2.6 that p n is a pmf whose support is included in {0, . . . , S +1} with probability one, for sufficiently large n. This implies that F pn (S +1) = F p 0 (S + 1) = 1 and therefore, Y n (S + 2) = Y n (S + 1). Similarly, Y n (S + 2) = Y n (S + 1) with probability one. Now, S + 1 is a knot of p 0 so it follows from Proposition 2.4 that S + 1 is also a knot of p n with probability one, for n sufficiently large. Hence, by (5.29)

we have Y n (S + 1) = Y n (S + 1). We conclude that with probability one and n large enough,

Y n (S + 2) = Y n (S + 1) = Y n (S + 1) = Y n (S + 2),
and the claim follows by passing n → ∞. Hence, with probability one we have that

L(x) ≥ H(x), for x ∈ {0, . . . , S + 2} = H(x), if x ∈ K ∪ {0, S + 1, S + 2} or ∆g(x) > 0.
Equality of L and H at points in K ∪ {0, S + 1, S + 2} in the last assertion follows from the chosen convention at 0, Proposition 2.4 together with the equalities Y n (x) = Y n (x) with probability one and n large enough for x ∈ K, and the identity in (5.30) for S + 1 and S + 2. Equality of L and H at points x ∈ {1, . . . , S}\K with ∆g(x) > 0 follows from the fact that x is a knot of p n in {s + 1, . . . , s -1}, with s and s being two successive knots of p 0 , if and only if it is a knot of √ n ( p n -p 0 ) using linearity of p 0 between two successive knots. Thus, if x is a knot of g, then as soon as n is large enough x is also a

knot of z → Y n (z + 1) + Y n (z -1) -2 Y n (z) = √ n ( p n (z) -p 0 (z)).
This in turn implies that Y n (x) = Y n (x) implying after passing to the limit that L(x) = H(x) almost surely. Furthermore, g is clearly in C(K). Therefore, it follows from Theorem 3.1 that g must be equal to the minimizer of Φ defined in (3.11). Thus, there exists a version of g such that g(x) = L(x + 1) + L(x -1) -2L(x) = H(x + 1) + H(x -1) -2 H(x) for x ∈ {0, . . . , S + 1}. Put ∆ = H -L. Then, for x ∈ {0, . . . , S + 1}, we have that ∆(x + 1) = 2∆(x) -∆(x -1). But ∆(-1) = ∆(0) = 0 since L(-1) = H(-1) = 0 and L(0) = H(0) = 0. We conclude by induction that ∆ = 0, that is H = L, on {0, . . . , S +2}. Now, from an arbitrary subsequence n we can extract a further subsequence n along which Y n and Y n weakly converge jointly to H and H. Since the limit is the same for any such subsequence, we conclude that Y n and Y n weakly converge jointly to H and H on {0, . . . , S + 2}. This in turn implies that the following convergences √ n(H pn -H p 0 ) ⇒ H, √ n(F pn -F p 0 ) ⇒ G and √ n( p n -p 0 ) ⇒ g occur jointly, and the proof is complete.

Proof of Theorem 3.3. Let K n be the set of all points x ∈ {1, . . . , S} that satisfy ∆ p n (x) > v n . Let ε = min x∈K ∆p 0 (x). Since K is the set of all interior knots of p 0 , we have ε > 0 whenever K = ∅. We will now prove that lim n→∞ P (K n = K) = 0. To this end, note that P (K n = K) ≤ P (there exists x ∈ K such that x ∈ K n ) (5.31) +P (there exists x ∈ K n such that x ∈ K), whence it suffices to show that both probabilities on the right hand side tend to zero.

Moreover, with Γ being the (S + 2) × (S + 2) matrix with component (i + 1, j + 1) equal to p 0 (i)(1 -p 0 (i)) for all i = j and -p 0 (i)p 0 (j) for all i = j, with i, j = 0, . . . , S + 1, the random vector (W(0), . . . , W(S + 1)) has the same distribution as Γ 1/2 G.

In the sequel, we assume without loss of generality that (g n (0), . . . , g n (S + 1)) = Γ

1/2 n G and (W(0), . . . , W(S +1)) = Γ 1/2 G. Thus in particular, W and g n are defined on the same probability space. From what precedes, g n is the convex projection of g n on the nonempty closed convex set C(K) in R S+2 whereas g was defined to be the convex projection of W on the same set C(K) in R S+2 . Using that the metric projection is Lipschitz, we conclude that

S+1 k=0 ( g(k) -g n (k)) 2 ≤ S+1 k=0 (W(k) -g n (k)) 2 .
From the Cauchy-Swartz inequality, it follows that

S+1 k=0 ( g(k) -g n (k)) 2 ≤ S+2 i=1 S+2 j=1 (Γ 1/2 n,i,j -Γ 1/2 i,j ) 2 × S+2 k=1 G 2 k , (5.33)
where Γ n,i,j , Γ i,j and G k respectively denote the component (i, j) of Γ n , the component (i, j) of Γ, and the component k of G. But p n almost surely converges to p 0 on {0, . . . , S + 2}, so Γ n converges to Γ conditionally on (X i ) i∈N , with probability one. This means that the right hand side in (5.33) converges to zero conditionally on (X i ) i∈N , with probability one. As this implies that the left hand side converges to zero as well, this proves that g n converges in distribution to g conditionally on (X i ) i∈N , which completes the proof of Theorem 3.3.

Proof of Theorem 3.6. Existence and uniqueness of the minimizer both follow from the projection theorem on closed convex cones in R s+1 . With similar arguments as for the proof of Theorem 3.1 and using that s ∈ K, it can be shown that an arbitrary element g ≤s ∈ C ≤s (K) is the minimizer if and only if the process H ≤s defined on {0, . . . , s + 1} by

H ≤s (x) =
x-1 k=0 k j=0 g ≤s (j), if x ∈ {1, . . . , s + 1} and H ≤s (0) = 0 satisfies

H ≤s (x) ≥ H(x)
for all x ∈ {0, . . . , s + 1}, with an equality if x ∈ K ∪ {0, s + 1} or x ∈ {1, . . . , s -1} satisfies ∆ g ≤s (x) > 0. Consider the restriction g ≤s = ( g(0), . . . , g(s)) of g to {0, . . . , s}.

A point x ∈ {1, . . . , s -1} is a knot of g ≤s if, and only if, it is a knot of g. Therefore, it immediately follows from the characterization of g given in Theorem 3.1 that the minimizer of Φ ≤s over C ≤s is equal to g ≤s if, and only if, H(s + 1) = H(s + 1). Since we already have H(s) = H(s), this is equivalent to H(s + 1) -H(s) = H(s + 1) -H(s), that is (3.18).

To prove the last assertion, note that from Theorem 3.2, it follows that √ n( p n (0)p 0 (0), . . . , p n (s) -p 0 (s)) converges in distribution to ( g(0), . . . , g(s)) as n → ∞. Thus, it converges in distribution to the minimizer of Φ ≤s over C ≤s (K) if, and only if, (3.18) holds true with probability one. On the other hand, fromTheorem 3.2, one also has

√ n F pn -F p 0 F pn -F p 0 ⇒ G U n (F p 0 ) (5.34)
as n → ∞. Therefore, one can have (3.18) with probability one if, and only if,

√

n (F pn (s) -F p 0 (s)) -(F pn (s) -F p 0 (s))

converges in probability to zero as n → ∞. This is equivalent to (3.19), so the proof of the theorem is complete.

Proof of Theorem 3.7. Existence and uniqueness of the minimizer both follow from the projection theorem on closed convex cones in R S-s . With similar arguments as for the proof of Theorem 3.1, it can be shown that an arbitrary element g ≥s ∈ C ≥s (K) is the minimizer if and only if the process H ≥s defined on {s, . . . , S + 2} by H ≥s (x) =

x-1 k=s k j=s g ≥s (j), if x ∈ {s + 1, . . . , S + 2} and H ≥s (s) = 0 satisfies H ≥s (x) ≥ H ≥s (x) for all x ∈ {s, . . . , S + 2}, with an equality if x ∈ K ∪ {0, S + 1, S + 2} or x ∈ {1, . . . , S} satisfies ∆ g ≥s (x) > 0, where H ≥s (s) = 0 and H ≥s (x) = Similarly, H(x) = H(s) + (x -s) H(s) -H(s -1) + H ≥s (x)

Figure 2 :

 2 Figure 2: The figures show the process √ n(H pn -H pn ) for a random sample of size n as shown. The samples were generated from a triangular pmf supported on {0, 1, . . . , 10}. The diamond symbols depict the knots of the LSE p n computed based on the samples.

Figure 3 :

 3 Figure 3: Boxplots of D n,M,M with M = 1000 and M = 5000. The sample size n is as indicated and the true convex pmf is p 0 on the left figure, and p 1 on the right figure. See text for details.

Figure 4 :

 4 Figure 4: Boxplots of D n,M,M with M = 1000 and M = 5000. The sample size n is as indicated and the true convex pmf is p 2 on the left figure, and p 3 on the right figure. See text for details.

Figure 5 :

 5 Figure 5: Boxplots of D n,M,M with M = 1000 and M = 5000. The sample size n is as indicated and the true convex pmf is p 4 on the left figure, and p 5 on the right figure. See text for details.

Figure 6 :

 6 Figure 6: Boxplots of D n,M,M with M = 1000 and M = 5000. The sample size n is as indicated and the true convex pmf is p 6 on the left figure, and the truncated geometric, p 7 , with success probability equal to 1/2. See text for details.

(

  D(k) -D(k -1))g(k) ≥ 0 and similarly, since we have an equality in (5.26) if ∆ g(x) > 0, S+1 k=0 ( D(k) -D(k -1)) g(k) = 0.

  x ∈ {s + 1, . . . , S + 2}. The connection between H and H ≥s is as follows. For all x ∈ {s, . . . , S + 2} one has + H ≥s (x) = H(s) + (x -s) H(s) -H(s -1) + H ≥s (x).

Table 1 :

 1 is similar to Figure1but now, the samples are generated from the triangular pmf T 11 , which means that Mixing weights π j for the convex pmf's p 1 , p 2 , p 3 , p 4 , p 5 , p 6 .

	pmf	π 1	π 2		π 3	π 4		π 5	π 6	π 7		π 8	π 9	π 10 π 11
	p 1	0	0		0	2/3			0	0	0		0	0	0	1/3
	p 2	1/3	0		0	0			0	1/2	0		0	0	0	1/6
	p 3	0	1/6	0	0		1/6	0	0		0	1/2	0	1/6
	p 4	0	0		0	1/6			0	1/6	0		1/12	0	1/2 1/12
	p 5	0	0		1/6 1/12 1/4	0	1/12		0	1/6 1/6 1/6
	p 6	0	1/12 1/6 1/12 1/12 1/12 1/12 1/12 1/12 1/6 1/12
					n= 50									n= 200
	0.25									0.25
	0.20									0.20
	0.15									0.15
	0.10									0.10
	0.05									0.05
	0.00									0.00
	0	2	4	6	8	10	12	14		0	2	4	6	8	10	12
	Figure 1: The figures show the process	√	n(H

pn -H pn ) for a random sample of size n as shown. The samples were generated from p 3 as in Table

Table 2 :

 2 Empirical frequencies in % of having all knots of the true convex pmf among those of the estimator p n for n ∈ {50, 200, 800, 3200, 12800, 51200}. The empirical frequencies are based on 1000 replications for each sample size and distribution. The true convex pmf's, p 1 , p 2 , p 3 , p 4 , p 5 and p 6 have 1 and 2, 3, 4, 6 and 9 interior knots respectively. See text for the exact expressions of those pmf's.

	n	p 1	p 2	p 3	p 4	p 5	p 6
	50	73.9 44.8 4.2	0.0	0.0	0.0
	200	96.8 82.8 14.5 2.1	0.3	0.0
	800	100 99.5 47.3 9.0	3.7	0.0
	3200	100 100 84.1 31.4 32.4 4.3
	12800 100 100 99.1 66.3 71.2 33.1
	51200 100 100 100 92.8 95.9 88.5

  In what follows, we will use the Skorokhod representation to assume that convergences of { Y n } n and {Y n } n to their respective limits happen almost surely. The goal now is to show that L and H, defined in Theorem 3.1 above, are equal with probability one. Let us define

follows from the characterization of p n in (2.6) that

Y n (x) ≥ Y n (x), for x ∈ {0, . . . , S + 2} = Y n (x), if x ∈ {0, . . . , S + 2} is a knot of p n .

(5.29)

By standard results on weak convergence of empirical processes we have the joint convergence

Y n (x) → d H(x), for x ∈ {0, . . . , S + 2}.

Now, Theorem 2.5 implies that there exists a subsequence { Y n } n which weakly converges to some L on {0, . . . , S + 2}.

g(x) :

(p) = log(p(X 1 )).(5.24)

Acknowledgments

The authors are very grateful to Sylvie Huet for many helpful comments, stimulating discussions on the subject, and also for a careful reading of the paper.

Consider the first probability. If there exists x ∈ K such that x ∈ K n , then K is not empty, and it follows from the definition of ε and K n that ∆ p n (x) ≤ v n and ∆p 0 (x) ≥ ε. Since lim n→∞ v n = 0, this means that ∆ p n (x) -∆p 0 (x) ≤ -ε/2

for n sufficiently large. Hence, the first probability is bounded from above by P (there exists x ∈ {1, . . . , S} such that ∆ p n (x) -∆p 0 (x) ≤ -ε/2)

(5.32)

for n sufficiently large. However, it follows from Theorem 3.2 that ∆ p n (x) -∆p 0 (x) = O p (n -1/2 ) for all x ∈ {1, . . . , S} and therefore, the probability in (5.32) converges to zero, implying that the first probability on the right hand side of (5.31) converges to zero as n → ∞.

Next consider the second probability on the right side of (5.31). If there exists x ∈ K n such that x ∈ K, then ∆ p n (x) > v n and ∆p 0 (x) = 0. Since lim n→∞ √ nv n = ∞, we can find N ∈ N such that for a given A > 0 we have that

for all n ≥ N . Fix η > 0. Applying again Theorem 3.2, we can choose A sufficiently large so that P (there exists x ∈ K n such that x ∈ K) ≤ P there exists x ∈ {1, . . . , S} such that √ n(∆ p n (x) -∆p 0 (x)) > A < η for all n ≥ N . Since η was arbitrary, this implies that the second probability on the right hand side of (5.31) converges to 0 and that lim n→∞ P (K n = K) = 0.

On the other hand, S n = S with probability converging to 1. Hence, we can assume without loss of generality that S n = S and K n = K. In this case, we also have C n = C(K) and g n is precisely the minimizer of

over C(K), which means that g n is the convex projection of g n on the non-empty closed convex set C(K) in R S+2 . Now, assume that X 1 , . . . , X n are the first n terms of a sequence (X i ) i∈N of i.i.d. random variables, and let G be a standard Gaussian vector with dimension S + 2, which is independent of (X i ) i∈N . Conditionally on (X 1 , . . . , X n ), the random vector (g n (0), . . . , g n (S + 1)) has the same distribution as

for all x ∈ {s, . . . , S + 2}, so that

using that H(s) = H(s).

Consider g ≥s = ( g(s), . . . , g(S + 1)). A point x ∈ {s + 1, . . . , S} is a knot of g ≥s if, and only if, it is a knot of g. Therefore, it immediately follows from the characterization of g given in Theorem 3.1, together with (5.35), that the minimizer of Φ ≥s over C ≥s (K) is equal to ( g(s), . . . , g(S + 1)) if, and only if, H(s -1) = H(s -1). Since we already have H(s) = H(s), this is equivalent to

To prove the last assertion, note that from Theorem 3.2, it follows that √ n( p n (s)p 0 (s), . . . , p n (S+1)-p 0 (S+1)) converges in distribution to ( g(s), . . . , g(S+1)) as n → ∞. Thus, it converges in distribution to the minimizer of Φ ≥s over C ≥s (K) if, and only if, (3.20) holds true with probability one. According to (5.34), this happens if, and only if,

converges in probability to zero as n → ∞. This is equivalent to (3.21), so the proof of the theorem is complete.

Proof of Lemma 4.2. We have ∆p(k) ≥ 0 for all k < S by convexity of the function k → q k . We also have ∆p(k) ≥ 0 for all integers k > S + 1 since for those k, ∆p(k) = 0. Now, ∆p(S + 1) = p(S) ≥ 0, and

which is ≥ 0 if, and only if, q ≤ 1/2. We conclude that ∆p(k) ≥ 0 for all k ∈ N if, and only if, q ≤ 1/2.


Fadoua Balabdaoui

Cécile Durot
email: cecile.durot@gmail.com

Marshall Lemma in discrete convex estimation

Keywords: convex, nonparametric least squares, Marshall lemma, pmf, shape constraints

published or not. The documents may come

Marshall lemma in discrete convex estimation

Fadoua Balabdaoui, Cécile

Introduction 1.A brief overview

The first Marshall's inequality goes back to [START_REF] Marshall | Discussion of Barlow and van Zwet's paper[END_REF]. It states that if F n is the least concave majorant (LCM) of the empirical distribution function F n , then F n -F ∞ ≤ F n -F ∞ for an arbitrary concave distribution function F . Here, all the distributions involved are supported on [0, ∞). The proof of this inequality is rather elementary and uses basic properties of the LCM. When F is the true distribution function with a decreasing density f supported on a compact real interval and assumed to be continuously differentiable with a strictly negative derivative, [START_REF] Kiefer | Asymptotically minimax estimation of concave and convex distribution functions[END_REF] showed that the global rate of convergence of F n -F n ∞ is of order n -2/3 log(n) almost surely. In convex density estimation, two Marshall-type of inequalities have been established for the convex least squares estimator (LSE) of a density on [0, ∞) defined by [START_REF] Groeneboom | Estimation of a convex function: characterizations and asymptotic theory[END_REF]. Let F be an arbitrary distribution function on [0, ∞) such that F is convex, F n the empirical distribution function, F n the cumulative distribution of the LSE, H n = • 0 F n (s)ds, H n = • 0 F n (s)ds and H = • 0 F (s)ds respectively. Then, [START_REF] Dümbgen | Marshalls lemma for convex density estimation[END_REF] and [START_REF] Balabdaoui | A second Marshall inequality in convex estimation[END_REF]

showed that F n -F ∞ ≤ 2 F n -F ∞ , and H n -H ∞ ≤ H n -H ∞
respectively. Those results were used by [START_REF] Balabdaoui | A Kiefer-Wolfowitz theorem for convex densities[END_REF] to show Kiefer-Wolfowitz-type of inequalities. Specifically, they show that when F is the true distribution such that f = F is twice continuously differentiable with f > 0, F n -F n ∞ and H n -H n ∞ are respectively of order (n -1 log(n)) 3/5 and (n -1 log(n)) 4/5 .

Discrete versus continuous

In both the monotone and convex estimation problems, the Kiefer-Wolfowitz-type of inequalities recalled above clearly suggest that if one is ready to assume that the true density or its derivative does not admit any flat part on its support, then the empirical and constrained estimators for the unknown distribution function are equivalent for n large enough.

In the discrete setting, this is not true anymore simply because the notion of a strict curvature does not exist in this case. In fact, with F n the empirical distribution and F n the cumulative distribution of the LSE studied by [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] and [START_REF] Balabdaoui | On asymptotics of the discrete convex lse of a pmf[END_REF], it can be shown with similar arguments as for the proof of Theorem 3.2 in [START_REF] Balabdaoui | On asymptotics of the discrete convex lse of a pmf[END_REF] [START_REF] Dümbgen | Marshalls lemma for convex density estimation[END_REF] for the convex LSE in the continuous setting. Although we re-adapt their idea of using concavity of the difference between the LSE and the density of F (with respect to the counting measure in our case) between two successive knot points a < b, our proof does not rely on the equalities F n (a) = F n (a) and

F n (b) = F n (b)
as they are no longer true for the discrete LSE. One has also to deal with discrete sums instead of integrals, which makes the final inequalities a bit less straightforward to obtain. One of the consequences of this note is to be able to assert that the convergence rate of F n to the truth F is the expected rate 1/ √ n, whether F has a finite support or not.

In [START_REF] Balabdaoui | On asymptotics of the discrete convex lse of a pmf[END_REF], the assumption that F is finitely supported on {0, . . . , S} for some unknown integer S > 0 was made to be able to establish the limiting distribution of the LSE, the general case being much more complex to handle. However, this assumption was not at all necessary for [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] to obtain that p n -

p k = O p (1/ √ n) for all k ∈ [2, ∞],
where p n and p are respectively the convex discrete LSE and the true probability mass function (pmf). However, for k = ∞, the transition from this result to showing

that F n -F ∞ = O p (1/ √ n) is not immediate unless F admits a finite support. The
Marshall lemma established in this note alleviates any existing doubt that the parametric convergence rate holds true independently of the nature of the support of the true convex pmf.

Based on a n-sample from a convex discrete probability mass function (pmf) on N, let p n denote the discrete convex LSE of the pmf as defined by [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF]. We recall that the points in N\{0} where p n changes its slopes are called knots, and that the characterization of p n is given by

z-1 x=0 F n (x)        ≥ z-1 x=0 F n (x), z ∈ N\{0} = z-1 x=0 F n (x), if z is a knot of p n , (2.1)
where F n is the empirical distribution function and F n is the distribution function corresponding to p n , see Proposition 2.1 in [START_REF] Balabdaoui | On asymptotics of the discrete convex lse of a pmf[END_REF]. In the sequel, F is a distribution function on N with corresponding pmf, p, that is decreasing and convex on N. We denote by K n the set consisting of the point 0 and all knots of p n and by pn the empirical pmf, that is the pmf corresponding to F n . We start with the following result.

Lemma 2.1 For τ ∈ K n , we have

F n (τ -1) ≤ F n (τ -1) and 0 ≤ F n (τ ) -F n (τ ) ≤ p n (τ ) -pn (τ ).
Proof. First, suppose that τ ≥ 2. From the characterization in (2.1), it follows that

τ -1 k=0 F n (k) = τ -1 k=0 F n (k) (2.2) τ -2 k=0 F n (k) ≥ τ -2 k=0 F n (k) (2.3) Then, (2.2) -(2.3) yields F n (τ -1) ≤ F n (τ -1). Likewise, (2.2) combined to (2.1) with z = τ + 1 yields F n (τ ) ≤ F n (τ ). As the inequality F n (τ -1) ≤ F n (τ -1
) can be rewritten under the alternative form F n (τ ) ≤ F n (τ ) + p n (τ ) -pn (τ ), this gives the result for τ ≥ 2.

If τ = 1, then the equality in (2.2) gives the first claimed inequality of the lemma

F n (0) = F n (0)
. Combined with the inequality in (2.1) with z = 2, this yields the second claimed inequality of the lemma, that is,

F n (1) ≤ F n (1) = F n (1) + p n (1) -pn (1).
Finally, if τ = 0, then F n (-1) = F n (-1) = 0 and (2.1) with z = 1 yields 0 ≤ F n (0) -

F n (0) = p n (0) -pn (0) which completes the proof of the Lemma.
In what follows, we will establish two important inequalities linking the extrema of

F n -F to those of F n -F . Proposition 2.2 We have max x∈N F n (x) -F (x) ≤ 2 max x∈N F n (x) -F (x) (2.4)
and

min x∈N F n (x) -F (x) ≥ -2 max x∈N F n (x) -F (x) .
(2.5)

Proof. Put D = F n -F and d = p n -p.
We begin with the proof of (2.4).

Assume first that the supremum of D over N is achieved at some m ≥ s n , where s n is the greatest point in the support of p n . Note that s n + 1 is the largest knot of p n . It follows from Theorem 1 of [START_REF] Durot | Least-squares estimation of a convex discrete distribution[END_REF] that s n ≥ max(X 1 , . . . , X n ), and

F n (x) = F n (x) = 1
for all x ≥ s n , and hence

sup x∈N F n (x) -F (x) = sup x≥ sn 1 -F (x) ≤ sup x∈N F n (x) -F (x)
implying the inequality in (2.4). In the sequel, we assume that the supremum is achieved at some m < s n and we denote by τ 1 and τ 2 two successive points in K n such that τ 1 ≤ m < τ 2 .

If m = τ 2 -1, then by the first inequality of Lemma 2.1 we can write

F n (m) -F (m) ≤ F n (m) -F (m) ≤ sup x∈N F n (x) -F (x)
implying (2.4). Thus, we assume in the sequel that the maximum of D over N is achieved at some m ∈ {τ 1 , . . . , τ 2 -2} for some consecutive points τ 1 and τ 2 in K n that satisfy (2.7) Thus d(x) = α(x -m 0 ), where the slope α is given by x ∈ { z 0 + 1, . . . , τ 2 }, where t denotes the integer part of a real number t. Hence, the inequality in (2.8) holds true for z ∈ {m + 1, . . . , z 0 }. Now, the second equality in (2.7)

τ 2 ≥ τ 1 + 2.
α = D(τ 2 ) -D(m) τ 2 x=m+1 (x -m 0 ) = 2(D(τ 2 ) -D(m)) (τ 2 -m)(τ 2 + m + 1 -2m 0 ) . Since d -d is concave on [m 0 , τ 2 ]
implies that if z ∈ { z 0 + 1, . . . , τ 2 -1}, then z x=m+1 d(x) -d(x) = - τ 2 x=z+1 d(x) -d(x) > 0;
and if z = τ 2 , then z x=m+1 d(x)-d(x) = 0. Thus, we can write for all z ∈ {m+1, . . . , τ 2 }

D(z) -D(m) ≥ z x=m+1 d(x) = α z x=m+1 (x -m 0 )
or equivalently

D(z) ≥ D(m) + (D(τ 2 ) -D(m)) (z -m)(z + m + 1 -2m 0 ) (τ 2 -m)(τ 2 + m + 1 -2m 0 ) . (2.9)
On the other hand, taking the difference between the equality and inequality of the characterization in (2.1) at the points z = τ 2 and z = m + 1 respectively we can write

τ 2 -1 x=m+1 D(x) ≤ τ 2 -1 x=m+1 F n (x) -F (x)
which, combined with (2.9), implies that

τ 2 -1 x=m+1 F n (x) -F (x) ≥ (τ 2 -1 -m)D(m) + D(τ 2 ) -D(m) S (2.10)
where

S = τ 2 -1 z=m+1 (z -m)(z -m + 1) -2(m 0 -m) τ 2 -1 z=m+1 (z -m) (τ 2 -m)(τ 2 + m + 1 -2m 0 ) = τ 2 -1-m k=1 k 2 + τ 2 -1-m k=1 k -2(m 0 -m) τ 2 -1-m k=1 k (τ 2 -m)(τ 2 + m + 1 -2m 0 ) = 1 3 (τ 2 -1 -m)(τ 2 -m)(τ 2 -m -1 2 ) + (τ 2 -1 -m)(τ 2 -m) 1 2 -(m 0 -m) (τ 2 -m)(τ 2 + m + 1 -2m 0 ) = 1 3 (τ 2 -1 -m) × τ 2 -m + 1 -3t τ 2 -m + 1 -2t , where t = m 0 -m ∈ [0, 1].
Since D(τ 2 ) -D(m) ≤ 0 by definition of m, we want to find an upper bound for S in t ∈ [0, 1]. To make the notation even lighter, let us put η = τ 2 -m + 1. Note that m ≤ τ 2 -2 by assumption so that η > 2 and η -2t > 0 for all t ∈ [0, 1]. A quick study of the variations of the function t → (η -3t)/(η -2t), for t ∈ [0, 1] shows that it attains its maximal value at 0 and that the maximal value is equal to 1. Hence, S ≤ (τ 2 -1 -m)/3 so that the inequality in (2.10) implies that

τ 2 -1 x=m+1 F n (x) -F (x) ≥ (τ 2 -1 -m)D(m) + D(τ 2 ) -D(m) 3 (τ 2 -1 -m).
Now, using the fact that

τ 2 -1 x=m+1 F n (x) -F (x) ≤ (τ 2 -1 -m) max x∈N F n (x) -F (x)
it follows that

D(m) ≤ 3 2 max x∈N F n (x) -F (x) - 1 2 D(τ 2 ).
(2.11)

Combining the second statement of Lemma 2.1 with (2.11) yields

D(m) ≤ 3 2 max x∈N F n (x) -F (x) + 1 2 max x∈N F n (x) -F (x) ≤ 2 max x∈N F n (x) -F (x) ,
which completes the proof of (2.4).

Now we turn to the proof of (2.5). Similar to the proof of (2.4), it is easy to see that (2.5) holds if the minimum of D is achieved at some m ≥ s n . Therefore, it suffices to prove (2.5) for the case where the minimum of D over N is achieved at some m < s n . As done above, we denote by τ 1 and τ 2 two successive points in K n such that τ 1 ≤ m < τ 2 . If m = τ 1 , then it follows from the second statement of Lemma 2.1 that

F n (m) -F (m) ≥ F n (m) -F (m) ≥ -max x∈N F n (x) -F (x)
(2.12) implying (2.5). Thus, we assume in the sequel that the minimum of D over N is achieved at some m ∈ {τ 1 + 1, . . . , τ 2 } for some consecutive points τ 1 and τ 2 in K n that satisfy Thus, we can write for all z ∈ {τ 1 , . . . , m} In what follows, we use q ∞ to denote sup x∈N |q(x)| for a function q defined on N. We now state the Marshall lemma for the convex discrete estimator.

τ 1 ≤ τ 2 -
D(m) -D(z -1) ≥ (D(m) -D(τ 1 -1)) (m -z + 1)(m + z -2m 0 ) (m -τ 1 + 1)(m + τ 1 -2m 0 ) or equivalently D(y) ≤ D(m) -(D(m) -D(τ 1 -1)) (m -y)(m + y + 1 -2m 0 ) (m -τ 1 + 1)(m + τ 1 -2m 0 ) ( 2
Theorem 2.3 For any distribution function F defined on N whose probability mass function is convex on N, we have

F n -F ∞ ≤ 2 F n -F ∞ .
Proof. The claimed inequality is an immediate consequence of Proposition 2.2 and the fact that q ∞ = max x∈N q(x) ∨ max x∈N (-q(x)) = max x∈N q(x) ∨ (-min x∈N q(x)).

  Since the inequality in (2.4) is trivial in the case where D(m) ≤ 0, we assume furthermore that D(m) > 0. Since D(-1) = 0, it follows from the definition of m that D(m) ≥ D(m + 1) and D(m) ≥ D(m -1), which in turn implies that p n (m) ≥ p(m) and p n (m + 1) ≤ p(m + 1). (2.6) Consider now the piecewise linear function d defined on the real interval [τ 1 , τ 2 ] such that d = d on the set of integers {τ 1 , . . . , τ 2 } and which linearly interpolates d between the integers. The inequalities in (2.6) and continuity of d imply that there exists a real number m 0 ∈ [m, m + 1] such that d(m 0 ) = 0. Note that since p is a convex pmf and p n is linear on {τ 1 , . . . , τ 2 }, d is concave on [τ 1 , τ 2 ]. Using the same idea as in Dümbgen et al. (2007), consider the auxiliary linear function d defined on the real interval [τ 1 , τ 2 ] such that d(m 0 ) = 0, and τ 2 x=m+1 d(x) = D(τ 2 ) -D(m).

  with a zero at m 0 , it follows that it can only bear a unique sign change on that interval. Therefore, its discretized version d -d such that d is defined as d(x) = d(x) = α(x -m 0 ) on the set of integers {m + 1, . . . , τ 2 } can only bear a unique sign change on that set. This in turn implies that z x=m+1 d(x) -d(x) ≥ 0, for all z ∈ {m + 1, . . . , τ 2 }. (2.8) To see this, note that there exists z 0 ∈ [m 0 , τ 2 ] such that dd ≥ 0 on [m 0 , z 0 ] and < 0 on (z 0 , τ 2 ]. It follows that d(x) -d(x) ≥ 0 if x ∈ {m + 1, . . . , z 0 } and d(x) -d(x) < 0 if

  1. By definition of m, we have D(m) ≤ D(m + 1) and D(m) ≤ D(m -1), which imply that p n (m) ≤ p(m) and p n (m + 1) ≥ p(m + 1). (2.13) Consider now the piecewise linear function d defined on [τ 1 , τ 2 ] such that d = d on the set of integers {τ 1 , . . . , τ 2 } and which linearly interpolates d between the integers. The inequalities in (2.13) and continuity of d imply that there exists a real number m 0 ∈ [m, m + 1] such that d(m 0 ) = 0. As in the proof of (2.4), consider again the auxiliary linear function d defined on [τ 1 , τ 2 ] such that d(m 0 ) = 0, and m x=τ 1 d(x) = D(m) -D(τ 1 -1). Thus d(x) = α(x -m 0 ), where α = 2(D(m) -D(τ 1 -1)) (m -τ 1 + 1)(τ 1 + m -2m 0 ) . Using the fact that d-d is concave on the real interval [τ 1 , τ 2 ] with a zero at m 0 ∈ [m, m+1], it follows that its discretized version d -d can only bear a unique sign change on the set of integers {τ 1 , . . . , m}. This in turn implies that we have m x=z d(x) -d(x) ≥ 0, for all z ∈ {τ 1 , . . . , m}.

FF

  .14) for y ∈ {τ 1 -1, . . . , m -1}. On the other hand, taking the difference between the equality and inequality of the characterization in (2.1) at the points z = τ 1 and z = m respectivelyimplies that n (x) -F (x) ≤ (m -τ 1 )D(m) -D(m) -D(τ 1τ 1 ) with η = m -τ 1 -1 and t = m 0 -m ∈ [0, 1]. Now, using the fact that n (x) -F (x) ≥ (m -τ 1 ) min x∈N F n (x) -F (x) it follows that min x∈N F n (x) -F (x) ≤ D(m) -1 3 (D(m) -D(τ 1 -1)n (τ 1 -1) -F (τ 1 -1))where the last inequality is an immediate consequence of the first equality of Lemma 2

  , that ( F n , F n ) converges jointly, at the rate

				√	n, to a quite complicated
	limiting distribution, so that	√	n( F n -F n ) converges to a distribution that we conjecture
	is not degenerate. Hence, it is somehow expected that the difference between F n and F n
	converges exactly at the rate 1/	√	n in this case. Although we do not pursue this in this
	short note, an immediate consequence of our main theorem is that this difference is at
	most O p (1/ √ n) in the supremum norm. This theorem gives the same form of the Mar-
	shall inequality proved by