# Unified study of the phase transition for block-weighted random planar maps

Zéphyr Salvy Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France.
E-mail<EMAIL_ADDRESS>
###### Abstract

In [Fleurat, Salvy 2024], we introduced a model of block-weighted random maps
that undergoes a phase transition as the density of separating elements
changes. The purpose of this note is to demonstrate that the methodology we
developed can be extended to many other families of maps. We prove that a
phase transition exists and provide detailed information about the size of the
largest blocks in each regime.

DOI: https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-109

##  1 Introduction

A _planar map_ $\mathfrak{m}$ is the proper embedding into the two-dimensional
sphere of a connected planar finite multigraph, considered up to
homeomorphisms. Maps exhibit very rich combinatorial and probabilistic
properties, which have been the focus of an extensive literature. Many
families of planar maps have very nice counting formulas [Tut63]. A key aspect
of planar maps is that they can be decomposed, typically into components of
higher connectivity degree. Such decompositions typically relate one family of
planar maps to another and gives an equation between their generating series.

Theses types of decompositions were initially introduced by Tutte [Tut63] to
obtain some enumerative results about planar maps. But they also play a major
role in the enumerative study of planar graphs [GN09]. They allow to study
certain models of discrete metric spaces in theoretical physics [Bon16]. In
view of applications to random generation [Sch99], the decomposition of planar
maps has been systematised in [BFSS01], where a uniform treatment via analytic
combinatorics is developed. A probabilistic approach was later derived using
encoding of maps via enriched trees [Stu18, AB19].

Planar map models exhibit _universality_ , meaning that many natural classes
of random maps show similar behavior as their size grows to infinity. When
taking an object of size $n$ uniformly at random among all objects in a class
and appropriately rescaling its distance, the sequence of random objects
converges to a certain metric space. This was first proved for uniform
quadrangulations by Miermont [Mie13] and Le Gall [LG13], and since then,
results have been extended to other families of maps, including uniform
triangulations and uniform $2q$-angulations ($q\geqslant 2$) [LG13], uniform
simple triangulations and uniform simple quadrangulations [ABA17], bipartite
planar maps with a prescribed face-degree sequence [Mar18],
$(2q+1)$-angulations [ABA21] and Eulerian triangulations [Car21].

In a previous article [FS24], together with Fleurat, we studied a model of
random maps, depending on a parameter $u$ which controls the density of
separating elements. We proved that this model exhibits a phase transition as
$u$ varies, and that it interpolates between the Brownian sphere and the
Brownian tree of Aldous [Ald91]. This approach — which we detailed in [FS24]
for general maps and their $2$-connected cores and for general
quadrangulations and their simple cores — can be applied to other
decompositions, such as those in [BFSS01, Table 3] (which is partially
reproduced in Table 1), and this is the focus of this note. We restrict our
study to decomposition schemes without “coreless” maps (the decompositions
involving coreless maps, such as $2$-connected maps into $3$-connected
components, bring further difficulties, which we expect to handle with some
more work).

Let us give some formalism for decompositions. A map is said to be _loopless_
if it does not contain any loop; _$2$ -connected_ if it does not contain any
_cut vertex_ (_i.e._ a vertex whose removal deconnects the map) and _simple_
if it has neither loops nor multiple edges. Planar maps can be decomposed into
loopless (or $2$-connected, or simple, or $2$-connected simple…) components,
which are the so-called “blocks”. It is also the case for _bipartite_ maps,
whose vertices can be properly bicolored in black and white; and for
_triangulations_ , whose faces all have degree $3$. The latter can be
decomposed into _irreducible_ components, in which every $3$-cycle defines a
face. We consider eight models here (see Table 1):

  1. 1.

Loopless maps decomposed into simple blocks;

  2. 2.

General maps decomposed into $2$-connected blocks;

  3. 3.

$2$-connected maps decomposed into $2$-connected simple blocks;

  4. 4.

Bipartite maps decomposed into bipartite simple blocks;

  5. 5.

Bipartite maps decomposed into bipartite $2$-connected blocks;

  6. 6.

Bipartite $2$-connected maps decomposed into bipartite $2$-connected simple
blocks;

  7. 7.

Loopless triangulations decomposed into triangular simple blocks;

  8. 8.

Simple triangulations decomposed into triangular irreducible blocks.

In general, the _size_ $|\mathfrak{m}|$ of a planar map $\mathfrak{m}$ is its
number of edges. In a decomposition scheme, we let
$M(z)=\sum_{n\in\mathbb{Z}_{\geqslant 0}}m_{n}z^{n}$ be the generating series
of the class of maps to be decomposed and similarly
$B(z)=\sum_{n\in\mathbb{Z}_{\geqslant 0}}b_{n}z^{n}$ be the generating series
of the class of “blocks” into which the maps are decomposed.

Setting
$M(z,u)=\sum_{\mathfrak{m}\in\mathcal{M}}z^{|\mathfrak{m}|}u^{b(\mathfrak{m})}$,
where $b(\mathfrak{m})$ is the number of blocks of positive size in
$\mathfrak{m}$, all the models we consider — which are listed in Table 1 —
satisfy

$M(z,u)=uB(H(z,M(z,u))),$ (1)

or, for the last one,

$M(z,u)=(1+M(z,u))\times uB(H(z,M(z,u))).$ (2)

For example, for the decomposition of general maps into $2$-connected ones
(which is the case studied in [FS24]), one has

$M(z,u)=uB(z(1+M(z,u))^{2}).$

For $u>0$, denote by $\rho(u)$ the radius of convergence of $z\mapsto M(z,u)$.
In view of the form of Equations 1 and 2 and in particular that they are non-
linear, it holds that $M(\rho(u),u)<\infty$.

In the following, $\mathbf{M}$ and $\mathbf{M}_{n}$ are random variables drawn
according to the following probability distributions. For
$u\in\mathbb{R}_{>0}$, $n\in\mathbb{Z}_{>0}$ and $\mathfrak{m}\in\mathcal{M}$,
we set

$\mathbb{P}_{u}\left(\mathfrak{m}\right)=\frac{\rho(u)^{|\mathfrak{m}|}u^{b(\mathfrak{m})}}{M(\rho(u),u)}\qquad\text{and}\qquad\mathbb{P}_{n,u}\left(\mathfrak{m}\right)=\frac{u^{b(\mathfrak{m})}}{[z^{n}]M(z,u)}\mathbb{1}_{|\mathfrak{m}|=n}.$

Scheme | maps, $M(z)$ | blocks, $B(z)$ | submaps, $H(z,M)$
---|---|---|---
1 | loopless, $M_{2}(z)$ | simple, $M_{3}(z)$ | $z(1+M)$
2 | all, $M_{1}(z)$ |  $2$-connected, $M_{4}(z)$ | $z(1+M)^{2}$
3 |  $2$-connected $M_{4}(z)-z$ |  $2$-connected simple, $M_{5}(z)$ | $z(1+M)$
4 | bipartite, $B_{1}(z)$ | bipartite simple, $B_{2}(z)$ | $z(1+M)$
5 | bipartite, $B_{1}(z)$ | bipartite $2$-connected, $B_{4}(z)$ | $z(1+M)^{2}$
6 | bipartite $2$-connected, $B_{4}(z)$ | bipartite $2$-connected simple $B_{5}(z)$ | $z(1+M)$
7 | loopless triangulations, $T_{1}(z)$ | simple triangulations, $z+zT_{2}(z)$ | $z(1+M)^{3}$
8 | simple triangulations, $T_{2}(z)$ | irreducible triangulations, $T_{3}(z)$ | $z(1+M)^{2}$
Table 1: Partial reproduction of [BFSS01, Table 3], which describes
composition schemas of the form $\mathcal{M}=\mathcal{B}\circ\mathcal{H}$
except the last one where
$\mathcal{M}=(1+\mathcal{M})\times\mathcal{B}\circ\mathcal{H}$. The
terminology and notation were slightly changed. For all $i$, $[z^{n}]M_{i}(z)$
and $[z^{n}]B_{i}(z)$ is the number of such maps with $n$ edges.
$[z^{n}]T_{1}(z)$ (resp. $[z^{n}]T_{2}(z)$ and $[z^{n}]T_{3}(z)$) is the
number of loopless (resp. simple or irreducible) triangulations with $n+2$
(resp. $n+3$) vertices.

Regarding enumeration in our setting, we show the following by analytic
methods (details are omitted in this short note).

######  Theorem 1.

For any model described in Table 1, where maps are decomposed into blocks
weighted with a weight $u>0$, there exists a critical value $u_{C}$ at which
the model undergoes a phase transition. As $u$ varies, there exists $c(u)>0$
such that

$[z^{n}]M(z,u)\sim\begin{cases}c(u)n^{-5/2}\rho(u)^{-n}\quad\text{if}\
u<u_{C}\\\ c(u_{C})n^{-5/3}\rho(u_{C})^{-n}\quad\text{if}\ u=u_{C}\\\
c(u)n^{-3/2}\rho(u)^{-n}\quad\text{if}\ u>u_{C}\end{cases}.$

All the constants involved in Theorem 1 are explicit. Table 2 gives the
expressions for $u_{C}$, $\rho(u)$ and $M(\rho(u),u)$ when $u\leqslant u_{C}$.

The polynomial correction for $u<u_{C}$ (subcritical case) is the same than
for planar maps, whereas when $u>u_{C}$ (supercritical case) it is the same
than for plane trees. Moreover, at $u=u_{C}$, a new asymptotic behaviour
appears with a polynomial correction in $n^{-5/3}$.

In this note, we also focus on another aspect of the phase transition, namely
the size of the largest blocks. We show that if $u<u_{C}$, a condensation
phenomenon occurs and the largest block is of size $\Theta(n)$; when
$u>u_{C}$, the largest block is of size $\Theta(\log(n))$; for $u=u_{C}$, the
largest block is of size $\Theta(n^{2/3})$ (Theorem 3). For the subcritical
case, as in [FS24], we follow the probabilistic approach of [AB19] (whereas
[BFSS01] gives an analytic approach).

These results further support that the scaling limits should be the Brownian
sphere when $u<u_{C}$, the Brownian tree when $u>u_{C}$ and the stable tree of
parameter $3/2$ when $u=u_{C}$. This was proved for the decomposition of
quadrangulations into simple components [FS24], and we expect this phenomenon
to be generic. For model 2, the critical scaling limit was established in
[FS24] and the supercritcal one in [Stu20a]. For model 5, the supercritical
case was also established [Stu20a].

##  2 Tree structure

We explain here how an underlying tree structure can be associated to each of
the models of Table 1. As a first step, we rewrite the decomposition equations
in the standard Lagrangian form $M(z)=z\times\Phi(M(z))$ for some function
$\Phi$, taking the weight $u$ into account. (Beware that Equations 1 and 2 are
not of this form as the products by $z$ are inside $H$.)

######  Proposition 1.

For all models listed in Table 1, there exists a generating function $\Phi$
with nonnegative coefficients such that

$M(z,u)=z\times\Phi(M(z,u),u).$ (3)

###### Proof sketch.

We discuss how the rewriting is done for two cases: general maps into
$2$-connected components, and simple triangulations into irreducible
components.

We start by maps decomposed into $2$-connected components. In order to do the
rewriting, we need to change the size parameter, which we take as the number
of half-edges plus one. Accordingly, we set $\hat{M}(z,u)=z(1+M(z^{2},u))$.
The equation then becomes

$\hat{M}(z,u)=z\left(1+uB(\hat{M}(z,u)^{2})\right),$

which is of the desired form.

The second case we discuss is the decomposition of simple triangulations into
irreducible components. We also need to change the size parameter, taking here
the number of inner faces instead of the number of vertices. A further
ingredient compared to the first case is that we need to group the components
into sequences to obtain an equation in Lagrangian form. Let $\hat{z}$ count
internal faces. The generating series of simple (resp. irreducible)
triangulations counted by internal faces $\hat{T_{2}}(\hat{z},u)$ (resp.
$\widetilde{T_{3}}(\hat{z})$) is closely related to $T_{2}(z,u)$ (resp.
$T_{3}(z)$) since a triangulation with $n+3$ vertices has $2n+2$ faces so
$2n+1$ internal faces. Then, denoting
$\hat{T_{3}}(\hat{z})=\widetilde{T_{3}}(\hat{z})/\hat{z}$, It holds that

$\hat{T_{2}}(\hat{z},u)=\hat{z}+u\hat{T_{2}}(\hat{z},u)\hat{T_{3}}(\hat{T_{2}}(\hat{z},u)),\qquad\text{so}\qquad\hat{T_{2}}(\hat{z},u)=\frac{\hat{z}}{1-u\hat{T_{3}}(\hat{T_{2}}(\hat{z},u))}.$

Therefore, we set $\Phi(M,u)=\frac{1}{1-u\hat{T_{3}}(M)}$. This corresponds to
the vertices of the tree encoding a sequence of irreducible triangulations,
which is represented on Fig. 1111With additional work, one can do the same for
simple quadrangulations decomposed into irreducible ones.. ∎

Figure 1: A simple triangulation, its classical tree of (irreducible) blocks,
the adapted tree where some blocks are grouped into sequences.

The _block tree_ $T_{\mathfrak{m}}$ of a map $\mathfrak{m}$ is the tree
associated to the the decomposition of $\mathfrak{m}$ as expressed in
Proposition 1. Each node of the tree correspond to an object $\varphi$ counted
by $\Phi$. The subtrees hanging at a node (corresponding to some $\varphi$)
are the trees of the components substituted into $\varphi$.

As a consequence of 3, if we set a probability measure $\mu^{u}$ such that,
for $k\in\mathbb{Z}_{\geqslant 0}$,

$\mu^{u}(k)=\frac{[X^{k}]\Phi(X,u)y(u)^{k}}{\Phi(y(u),u)}$

for $y(u)=M(\rho(u),u)$ (using the definition of $M$ given in 3); then, using
the fact that $T_{\mathfrak{m}}$ and the decoration of its vertices are
bijectively linked to $\mathfrak{m}$, we have the following result (again
stated in terms of the $M$ of 3):

######  Theorem 2.

For all $u>0$, $T_{\mathbf{M}}$ follows the law of a Galton-Watson tree of
reproduction law $\mu^{u}$. Moreover, $T_{\mathbf{M}_{n}}$ follows the law of
a Galton-Watson tree of reproduction law $\mu^{u}$ conditioned to have $n$
vertices.

The decomposition tree of a random map of “Lagrangian size” $n$ is a Galton-
Watson tree of reproduction law $\mu^{u}$ conditioned to have $n$ vertices.
For instance, for maps decomposed into $2$-connected components, the tree of a
random map with $n$ edges is a Galton-Watson tree conditioned to have $2n+1$
vertices. This enables to put into light a phase transition on the tree
structure, using the usual phase transition for Galton-Watson trees [Nev86].

######  Proposition 2.

The expectation $E(u)$ of $\mu^{u}$ is written down in Table 2.

Scheme | $u_{C}$ | $\rho(u)$ | $M(\rho(u),u)$ | $E(u)$ | $1-E(1)$
---|---|---|---|---|---
1 | $\frac{81}{17}$ | $\frac{27}{8(5u+27)}$ | $\frac{5u}{27}$ | $\frac{32u}{3(5u+27)}$ | $\frac{2}{3}$
2 | $\frac{9}{5}$ | $\frac{4}{3(u^{2}+6u+9)}$ | $\frac{u}{3}$ | $\frac{8u}{3(u+3)}$ | $\frac{1}{3}$
3 | $\frac{135}{7}$ | $\frac{128}{27(5u+27)}$ | $\frac{25u^{2}+135u+128}{27(5u+27)}$ | $\frac{32u}{5(5u+27)}$ | $\frac{4}{5}$
4 | $\frac{36}{11}$ | $\frac{5}{8(u+4)}$ | $\frac{u}{4}$ | $\frac{20u}{9(u+4)}$ | $\frac{5}{9}$
5 | $\frac{52}{27}$ | $\frac{25}{8(u^{2}+8u+16)}$ | $\frac{u}{4}$ | $\frac{40u}{13(u+4)}$ | $\frac{5}{13}$
6 | $\frac{68}{3}$ | $\frac{125}{128(u+4)}$ | $\frac{u}{4}$ | $\frac{20u}{17(u+4)}$ | $\frac{13}{17}$
7 | $\frac{16}{7}$ | $\frac{54}{u^{3}+24u^{2}+192u+512}$ | $\frac{u}{8}$ | $\frac{9u}{2(u+8)}$ | $\frac{1}{2}$
8 | $\frac{64}{37}$ | $\frac{25}{6912}u^{2}-\frac{5}{108}u+\frac{4}{27}$ | $\frac{5u}{32-5u}$ | $\frac{27u}{2(32-5u)}$ | $\frac{1}{2}$
Table 2: Values of $u_{C}$, $\rho(u)$, $M(\rho(u),u)$ and $E(u)$ when
$u\leqslant u_{C}$ for all the decomposition schemes of Table 1.

##  3 Results on the size of the largest blocks

Starting from Equations 1, 2 and 2, we use the same techniques as in [FS24] to
obtain results on decomposition schemes. However, simple triangulations
decomposed into irreducible blocks present a challenge, as the vertices of the
block trees are not decorated with a single block (or none) but with a
sequence of blocks. Hence, the size of the blocks cannot be immediately read
from the degrees in the block tree. However, an extreme condensation
phenomenon occurs, concentrating mass in only one element of the sequence (as
in [Gou98, Th1]), resulting in a similar behaviour.

Denote by $L_{n,j}$ the size of the $j$-th largest block of $\mathbf{M}_{n}$.
By Theorem 2, the same arguments as in [FS24] apply and the following holds.

######  Theorem 3.

Models described in Table 1, where maps are decomposed into blocks weighted
with a weight $u>0$, satisfy the following.

Subcritical case

For all $u<u_{C}$, we have

$L_{n,1}=(1-E(u))n+O_{\mathbb{P}}(n^{2/3})\quad\text{and}\quad
L_{n,2}=O_{\mathbb{P}}(n^{2/3}).$

Moreover, there exists an explicit constant $\tilde{c}(u)>0$ such that the
following joint convergence holds:

$\left(\frac{1}{n\tilde{c}(u)}\right)^{2/3}\left((1-E(u))n-L_{n,1},\left(L_{n,j},j\geqslant
2\right)\right)\xrightarrow[n\to\infty]{(d)}\left(L_{1},\left(\Delta
L_{(j-1)},j\geqslant 2\right)\right)$ (4)

where $(L_{t})_{t\in[0,1]}$ is a Stable process of parameter $3/2$ such that
$\mathbb{E}\left[e^{-sL_{1}}\right]=e^{\Gamma(-3/2)s^{3/2}}$ and $\Delta
L_{(1)}\geqslant\Delta L_{(2)}\geqslant\dots$ is the ranked sequence of its
jumps.

Supercritical case

For all $u>u_{C}$, there exist explicit values $F(u),G(u)>0$ such that, for
all fixed $j\geqslant 1$,

$L_{n,j}=F(u)\ln(n)-G(u)\ln(\ln(n))+O_{\mathbb{P}}(1).$

Critical case

If $u=u_{C}$, then

$\left(\frac{L_{n,j}}{n^{2/3}},j\geqslant
1\right)\xrightarrow[n\to\infty]{(d)}\left(E_{(j)},j\geqslant 1\right),$

where the $\left(E_{(j)}\right)$ are the ordered atoms of an explicite Point
Process, specified in [Jan12, Ex19.27, Rk19.28].

As mentioned in [FS24], for $u=1$, we retrieve by a probabilistic method the
results of [BFSS01, Table 4], established by analytic techniques: indeed, our
$1-E(1)$ corresponds to their $\alpha_{0}$. The probabilistic approach we
follow was first developed by [AB19] and has the advantage that we obtain a
joint limit law for the largest block and the subsequent ones. It can also
yield local limit theorems for the size of the largest block, as is discussed
by Stufler in [Stu20b].

## References

  * [AB19] Louigi Addario-Berry.  A probabilistic approach to block sizes in random maps.  ALEA - Latin American Journal of Probability and Mathematical Statistics, XVI(1):1–13, 2019.
  * [ABA17] Louigi Addario-Berry and Marie Albenque.  The scaling limit of random simple triangulations and random simple quadrangulations.  The Annals of Probability, 45(5):2767 – 2825, 9 2017.
  * [ABA21] Louigi Addario-Berry and Marie Albenque.  Convergence of odd-angulations via symmetrization of labeled trees.  Annales Henri Lebesgue, 4:653–683, 8 2021.
  * [Ald91] David Aldous.  The continuum random tree. II. an overview.  Stochastic analysis, 167:23–70, 10 1991.
  * [BFSS01] Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, and Michèle Soria.  Random Maps, Coalescing Saddles, Singularity Analysis, and Airy Phenomena.  Random Struct. Algorithms, 19(3-4):194–246, oct 2001.
  * [Bon16] Valentin Bonzom.  Large $N$ limits in tensor models: Towards more universality classes of colored triangulations in dimension $d\geqslant 2$.  Symmetry, Integrability and Geometry: Methods and Applications, 12(073):39, 7 2016.
  * [Car21] Ariane Carrance.  Convergence of Eulerian triangulations.  Electronic Journal of Probability, 26(26):1–48, 1 2021.
  * [FS24] William Fleurat and Zéphyr Salvy.  A phase transition in block-weighted random maps.  Electron. J. Probab., 29:1–61, 1 2024.
  * [GN09] Omer Giménez and Marc Noy.  Asymptotic enumeration and limit laws of planar graphs.  Journal of the American Mathematical Society, 22(2):309–329, 2009\.
  * [Gou98] Xavier Gourdon.  Largest component in random combinatorial structures.  Discrete Mathematics, 180(1):185–209, 2 1998.
  * [Jan12] Svante Janson.  Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation.  Probability Surveys, 9:103 – 252, 1 2012.
  * [LG13] Jean-François Le Gall.  Uniqueness and universality of the Brownian map.  The Annals of Probability, 41(4):2880 – 2960, 7 2013.
  * [Mar18] Cyril Marzouk.  Scaling limits of random bipartite planar maps with a prescribed degree sequence.  Random Structures & Algorithms, 53(3):448–503, 2 2018.
  * [Mie13] Grégory Miermont.  The Brownian map is the scaling limit of uniform random plane quadrangulations.  Acta Mathematica, 210(2):319–401, 2013.
  * [Nev86] Jacques Neveu.  Arbres et processus de Galton-Watson.  Annales de l’I.H.P. Probabilités et statistiques, 22(2):199–207, 1986.
  * [Sch99] Gilles Schaeffer.  Random sampling of large planar maps and convex polyhedra.  In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99, pages 760–769, New York, NY, USA, 5 1999. Association for Computing Machinery.
  * [Stu18] Benedikt Stufler.  Random enriched trees with applications to random graphs.  Electronic Journal of Combinatorics, 25(3), 7 2018.
  * [Stu20a] Benedikt Stufler.  Limits of random tree-like discrete structures.  Probability Surveys, 17:318–477, 1 2020.
  * [Stu20b] Benedikt Stufler.  On the maximal offspring in a subcritical branching process.  Electronic Journal of Probability, 25:1 – 62, 1 2020.
  * [Tut63] W. T. Tutte.  A census of planar maps.  Canadian Journal of Mathematics, 15:249–271, 1963.

## Acknowledgements

The author would like to thank their supervisors Marie Albenque and Éric Fusy
for their guidance and support.


[1]Dietmar Ferger

[1]Fakultät Mathematik, Technische Universität Dresden, Zellescher Weg 12-14,
01062 Dresden, Germany

# Supremal inequalities for convex M-estimators with applications to complete
and quick convergence

<EMAIL_ADDRESS>*

###### Abstract

Let $\hat{m}_{n}$ be an $M$-estimator for a parameter $m$ based on a sample of
size $n\in\mathbb{N}$. We derive exponential and polynomial upper bounds for
the tail-probabilities of $\sup_{k\geq n}|\hat{m}_{k}-m|$ according as a
boundedness- or a moment-condition is fulfilled. This enables us to derive
rates of $r$-complete convergence and also to show $r$-qick convergence in the
sense of Strasser.

###### keywords:

argmin, convex stochastic process, probability inequalities, rates of
convergence

##  1 Introduction

In statistics many parameters $m$ of interest are defined or can be
characterized as a minimizer of a certain convex criterion function
$M:\mathbb{R}\rightarrow\mathbb{R}$. In mathematical optimisation or decision
theory $M$ is a loss function or a cost function depending on some (real)
value and the problem is to find that value, which minimizes the pertaining
loss or costs, respectively. A huge class of such functions $M$ is given by a
bivariate function

$h:S\times\mathbb{R}\rightarrow\mathbb{R}.$

If $(S,\mathcal{S},Q)$ is a probability space, then $M$ is given by

$M(t):=\int_{S}h(x,t)-h(x,t_{0})Q(dx),\;t\in\mathbb{R},$ (1)

where $t_{0}$ is any fixed real number. To ensure the existence of $M$ we
assume that $h(\cdot,t):S\rightarrow\mathbb{R}$ is $\mathcal{S}$-Borel
measurable for every $t\in\mathbb{R}$ and further that
$h(x,\cdot):\mathbb{R}\rightarrow\mathbb{R}$ is convex for every $x\in S$.
Moreover, suppose that

$\int_{S}|D^{+}h(x,t)|Q(dx)<\infty\text{ and
}\int_{S}|D^{-}h(x,t)|Q(dx)<\infty\quad\forall\;t\in\mathbb{R}.$ (2)

Here, $D^{+}h(x,t)$ and $D^{-}h(x,t)$ denote the right derivative and the left
derivative of $h(x,\cdot):\mathbb{R}\rightarrow\mathbb{R}$ at point
$t\in\mathbb{R}$. Then by Proposition 2.1 of Ferger [7] the criterion function
$M$ exists and furthermore it is real-valued and convex.

######  Remark 1.

Actually, one is interested in the minimizing point $m$ of $M_{0}$ defined by
$M_{0}(t):=\int_{S}h(x,t)Q(dx)$. Since $M_{0}$ also has $m$ as its minimizer,
both are suitable as criterion functions, although $M$ seems unnecessarily
complicated and therefore less intuitive. The decisive reason for choosing $M$
is that $M_{0}$ only exists as a real-valued function, if and only if

$\int_{S}|h(x,t)|Q(dx)<\infty\text{ for all }\quad\forall\;t\in\mathbb{R}.$
(3)

However, this requirement is strictly stronger than condition (2) as shown in
Lemma 2.2 of Ferger [7]. In fact, requirement (2) proves to be much weaker
than (3). For instance, if $h(x,t):=|t-x|^{p}$ with $(x,t)\in\mathbb{R}^{2}$
and $p\geq 1$, then $M_{0}$ exists if (and only if) $\int|x|^{p}Q(dx)<\infty$,
whereas $M$ exists if $\int|x|^{p-1}Q(dx)<\infty$. In case that $p=1$, which
corresponds to the median, in fact no integrability assumption is needed.

######  Remark 2.

In Ferger [7] we derive several analytical properties of the criterion
function $M$ with emphasis on the existence, characterisation and possible
uniqueness of its minimizers, see section 3 below for a summary.

Usually $Q$ is unknown, but it can be approximated by the empirical measure
$Q_{n}$ pertaining to a sample $X_{1},\ldots,X_{n},n\in\mathbb{N},$ of
$S-$valued random variables defined on a common probability space
$(\Omega,\mathcal{A},\mathbb{P})$, that is
$Q_{n}:=n^{-1}\sum_{i=1}^{n}\delta_{X_{i}}$, where $\delta_{x}$ denotes the
Dirac-measure at point $x\in S$. Replacing $Q$ in the definition (1) of $M$ by
$Q_{n}$ leads to the empirical counterpart $M_{n}$ given by

$M_{n}(t)=\frac{1}{n}\sum_{i=1}^{n}h(X_{i},t)-h(X_{i},t_{0}),\;t\in\mathbb{R}.$
(4)

Let $X_{1},\ldots,X_{n}$ be independent with common distribution $Q$ and
assume (only for that moment) that (3) holds. Then by the Strong Law of Large
Numbers $M_{n}(t)\rightarrow M(t)\;\mathbb{P}-$almost surely (a.s.) for each
$t\in\mathbb{R}$. Let

$\hat{m}_{n}\text{ be the {smallest minimizing point} of }M_{n}.$

Of course $\hat{m}_{n}$ is also the (smallest) minimiser of $t\mapsto
1/n\sum_{1\leq i\leq n}h(X_{i},t)$. By Corollary 6 of Ferger [5] the estimator
$\hat{m}_{n}$ for $m$ is $\mathcal{A}$-Borel measurable. If $M$ is coercive
and $m$ is unique, then $\hat{m}_{n}$ converges to $m$ a.s. by Theorem 9 of
Ferger [5]. Now it is well known that almost sure convergence is equivalent to
$\lim_{n\rightarrow\infty}\mathbb{P}(\sup_{k\geq n}|\hat{m}_{k}-m|>x)=0$ for
all $x>0$. We will improve this result significantly by showing that here the
tail probabilities of the suprema converge exponentially fast or polynomially
fast, depending on whether a boundedness condition or a moment condition is
satisfied.

The random variable $\hat{m}_{n}$ is called _convex M-estimator_ , because the
pertaining criterion function $M_{n}$ is convex. A first systematic study of
such convex M-estimators based on $M_{n}$ of general type (4) was done by
Habermann (1989) [10] and Niemiro (1992) [18]. Habermann [10] focuses on
consistency and $\sqrt{n}-$ asymptotic normality, whereas Niemiro [18] derives
an asymptotic linearization of $\sqrt{n}(\hat{m}_{n}-m)$ with almost sure
rates of convergence for the remainder term. Moreover, he extends the
consistency results by giving rates of convergence for the tail-probabilities,
confer (20) and Proposition 3 below for details. It should be noted that both
authors more generally consider $M_{n}(t)$ with parameter $t$ running through
the euclidian space $\mathbb{R}^{d}$ with $d\geq 1$ and not only $d=1$ as we
do. An alternative approach to the asymptotic linearization is given by Hjort
and Pollard (1993) [11]. Here, the key idea is to represent
$\sqrt{n}(\hat{m}_{n}-m)$ as a minimizer of the convex process $Z_{n}$, which
arises from $M_{n}$ by
$Z_{n}(t):=n\\{M_{n}(m+n^{-1/2}t)-M_{n}(m)\\},t\in\mathbb{R}^{d}$. Under some
conditions on $h$ and $M$ one has that $Z_{n}$ allows for a decomposition into
a linear part plus a quadratic form and a negligible additive term. Hjort and
Pollard prove an argmin-theorem for such convex stochastic processes and
herewith obtain asymptotic normality, confer also Liese and Mieschke (2008)
[14]. Davis, Knight and Liu (1992) give an extension to general convex
processes $Z_{n}$. In short their argmin-theorem says that if the fidis of the
$Z_{n}$ converge to $Z$ and if $Z$ has a.s. an unique minimizer, $\xi$ say,
then the argmins of $Z_{n}$, $\xi_{n}$ say, converge in distribution to $\xi$.
In a further step of generalization Geyer (1996) [9] considers $Z_{n}$ and $Z$
with values in the extended real line
$\overline{\mathbb{R}}=[-\infty,\infty]$. Geyer’s result brings forth non-
normal limits and normalizing sequences different from $\sqrt{n}$. Here the
uniqueness of $\xi$, the argmin of $Z$, is essential, because $\xi$ acts as
limit variable. If uniqueness is not given, Ferger (2021) [7] shows that the
$\xi_{n}$ converge in distribution to the set of all minimizer $Z$. To explain
this notion of ”distributional convergence to a set” first recall that
classical distributional convergence means that the distributions converge
weakly to a probability measure, namely the distribution of the limit
variable. In case of convergence to a set the limit is no longer a probability
measure, but a _Choquet-capacity_ , which in turn uniquely determines a
_random closed set_. (For the notions of _Choquet-capacity_ and _random closed
set_ we refer to the monograph of Molchanov [16].) The limit of the $\xi_{n}$
is the capacity functional of the random closed set of all minimizers of $Z$.
For unique $\xi$ this capacity functional coincides with the distribution of
$\xi$ and we are back to the usual convergence in distribution.

In contrast to the above asymptotics (mainly for the distributions) the
novelty in this work is that we give upper bounds for the tail probabilities
$\mathbb{P}(\sup_{k\geq n}|\hat{m}_{k}-m|>x),x>0,$ that hold for every finite
sample size $n\in\mathbb{N}$. From these inequalities, we derive $r$-complete
convergence (including rates) and $r$-quick convergence. This is completely
new in convex M-estimation. The concept of $r-$complete convergence was for
$r=1$ as first introduced by Hsu and Robbins (1947) [12] and later on
generalized to $r>0$ by Tartakovsy (1998) [24], confer also Tartakovsky (2023)
[25]. Whereas the mode of $r$-quick convergence goes back to Strassen (1967)
[23].

The paper is organized as follows: In section 2 we derive exponential
inequalities for the suprema $\sup_{k\geq n}|\hat{m}_{k}-m|$. Herewith a
result of Niemiro [18] can be improved substantially (at least for dimension
$d=1$). Section 3 is devoted to the analysis of the criterion function $M$.
The important special case of quantile-estimators is treated in section 4 with
an improvement of Serfling’s [21] inequality. Section 5 contains the above
mentioned results on $r$-complete and $r$-quick convergence, but also many
examples. One of these examples gives an extension of Hoeffdings’s inequality.
Finally, in section 6 we derive the corresponding propositions when instead of
boundedness only a moment-conditions is fulfilled.

##  2 Exponential tail-bounds

In order to derive exponential inequalities for the tail-probabilities of the
suprema we need that the following boundedness-assumption is fulfilled: For
every $x\neq 0$ there exist reals $a(x)<b(x)$ such that

$a(x)\leq D^{+}h(X_{i},m+x)\leq b(x)\text{ a.s. for all }1\leq i\leq n.$ (5)

Let $D^{+}f$ and $D^{-}f$ denote the right-and left derivative of a function
$f:\mathbb{R}\rightarrow\mathbb{R}$. It is well known that $M$ as a convex
function possesses the right and left derivatives, which in addition are non-
decreasing. Moreover, $m\in\mathbb{R}$ is a minimizer of $M$ if and only if

$D^{-}M(m)\leq 0\leq D^{+}M(m).$ (6)

Confer Corollary 7.2 of Ferger [7], where we give a short proof.

Our first main result is as follows:

######  Theorem 1.

Suppose $m\in\mathbb{R}$ satisfies (6). Further assume that
$X_{1},\ldots,X_{n},n\in\mathbb{N}$, are i.i.d. with distribution $Q$ such
that (5) is fulfilled. Then the following exponential inequalities hold for
every $n\in\mathbb{N}$:

$\displaystyle\mathbb{P}(\sup_{k\geq
n}(\hat{m}_{k}-m)>x)\leq\exp\\{-2(b(x)-a(x))^{-2}nD^{+}M(m+x)^{2}\\}\quad\forall\;x>0.$
(7) $\displaystyle\mathbb{P}(\inf_{k\geq
n}(\hat{m}_{k}-m)<-x)\leq\exp\\{-2(b(-x)-a(-x))^{-2}nD^{+}M(m-x)^{2}\\}\quad\forall\;x>0.$
(8) $\displaystyle\mathbb{P}(\sup_{k\geq n}|\hat{m}_{k}-m|>x)\leq
2\exp\\{-2A(x)^{-2}nd(x)^{2}\\}\quad\forall\;x>0,$ (9)

where

$A(x):=\max\\{b(x)-a(x),b(-x)-a(-x)\\}$

and

$d(x):=\min\\{D^{+}M(m+x),-D^{+}(m-x)\\}\geq 0.$

If $m$ is the unique minimizing point of $M$, then actually $d(x)$ is positive
for every $x>0$ and in (7)-(9) we obtain in each case an exponentially fast
rate of convergence.

###### Proof.

For the derivation of (7) first observe that

$\\{\sup_{k\geq n}(\hat{m}_{k}-m)>x\\}=\bigcup_{k\geq
n}\\{\hat{m_{k}}-m>x\\}=\bigcup_{l\geq n}\bigcup_{n\leq k\leq
l}\\{\hat{m_{k}}-m>x\\},$

whence by $\sigma$-continuity from below

$\displaystyle\mathbb{P}(\sup_{k\geq
n}(\hat{m}_{k}-m)>x)=\lim_{l\rightarrow\infty}\mathbb{P}(\bigcup_{n\leq k\leq
l}\\{\hat{m}_{k}-m>x\\}).$ (10)

By Theorem 1 of Ferger [5] we have the following basic equality:
$\\{\hat{m}_{k}>m+x\\}=\\{D^{+}M_{k}(m+x)<0\\}$. Herewith it follows that

$\displaystyle\\{\hat{m}_{k}-m>x\\}$ $\displaystyle=$
$\displaystyle\\{D^{+}M_{k}(m+x)<0\\}$ (11) $\displaystyle=$
$\displaystyle\\{\frac{1}{k}\sum_{i=1}^{k}D^{+}h(X_{i},m+x)<0\\}$
$\displaystyle=$
$\displaystyle\\{\frac{1}{k}\sum_{i=1}^{k}\big{(}D^{+}h(X_{i},m+x)-\mathbb{E}[D^{+}h(X_{i},m+x)]\big{)}<-\mathbb{E}[D^{+}h(X_{i},m+x)]\\}$
$\displaystyle=$
$\displaystyle\\{\frac{1}{k}\sum_{i=1}^{k}-\big{(}D^{+}h(X_{i},m+x)-\mathbb{E}[D^{+}h(X_{i},m+x)]\big{)}>\mathbb{E}[D^{+}h(X_{i},m+x)]\\}$
$\displaystyle=$
$\displaystyle\\{\frac{1}{k}\sum_{i=1}^{k}-\big{(}D^{+}h(X_{i},m+x)-\mathbb{E}[D^{+}h(X_{i},m+x)]\big{)}>D^{+}M(m+x)\\},$

where the last equality holds, because $\mathbb{E}[D^{+}h(X_{i},t)]=D^{+}M(t)$
for all $t\in\mathbb{R}$ according to Proposition 2.4 of Ferger [7] upon
noticing that the $D^{+}h(X_{i},t)$ are integrable by (5). Put
$\xi_{i}:=\xi_{i}(x,m):=-\big{(}D^{+}h(X_{i},m+x)-\mathbb{E}[D^{+}h(X_{i},m+x)]\big{)},i\in\mathbb{N}$.
Then $(\xi_{i})_{i\in\mathbb{N}}$ is a sequence of i.i.d. integrable real
random variable. If

$T_{k}:=\frac{1}{k}\sum_{i=1}^{k}\xi_{i}\quad\text{and}\quad\mathcal{G}_{k}:=\sigma(T_{j}:j\geq
k),\;k\in\mathbb{N},$

then by Example 6.5.5 (c) in Gänssler and Stute [8] the sequence
$(T_{k},\mathcal{G}_{k})_{k\in\mathbb{N}}$ is a reverse martingale, confer
also Example 3 on p. 241 in Chow and Teicher [2]. Infer from the monotonicity
of $D^{+}M$ and (6) that $\eta:=D^{+}M(m+x)\geq D^{+}M(m)\geq 0$ is non-
negative. Thus with (11) we obtain for every $l\geq n$:

$\displaystyle\bigcup_{n\leq k\leq l}\\{\hat{m}_{k}-m>x\\}$ $\displaystyle=$
$\displaystyle\bigcup_{n\leq k\leq l}\\{T_{k}>\eta\\}=\bigcup_{1\leq j\leq
l-n+1}\\{T_{l-j+1}>\eta\\}$ $\displaystyle=$ $\displaystyle\bigcup_{1\leq
j\leq l-n+1}\\{e^{hT_{l-j+1}}>e^{h\eta}\\}$ $\displaystyle=$
$\displaystyle\\{\max_{1\leq j\leq
l-n+1}e^{hT_{l-j+1}}>e^{h\eta}\\}\quad\forall\;h>0.$ (13)

The reversing of time in (2) leads to the martingale
$(T_{l-j+1},\mathcal{G}_{l-j+1})_{1\leq j\leq l-n+1}$. Since $x\mapsto
e^{hx},x\in\mathbb{R}$, is convex for each $h>0$, it follows that
$(e^{hT_{l-j+1}},\mathcal{G}_{l-j+1})_{1\leq j\leq l-n+1}$ is a non-negative
sub-martingale. Hence Doob’s maximal-inequality yields that

$\mathbb{P}\big{(}\max_{1\leq j\leq l-n+1}e^{hT_{l-j+1}}>e^{h\eta}\big{)}\leq
e^{-h\eta}\mathbb{E}[e^{hT_{n}}]\quad\forall\;h>0.$

Notice that the upper bound here does not depend on $l\geq n$. Therefore by
(10) and (13) we arrive at

$\mathbb{P}(\sup_{k\geq n}(\hat{m_{k}}-m)>x)\leq
e^{-h\eta}\mathbb{E}[e^{hT_{n}}]\quad\forall\;h>0.$ (14)

If $S_{n}:=\sum_{i=1}^{n}\xi_{i}$, then
$\mathbb{E}[e^{hT_{n}}]=\mathbb{E}[e^{uS_{n}}]$, where $u:=h/n>0$. By
definition $\xi_{i}=\rho_{i}-\mathbb{E}[\rho_{i}]$, where
$\rho_{i}=-D^{+}h(X_{i},m+x),i\in\mathbb{N}$, whence
$-b(x)\leq\rho_{i}\leq-a(x)$ a.s. for all $1\leq i\leq n$ by the boundedness
assumption (5). Now it follows from Hoeffding’s lemma, confer, e.g., Lemma 2.6
in Massart (2007) [15] that

$\mathbb{E}[e^{uS_{n}}]\leq
e^{\frac{1}{8}nu^{2}(a(x)-b(x))^{2}}\quad\forall\;u>0.$

Consequently we obtain with (14) that

$\mathbb{P}(\sup_{k\geq n}(\hat{m}_{k}-m)>x)\leq
e^{-h\eta+\frac{1}{8}\frac{h^{2}}{n}(b(x)-a(x))^{2}}\quad\forall\;h>0.$ (15)

An elementary minimization of the upper bound with respect to $h$ results in
$h_{0}=\frac{4n\eta}{(b(x)-a(x))^{2}}$ as minimizer, which is positive, if
$\eta$ is positive. Substituting $h_{0}$ into the upper bound on the right-
hand side of (15) gives

$\mathbb{P}(\sup_{k\geq n}(\hat{m_{k}}-m)>x)\leq
e^{-\frac{2}{(b(x)-a(x))^{2}}n\eta^{2}},$

which is inequality (7). In case that $\eta=0$ taking the limit $h\downarrow
0$ in (15) yields $1$ as (trivial) upper bound in accordance with (7). As to
the derivation of inequality (8) one analogously starts with

$\mathbb{P}(\inf_{k\geq
n}(\hat{m_{k}}-m)<-x)=\lim_{l\rightarrow\infty}\mathbb{P}(\bigcup_{n\leq k\leq
l}\\{\hat{m_{k}}-m<-x\\}).$ (16)

Now it is true that

$\displaystyle\\{\hat{m}_{k}-m<-x\\}\subseteq\\{\hat{m}_{k}-m\leq-x\\}=\\{\hat{m}_{k}\leq
m-x\\}$ (17) $\displaystyle=$ $\displaystyle\\{D^{+}M_{k}(m-x)\geq 0\\}$
$\displaystyle=$
$\displaystyle\\{\frac{1}{k}\sum_{i=1}^{k}D^{+}h(X_{i},m-x)-\mathbb{E}[D^{+}h(X_{i},m-x)]\big{)}\geq-D^{+}M(m-x)\\},$
(18)

where the equality in (17) holds by Theorem 1 of Ferger [5]. Put
$\eta:=-D^{+}M(m-x)$. Since $m-x<m$, it follows from Theorem 24.1 in
Rockafellar that $D^{+}M(m-x)\leq D^{-}M(m)$. But $D^{-}M(m)\leq 0$ by (6),
whence $\eta\geq 0$. From here on, the rest of the proof of (8) is completely
analogous to the one above.

Finally, the third inequality (9) follows from what we have shown so far,
because

$\\{\sup_{k\geq n}|\hat{m}_{k}-m|>x\\}=\\{\sup_{k\geq
n}(\hat{m}_{k}-m)>x\\}\cup\\{\inf_{k\geq n}(\hat{m_{k}}-m)<-x\\}.$ (19)

It remains to prove the last part of the theorem. For that purpose assume that
there exists some positive $x$ such that $d(x)=0$, so that $D^{+}M(m+x)=0$ or
$D^{+}M(m-x)=0$. In the first case it follows by monotonicity that
$D^{+}M(z)=0$ for all $z\in[m,m+x]$. Since the set of points at which $D^{+}M$
and $D^{-}M$ coincide lies dense in $\mathbb{R}$, we find a point
$z\in(m,m+x)$ with $D^{-}M(z)=D^{+}M(z)=0$. Consequently $z$ is a further
minimizer of $M$ by (6), in contradiction to the uniqueness of $m$. In the
second case notice that $0=D^{+}M(m-x)\leq D^{-}M(m-x/2)\leq D^{-}M(m)\leq 0$,
where the first inequality holds by Theorem 24.1 of Rockafellar [20]. Thus
$D^{-}M(z)=0$ for all $z\in[m-x/2,m]$ and one can argue as in the first case
to arrive at a contradiction to the uniqueness of $m$. Herewith the proof is
complete. ∎

Assume that $m$ is unique. Niemiro in Theorem 3 [18] shows that for every
$x>0$ there exist constants $\alpha(x)>0$ and $K(x)$ such that

$\mathbb{P}(|\hat{m}_{n}-m|>x)\leq
K(x)\exp\\{-\alpha(x)n\\}\quad\forall\;x>0\quad\forall\;n\in\mathbb{N}.$ (20)

Comparing this with inequality (9) one sees that the constants can be
identified: $K(x)=2$ and $\alpha(x)=2\\{d(x)/A(x)\\}^{2}>0$. But actually more
remarkable is that our inequality even applies to the larger tail-
probabilities for the suprema, $\mathbb{P}(\sup_{k\geq
n}|\hat{m}_{k}-m|>x)\geq\mathbb{P}(|\hat{m}_{n}-m|>x)$, namely:

$\mathbb{P}(\sup_{k\geq n}|\hat{m}_{k}-m|>x)\leq
2\exp\\{-\alpha(x)n\\}\quad\forall\;x>0\quad\forall\;n\in\mathbb{N}.$ (21)

This is a significant improvement of Niemiro’s result (20). On the other hand
Niemiro in comparison to our boundedness-assumption (5) merely requires the
existence of a moment generating function. More precisely, he requires there
exists some $x_{0}>0$ such that for every $x\in[-x_{0},x_{0}]$ there exists
some $\theta_{0}=\theta_{0}(x)>0$ so that

$\mathbb{E}[\exp\\{\theta
D^{+}M(X_{1},m+x)\\}]<\infty\quad\forall\;\theta\in(0,\theta_{0}).$ (22)

We will see that a result of type (21) still holds under the weaker
requirement (22).

To do this, note that that under (22) all moments of the random variables
$D^{+}M(X_{1},m+x),|x|\leq x_{0}$, exist and are finite, confer, e.g.,
Billingsley [1], p.285. In particular, the $\xi_{i}=\xi_{i}(x)$ in the above
proof of Theorem 1 are integrable. Therefore we may apply (14) with
$h=n\theta$ and $0<\theta<\theta_{0}$. It gives:

$\mathbb{P}(\sup_{k\geq n}(\hat{m_{k}}-m)>x)\leq
e^{-n\theta\eta}\mathbb{E}[e^{\theta
S_{n}}]=e^{-n\theta\eta}\varphi_{x}(\theta)^{n},$ (23)

where $\varphi_{x}(\theta)=\mathbb{E}[\exp\\{\theta\xi_{1}(x)\\}]$ is the
common moment generating function of the $\xi_{i}(x)$. Letting
$\kappa_{x}(\theta):=\log\varphi_{x}(\theta)$ we arrive at

$\mathbb{P}(\sup_{k\geq
n}(\hat{m_{k}}-m)>x)\leq\exp\\{-n(\eta\theta-\kappa_{x}(\theta)\\}\quad\forall\;x\in(0,x_{0}].$

Recall from Theorem 1 that $\eta=\eta_{x}=D^{+}M(m+x)$ is positive as long as
$x$ is positive. Thus Lemma 2.7.2 of Durrett [4] yields that the factor
$\eta\theta-\kappa_{x}(\theta)=:\beta_{1}(x)$ is positive provided $\theta$ is
sufficiently small, say $\theta\leq\theta_{1}(x)$ for some positive
$\theta_{1}(x)$. In summary we get:

$\mathbb{P}(\sup_{k\geq
n}(\hat{m_{k}}-m)>x)\leq\exp\\{-\beta_{1}(x)n\\}\quad\forall\;x\in(0,x_{0}]\quad\forall\;n\in\mathbb{N}.$
(24)

Analogously it follows that there exists some positive $\beta_{2}(x)$ such
that

$\mathbb{P}(\inf_{k\geq
n}(\hat{m_{k}}-m)<-x)\leq\exp\\{-\beta_{2}(x)n\\}\quad\forall\;x\in(0,x_{0}]\quad\forall\;n\in\mathbb{N}.$
(25)

Combining (19) with the above inequalities (24) and (25) finally results in

$\mathbb{P}(\sup_{k\geq n}|\hat{m_{k}}-m|>x)\leq
2\exp\\{-\beta(x)n\\}\quad\forall\;x\in(0,x_{0}]\quad\forall\;n\in\mathbb{N},$
(26)

where $\beta(x)=\min\\{\beta_{1}(x),\beta_{2}(x)$ is positive. If we replace
$\beta(x)$ by $\beta(x\wedge x_{0})$, then the inequality holds actually for
all $x>0$. Thus we have indeed shown the counterpart of inequality (21), but
under the assumption (22), which is weaker than the boundedness-assumption (5)
used in the derivation of (21).

##  3 Existence and uniqueness of $m$

In this section, we summarise results from Ferger [7] about analytical
properties of M and its _minimum set_ $A(M)$, in terms of its existence,
characterisation and uniqueness. Here,
$A(f):=\\{t\in\mathbb{R}:f(t)=\inf_{s\in\mathbb{R}}f(s)\\}$ is the set of all
minimizing arguments of an arbitrary function
$f:\mathbb{R}\rightarrow\mathbb{R}$.

If condition (2) holds, then for each fixed real number $t_{0}$ the pertaining
criterion function $M$ in (1) exists and is real-valued for each
$t\in\mathbb{R}$. Moreover $M:\mathbb{R}\rightarrow\mathbb{R}$ is convex and

$D^{\pm}M(t)=\int_{S}D^{\pm}h(x,t)Q(dx)\text{ for every }t\in\mathbb{R}.$ (27)

For each distribution $Q$ the minimum set is given by

$\displaystyle A(M)$ $\displaystyle=$
$\displaystyle\\{m\in\mathbb{R}:D^{-}M(m)\leq 0\leq D^{+}M(m)\\}$ (28)
$\displaystyle=$ $\displaystyle\\{m\in\mathbb{R}:\int_{S}D^{-}h(x,t)Q(dx)\leq
0\leq\int_{S}D^{+}h(x,t)Q(dx)\\}.$ (29)

In particular, $Q_{n}$ instead of $Q$ yields $A(M_{n})$. In the further course
we consider the rich subclass of estimators induced by bivariate functions of
the type $h:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$ given through

$h(x,t)=v(t-x)\text{ where }v:\mathbb{R}\rightarrow\mathbb{R}\text{ is
convex}.$ (30)

Furthermore, for the sake of simplicity, we consider only $t_{0}=0$. So let

$M(t)=\int_{\mathbb{R}}v(t-x)-v(-x)Q(dx)$

with general probability measure $Q$. Notice that (27) reduces to

$D^{\pm}M(t)=\int_{S}D^{\pm}v(t-x)Q(dx)\text{ for every }t\in\mathbb{R}.$ (31)

If $v$ is not only convex but coercive with $D^{-}v(0)\leq 0\leq D^{+}v(0)$,
(which means that $0$ is a minimizer of $v$), then $M$ is coercive and
Argmin$(M)$ is a non-empty compact interval. In particular, $m\in$ Argmin$(M)$
exists. For $Q$ symmetric at $m\in\mathbb{R}$, i.e., $X_{1}-m$ and $m-X_{1}$
are equal in distribution, one has that $m\in A(M)\neq\emptyset$ provided $v$
is convex and even. In both cases, if in addition $v$ is differentiable on
$\mathbb{R}\setminus\\{0\\}$ and $F$ is continuous on Argmin$(M)$, then
Argmin$(M)$ is non-empty and given by

$\displaystyle\text{Argmin}(M)$ $\displaystyle=$
$\displaystyle\\{m\in\mathbb{R}:\int_{\mathbb{R}}D^{-}v(m-x)Q(dx)=0=\int_{\mathbb{R}}D^{+}v(m-x)Q(dx)\\}$
(32) $\displaystyle=$
$\displaystyle\\{m\in\mathbb{R}:\int_{\mathbb{R}\setminus\\{m\\}}v^{\prime}(m-x)Q(dx)=0\\}.$
(33)

Finally, Argmin$(M)=\\{m\\}$ is a singleton in case that $v$ is strictly
convex. For $v$ differentiable on the entire real line the continuity
assumption on $F$ can be dropped and the integral in (33) is over the entire
space $\mathbb{R}$ rather than over $\mathbb{R}\setminus\\{m\\}$.

In summary, it can be said that under strict convexity (and the above
requirements), a unique minimizing point exists and this results as the
solution of the integral equation $\int_{\mathbb{R}}v^{\prime}(m-x)Q(dx)=0$ or
$\int_{\mathbb{R}\setminus\\{m\\}}v^{\prime}(m-x)Q(dx)=0$, according as $v$ is
differentiable at zero or not.

##  4 Quantile estimators

Before we come to the conclusions of our theorem, we would first like to
illustrate it with an important example. For a given $\alpha\in(0,1)$ define
$v(u):=v_{\alpha}(u):=u(1_{\\{u\geq 0\\}}-\alpha)$. The one-sided derivatives
are given by $D^{+}v(u)=1_{\\{u\geq 0\\}}-\alpha$ and
$D^{-}v(u)=1_{\\{u>0\\}}-\alpha$, so that by (31) one obtains
$D^{+}M(t)=F(t)-\alpha$ and $D^{-}M(t)=F(t-)-\alpha$, where $F$ is the
distribution function of $Q$ and $F(t-)$ is the left-limit of $F$ at point
$t\in\mathbb{R}$. It follows from (28) that $A(M)$ is equal to the set of all
$\alpha$-quantiles $q_{\alpha}$ of $F$. Similarly, if $F_{n}$ is the empirical
distribution function of the sample $X_{1},\ldots,X_{n}$, then
$\hat{m}_{n}=F^{-1}_{n}(\alpha)$ with $F^{-1}$ denoting the quantile function
(general inverse) of any distribution function $F$. The boundedness assumption
is fulfilled with $b(x)=1-\alpha$ and $a(x)=-\alpha$, so that $b(x)-a(x)=1$.
Moreover $d(x)=\min\\{F(q_{\alpha}+x)-\alpha,\alpha-F(q_{\alpha}-x)\\}$. If
$q_{\alpha}$ is unique we obtain from Theorem 1 that $d(x)$ is positive and

$\mathbb{P}(\sup_{k\geq n}|F^{-1}_{k}(\alpha)-F^{-1}(\alpha)|>x)\leq
2e^{-2nd(x)^{2}}\quad\forall\;x>0.$ (34)

Serfling [21] shows in Theorem 2.3.2 that

$\mathbb{P}(|F^{-1}_{n}(\alpha)-F^{-1}(\alpha)|>x)\leq
2e^{-2nd(x)^{2}}\quad\forall\;x>0.$ (35)

In view of $\sup_{k\geq
n}|F^{-1}_{k}(\alpha)-F^{-1}(\alpha)|\geq|F^{-1}_{n}(\alpha)-F^{-1}(\alpha)|$
our inequality (34) is significantly sharper than Serfling’s inequality (35)
with the same bound. In Corollary 2.3.2 Serfling [21] gives the following
supremal-inequality:

$\mathbb{P}(\sup_{k\geq
n}|F^{-1}_{k}(\alpha)-F^{-1}(\alpha)|>x)\leq\frac{2}{1-\rho(x)}e^{-2nd(x)^{2}}\quad\forall\;x>0,$
(36)

where $\rho(x)=e^{-2d(x)^{2}}$. We see that not only $2<\frac{2}{1-\rho(x)}$
for all $x>0$, but also that $\frac{2}{1-\rho(x)}\uparrow\infty$ as
$x\downarrow 0$. The reason for this lies in that Serfling argues as follows:

$\displaystyle\mathbb{P}(\sup_{k\geq n}|F^{-1}_{k}(\alpha)-F^{-1}(\alpha)|>x)$
$\displaystyle=$ $\displaystyle\mathbb{P}(\bigcup_{k\geq
n}\\{|F^{-1}_{k}(\alpha)-F^{-1}(\alpha)|>x\\})$ $\displaystyle\leq$
$\displaystyle\sum_{k\geq n}\mathbb{P}(|F^{-1}_{k}(\alpha)-F^{-1}(\alpha)|>x)$
$\displaystyle\leq$ $\displaystyle 2\sum_{k\geq
n}(e^{-2d(x)^{2}})^{k}\quad\text{by }(\ref{S})$

and the geometric sum does the rest. Obviously the upper bound in (4) based on
the $\sigma$-subadditivity of $\mathbb{P}$ is far from doing the same thing as
Doob’s maximal-inequality for martingale does in our proof.

##  5 Conclusions in the general framework

The boundedness requirement (5) is intended to apply to the entire section,
without further constant mention of it.

We can conclude from Theorem 1 that the suprema $\sup_{k\geq
n}|\hat{m}_{k}-m|,n\in\mathbb{N},$ of the distances converge completely to
$0$, provided $m$ is unique, that is

$\sum_{n=1}^{\infty}\mathbb{P}(\sup_{k\geq
n}|\hat{m}_{k}-m|>x)<\infty\quad\text{for all }x>0.$ (38)

This implies that $\sup_{k\geq n}|\hat{m}_{k}-m|\rightarrow 0$ a.s. from which
in turn we can conclude the a.s. convergence of $\hat{m}_{n}$ to $m$.

In fact one can upgrade the complete convergence (38) substantially under the
assumption that there exist positive constants $c$ and $\delta$ such that

$|D^{+}M(m+x)|\geq c\;|x|\quad\forall\;x\in[-\delta,\delta].$ (39)

In Lemma 1 below we give a very huge class of examples, where the above
inequality (39) is fulfilled.

######  Corollary 1.

Suppose that in (5) the one-sided limits of the lower and upper bounds $a$ and
$b$ at $0$ exist and are finite. If $D^{+}M$ meets the requirement (39), then

$n^{\gamma}\;\sup_{k\geq n}|\hat{m}_{k}-m|$

_converges $r$-completely _to $0$ for all $r>0$, whenever $\gamma<1/2$, that
is by definition

$\sum_{n=1}^{\infty}n^{r-1}\mathbb{P}\big{(}n^{\gamma}\sup_{k\geq
n}|\hat{m}_{k}-m|>\epsilon\big{)}<\infty\quad\forall\;\epsilon>0.$ (40)

We write

$\sup_{k\geq n}|\hat{m}_{k}-m|=o(n^{-\gamma})\;\mathbb{P}\text{-r
completely}.$ (41)

###### Proof.

If $x\in(0,\delta]$, then $D^{+}M(m+x)\geq D^{+}M(m)\geq 0$, whence
$D^{+}M(m+x)=|D^{+}M(m+x)|\geq c|x|=cx$. If $x\in[-\delta,0)$, then
$D^{+}M(m+x)\leq D^{-}M(m)\leq 0$, where the first inequality holds by Theorem
24.1 of Rockafellar [20]. Consequently, $-D^{+}M(m+x)=|D^{+}M(m+x)|\geq
c|x|=c(-x)$. Replacing $x$ by $-x$ yields that $-D^{+}M(m-x)\geq cx$ for all
$x\in(0,\delta]$. This shows that $d(x)=\min\\{D^{+}M(m+x),-D^{+}(m-x)\\}$
satisfies

$d(x)\geq c\;x\quad\forall\;0<x\leq\delta.$ (42)

Put $x_{n}:=x_{n}(\epsilon):=\epsilon n^{-\gamma}$. Then by Theorem 1

$\mathbb{P}\big{(}n^{\gamma}\sup_{k\geq
n}|\hat{m}_{k}-m|>\epsilon\big{)}=\mathbb{P}\big{(}\sup_{k\geq
n}|\hat{m}_{k}-m|>x_{n}\big{)}\leq
2e^{-\frac{2}{A(x_{n})^{2}}nd(x_{n})^{2}}\quad\forall\;n\in\mathbb{N}.$ (43)

W.l.o.g. $\gamma>0$. Deduce from $x_{n}\downarrow 0$ that
$A(x_{n})\rightarrow\max\\{b(0+)-a(0+),b(0-)-a(0-)\\}=:A_{0}$, where w.l.o.g.
$A_{0}$ is positive. Indeed, in (5) we may replace for instance the upper
bound $b(x)$ by $b(x)+1$ resulting in $A_{0}>1$. Thus there exists an integer
$n_{0}$ such that $\frac{2}{A(x_{n})^{2}}\geq\frac{1}{A_{0}^{2}}$ for all
$n\geq n_{0}$. Moreover, $x_{n}\in(0,\delta]$ for all $n\geq n_{1}$ with some
$n_{1}\in\mathbb{N}$, whence we can conclude from (42) that
$\frac{2}{A(x_{n})^{2}}nd(x_{n})^{2}\geq\frac{nc^{2}x_{n}^{2}}{A_{0}^{2}}=L\epsilon^{2}n^{1-2\gamma}$
for every $n>n_{2}=\max\\{n_{0},n_{1}\\}\in\mathbb{N}$, where
$L=c^{2}/A_{0}^{2}$ is a positive constant. It follows with (43) that

$\sum_{n=1}^{\infty}n^{r-1}\mathbb{P}\big{(}n^{\gamma}\sup_{k\geq
n}|\hat{m}_{k}-m|>\epsilon\big{)}\leq\sum_{n=1}^{n_{2}}n^{r-1}+2\sum_{n>n_{2}}n^{r-1}e^{-L\epsilon^{2}n^{1-2\gamma}}<\infty\quad\forall\;\epsilon>0$

and for all $r>0$, since $1-2\gamma>0$. ∎

Since complete convergence $(r=1)$ implies almost sure convergence, one can
conclude from (41) that $\sup_{k\geq n}|\hat{m}_{k}-m|=o(n^{-\gamma})$ a.s.
for all $\gamma<1/2$. Our next result concerns the limit case $\gamma=1/2$,
which involves an additional logarithmic factor. In fact the rate is
$O(n^{-1/2}\sqrt{\log n})$. Actually, we can show a bit more:

######  Corollary 2.

Under the assumptions of Corollary 1 it follows that there exists a
deterministic real constant $K>0$ such that with probability one

$\sup_{k\geq n}|\hat{m}_{k}-m|\leq Kn^{-1/2}\sqrt{\log n}\quad\text{ for
eventually all }n\in\mathbb{N}.$

###### Proof.

Put $x_{n}:=Kn^{-1/2}\sqrt{\log n}$. By Theorem 1

$\mathbb{P}\big{(}\sup_{k\geq n}|\hat{m}_{k}-m|>x_{n}\big{)}\leq
2e^{-\frac{2}{A(x_{n})^{2}}nd(x_{n})^{2}}\quad\forall\;n\in\mathbb{N}.$ (44)

Since $x_{n}\downarrow 0$ it follows as in the above proof that there exists
some integer $n_{0}$ such that $\frac{2}{A(x_{n})^{2}}nd(x_{n})^{2}\geq
A_{0}^{-2}nc^{2}x_{n}^{2}=A_{0}^{-2}c^{2}K^{2}\log n$ for all $n\geq n_{0}$.
Thus with the inequality (44) we obtain

$\sum_{n\geq n_{0}}\mathbb{P}\big{(}\sup_{k\geq
n}|\hat{m}_{k}-m|>x_{n}\big{)}\leq 2\sum_{n\geq
n_{0}}n^{-c^{2}K^{2}/A_{0}^{2}}<\infty,$

if $K>A_{0}/c$. Now an application of the 1. Borel-Cantelli Lemma gives the
desired result. ∎

In the further course, we deal with _$r-$ quick convergence_, which goes back
to Strassen (1967) [23]. For real random variables $Z$ and
$Z_{n},n\in\mathbb{N}$, and $\epsilon>0$ one considers the random set of
indices $\mathbb{I}_{\epsilon}:=\\{k\in\mathbb{N}:|Z_{k}-Z|>\epsilon\\}$.
Define $L_{\epsilon}:=\sup\mathbb{I}_{\epsilon}$, if $\mathbb{I}_{\epsilon}$
is non-empty and bounded. Then $L_{\epsilon}\in\mathbb{I}_{\epsilon}$, whence
$L_{\epsilon}+1$ is the first index from which the sequence
$(Z_{n})_{n\in\mathbb{N}}$ eventually stays in the region
$[Z-\epsilon,Z+\epsilon]$. It may happen that the sequence from the start lies
in $[Z-\epsilon,Z+\epsilon]$, that is $\mathbb{I}_{\epsilon}=\emptyset$. Then
$L_{\epsilon}:=0$ describes this situation in a suitable way. Finally, in case
that $\mathbb{I}_{\epsilon}$ is unbounded, that is the sequence lies outside
the interval $[Z-\epsilon,Z+\epsilon]$ infinitely often, then
$L_{\epsilon}:=\infty$ fits. Now for $r>0$ the sequence
$(Z_{n})_{n\in\mathbb{N}}$ _converges $\mathbb{P}-r-$quickley to_ $Z$, if
$\mathbb{E}[L_{\epsilon}^{r}]<\infty$ for all $\epsilon>0$. This is denoted by
$Z_{n}\rightarrow Z\;\mathbb{P}-r-$quickley. The following relation follows
from the definition of $L_{\epsilon}$. It holds for every positive real number
$z$.

$L_{\epsilon}<z\quad\Longleftrightarrow\quad\sup_{k\geq[z]}|Z_{k}-Z|\leq\epsilon,$
(45)

where $[z]:=\min\\{k\in\mathbb{Z}:k\geq z\\}$.

######  Corollary 3.

If $m\in\mathbb{R}$ is the unique minimizer of $M$, then
$\hat{m}_{n}\rightarrow m\;\mathbb{P}-r-$quickley for all $r>0$.

###### Proof.

Since

$\displaystyle\mathbb{P}(L_{\epsilon}^{r}\geq n)$ $\displaystyle=$
$\displaystyle\mathbb{P}(L_{\epsilon}\geq n^{1/r})$ $\displaystyle=$
$\displaystyle\mathbb{P}(\sup_{k\geq[n^{1/r}]}|\hat{m}_{k}-m|>\epsilon)\quad\text{by
}(\ref{rel})$ $\displaystyle\leq$ $\displaystyle
2\exp\\{-2A(\epsilon)^{-2}[n^{1/r}]d(\epsilon)^{2}\\}\quad\text{by Theorem
}\ref{expb}$ $\displaystyle\leq$ $\displaystyle
2\exp\\{-2A(\epsilon)^{-2}n^{1/r}d(\epsilon)^{2}\\}\quad\text{by }[z]\geq z,$

it follows for each positive $\epsilon$ that $\sum_{n\geq
1}\mathbb{P}(L_{\epsilon}^{r}\geq n)<\infty$, because $A(\epsilon)^{-2}>0$ and
$d(\epsilon)>0$ by uniqueness of $m$ as was shown in the proof of Theorem 1.
From the convergence of the series we can conclude that
$\mathbb{E}[L_{\epsilon}^{r}]<\infty$ for all $\epsilon>0$, which gives the
desired result. ∎

Next notice that $nD^{+}M(m+x)^{2}=\delta_{n}(x)^{2}$, where the functions
$\delta_{n}(x)=\sqrt{n}D^{+}M(m+x),n\in\mathbb{N},$ play a crucial role in the
distributional convergence of the M-estimators $\hat{m}_{n}$. In fact in
Theorem 3.4 of Ferger [7] we show the following result:

Suppose $D^{+}M(m)=0=D^{-}M(m)$ and
$\sigma^{2}:=\mathbb{E}[D^{+}h(X_{1},m)^{2}]\in(0,\infty)$. Further assume
that $(a_{n})_{n\in\mathbb{N}}$ is a positive sequence converging to infinity
such that

$\delta_{n}(x/a_{n})=\sqrt{n}D^{+}M(m+x/a_{n})\rightarrow\delta(x)\;\text{ for
all }x\in\mathbb{R}.$ (46)

Then $\delta:\mathbb{R}\rightarrow[-\infty,\infty]$ is increasing with
$\delta\geq 0$ on $[0,\infty)$, $\delta\leq 0$ on $(-\infty,0)$ and
$\delta(0)=0$. Notice that $\delta$ can take the values $-\infty$ or $\infty$.
In view of Smirnov’s [22] results for quantile esimators it is assumed that
there are the following four types of limit functions. To introduce them put
$I_{\delta}=\\{t\in\mathbb{R}:-\infty<\delta(t)<\infty\\}$. We say that
$\delta$ is of type 1, 2, 3 or 4 according as $I_{\delta}$ is equal to
$[0,\infty),(-\infty,0],(-\infty,\infty)$ or $[-c_{1},c_{2}]$, respectively,
where $c_{1},c_{2}\geq 0$ and $\max\\{c_{1},c_{2}\\}>0$. Moreover, the
$\delta$’s of type 1-3 are supposed to be continuous and strictly increasing
on $I_{\delta}$, and $\delta$ of type 4 is assumed to be equal to zero on
$(-c_{1},c_{2})$ with finite one-sided limits at the end-points, which
necessarily are equal to zero. In Theorem 3.4 [7] we obtain:

$\lim_{n\rightarrow\infty}\mathbb{P}(a_{n}(\hat{m}_{n}-m)\leq
x)=\Phi_{\sigma}(\delta(x))=:H(x)\quad\text{for all continuity points }x\text{
of }H,$ (47)

where $\Phi_{\sigma}$ is the distribution function of the centred normal
distribution $N(0,\sigma^{2})$ with variance $\sigma^{2}$. Notice that the
discontinuity points $x$ of $H$ are exactly the boundary points of
$I_{\delta}$, i.e., $x=0$ for $\delta$ of type $1$ or $2$ and
$x\in\\{-c_{1},c_{2}\\}$ for $\delta$ of type $4$, whereas for $\delta$ of
type $3$ all $x\in\mathbb{R}$ are continuity points of $H$. If $\delta$ is of
type 1 or 3, then $H$ is a distribution function. In the other two cases, $H$
can be modified to a distribution function by redefining $H(0):=1$ for type 2
and $H(-c_{1}):=1/2,H(c_{2}):=1$ for type 4, so that the convergence (47)
still holds. This shows that $a_{n}(\hat{m}_{n}-m)$ converges in distribution
to a random variable $V\sim H$.

Further conclusions from Theorem 1 are the following asymptotic tail bounds:

######  Corollary 4.

Under the assumptions of Theorem 1 suppose that $(a_{n})_{n\in\mathbb{N}}$
satisfies condition (46).

  * (1)

If the right limits $\alpha_{+}:=a(0+)\in\mathbb{R}$ and
$\beta_{+}:=b(0+)\in\mathbb{R}$ of $a$ and $b$ at $0$ exist, then

$\limsup_{n\rightarrow\infty}\mathbb{P}(a_{n}\sup_{k\geq
n}(\hat{m}_{k}-m)>x)\leq\exp\\{-2(\beta_{+}-\alpha_{+})^{-2}\delta(x)^{2}\\}\quad\forall\;x>0.$

  * (2)

If the left limits $\alpha_{-}:=a(0-)\in\mathbb{R}$ and
$\beta_{-}:=b(0-)\in\mathbb{R}$ of $a$ and $b$ at zero exist, then

$\limsup_{n\rightarrow\infty}\mathbb{P}(a_{n}\inf_{k\geq
n}(\hat{m}_{k}-m)<x)\leq\exp\\{-2(\beta_{-}-\alpha_{-})^{-2}\delta(x)^{2}\\}\quad\forall\;x<0.$

  * (3)

If the right and left limits of $a$ and $b$ at $0$ exist, then

$\limsup_{n\rightarrow\infty}\mathbb{P}(a_{n}\sup_{k\geq
n}|\hat{m}_{k}-m|>x)\leq
2\exp\\{-2\tau^{-2}\Delta(x)^{2}\\}\quad\forall\;x>0,$

where $\tau=\max\\{\beta_{+}-\alpha_{+},\beta_{-}-\alpha_{-}\\}$ and
$\Delta(x)=\min\\{\delta(x),-\delta(-x)\\}$.

###### Proof.

We apply inequalities (7) and (9) with $x$ replaced by $x/a_{n}$ and
inequality (8) with $x$ replaced by $-x/a_{n}$. Then taking the limit
$n\rightarrow\infty$ yields the result upon noticing (46). ∎

######  Remark 3.

If $|\delta(x)|\rightarrow\infty,|x|\rightarrow\infty$, then it follows from
the above corollary that

$\lim_{x\rightarrow\infty}\limsup_{n\rightarrow\infty}\mathbb{P}(a_{n}\sup_{k\geq
n}|\hat{m}_{k}-m|>x)=0.$

Thus the sequence $(a_{n}\sup_{k\geq n}|\hat{m}_{k}-m|)_{n\in\mathbb{N}}$ is
tight and hence by Prokorov’s Theorem it is relatively compact. Since $|\sup
S|\leq\sup|S|$ and $|\inf S|\leq\sup|S|$ for every non-empty
$S\subseteq\mathbb{R}$, it follows that the sequences
$(a_{n}\sup_{k\geq n}(\hat{m}_{k}-m))_{n\in\mathbb{N}}$ and $(a_{n}\inf_{k\geq
n}(\hat{m}_{k}-m))_{n\in\mathbb{N}}$ are relatively compact as well. Given
this, we conjecture that these three sequences actually converge in
distribution.

In the sequel we consider bivariate functions $h(x,t)=v(t-x)$ with convex
$v:\mathbb{R}\rightarrow\mathbb{R}$. As it becomes clear further below, it is
convenient to construct the functions $v$ as follows: Let
$\varphi:\mathbb{R}\rightarrow\mathbb{R}$ be a nondecreasing and right-
continuous function. Then

$v(u):=v_{\varphi}(u):=\int_{0}^{u}\varphi(s)ds,\;u\in\mathbb{R},$ (48)

is convex, confer e.g. section 1.6 in Niculescu and Persson [17].
Consequently, we can apply our results from section 3. By Theorem 24.2 in
Rockafellar [20] $D^{-}v(u)=\varphi(u-)$ and
$D^{+}v(u)=\varphi(u+)=\varphi(u)$ by right continuity. Thus the requirement
$D^{-}v(0)\leq 0\leq D^{+}v(0)$ is the same as $\varphi(0-)\leq
0\leq\varphi(0).$ Moreover, $v_{\varphi}$ is differentiable at a point
$u\in\mathbb{R}$ if and only if $\varphi$ is continuous at $u$. Typically, but
not necessarily, the graph of $\varphi$ is roughly $S$-shaped, that is
$\varphi$ is a sigmoid function, which is everywhere continuous, except with a
possible jump at zero. If actually $\varphi(u)<0$ for all $u<0$ and
$\varphi(u)>0$ for all $u>0$ (in brief $\varphi<>0$), then $v_{\varphi}$ is
strictly convex and $m$ is unique. It satisfies the equation
$\int_{\mathbb{R}}\varphi(m-s)Q(ds)=0$. Analogously, the estimator
$\hat{m}_{n}$ is also unique and given as the solution $t=\hat{m}_{n}$ of
$\int_{\mathbb{R}}\varphi(t-s)Q_{n}(ds)=0$. Since
$D^{+}h(X_{i},m+x)=\varphi(m+x-X_{i})$, the boundedness assumption (5) is
fulfilled, whenever $\varphi$ is bounded. Then a possible choice are the
constant functions $a(x)=\inf_{u\in\mathbb{R}}\varphi(u)$ and
$b(x)=\sup_{u\in\mathbb{R}}\varphi(u)$. If $\varphi$ is unbounded, but has an
inverse $\varphi^{-1}$, then we need that the $X_{i}$ are bounded, say $A\leq
X_{i}\leq B$ for some constants $A<B$. In fact in that case (5) is satisfied
with $a(x)=\varphi(m+x-B)$ and $b(x)=\varphi(m+x-A)$ as one can easily verify.

Our first example is simple, but it yields a surprising result.

######  Example 1.

(Hoeffding) Let $\varphi(u)=u$. Then
$0=\int\varphi(m-s)Q(ds)=m-\mathbb{E}[X_{1}]$, whence
$m=\mathbb{E}[X_{1}]=:\mu$. Replacing $Q$ by $Q_{n}$ gives the estimator
$\hat{m}_{n}=\bar{X}_{n}:=1/n\sum_{i=1}^{n}X_{i}$, the arithmetic mean of the
data. Moreover, $D^{+}M(m+x)=\int_{\mathbb{R}}\varphi(m+x-s)Q(ds)=m+x-\mu=x$.
If $A\leq X_{i}\leq B$ for every $1\leq i\leq n$, then $b(x)-a(x)=B-A$. Thus
for instance the exponential inequality (9) in Theorem 1 reduces to

$\mathbb{P}\Big{(}\sup_{k\geq
n}|\hat{m}_{k}-m|>x\Big{)}=\mathbb{P}\Big{(}\sup_{k\geq
n}|\bar{X}_{k}-\mu|>x\Big{)}\leq 2\exp\\{-2(B-A)^{-2}nx^{2}\\}.$ (49)

Compare this with Hoeffding’s inequality:

$\mathbb{P}\Big{(}|\bar{X}_{n}-\mu|>x\Big{)}\leq
2\exp\\{-2(B-A)^{-2}nx^{2}\\}.$

We see that in Hoeffding’s inequality one can replace $|\bar{X}_{n}-\mu|$ by
the much larger variable $\sup_{k\geq
n}|\bar{X}_{k}-\mu|\geq|\bar{X}_{n}-\mu|$ while maintaining the same
exponential bound. This is a substantial extension of Hoeffding’s result.

When certain symmetries are present, the inequality (9) simplifies.

######  Remark 4.

(Symmetric case) Assume that $Q$ is symmetric at $m\in\mathbb{R}$ and
$\varphi<>0$ is an odd function in the sense that $\varphi(-u)=-\varphi(u)$
for every $u\neq 0$. Then $v_{\varphi}$ is even (and strictly convex).
Therefore $m$ is the unique minimizer of $M$. Moreover,

$\displaystyle D^{+}M(m-x)$ $\displaystyle=$
$\displaystyle\mathbb{E}[\varphi(m-x-
X_{1})]=-\mathbb{E}[\varphi(-m+x+X_{1})]=-\mathbb{E}[\varphi(m+x-X_{1})]$
$\displaystyle=$ $\displaystyle-D^{+}(m+x)\quad\forall\;x\in\mathbb{R}.$

If in addition $\varphi(0)=0$, i.e., $\varphi(-u)=-\varphi(u)$ for all
$u\in\mathbb{R}$, then $a(-x)=-b(x)$ and $b(-x)=-a(x)$ for all $x>0$, whence
$A(x)=b(x)-a(x)$ and $d(x)=D^{+}M(m+x)$. In summary we get

$\mathbb{P}(\sup_{k\geq n}|\hat{m}_{k}-m|>x)\leq
2\exp\\{-2(b(x)-a(x))^{-2}nD^{+}M(m+x)^{2}\\}\quad\forall\;x>0.$

If $\varphi$ is bounded, then the constant $2(b(x)-a(x))^{-2}$ can be replaced
by $\frac{1}{2}||\varphi||^{-2}$, where $||\varphi||$ is the sup-norm of
$\varphi$.

Recall the assumption (39), which was pivotal for the speed of $r-$complete
convergence. Suppose $\varphi$ is differentiable on $\mathbb{R}$ with bounded
derivative, i.e., $||\varphi^{\prime}||<\infty$. If $D^{+}M(m)=0$, then

$\displaystyle D^{+}M(m+x)$ $\displaystyle=$ $\displaystyle
D^{+}M(m+x)-D^{+}M(m)=\int_{\mathbb{R}}\varphi(m+x-s)-\varphi(m-s)Q(ds)$ (50)
$\displaystyle=$
$\displaystyle\int_{\mathbb{R}}\frac{\varphi(m+x-s)-\varphi(m-s)}{x}Q(ds)\;x.$

Since the integrand in the last integral (50) is dominated by
$||\varphi^{\prime}||$, it follows from the Dominated Convergence Theorem that

$\int_{\mathbb{R}}\frac{\varphi(m+x-s)-\varphi(m-s)}{x}Q(ds)\rightarrow\int_{\mathbb{R}}\varphi^{\prime}(m-s)Q(ds),\;x\rightarrow
0.$ (51)

Assume that $\varphi^{\prime}$ is positive, i.e., $\varphi^{\prime}(u)>0$ for
all $u\in\mathbb{R}$. Then the integral on the right side of (51) is positive.
Indeed, the integrand $\varphi^{\prime}(m-s)\geq 0$ for all $s\in\mathbb{R}$,
because $\varphi$ is monotone increasing. Suppose the integral is equal to
zero. Then $\varphi^{\prime}(m-s)=0$ for $Q-$almost all $s\in\mathbb{R}$. In
particular, there exists some $s\in\mathbb{R}$ such that
$\varphi^{\prime}(m-s)=0$ in contradiction to positiveness of
$\varphi^{\prime}$. Infer from (51) that

$\int_{\mathbb{R}}\frac{\varphi(m+x-s)-\varphi(m-s)}{x}Q(ds)\geq\frac{1}{2}\int_{\mathbb{R}}\varphi^{\prime}(m-s)Q(ds)\quad\forall\;x\in[-\delta,\delta]$
(52)

for some $\delta$ sufficiently small. Combining (50) with (52) leads to the
following

######  Lemma 1.

Assume that $\varphi$ in (48) has a positive and bounded derivative
$\varphi^{\prime}$ and that $D^{+}M(m)=0$. Then there exists a real $\delta>0$
such that

$|D^{+}M(m+x)|\geq c\;|x|\quad\forall\;x\in[-\delta,\delta],$ (53)

where $c=\frac{1}{2}\int_{\mathbb{R}}\varphi^{\prime}(m-s)Q(ds)$ is positive.
(In fact the constant $\frac{1}{2}$ can be replaced by any constant strictly
smaller than $1$.)

Finally, we would like to determine the crucial function

$K(x):=D^{+}M(m+x)=\int_{\mathbb{R}}\varphi(m+x-s)Q(ds),\;x\in\mathbb{R}.$
(54)

We have already seen two examples. The $\alpha-$quantile arises from
$\varphi(u)=1_{\\{u\geq 0\\}}-\alpha$, which yields
$D^{+}M(m+x)=F(m+x)-\alpha$. And $\varphi(u)=u$ induces $D^{+}M(m+x)=x$ as
shown in Example 1.

The following observation is very useful, because it makes the integral in
(54) in some situations analytically tractable. Namely, if $Q$ has a Lebesgue-
density $f$, then $K(x)=\varphi\star f(m+x)$, where $\star$ denotes the
convolution-operator. Thus by the Differentiation-Lemma (which can be applied
for instance if $||\varphi^{\prime}||<\infty$) it follows that

$K^{\prime}(x)=\varphi^{\prime}\star f(m+x).$ (55)

Consequently, $K(x)=\int\varphi^{\prime}\star f(m+x)dx+C$ is the primitive,
where the integration constant $C$ is uniquely determined by the constrained
$K(0)=0$.

######  Example 2.

(Normal) Assume $F=\Phi_{\mu,\sigma^{2}}$ is the distribution function of the
normal law $N(\mu,\sigma^{2})$ with pertaining density

$\phi_{\mu,\sigma^{2}}(s)=\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp\\{-\frac{(s-\mu)^{2}}{2\sigma^{2}}\\}.$

Let $\varphi(u)=\Phi(u)-1/2$ with $\Phi:=\Phi_{0,1}$. Then $m=\mu$ according
to Remark 4 and

$K(x)=\int_{\mathbb{R}}(\Phi_{0,1}(\mu+x-s)-1/2)N(\mu,\sigma^{2})(ds)=\int_{\mathbb{R}}(\Phi_{0,1}(\mu+x-s)-1/2)\phi_{\mu,\sigma^{2}}(s)ds.$

By the Differentiation-Lemma

$K^{\prime}(x)=\int_{\mathbb{R}}\phi_{0,1}(\mu+x-s)\phi_{\mu,\sigma^{2}}(s)ds=\phi_{0,1}\star\phi_{\mu,\sigma^{2}}(\mu+x)=\phi_{\mu,1+\sigma^{2}}(\mu+x)=\phi_{0,1+\sigma^{2}}(x),$

where the second last equality is the additive property of the normal
distribution. Integration yields

$D^{+}M(m+x)=\Phi\Big{(}\frac{x}{\sqrt{1+\sigma^{2}}}\Big{)}-1/2.$

######  Example 3.

(Cauchy) Let $F=F_{a}$ be the Cauchy-distribution function with location
parameter $a\in\mathbb{R}$ and let $\varphi=F_{0}-1/2$. Then by symmetry
$m=a$. Using the additive property of the Cauchy-distribution, the same
arguments as in the example above lead to

$D^{+}M(m+x)=\frac{1}{\pi}\arctan(x).$

######  Example 4.

(Uniform) For reals $a<b$ let $F$ be the distribution function of $U(a,b)$,
the uniform distribution on $[a,b]$. Consider $\varphi=\Phi-1/2$, so that by
symmetry $m=(a+b)/2$. Furthermore, if $\phi:=\phi_{0,1}$, then

$K^{\prime}(x)=\int_{\mathbb{R}}\phi(m+x-s)U(a,b)(ds)=\frac{1}{b-a}\int_{a}^{b}\phi(m+x-s)ds=\frac{1}{b-a}\int_{m+x-b}^{m+x-a}\phi(u)du.$

Consequently,
$K^{\prime}(x)=\frac{1}{b-a}\\{\Phi(m+x-a)-\Phi(m+x-b)\\}=\frac{1}{b-a}\\{\Phi(x+(b-a)/2)-\Phi(x-(b-a)/2)\\}$.
Now, the primitive of $\Phi(s)$ is equal to $H(s):=s\Phi(s)+\phi(s)$ as one
can easily verify by differentiation. Thus

$K(x)=\frac{1}{b-a}\\{H(x+(b-a)/2)-H(x-(b-a)/2)\\}-1/2,$

where the constant $1/2$ arises from the constraint $K(0)=0$.

######  Example 5.

As already seen $\varphi(u)=1_{\\{u\geq 0\\}}-1/2$ corresponds to the median
($\alpha=1/2$). This is a simple step function with value $-1/2$ on
$(-\infty,0)$ and $1/2$ on $[0,\infty)$. We change this discontinuous function
to a continuous function. For $c>0$ let $\varphi_{c}=\varphi$ outside the
interval $[-c,c]$ and on that interval let $\varphi_{c}$ be the straight line
connecting the points $(-c,-1/2)$ and $(c,1/2)$ i.e.,
$\varphi_{c}(u)=\frac{1}{2c}u,u\in[-c,c]$. Assume $Q$ is symmetric at $0$.
From Remark 4 we know that $m=0$. Thus by (54)

$\displaystyle D^{+}M(x)=\int_{\mathbb{R}}\varphi_{c}(x-s)Q(ds)$
$\displaystyle=$
$\displaystyle\int_{(-\infty,x-c]}1/2Q(ds)-\int_{(x+c,\infty)}1/2Q(ds)+\frac{1}{2c}\int_{(x-c,x+c]}x-sQ(ds)$
$\displaystyle=$ $\displaystyle
1/2F(x-c)-1/2(1-F(x+c))+\frac{1}{2c}x(F(x+c)-F(x-c))-\frac{1}{2c}\int_{x-c}^{x+c}sF(ds).$

Integration by parts yields

$\int_{x-c}^{x+c}sF(ds)=(x+c)F(x+c)-(x-c)F(x-c)-\int_{x-c}^{x+c}F(s)ds,$

so that after some simple algebra we arrive at

$D^{+}M(x)=\frac{1}{2c}\int_{x-c}^{x+c}F(s)ds-\frac{1}{2}.$ (56)

If for instance $F=\Phi$, then

$\int_{x-c}^{x+c}F(s)ds=\int_{x-c}^{x+c}\Phi(s)ds=(x+c)\Phi(x+c)-(x-c)\Phi(x-c)+\phi(x+c)-\phi(x-c).$

This is so, because the primitive of $\Phi(s)$ is equal to $s\Phi(s)+\phi(s)$
as we know from from Example 4.

Observe that $\frac{1}{2c}\int_{x-c}^{x+c}F(s)ds\rightarrow F(x)$ as
$c\rightarrow 0$, which leads us back to $D^{+}M(x)=F(x)-1/2$ pertaining to
the median.

Our next example combines the median and the mean. It goes back to Huber [13],
confer also Serfling [21], p.247.

######  Example 6.

(Huber) Assume that $Q$ is symmetric at $0$. For some fixed $c>0$ put

$\varphi(u):=\left\\{\begin{array}[]{l@{\quad,\quad}l}-c&u<c\\\ u&|u|\leq c\\\
c&u>c\end{array}\right.$

Again according to Remark 4 we have that $m=0$ and similarly as in the example
before one obtains:

$D^{+}M(x)=\int_{x-c}^{x+c}F(s)ds-c.$

######  Example 7.

Let $\varphi(u):=u/\sqrt{1+u^{2}},u\in\mathbb{R},$ and $Q$ be the uniform
distribution on $[-1,1]$. Then $m=0$ and

$D^{+}M(x)=\int_{\mathbb{R}}\varphi(x-s)Q(ds)=\frac{1}{2}\int_{-1}^{1}\varphi(x-s)ds=\frac{1}{2}\int_{x-1}^{x+1}u/\sqrt{1+u^{2}}du$

by substitution $u=x-s$. Now check that $\sqrt{u^{2}+1}$ is the primitive of
$u/\sqrt{1+u^{2}}$, whence we obtain:

$D^{+}M(x)=\frac{1}{2}\Big{(}\sqrt{(x+1)^{2}+1}-\sqrt{(x-1)^{2}+1}\Big{)}$

.

##  6 Polynomial bounds under moment-conditions

Assume that instead of the boundedness condition (5) we only have that
$D^{+}h(X_{1},\cdot)$ possesses $s$-th absolute moments in an arbitrarily
small neighborhood of $m$. More precisely let $s\geq 1$ and suppose that there
exists some $x_{0}>0$ such that:

$R_{s}(x):=\mathbb{E}[|D^{+}h(X_{1},m+x)|^{s}]<\infty\quad\text{for all
}x\in[-x_{0},x_{0}].$ (57)

######  Theorem 2.

If (57) holds with $s\geq 2$ and $m$ is unique, then there exist positive real
constants $B_{s}$ such that for all $x\in(0,x_{0}]$ the following inequalities
hold:

$\displaystyle\mathbb{P}(\sup_{k\geq n}(\hat{m}_{k}-m)>x)\leq
2^{s}B_{s}R_{s}(x)\big{(}D^{+}M(m+x)\big{)}^{-s}n^{-s/2},$ (58)
$\displaystyle\mathbb{P}(\inf_{k\geq n}(\hat{m}_{k}-m)<-x)\leq
2^{s}B_{s}R_{s}(x)\big{(}-D^{+}M(m-x)\big{)}^{-s}n^{-s/2},$ (59)
$\displaystyle\mathbb{P}(\sup_{k\geq n}|\hat{m}_{k}-m|>x)\leq
2^{s+1}B_{s}\mu_{s}(x)d(x)^{-s}n^{-s/2},$ (60)

where

$d(x)=\min\\{D^{+}M(m+x),-D^{+}M(m-x)\\}>0,\;\mu_{s}(x)=\max\\{R_{s}(x),R_{s}(-x)\\}<\infty.$

###### Proof.

We begin with the proof of (58). Recall that $\eta=D^{+}M(m+x)$ is positive by
Theorem 1. (The proof of this fact does not use the boundedness assumption.)
From (2) it follows that

$\displaystyle\mathbb{P}(\bigcup_{n\leq k\leq l}\\{\hat{m}_{k}-m>x\\})$
$\displaystyle=$ $\displaystyle\mathbb{P}(\bigcup_{1\leq j\leq
l-n+1}\\{T_{l-j+1}>\eta\\})=\mathbb{P}(\bigcup_{1\leq j\leq
l-n+1}\\{|T_{l-j+1}|^{s}>\eta^{s}\\})$ (61) $\displaystyle=$
$\displaystyle\mathbb{P}(\max_{1\leq j\leq l-n+1}|T_{l-j+1}|^{s}>\eta^{s})$
$\displaystyle\leq$
$\displaystyle\eta^{-s}\mathbb{E}[|T_{n}|^{s}]\qquad\qquad\text{ by Doob's
inequality, because }\eta\text{ is positive}$ $\displaystyle=$
$\displaystyle\eta^{-s}n^{-s}\mathbb{E}[|\sum_{i=1}^{n}\xi_{i}(x)|^{s}].$

Since

$\displaystyle|\xi_{i}(x)|^{s}$ $\displaystyle=$
$\displaystyle|D^{+}h(X_{i},m+x)-\mathbb{E}[D^{+}h(X_{i},m+x)]|^{s}\leq
2^{s-1}\\{|D^{+}h(X_{i},m+x)|^{s}+|\mathbb{E}[D^{+}h(X_{i},m+x)]|^{s}\\}$
$\displaystyle\leq$ $\displaystyle
2^{s-1}\\{|D^{+}h(X_{i},m+x)|^{s}+\mathbb{E}[|D^{+}h(X_{i},m+x)|^{s}]\\}\qquad\text{
by Jensen's inequality},$

it follows that

$\mathbb{E}[|\xi_{i}(x)|^{s}]\leq
2^{s}\mathbb{E}[|D^{+}h(X_{i},m+x)|^{s}]=2^{s}R_{s}(x)<\infty\quad\text{ by
}(\ref{rm}).$ (62)

For $s>2$ a combination of Hölder’s inequality with the Marcinkiewicz-Zygmund
inequality yields, confer, e.g., (1.5) in Ferger (2014) [6]:

$\mathbb{E}[|\sum_{i=1}^{n}\xi_{i}(x)|^{s}]\leq
B_{s}n^{s/2}\mathbb{E}[|\xi_{1}(x)|^{s}].$ (63)

For $s=2$ the above inequality holds (with $B_{2}=1$) by Bienaymé’s equality.
Thus (61) - (63) together with (10) result in inequality (58). For the
derivation of (59) we can start with (16) and (18), which make us to proceed
as above, because $\eta:=-D^{+}M(m-x)$ is positive by Theorem 1. Finally, the
third inequality (60) follows from (19), (58) and (59). ∎

In the following we derive the counterparts of Corollaries 1, 3 and 4. As to
the first one we use a uniform version of the moment-condition (57):

$L:=L_{s}:=\sup_{|x|\leq x_{0}}\mathbb{E}[|D^{+}h(X_{1},m+x)|^{s}]<\infty.$
(64)

######  Corollary 5.

Suppose (39) is fulfilled and (64) holds with $s>2$. Then

$\sup_{k\geq n}|\hat{m}_{k}-m|=o(n^{-\gamma})\;\;\mathbb{P}\text{-r completely
for all }\gamma<\frac{1}{2}\;\text{ and for all }r<(1/2-\gamma)s.$ (65)

###### Proof.

Put $x_{n}:=\epsilon n^{-\gamma}$. From the proof of Corollary 1 we know that
$d(x)\geq cx$ for all $x\in(0,\delta]$, confer (42). If (65) is valid for some
$\gamma$, then a fortiori for each smaller one. Thus we may assume that
$\gamma>0$. Then there exists an integer $n_{0}$ such that
$0<x_{n}\leq\min\\{\delta,x_{0}\\}$. Infer from Theorem 2 that

$\displaystyle\mathbb{P}(n^{\gamma}\sup_{k\geq n}|\hat{m}_{k}-m|>\epsilon)$
$\displaystyle=$ $\displaystyle\mathbb{P}(\sup_{k\geq
n}|\hat{m}_{k}-m|>x_{n})\leq 2^{s+1}B_{s}d(x_{n})^{-s}\mu_{s}(x_{n})n^{-s/2}$
$\displaystyle\leq$ $\displaystyle
2^{s+1}B_{s}c^{-s}x_{n}^{-s}Ln^{-s/2}=D\epsilon^{-s}n^{s(\gamma-1/2)},$

with constant $D=2^{s+1}B_{s}c^{-s}L$. Thus we arrive at

$\sum_{n\geq n_{0}}n^{r-1}\mathbb{P}(n^{\gamma}\sup_{k\geq
n}|\hat{m}_{k}-m|>\epsilon)\leq D\epsilon^{-s}\sum_{n\geq
n_{0}}n^{r-1+s(\gamma-1/2)}<\infty,$

because the exponent $r-1+s(\gamma-1/2)<-1$. This completes our proof. ∎

Of course $\gamma<0$ or $r<1$ are uninteresting. The extreme constellation
$\gamma=0$ and $r=1$ gives complete and in particularly a.s. convergence. Note
that our assumptions cover this case, since $(1/2-\gamma)s=s/2>r=1$. To obtain
the convergence rate $o(n^{-\gamma})$ with positive $\gamma$ the order $s$ in
the uniform moment-condition (64) must be sufficiently high, namely
$s>1/(1/2-\gamma)$.

######  Corollary 6.

If $m\in\mathbb{R}$ is the unique minimizer of $M$ and (57) holds for some
$s>2$, then $\hat{m}_{n}\rightarrow m\;\mathbb{P}$-r quickley for all
$r\in(0,s/2)$.

###### Proof.

Using the equivalence (45) it follows from Theorem 2 that

$\mathbb{P}(L_{\epsilon}^{r}\geq
n)=\mathbb{P}(\sup_{k\geq[n^{1/r}]}|\hat{m}_{k}-m|>\epsilon)\leq
2^{s+1}B_{s}d(\epsilon)^{-s}\mu_{s}(\epsilon)n^{-\frac{s}{2r}},$

whence $\sum_{n\geq 1}\mathbb{P}(L_{\epsilon}^{r}\geq n)<\infty$ for all
$\epsilon\in(0,x_{0}]$. If $\epsilon>x_{0}$, then $L_{\epsilon}\leq L_{x_{0}}$
and so the series is finite actually for all $\epsilon>0$, which in turn
ensures that $\mathbb{E}[L_{\epsilon}^{r}]<\infty$ for every $\epsilon>0$ as
desired. ∎

Finally, the counterpart of Corollary 4 reads as follows:

######  Corollary 7.

Assume that (64) holds with $s\geq 2$ and that $m$ is unique. If the sequence
$(a_{n})$ satisfies (46), then there exists a positive constant $K_{s}$ such
that:

$\displaystyle\limsup_{n\rightarrow\infty}\mathbb{P}(a_{n}\sup_{k\geq
n}(\hat{m}_{k}-m)>x)\leq K_{s}\delta(x)^{-s}\quad\forall\;x>0.$ (66)
$\displaystyle\limsup_{n\rightarrow\infty}\mathbb{P}(a_{n}\inf_{k\geq
n}(\hat{m}_{k}-m)<x)\leq K_{s}(-\delta(x))^{-s}\quad\forall\;x<0.$ (67)
$\displaystyle\limsup_{n\rightarrow\infty}\mathbb{P}(a_{n}\sup_{k\geq
n}|\hat{m}_{k}-m|>x)\leq 2K_{s}\Delta(x)^{2}\quad\forall\;x>0,$ (68)

where $\Delta(x)=\min\\{\delta(x),-\delta(-x)\\}$.

###### Proof.

The proof follows from Theorem 2, where $K_{s}=2^{s}B_{s}L_{s}$. ∎

As a consequence, the conjecture we made in Remark 3 is also appropriate here.

Our last result yields Niemiro’s [18] Theorem 2, however only for dimension
$d=1$. We state it here, because in comparison to Niemiro our proof is really
short.

######  Proposition 3.

Suppose $m\in\mathbb{R}$ is the unique minimizer of $M$ and (57) holds for
some $s>1$. Then, for every $x>0$,

$\mathbb{P}(\sup_{k\geq n}|\hat{m}_{k}-m|>x)=o(n^{-s+1}),\quad
n\rightarrow\infty.$

###### Proof.

Observe that

$\displaystyle\mathbb{P}(\sup_{k\geq n}(\hat{m}_{k}-m)>x)$ $\displaystyle=$
$\displaystyle\mathbb{P}(\bigcup_{k\geq
n}\\{\hat{m}_{k}-m>x\\})=\mathbb{P}(\bigcup_{k\geq n}\\{T_{k}>\eta\\})$
$\displaystyle\leq$ $\displaystyle\mathbb{P}(\sup_{k\geq
n}|\frac{1}{k}\sum_{i=1}^{k}\xi_{i}|>\eta)=o(n^{-s+1}),$

where the second equality holds by (11) and the last equality follows from
Theorem 28 in Petrov [19] taking into account the equivalence of (4.1) and
(4.4) in Theorem 27 in [19]. Analogously, one obtains that

$\mathbb{P}(\inf_{k\geq n}(\hat{m}_{k}-m)<-x)=o(n^{-s+1}),$

whence the assertion follows from (19). ∎

Let $\hat{m}_{n}$ be the largest minimizing point of $M_{n}$. Then all results
above remain valid with $D^{+}M$ and $D^{+}h$ replaced by $D^{-}M$ and
$D^{-}h$, respectively. This is the case due to the second part of Theorem 1
of Ferger [5].

## References

  * [1] P. Billingsley, Probability and Measure (Second Edition), New York, Chichester, Brisbane, Toronto, Singngapore: John Wiley & Sons, 1986.
  * [2] Y. S. Chow and H. Teicher, Probability Theory. Independence, Interchangeability, Martingales (Third Edition), New York: Springer-Verlag, 1997.
  * [3] R. A. Davis, K. Knight and J. Liu, M-estimation for autoregressions with infinite variance, Stochastic Process. Appl. 40 (1992), 145–180.
  * [4] R. Durrett, Probability: Theory and Examples (Fifth Edition), Cambridge University Press, 2019.
  * [5] D. Ferger, On semi-continuity and continuity of the smallest and largest minimizing point of real convex functions with applications in probability and statistics, arXiv:2306.08358 https://doi.org/10.48550/arXiv.2306.08358.
  * [6] D. Ferger, Optimal constants in the Marcinkiewicz-Zygmund inequalities, Statist. Probab. Lett. 84 (2014), 96–101.
  * [7] D. Ferger, Distributional hyperspace-convergence of Argmin-sets in convex M-estimation, Theor. Probability and Math. Statist. 109 (2023), 3–35. https://doi.org/10.1090/tpms/1195
  * [8] P. Gänssler and W. Stute, Wahrscheinlichkeitstheorie, Berlin, Heidelberg, Germany: Springer-Verlag, 1977.
  * [9] J. Geyer, On the asymptotics of convex stochastic optimization, Unpublished manuscript (1996).
  * [10] S. J. Habermann, Concavity and estimation, Ann. Statist. 17 (1989), 1631–1661.
  * [11] N. L. Hjort and D. Pollard, Asymptotic for minimizers of convex processes, Preprint, Dept. of Statistics, Yale University (1993). arxiv:1107.3806v1
  * [12] P. L. Hsu and H. Robbins, Complete convergence and the law of large numbers. Proceedings of the National Academy of Sciences of the United States of America 33 (1947), 25–31.
  * [13] P. J. Huber, Robust estimation of a location parameter, Ann. Math. Statist. 35 (1964), 73–101.
  * [14] F. Liese and K.-J. Mieschke, Statistical Decision Theory, New York: Springer Science+Business Media, LLC, 2008.
  * [15] P. Massart, Concentration Inequalities and Model Selection (J. Picard, ed.), Berlin, Heidelberg, Germany: Springer-Verlag, 2007.
  * [16] I. Molchanov, Theory of Random Closed Sets (Second Edition), London: Springer-Verlag.
  * [17] C. P. Niculescu and L.-E. Persson, Convex Functions and Their Applications: A Contemporary Approach, New York: Springer Science+Business Media, Inc., 2006.
  * [18] W. Niemiro, Asymptotic for M-estimators defined by convex minimization, Ann. Statist. 20 (1992), 1514–1533.
  * [19] V.V. Petrov, Sums of independend random variables, Berlin, Heidelberg, New York: Springer-Verlag.
  * [20] R. T. Rockafellar, Convex Analysis, Princeton, New Jersey: Princeton University Press, 1970.
  * [21] R. J. Serfling, Approximation Theorems of Mathematical Statistics, New York, Chichester, Brisbane, Toronto, Singapore: John Wiley & Sons, 1980.
  * [22] N. V. Smirnov, Limit distributions for the terms of a variational series, Mathematical Society Translations, 67, 1952.
  * [23] V. Strassen, Almost sure behavior of sums of independent random variables and martingales, In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Volume II, Part I: Probability Theory (L. Le Cam, J. Neyman, ed.) 315–343. Berkley, Los Angeles: University of California Press, 1967.
  * [24] A. G. Tartakovsky, Asymptotic optimality of certain multihypothesis sequential tests: Non-i.i.d. case, Stat. Inference Stoch. Process 1 1998, 265–295.
  * [25] A. G. Tartakovsky, Quick and Complete Convergence in the Law of Large Numbers with Applications to Statistics, Mathematics 11 2023, 1–30. https://doi.org/10.3390/math11122687