\documentclass[a4paper]{amsart}

\usepackage[utf8]{inputenc}
%\usepackage[french,english]{babel}
\usepackage{amsthm, amssymb, amsmath, amsfonts}
\usepackage{url}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\subset}{\subseteq}
\newcommand{\mcl}{\mathcal}
\newcommand{\mb}{\mathbf}
\newcommand{\mbx}{\mathbf{X}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\EE}{\mathbf{E}}
\newcommand{\EEo}{\mathbf{E}^\omega}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\N}{\mathbb{N}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\LL}{\mathbb{L}}
\newcommand{\1}{\mathbf{1}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\PP}{\mathbf{P}}
\newcommand{\PPo}{\mathbf{P}^\omega}
\newcommand{\ov}{\overline}
\newcommand{\td}{\tilde}
\newcommand{\eps}{\varepsilon}
\def\d{{\mathrm{d}}}
\newcommand{\mclN}{\mathcal{N}}
\newcommand{\var}{\mathbb{V}\mathrm{ar}}
\newcommand{\mfk}{\mathfrak}
\renewcommand{\ll}{\left}
\newcommand{\rr}{\right}
\renewcommand{\phi}{\varphi}

\renewcommand{\theequation}{\thesection .\arabic{equation}}

\title[Rate of convergence in the martingale central limit theorem]{On the rate of convergence in the martingale central limit theorem}
\author{Jean-Christophe Mourrat}

\address{Ecole polytechnique fédérale de Lausanne, institut de mathématiques, station 8, 1015 Lausanne, Switzerland}

\begin{document}
%
\begin{abstract}
Consider a discrete-time martingale, and let $V^2$ be its normalized quadratic variation. As $V^2$ approaches $1$ and provided some Lindeberg condition is satisfied, the distribution of the rescaled martingale approaches the Gaussian distribution. For any $p \ge 1$, \cite{ha88} gives a bound on the rate of convergence in this central limit theorem, that is the sum of two terms, say $A_p + B_p$, where up to a constant, $A_p = {\|V^2-1\|}_p^{p/(2p+1)}$. We discuss here the optimality of this term, focusing on the restricted class of martingales with bounded increments. In this context, \cite{bo} sketches a strategy to prove optimality for $p = 1$. Here, we extend this strategy to any $p \ge 1$, thus justifying the optimality of the term $A_p$. As a necessary step, we also provide a new bound on the rate of convergence in the central limit theorem for martingales with bounded increments that improves on the term $B_p$, 
generalizing another result of \cite{bo}.

\bigskip
\noindent \textsc{MSC 2010:} 60F05, 60G42.

\bigskip
\noindent \textsc{Keywords:} Martingale, central limit theorem, rate of convergence.

\end{abstract}
%
\maketitle
%
%
%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%
\section{introduction}
\label{s:intro}
\setcounter{equation}{0}

Let $\mb{X} = (X_1,\ldots,X_n)$ be a sequence of square-integrable random variables such that for any $i$, $X_i$ satisfies $\E[X_i \ | \ \mcl{F}_{i-1}] = 0$, where $\mcl{F}_i$ is the $\sigma$-algebra generated by $(X_1,\ldots,X_i)$. In other words, $\mbx$ is a square-integrable martingale difference sequence. Following the notation of \cite{bo}, we write $M_n$ for the set of all such sequences of length $n$, and introduce
$$
s^2(\mb{X}) = \sum_{i = 1}^n \E[X_i^2],
$$
$$
V^2(\mb{X}) = s^{-2}(\mbx) \ \sum_{i = 1}^n \E[X_i^2 \ | \ \mcl{F}_{i-1}],
$$
$$
S(\mb{X}) = \sum_{i = 1}^n X_i.
$$
One may call $V^2(\mb{X})$ the normalized quadratic variation of $\mb{X}$. 
Let $(\mb{X}_n)_{n \in \N}$ be such that for any $n$, $\mb{X}_n \in M_n$. It is well known (see for instance \cite[Section~7.7.a]{durrett}) that if
\begin{equation}
\label{convprob}
V^2(\mb{X}_n) \xrightarrow[n \to + \infty]{\text{(prob.)}} 1
\end{equation}
and some Lindeberg condition is satisfied, then the rescaled sum $S(\mb{X}_n)/s(\mb{X}_n)$ converges in distribution to a standard Gaussian random variable, that is to say:
\begin{equation}
\label{tcl}
\forall t \in \R, \quad \P[S(\mb{X}_n)/s(\mb{X}_n) \le t ] \xrightarrow[n \to +\infty]{} \Phi(t),	
\end{equation}
where $\Phi(t) = (2\pi)^{-1/2} \int_{-\infty}^t e^{-x^2/2} \ \d x$.

\medskip

We are interested in bounds on the speed of convergence in this central limit theorem. Several results have been obtained under a variety of additional assumptions. One natural way to strengthen the convergence in probability (\ref{convprob}) is to change it for a convergence in $L^p$ for some $p \in [1,+\infty]$. Quantitative estimates in terms of $\|V^2 - 1 \|_p$ seem indeed particularly convenient when one wants to apply the result to practical situations. Let us write
$$
D(\mbx) = \sup_{t \in \R} \big| \P[S(\mb{X})/s(\mb{X}) \le t ] - \Phi(t) \big|,
$$
and 
$$
\|\mb{X}\|_p = \max_{1 \le i \le n} \|X_i\|_p \qquad (p \in [1,+\infty]).
$$
\cite{ha88} proves the following result. 
\begin{thm}[\cite{ha88}]
\label{t:ha}
Let $p \in [1 , +\infty)$. There exists a constant $C_{p} > 0$ such that, for any $n \ge 1$ and any $\mbx \in M_n$, one has
\begin{equation}
\label{eq:ha}
D(\mbx) \le C_{p} \left({\|V^2(\mbx)-1\|}_p^{p} + s^{-2p}(\mbx) \sum_{i = 1}^n {\|X_i\|}_{2p}^{2p} \right)^{1/(2p+1)}.
\end{equation}
\end{thm}
In \cite{joos}, Theorem~\ref{t:ha} is generalized to the following.
\begin{thm}
Let $p \in [1,+\infty]$ and $p' \in [1,+\infty)$. There exists $C_{p,p'} > 0$ such that for any $n \ge 1$ and any $\mbx \in M_n$, one has
\begin{equation}
\label{eq:joos}
D(\mbx) \le C_{p,p'} \left[{\|V^2(\mbx)-1\|}_p^{p/(2p+1)} + \left(s^{-2p'}(\mbx) \sum_{i = 1}^n {\|X_i\|}_{2p'}^{2p'}\right)^{1/(2p'+1)} \right].	
\end{equation}
\end{thm}
One should unerstand that $p/(2p+1) = 1/2$ for $p = + \infty$. In fact, a stronger, non-uniform bound is given ; we refer to \cite[Theorem~2.2]{joos} (or equivalently, to \cite{pubjoos}) for details. 

The main question that is addressed here concerns the optimality of the term ${\|V^2(\mbx)-1\|}_p^{p/(2p+1)}$ appearing in the r.h.s.\ of (\ref{eq:ha}) or (\ref{eq:joos}). About this, \cite{ha88} constructs a sequence of elements $\mbx_n \in M_n$ such that
\begin{itemize}
\item  $s(\mbx_n) \simeq \sqrt{n}$,
\item  $D(\mbx_n) \simeq \log^{-1/2}(n)$,
\item $\displaystyle {\|V^2(\mbx)-1\|}_p^{p} \simeq s^{-2p}(\mbx) \ {\|\mbx\|}^{2p}_{2p} \simeq s^{-2p}(\mbx) \sum_{i = 1}^n {\|X_i\|}_{2p}^{2p} \simeq \log^{-(2p+1)/2}(n)$,
\end{itemize}
where we write $a_n \simeq b_n$ if there exists $C > 0$ such that $a_n/C \le b_n \le C a_n$ for all large enough $n$. The example demonstrates that one cannot improve the exponent $1/(2p+1)$ appearing on the outer bracket of the r.h.s.\ of (\ref{eq:ha}). But as the two terms of the r.h.s.\ of (\ref{eq:ha}) are of the same order, one cannot draw any conclusion about the optimality of the term $ {\|V^2(\mbx)-1\|}_p^{p/(2p+1)}$ alone. Most importantly, it is rather disappointing that in the example, ${\|\mbx\|}^{2p}_{2p}$ and $\sum_{i = 1}^n {\|X_i\|}_{2p}^{2p}$ are of the same order, if the typical martingales that one has in mind have increments of roughly the same order. 

Using a similar construction, but imposing also that $V^2(\mbx) = 1$ a.s.,\ \cite[Example~2.4]{joos} proves the optimality of the exponent $1/(2p'+1)$ appearing on the second term of the sum in the r.h.s.\ of (\ref{eq:joos}), but does not discuss the optimality of the first term ${\|V^2(\mbx)-1\|}_p^{p/(2p+1)}$.

For $1 \le p \le 2$, Theorem~\ref{t:ha} is in fact already proved in \cite{hb}. In \cite[Section~3.6]{hh}, the authors could only show that the bound on $D(\mbx)$ can be no better than $\|V^2(\mbx) - 1 \|_1^{1/2}$. 

\medskip

The proof of Theorem~\ref{t:ha} given in \cite{ha88} is inspired by a method introduced in \cite{bo}. There, the following results are proved.

\begin{thm}[\cite{bo}]
\label{t:bo}
Let $\gamma \in (0,+\infty)$. There exists a constant $C_{\gamma} > 0$ such that, for any $n \ge 2$ and any $\mbx \in M_n$ satisfying $\|\mbx\|_{\infty} \le \gamma$ and $V^2(\mbx) = 1$ a.s., one has
\begin{equation*}
%\label{eq:bo}
D(\mbx) \le C_{\gamma} \frac{n \log(n)}{s^3(\mbx)}.
\end{equation*}
\end{thm}
In typical instances, $s(\mbx)$ is of order $\sqrt{n}$ when $\mbx \in M_n$. Under such a circumstance, Theorem~\ref{t:bo} thus gives a bound of order $\log(n)/\sqrt{n}$. Moreover, \cite{bo} provides an example of a sequence of elements $\mbx_n \in M_n$ satisfying the conditions of Theorem~\ref{t:bo}, such that $s^2(\mbx_n) = n$ and for which 
$$
\limsup_{n \to + \infty} \sqrt{n} \log^{-1}(n) D(\mbx_n) > 0,
$$
so the result is optimal.

Relaxing the condition that $V^2(\mbx) = 1$ a.s., \cite{bo} then shows the following.
\begin{cor}[\cite{bo}]
\label{cor:bo0}
Let $\gamma \in (0,+\infty)$. There exists a constant $\ov{C}_{\gamma} > 0$ such that, for any $n \ge 2$ and any $\mbx \in M_n$ satisfying $\|\mbx\|_{\infty} \le \gamma$, one has
\begin{equation}
\label{eq:bo0}
D(\mbx) \le \ov{C}_{\gamma} \ll[ \frac{n \log(n)}{s^3(\mbx)} + \min\ll({\|V^2(\mbx)-1\|}_1^{1/3},{\|V^2(\mbx)-1\|}_\infty^{1/2}\rr) \rr].
\end{equation}
\end{cor}
%
We refer to \cite[Theorem~3.2]{joos} for a non-uniform version of this result. A strategy is sketched in \cite{bo} to prove that the bound $\|V^2(\mbx) - 1 \|_1^{1/3}$ is indeed optimal, even on the restricted class considered by Corollary~\ref{cor:bo0} of martingales with bounded increments. This example provides a satisfactory answer to our question of optimality for $p = 1$. The aim of the present paper is to generalize Corollary~\ref{cor:bo0} and the optimality result to any $p \in [1,+\infty)$. We begin by proving the following general result.

\begin{thm}
\label{cor:bo}
Let $p \in [1,+\infty)$ and $\gamma \in (0,+\infty)$. There exists a constant $C_{p,\gamma} > 0$ such that, for any $n \ge 2$ and any $\mbx \in M_n$ satisfying $\|\mbx\|_{\infty} \le \gamma$, one has
\begin{equation}
\label{eq:bo}
D(\mbx) \le C_{p,\gamma} \ll[ \frac{n \log(n)}{s^3(\mbx)} + \ll({\|V^2(\mbx)-1\|}_p^p + s^{-2p}(\mbx) \rr)^{1/(2p+1)} \rr].
\end{equation}
\end{thm}

Note that, somewhat surprisingly, the term $s^{-2p}(\mbx) \sum_{i = 1}^n {\|X_i\|}_{2p}^{2p}$ appearing in inequality (\ref{eq:ha}) is no longer present in (\ref{eq:bo0}), and is changed for the smaller $s^{-2p}(\mbx)$ in (\ref{eq:bo}).

Finally, we justify the optimality of the term ${\|V^2(\mbx)-1\|}_p^{p/(2p+1)}$ appearing in the r.h.s.\ of (\ref{eq:bo}).

\begin{thm}
\label{t:example}
Let $p \in [1,+\infty)$ and $\alpha \in (1/2,1)$. There exists a sequence of elements $\mbx_n \in M_n$ such that 
\begin{itemize}
\item $\displaystyle \|\mbx_n\|_\infty \le 2$,
\item $\displaystyle s(\mbx_n) \simeq \sqrt{n}$,
\item $\displaystyle {\|V^2(\mbx_n) - 1\|}_p^{p/(2p+1)} = O\ll( n^{(\alpha - 1)/2} \rr)$,
\item $\displaystyle \limsup_{n \to + \infty} n^{(1-\alpha)/2} D(\mbx_n) > 0$.
\end{itemize}
\end{thm}

Our strategy to prove Theorem~\ref{t:example} builds up on the one sketched in \cite{bo} for the case when $p = 1$. Interestingly, Theorem~\ref{cor:bo} is used in the proof of Theorem~\ref{t:example}.

\medskip

The question of optimality of the term ${\|V^2(\mbx)-1\|}_p^{p/(2p+1)}$, now settled by Theorem~\ref{t:example}, arises naturally in the problem of showing a quantitative central limit theorem for the random walk among random conductances on $\Z^d$ \cite{berry}. There, one approximates the random walk by a martingale. The martingale increments are stationary and ``almost bounded'' for $d \ge 3$, in the sense that they have bounded $L^p$ norm for every $p < + \infty$. Roughly speaking, it is shown that for $d \ge 3$, the variance of the rescaled quadratic variation up to time $t$ decays like $t^{-1}$. This bound is optimal, and leads to a Berry-Esseen bound of order $t^{-1/5}$. Theorem~\ref{t:example} thus demonstrates that there is no way to obtain a better exponent of decay than $1/5$ if one relies only on information about the variance of the quadratic variation.

\medskip

Theorem~\ref{cor:bo} is proved in Section~\ref{s:proofcor}, and Theorem~\ref{t:example} in Section~\ref{s:example}.

%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%       Proof cor      %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%
\section{Proof of Theorem~\ref{cor:bo}}
\label{s:proofcor}
\setcounter{equation}{0}


The proof of Theorem~\ref{cor:bo} is essentially similar to the proof of Corollary~\ref{cor:bo0} given in \cite{bo}, with the additional ingredient of a Burkholder inequality.

Let $\mbx = (X_1,\ldots, X_n) \in M_n$ be such that $\|\mbx\|_\infty \le \gamma$. The idea, which probably first appeared in \cite{dvo}, is to augment the sequence to some $\hat{\mbx} \in M_{2n}$ such that $V^2(\hat{\mbx}) = 1$ almost surely, while preserving the property that $\|\hat{\mbx}\|_\infty \le \gamma$, and apply Theorem~\ref{t:bo} to this enlarged sequence. Let 
$$
\tau = \sup \ll\{ k \le n : \sum_{i=1}^k \E[X_i^2 \ | \ \mcl{F}_{i-1}] \le s^2(\mbx) \rr\}.
$$
For $i \le \tau$, we define $\hat{X}_i = X_i$. Let $r$ be the largest integer not exceeding 
$$
\frac{s^2(\mbx) - \sum_{i = 1}^\tau \E[X_i^2 \ | \ \mcl{F}_{i-1}]}{\gamma^2}.
$$
As $\|X\|_\infty \le \gamma$, it is clear that $r \le n$. Conditionally on $\mcl{F}_\tau$ and for $1 \le i \le r$, we let $\hat{X}_{i}$ be independent random variables such that 
$\P[\hat{X}_{\tau + i} = \pm \gamma] = 1/2$. If $\tau + r < 2n$, we let $\hat{X}_{\tau + r + 1}$ be such that
$$
\P\ll[ \hat{X}_{\tau + r + 1} = \pm \ll(s^2(\mbx) - \sum_{i = 1}^\tau \E[X_i^2 \ | \ \mcl{F}_{i-1}] - r \gamma^2 \rr)^{1/2} \rr] = \frac{1}{2},
$$
the sign being decided independently of everything else.
Finally, if $\tau + r + 1 < 2n$, we let $\hat{X}_{\tau + r + i} = 0$ for $i \ge 2$.

Possibly enlarging the $\sigma$-fields, we can assume that $\hat{X}_i$ is $\mcl{F}_i$-measurable for $i \le n$, and define $\mcl{F}_i$ to be the $\sigma$-field generated by $\mcl{F}_n$ and $\hat{X}_{n+1},\ldots, \hat{X}_{n+i}$ if $i > n$. By construction, one has
$$
\sum_{i = \tau + 1}^{2n} \E[\hat{X}_i^2 \ | \ \mcl{F}_{i-1}] = s^2(\mbx) - \sum_{i = 1}^\tau \E[X_i^2 \ | \ \mcl{F}_{i-1}],
$$
which can be rewritten as
$$
\sum_{i = 1}^{2n} \E[\hat{X}_i^2 \ | \ \mcl{F}_{i-1}] = s^2(\mbx).
$$
As a consequence, $s^2(\hat{\mbx}) = s^2(\mbx)$ and $V^2(\hat{\mbx}) = 1$ almost surely. The sequence $\hat{\mbx}$ thus satisfies the assumptions of Theorem~\ref{t:bo}, so
\begin{equation}
\label{Dhatx}
D(\hat{\mbx}) \le 4 C_\gamma \frac{n \log(n)}{s^3(\mbx)}.	
\end{equation}
For any $x > 0$, we have
\begin{eqnarray}
\label{ineqxhatx}
\P\ll[\frac{S(\mbx)}{s(\mbx)} \le t \rr] & \le & \P\ll[ \frac{S(\mbx)}{s(\mbx)} \le t, \frac{|S(\mbx) - S(\hat{\mbx})|}{s(\mbx)} \le x \rr] + \P\ll[ \frac{|S(\mbx) - S(\hat{\mbx})|}{s(\mbx)} \ge x \rr] \notag \\
& \le & \P\ll[ \frac{S(\hat{\mbx})}{s(\mbx)} \le t+x \rr]  + \frac{1}{x^{2p}} \E \ll[\left| \frac{S(\mbx) - S(\hat{\mbx})}{s(\mbx)} \rr|^{2p} \rr].
\end{eqnarray}
Due to (\ref{Dhatx}), the first term in the r.h.s.\ of (\ref{ineqxhatx}) is smaller than
\begin{equation}
\label{boundPhi}
\Phi(t+x) + 4 C_\gamma \frac{n \log(n)}{s^3(\mbx)} \le \Phi(t) + \frac{x}{\sqrt{2\pi}} +4 C_\gamma \frac{n \log(n)}{s^3(\mbx)}.	
\end{equation}
To control the second term, note first that
\begin{equation}
\label{SShat}
S(\mbx) - S(\hat{\mbx}) =  \sum_{i = \tau + 1}^{2n} (X_i - \hat{X}_i),	
\end{equation}
where we put $X_i = 0$ for $i > n$. As $\tau + 1$ is a stopping time, conditionally on $\tau$, the $(X_i - \hat{X}_i)_{i \ge \tau + 2}$ still forms a martingale difference sequence. We can thus use Burkholder's inequality (see for instance \cite[Theorem 2.11]{hh}), which states that
\begin{multline}
\label{multXXhat}
\frac{1}{C} \E\ll[ \ll| \sum_{i = \tau + 2}^{2n} (X_i - \hat{X}_i) \rr|^{2p} \rr] \\
 \le \E \ll[ \ll( \sum_{i = \tau + 2}^{2n} \E[(X_i - \hat{X}_i)^2 \ | \ \mcl{F}_{i-1}] \rr)^p \rr] + \E \ll[ \max_{\tau + 2 \le i \le 2n} \ll| X_i - \hat{X}_i \rr|^{2p} \rr],
\end{multline}
and we can safely discard the summand indexed by $\tau+1$ appearing in (\ref{SShat}), that is uniformly bounded. The maximum on the r.h.s.\ of (\ref{multXXhat}) is also bounded by $2\gamma^{2p}$. As for the other term, $X_i$ and $\hat{X}_i$ being orthogonal random variables, we have
\begin{eqnarray}
\label{eqnXXhat}
\sum_{i = \tau + 1}^{2n} \E[(X_i - \hat{X}_i)^2 \ | \ \mcl{F}_{i-1}] 
&  = & \sum_{i = \tau + 1}^{2n} \E[X_i^2 \ | \ \mcl{F}_{i-1}]  + \sum_{i = \tau + 1}^{2n} \E[\hat{X}_i^2 \ | \ \mcl{F}_{i-1}] \notag  \\
& = & s^2(\mbx) V^2(\mbx) + s^2(\mbx) - 2 \underbrace{\sum_{i = 1}^\tau \E[X_i^2 \ | \ \mcl{F}_{i-1}]}.
\end{eqnarray}
Now, if $\tau = n$, then by definition the sum underbraced above is $s^2(\mbx) V^2(\mbx)$. Otherwise, $\sum_{i = 1}^{\tau+1} \E[X_i^2 \ | \ \mcl{F}_{i-1}]$ exceeds $s^2(\mbx)$, but as the increments are bounded, the sum underbraced is necessarily larger than $s^2(\mbx) - \gamma^2$. In any case, we thus have
$$
\sum_{i = 1}^\tau \E[X_i^2 \ | \ \mcl{F}_{i-1}] \ge \min(s^2(\mbx)V^2(\mbx), s^2(\mbx) - \gamma^2).
$$
As a consequence, we obtain from (\ref{eqnXXhat}) that
$$
\sum_{i = \tau + 1}^{2n} \E[(X_i - \hat{X}_i)^2 \ | \ \mcl{F}_{i-1}] \le \ll| s^2(\mbx) V^2(\mbx) - s^2(\mbx) \rr| + 2 \gamma^2.
$$
Combining this with equations (\ref{multXXhat}), (\ref{SShat}), (\ref{boundPhi}) and (\ref{ineqxhatx}), we finally obtain that
$$
\P\ll[\frac{S(\mbx)}{s(\mbx)} \le t \rr] - \Phi(t) \le 4 C_\gamma \frac{n \log(n)}{s^3(\mbx)} + \frac{x}{\sqrt{2\pi}} + \frac{C}{x^{2p}} \ll( \|V^2(\mbx) - 1\|_p^p + \frac{\gamma^{2p}}{s^{2p}(\mbx)} \rr).
$$
Optimizing this over $x > 0$ leads to the correct estimate. The lower bound is obtained in the same way.
%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%       Example        %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%
\section{Proof of Theorem~\ref{t:example}}
\label{s:example}
\setcounter{equation}{0}
Let $p \ge 1$ and $\alpha \in (1/2,1)$ be fixed. We let $(X_{n i})_{1 \le i \le n - n^\alpha}$ be independent random variables with $\P[X_{ni} = \pm 1] = 1/2$. The subsequent $(X_{n i})_{n - n^\alpha < i \le n}$ are defined recursively. Let
$$
\lambda_{n i} = \sqrt{n - i + \kappa_n^2},
$$
where $\kappa_n = n^{1/4}$ (in fact, any $n^\beta$ with $1-\alpha < 2\beta < \alpha$ would be fine).
Assuming that $X_{n,1},\ldots,X_{n,i-1}$ have already been defined, we write $\mathcal{F}_{n,i-1}$ for the $\sigma$-algebra that they generate, and let
$$
S_{n, i-1} = \sum_{j = 1}^{i-1} X_{nj}.
$$
For any $i$ such that $n - n^\alpha < i \le n$, we construct $X_{n i}$ such that
\begin{equation}
\label{defXni}
\P[X_{n i} \in \cdot \ | \ \mathcal{F}_{n,i-1}] = 
\left|
\begin{array}{ll}
\delta_{-\sqrt{3/2}} + \delta_{\sqrt{3/2}} & \text{if } S_{n,i-1} \in [\lambda_{n i}, 2 \lambda_{n i} ] , \\
\delta_{-\sqrt{1/2}}+ \delta_{\sqrt{1/2}} & \text{if } S_{n,i-1} \in [-2 \lambda_{n i}, - \lambda_{n i} ], \\
\delta_{-1} + \delta_{1} & \text{otherwise}, \\
\end{array}
\right.
\end{equation}
where $\delta_x$ is the Dirac mass at point $x$. One can view $(S_{ni})_{i \le n}$ as an inhomogeneous Markov chain. We write $\mbx_n = (X_{n1},\ldots,X_{nn})$, and $\mbx_{ni} = (X_{n1},\ldots,X_{ni})$ for any $i \le n$. Let 
\begin{equation}
\label{defdeltan}
\delta(i) = \sup_{n \ge i} D(\mbx_{ni}).
\end{equation}

\begin{prop}
\label{p:deltaO}
One has, uniformly over $n$,
\begin{equation}
\label{V2}
\|V^2(\mbx_{ni}) - 1\|_p = O \big( i^{(\alpha - 1)(1+1/2p)} \big) \qquad (i \to + \infty),
\end{equation}
and
\begin{equation}
\label{deltaO}
\delta(i) = O \left(i^{(\alpha-1)/2} \right) \qquad (i \to + \infty).
\end{equation}
\end{prop}
The proof goes the following way: first, we bound $\|V^2(\mbx_{ni}) - 1\|_p$ in terms of $(\delta(j))_{j \le i}$ in Lemma~\ref{l:deltaO}. This gives an inequality on the sequence $(\delta(i))_{i \in \N}$ through Theorem~\ref{cor:bo}, from which we deduce (\ref{deltaO}), and then (\ref{V2}). 
\begin{lem}
\label{l:deltaO}
Let $K_i = \max_{j \le i} \delta(j) j^{(1-\alpha)/2}$. 
For any $n$ and $i$, the following inequalities hold:
\begin{equation}
\label{square}
\left| \E[X_{ni}^2] - 1 \right| \le 
\left|
\begin{array}{ll}
0 & \text{if } i \le n - n^\alpha, \\
2 \delta(i-1) & \text{if } n - n^\alpha < i \le n,
\end{array}
\right.
\end{equation}
\begin{equation}
\label{s2}
\left| s^2(\mbx_{ni}) - i \right| \le 
\left|
\begin{array}{ll}
0 & \text{if } i \le n - n^\alpha, \\
C i^{(3\alpha - 1)/2} K_i \le C i^\alpha & \text{if } n - n^\alpha < i \le n,
\end{array}
\right.
\end{equation}
\begin{equation}
\label{V2delta}
\|V^2(\mbx_{ni}) - 1\|_p \le 
\left|
\begin{array}{ll}
0 & \text{if } i \le n - n^\alpha, \\
C i^{(\alpha - 1)(1+1/2p)} (1 + K_i)^{1/p} + C i^{(3\alpha - 3)/2} K_i & \text{otherwise}.
\end{array}
\right.
\end{equation}
\end{lem}
\begin{proof}[Proof of Lemma~\ref{l:deltaO}]
Inequality (\ref{square}) is obvious for $i \le n - n^\alpha$. Otherwise, from the definition (\ref{defXni}), we know that
$$
\E[X_{ni}^2] = 1 + \frac{1}{2} \P[S_{n,i-1} \in I^+_{ni}] - \frac{1}{2} \P[S_{n,i-1} \in I^-_{ni}],
$$
where we write 
\begin{equation}
\label{defI}
I^+_{ni} = [\lambda_{ni},2\lambda_{ni}] \quad \text{ and } \quad I^-_{ni} = [-2\lambda_{ni}, -\lambda_{ni}].
\end{equation}
The random variable $S_{n,i-1}/s(\mbx_{n,i-1})$ is approximately Gaussian, up to an error controlled by $\delta(i-1)$. More precisely,
$$
\left| \P[S_{n,i-1} \in I^+_{ni}] - \int_{I^+_{ni}/s(\mbx_{n,i-1})} \d \Phi \right| \le 2 \delta(i-1) .
$$
We obtain (\ref{square}) using the fact that 
$$
\int_{I^+_{ni}/s(\mbx_{n,i-1})} \d \Phi = \int_{I^-_{ni}/s(\mbx_{n,i-1})} \d \Phi.
$$ 
As a by-product, we also learn that
\begin{equation*}
%\label{s22}
\left| s^2(\mbx_{ni}) - i \rr| \le 
\left|
\begin{array}{ll}
0 & \text{if } i \le n - n^\alpha, \\
2 \sum_{n - n^\alpha < j \le i} \delta(j-1) & \text{if } n - n^\alpha < i \le n.
\end{array}
\right.
\end{equation*}
Recalling that $\alpha  < 1$, we obtain (\ref{s2}) noting that, for $n - n^\alpha < i \le n$,
$$
\sum_{n - n^\alpha < j \le i} \delta(j-1) \le n^\alpha (n - n^\alpha)^{(\alpha - 1)/2} K_i.
$$
In particular, it follows that
\begin{equation}
\label{s2isi}
s^2(\mbx_{ni}) = i(1+o(1)).	
\end{equation}
Turning now to (\ref{V2delta}), $\|V^2(\mbx_{ni}) - 1 \|_p$ is clearly equal to $0$ for $i \le n - n^\alpha$, so let us assume the contrary. We have:
\begin{eqnarray}
\label{eq1}
\|V^2(\mbx_{ni}) - 1 \|_p & \!\!\! = \!\!\! & s^{-2}(\mbx_{ni}) \left\| \sum_{j = 1}^i \E[X_{nj}^2 | \mcl{F}_{n,j-1}] - s^2(\mbx_{ni}) \right\|_p  \notag \\
& \!\!\! \le \!\!\! & \frac{1}{s^{2}(\mbx_{ni})}  \sum_{j = 1}^i \ll\| \E[X_{nj}^2 | \mcl{F}_{n,j-1}] - 1 \right\|_p  + \frac{\left| s^2(\mbx_{ni}) - i \rr|}{s^{2}(\mbx_{ni}) } \notag \\
& \!\! \le \!\!\! & \frac{1}{2 s^{2}(\mbx_{ni})}  \sum_{n - n^\alpha < j \le i} \left(\P[S_{n,j-1} \in I^+_{nj} \cup I^-_{nj}]\right)^{1/p} + \frac{\left| s^2(\mbx_{ni}) - i \rr|}{s^{2}(\mbx_{ni}) }.
\end{eqnarray}
We consider the two terms in (\ref{eq1}) separately. First, by the definition of $\delta$, we know that
$$
\left| \P[S_{n,j-1} \in I^+_{nj} \cup I^-_{nj}] - \int_{(I^+_{nj} \cup I^-_{nj})/s(\mbx_{n,j-1})} \d \Phi \right| \le 2 \delta(j-1).
$$
Equation (\ref{s2isi}) implies that, uniformly over $j > n - n^\alpha$,
$$
\int_{(I^+_{nj} \cup I^-_{nj})/s(\mbx_{n,j-1})} \d \Phi = (2\pi)^{-1/2} \frac{2 \lambda_{nj}}{s(\mbx_{n,j-1})} (1 + o(1)) \le C n^{(\alpha - 1)/2},
$$
so the first term of (\ref{eq1}) is bounded by 
\begin{equation}
\label{bound1}
\begin{split}
& \frac{C}{i} \sum_{n - n^\alpha < j \le i} (n^{(\alpha - 1)/2} + 2 \delta(j-1))^{1/p} \\
& \quad \le  \frac{C}{i} \sum_{n - n^\alpha < j \le i} (n^{(\alpha - 1)/2} + 2 (n - n^\alpha)^{(\alpha - 1)/2} K_i)^{1/p} \\ 
& \quad \le  C i^{(\alpha - 1)(1+1/2p)} (1 + K_i)^{1/p}.
\end{split}
\end{equation}
The second term in (\ref{eq1}) is controlled by (\ref{s2}), and we obtain inequality (\ref{V2delta}).
\end{proof}
\begin{proof}[Proof of Proposition~\ref{p:deltaO}]
Applying Theorem~\ref{cor:bo} with the information given by Lemma~\ref{l:deltaO}, we obtain that, up to a multiplicative constant that does not depend on $n$ and $i \le n$, $D(\mbx_{ni})$ is bounded by:
\begin{equation}
\label{eq2}
\frac{\log(i)}{\sqrt{i}} + i^{(\alpha - 1)/2} (1 + K_i)^{1/(2p+1)} + i^{- 3(1 - \alpha)p/(4p+2)} K_i^{p/(2p+1)} + i^{-p/(2p+1)}.
\end{equation}
The first term can be disregarded, as it is dominated by $i^{-p/(2p+1)}$. Note also that, as $p \ge 1$, we have
$$
\frac{3(1 - \alpha)p}{4p+2} \ge  \frac{1-\alpha}{2},
$$
and as $\alpha > 1/2 > 1/(2p+1)$, we also have
$$
\frac{p}{2p+1} \ge \frac{1-\alpha}{2}.
$$
Multiplying (\ref{eq2}) by $i^{(1-\alpha)/2}$, we thus obtain
$$
K_i \le C (1 + K_i)^{1/(2p+1)} + C K_i^{p/(2p+1)},
$$
where we recall that the constant $C$ does not depend on $i$. Observing that the set $\{x \ge 0 : x \le C (1+x)^{1/(2p+1)} + C x^{p/(2p+1)} \}$ is bounded, we obtain that $K_i$ is a bounded sequence, so (\ref{deltaO}) is proved. The relation (\ref{V2}) then follows from (\ref{deltaO}) and (\ref{V2delta}).
\end{proof}
\begin{prop}
\label{p:ex2}
We have
$$
\limsup_{i \to + \infty} \ i^{(1-\alpha)/2} \ \delta(i) > 0.
$$
\end{prop}
\begin{proof}
Our aim is to contradict, by reductio ad absurdum, the claim that
\begin{equation}
\label{cond*}
\delta(i) = o\left(i^{(\alpha-1)/2} \right)  \qquad (i \to + \infty).
\end{equation}
Let $Z_1,\ldots,Z_n$ be independent standard Gaussian random variables, and $\xi_n$ be an independent centred Gaussian random variable with variance $\kappa_n^2$, all being independent of $\mbx_{n}$. Assuming (\ref{cond*}), we will contradict the fact that 
\begin{equation}
\label{contrad}	
D(\mbx_n) = o \ll(n^{(\alpha - 1)/2} \rr).
\end{equation}
Let $W_{ni} = \sum_{j = {i+1}}^n Z_j + \xi_n$. Noting that $n^{-1/2} \sum_{j = 1}^n Z_j$ is a standard Gaussian random variable, and with the help of \cite[Lemma~1]{bo}, we learn that
$$
\ll| \P[W_{n0} \le 0] - \frac{1}{2} \rr| \le C \frac{\kappa_n}{\sqrt{n}},
$$
and similarly,
$$
\ll| \P[S_{nn} + \xi_n \le 0] - \frac{1}{2} \rr| \le C \ll(D(\mbx_n) + \frac{\kappa_n}{s(\mbx_{n})} \rr).
$$
Combining these two observations with (\ref{s2}), we thus obtain that
\begin{equation}
\label{decompSn}
\P[S_{nn} + \xi_n \le 0] - \P[W_{n0} \le 0] \le C \ll( D(\mbx_n) + \frac{\kappa_n}{\sqrt{n}} \rr).
\end{equation}
As $\kappa_n = n^{1/4}$ and $\alpha > 1/2$, we know that $\kappa_n/\sqrt{n} = o(n^{(\alpha - 1)/2})$. We decompose the l.h.s.\ of (\ref{decompSn}) as
$$	
\sum_{i = 1}^n \P[S_{n,i-1} + X_{ni} + W_{ni} \le 0] - \P[S_{n,i-1} + Z_i + W_{ni} \le 0].
$$
The random variable $W_{ni}$ is Gaussian with variance ${\lambda}_{ni}^2 = n-i+\kappa_n^2$, and independent of $\mbx_n$, so the sum can be rewritten as
\begin{equation}
\label{sum}
\sum_{i = 1}^n \E\ll[  \Phi\ll(-\frac{S_{n,i-1} + X_{ni}}{{\lambda}_{ni}}\rr) - \Phi\ll(-\frac{S_{n,i-1} + Z_i}{{\lambda}_{ni}}\rr)   \rr],
\end{equation}
Let $\phi(x) = (2\pi)^{-1/2} \ e^{-x^2/2}$. We can replace
\begin{equation}
\label{eq3}
\Phi\ll(-\frac{S_{n,i-1} + X_{ni}}{{\lambda}_{ni}}\rr)	
\end{equation}
by its Taylor expansion
\begin{equation}
\label{taylor}
\Phi\ll(-\frac{S_{n,i-1}}{{\lambda}_{ni}}\rr) - \frac{X_{ni}}{{\lambda}_{ni}} \phi\ll( -\frac{S_{n,i-1}}{{\lambda}_{ni}} \rr) + \frac{X_{ni}^2}{2 {\lambda}_{ni}^2} \phi'\ll( -\frac{S_{n,i-1}}{{\lambda}_{ni}} \rr),
\end{equation}
up to an error that is bounded by
\begin{equation}
\label{Taylorerror}
\frac{|X_{ni}|^3}{6{\lambda}_{ni}^3} \|\phi''\|_{\infty}.	
\end{equation}

\medskip

\noindent \emph{Step 1.} We show that the error term (\ref{Taylorerror}), after integration and summation over~$i$, is $o(n^{(\alpha - 1)/2})$. As $X_{ni}$ is uniformly bounded, it suffices to show that
\begin{equation}
\label{sumo1}
\sum_{i = 1}^n \frac{1}{\lambda_{ni}^3} = o \ll(n^{(\alpha - 1)/2} \rr).
\end{equation}
The sum above equals
$$
\sum_{i = 1}^n \frac{1}{(n-i+\kappa_n^2)^{3/2}} \le n^{-1/2} \int_{(\kappa_n^2 - 1)/n}^{(\kappa_n^2 +n)/n} x^{-3/2} \ \d x = O \ll(\kappa_n^{-1}\rr).
$$
As we defined $\kappa_n$ to be $n^{1/4}$ and $\alpha > 1/2$, equation (\ref{sumo1}) is proved.

\medskip

\noindent \emph{Step 2.} For the second part of the summands in (\ref{sum}), the same holds with $X_{ni}$ replaced by $Z_i$, and similarly,
\begin{equation}
\label{sumo2}
\sum_{i = 1}^n \frac{\E[|Z_i|^3]}{{\lambda}_{ni}^3}  = o \ll(n^{(\alpha - 1)/2} \rr).
\end{equation}

\medskip

\noindent \emph{Step 3.} Combining the results of the two previous steps, we know  that up to a term of order $o\ll(n^{(\alpha - 1)/2}\rr)$, the sum in (\ref{sum}) can be replaced by
$$
\sum_{i = 1}^n \E\ll[ \frac{Z_i - X_{ni}}{{\lambda}_{ni}} \phi\ll( -\frac{S_{n,i-1}}{{\lambda}_{ni}} \rr) + \frac{X_{ni}^2 - Z_i^2}{2 {\lambda}_{ni}^2} \phi'\ll( -\frac{S_{n,i-1}}{{\lambda}_{ni}} \rr)   \rr].
$$
Conditionally on $S_{n,i-1}$, both $Z_i$ and $X_{ni}$ are centred random variables, so the first part of the summands vanishes, and there remains only
\begin{equation}
\label{sumcondi}
\sum_{i = 1}^n \E\ll[ \frac{X_{ni}^2 - Z_i^2}{2 {\lambda}_{ni}^2} \phi'\ll( -\frac{S_{n,i-1}}{{\lambda}_{ni}} \rr)   \rr] = \sum_{i = 1}^n \E\ll[ \frac{\E[{X_{ni}^2 - 1 \ | \ S_{n,i-1}]}}{2 {\lambda}_{ni}^2} \phi'\ll( -\frac{S_{n,i-1}}{{\lambda}_{ni}} \rr)   \rr].
\end{equation}
From the definition of $X_{ni}$, we learn that $\E[X_{ni}^2 - 1 \ | \ S_{n,i-1}]$ is $0$ if $i \le n - n^\alpha$, and otherwise equals
$$
\ll|
\begin{array}{ll}
1/2 & \text{if } S_{n,i-1} \in I^+_{ni}, \\
- 1/2 & \text{if } S_{n,i-1} \in I^-_{ni}, \\
0 & \text{otherwise},
\end{array}
\rr.
$$
where $I^+_{ni}$ and $I^-_{ni}$ were defined in (\ref{defI}). As a consequence, it is clear that the contribution of each summand in the r.h.s.\ of (\ref{sumcondi}) is positive. Moreover, for $i > n - n^\alpha$ and on the event $S_{n,i-1} \in I^-_{ni} \cup I^+_{ni}$, we have
$$
\E [X_{ni}^2 - 1 \ | \ S_{n,i-1}] \  \phi'\ll( -\frac{S_{n,i-1}}{{\lambda}_{ni}} \rr) \ge \frac{1}{2} \inf_{[1,2]} \ll|\phi'\rr| > 0.
$$
Let us assume temporarily that, uniformly over $n$ and $i$ such that $n - n^\alpha < i \le n - (n^\alpha)/2$, we have
\begin{equation}
\label{tempassump}
\P[S_{n,i-1} \in I^-_{ni} \cup I^+_{ni}] \ge C \frac{\lambda_{ni}}{\sqrt{n}}.
\end{equation}
Then the sum in the r.h.s.\ of (\ref{sumcondi}) is, up to a constant, bounded from below by
$$
\sum_{n - n^\alpha < i \le n - (n^\alpha)/2} \frac{1}{\lambda_{ni} \sqrt{n}} \ge C {n^\alpha} \frac{1}{n^{\alpha/2} \sqrt{n}} = C {n^{(\alpha-1)/2}}.
$$
This contradicts (\ref{contrad}) via inequality (\ref{decompSn}), and thus finishes the proof of the Proposition.


\medskip

\noindent \emph{Step 4.} There remains to show (\ref{tempassump}), for $n - n^\alpha < i \le n - (n^\alpha)/2$. We have
$$
\ll|\P[S_{n,i-1} \in I^+_{ni}] - \int_{I^+_{ni}/s(\mbx_{n,i-1})} \d \Phi  \rr| \le 2 \delta(i-1).
$$
Using inequality (\ref{s2}), it follows that
$$
\int_{I^+_{ni}/s(\mbx_{n,i-1})} \d \Phi \ge C \frac{\lambda_{ni}}{\sqrt{n}}.
$$
As we choose $i$ inside $[n - n^\alpha, n - (n^\alpha)/2]$, $\lambda_{ni}$ is larger than $Cn^{\alpha/2}$, while $\delta(i - 1) = o\ll(i^{(\alpha - 1)/2}\rr)$ by assumption (\ref{cond*}). This proves (\ref{tempassump}).
\end{proof}

\noindent \textbf{Remark.} To match the example proposed in \cite{bo}, one should choose instead $\alpha = 1/3$ and $\kappa_n = 1$ in the definition of the sequences $(\mbx_n)$. In this case, Propositions~\ref{p:deltaO} and \ref{p:ex2} are still true. While the proof of Proposition~\ref{p:deltaO} can be kept unchanged, Proposition~\ref{p:ex2} requires a more subtle analysis. First, one needs to choose $\xi_n$ of variance $\ov{\kappa}_n^2 \neq 1$, thus requiring to change the $\lambda_{ni}$ appearing in (\ref{sum}) by, say, $\ov{\lambda}_{ni} = \sqrt{n - i + \ov{\kappa}_n^2}$. The sequence $\ov{\kappa}_n^2$ should grow to infinity with $n$, while remaining~$o(n^\alpha)$. In step 1, bounding the difference between (\ref{eq3}) and (\ref{taylor}) by (\ref{Taylorerror}) is too crude. Instead, one can bound it by
$$
\frac{C}{\ov{\lambda}_{ni}^3} \Psi\ll( - \frac{S_{n,i-1}}{\ov{\lambda}_{ni}} \rr),
$$
where $\Psi(x) = \sup_{|y| \le 1} |\phi''(x+y)|$. One can then appeal to \cite[Lemma 2]{bo} and get through this step, using the fact that $\ov{\kappa}_n$ tends to infinity. Step 2 is similar, with some additional care required by the fact that $Z_i$ is unbounded. The rest of the proof then applies, taking care of the discrepancy between $\lambda_{ni}$ and $\ov{\lambda}_{ni}$ when necessary.















%\section{Bolthausen's example}
%
%Let $p \ge 1$ be fixed (what about $p > 0$ ?), and $\alpha \in (0,1)$ be such that
%\begin{equation}
%\label{condalpha}
%(2p+1)^{-1} \le \alpha < 1.
%\end{equation}
%We let $(X_{n i})_{1 \le i \le n - n^\alpha}$ be independent random variables with $\P[X_{ni} = \pm 1] = 1/2$. The remaining $(X_{n i})_{i > n - n^\alpha}$ are defined recursively. Let
%$$
%\lambda_{n i} = \sqrt{n - i + \kappa_n^2},
%$$
%where $\kappa_n > 0$ will be chosen later, but satisfying
%\begin{equation}
%\label{cond1kappa}
%\kappa_n^2 \le n^\alpha.
%\end{equation}
%Assuming that $X_{n,1},\ldots,X_{n,i-1}$ have already been defined, we write $\mathcal{F}_{n,i-1}$ for the $\sigma$-algebra that they generate, and let
%$$
%S_{n, i-1} = \sum_{j = 1}^{i-1} X_{nj}.
%$$
%For any $i > n - n^\alpha$, we construct $X_{n i}$ such that
%\begin{equation}
%\label{defXni}
%\P[X_{n i} \in \cdot \ | \ \mathcal{F}_{n,i-1}] = 
%\left|
%\begin{array}{ll}
%\delta_{-\sqrt{3/2}} + \delta_{\sqrt{3/2}} & \text{if } S_{n,i-1} \in [\lambda_{n i}, 2 \lambda_{n i} ] , \\
%\delta_{-\sqrt{1/2}}+ \delta_{\sqrt{1/2}} & \text{if } S_{n,i-1} \in [-2 \lambda_{n i}, - \lambda_{n i} ], \\
%\delta_{-1} + \delta_{1} & \text{otherwise}, \\
%\end{array}
%\right.
%\end{equation}
%where $\delta_x$ is the Dirac mass at point $x$. One can view $(S_{ni})_{i \le n}$ as an inhomogeneous Markov chain. We write $\mbx_n = (X_{n1},\ldots,X_{nn})$, and $\mbx_{ni} = (X_{n1},\ldots,X_{ni})$ for any $i \le n$. Let 
%\begin{equation}
%\label{defdeltan}
%\delta(i) = \sup_{n \ge i} D(\mbx_{ni}).
%\end{equation}
%
%\begin{prop}
%\label{p:deltaO}
%One has, uniformly over $n$,
%\begin{equation}
%\label{V2}
%\|V^2(\mbx_{ni}) - 1\|_p = O \big( i^{(\alpha - 1)(1+1/2p)} \big) \qquad (i \to + \infty),
%\end{equation}
%and
%\begin{equation}
%\label{deltaO}
%\delta(i) = O \left(i^{(\alpha-1)/2} \right) \qquad (i \to + \infty).
%\end{equation}
%\end{prop}
%The proof goes the following way: first, we bound $\|V^2(\mbx_{ni}) - 1\|_p$ in terms of $(\delta(j))_{j \le i}$ in Lemma~\ref{l:deltaO}. This gives an inequality on the sequence $(\delta(i))_{i \in \N}$ through Corollary~\ref{cor:bo}, from which we deduce (\ref{deltaO}), and then (\ref{V2}). 
%\begin{lem}
%\label{l:deltaO}
%Let $K_i = \max_{j \le i} \delta(j) j^{(1-\alpha)/2}$. 
%For any $n$ and $i$, the following inequalities hold:
%\begin{equation}
%\label{square}
%\left| \E[X_{ni}^2] - 1 \right| \le 
%\left|
%\begin{array}{ll}
%0 & \text{if } i \le n - n^\alpha, \\
%2 \delta(i-1) & \text{if } n - n^\alpha < i \le n,
%\end{array}
%\right.
%\end{equation}
%\begin{equation}
%\label{s2}
%\left| s^2(\mbx_{ni}) - i \right| \le 
%\left|
%\begin{array}{ll}
%0 & \text{if } i \le n - n^\alpha, \\
%C i^{(3\alpha - 1)/2} K_i \le C i^\alpha & \text{if } n - n^\alpha < i \le n,
%\end{array}
%\right.
%\end{equation}
%\begin{equation}
%\label{V2delta}
%\|V^2(\mbx_{ni}) - 1\|_p \le 
%\left|
%\begin{array}{ll}
%0 & \text{if } i \le n - n^\alpha, \\
%C i^{(\alpha - 1)(1+1/2p)} (1 + K_i)^{1/p} + C i^{(3\alpha - 3)/2} K_i & \text{otherwise}.
%\end{array}
%\right.
%\end{equation}
%\end{lem}
%\begin{proof}[Proof of Lemma~\ref{l:deltaO}]
%Equation (\ref{square}) is obvious for $i \le n - n^\alpha$. Otherwise, from the definition (\ref{defXni}), we know that
%$$
%\E[X_{ni}^2] = 1 + \frac{1}{2} \P[S_{n,i-1} \in I^+_{ni}] - \frac{1}{2} \P[S_{n,i-1} \in I^-_{ni}],
%$$
%where we write 
%\begin{equation}
%\label{defI}
%I^+_{ni} = [\lambda_{ni},2\lambda_{ni}] \quad \text{ and } \quad I^-_{ni} = [-2\lambda_{ni}, -\lambda_{ni}].
%\end{equation}
%The random variable $S_{n,i-1}/s(\mbx_{n,i-1})$ is approximately Gaussian, up to an error controlled by $\delta(i-1)$. More precisely,
%$$
%\left| \P[S_{n,i-1} \in I^+_{ni}] - \int_{I^+_{ni}/s(\mbx_{n,i-1})} \d \Phi \right| \le 2 \delta(i-1) .
%$$
%We obtain (\ref{square}) using the fact that 
%$$
%\int_{I^+_{ni}/s(\mbx_{n,i-1})} \d \Phi = \int_{I^-_{ni}/s(\mbx_{n,i-1})} \d \Phi.
%$$ 
%As a by-product, we also learn that
%\begin{equation*}
%%\label{s22}
%\left| s^2(\mbx_{ni}) - i \rr| \le 
%\left|
%\begin{array}{ll}
%0 & \text{if } i \le n - n^\alpha, \\
%2 \sum_{n - n^\alpha < j \le i} \delta(j) & \text{if } n - n^\alpha < i \le n.
%\end{array}
%\right.
%\end{equation*}
%Recalling that $\alpha \in (0,1)$, we obtain (\ref{s2}) noting that, for $n - n^\alpha < i \le n$,
%$$
%\sum_{n - n^\alpha < j \le i} \delta(j) \le n^\alpha (n - n^\alpha)^{(\alpha - 1)/2} K_i.
%$$
%In particular, it follows that
%\begin{equation}
%\label{s2isi}
%s^2(\mbx_{ni}) = i(1+o(1)).	
%\end{equation}
%Turning now to (\ref{V2delta}), $\|V^2(\mbx_{ni}) - 1 \|_p$ is clearly equal to $0$ for $i \le n - n^\alpha$, so let us assume the contrary. We have:
%\begin{eqnarray}
%\label{eq1}
%\|V^2(\mbx_{ni}) - 1 \|_p & = & s^{-2}(\mbx_{ni}) \left\| \sum_{j = 1}^i \E[X_{nj}^2 | \mcl{F}_{n,j-1}] - s^2(\mbx_{ni}) \right\|_p  \notag \\
%& \le  & \frac{1}{s^{2}(\mbx_{ni})}  \sum_{j = 1}^i \ll\| \E[X_{nj}^2 | \mcl{F}_{n,j-1}] - 1 \right\|_p  + \frac{\left| s^2(\mbx_{ni}) - i \rr|}{s^{2}(\mbx_{ni}) } \notag \\
%& \le & \frac{1}{2 s^{2}(\mbx_{ni})}  \sum_{n - n^\alpha < j \le i} \left(\P[S_{n,j-1} \in I^+_{nj} \cup I^-_{nj}]\right)^{1/p} + \frac{\left| s^2(\mbx_{ni}) - i \rr|}{s^{2}(\mbx_{ni}) }.
%\end{eqnarray}
%We consider the two terms in (\ref{eq1}) separately. First, by the definition of $\delta$, we know that
%$$
%\left| \P[S_{n,j-1} \in I^+_{nj} \cup I^-_{nj}] - \int_{(I^+_{nj} \cup I^-_{nj})/s(\mbx_{n,j-1})} \d \Phi \right| \le 2 \delta(j-1).
%$$
%From (\ref{cond1kappa}) and (\ref{s2isi}), we then derive that, uniformly over $j > n - n^\alpha$,
%$$
%\int_{(I^+_{nj} \cup I^-_{nj})/s(\mbx_{n,j-1})} \d \Phi = (2\pi)^{-1/2} \frac{2 \lambda_{nj}}{s(\mbx_{n,j-1})} (1 + o(1)) \le C n^{(\alpha - 1)/2},
%$$
%so the first term of (\ref{eq1}) is bounded by 
%\begin{equation}
%\label{bound1}
%\begin{split}
%& \frac{C}{i} \sum_{n - n^\alpha < j \le i} (n^{(\alpha - 1)/2} + 2 \delta(j-1))^{1/p} \\
%& \quad \le  \frac{C}{i} \sum_{n - n^\alpha < j \le i} (n^{(\alpha - 1)/2} + 2 (n - n^\alpha)^{(\alpha - 1)/2} K_i)^{1/p} \\ 
%& \quad \le  C i^{(\alpha - 1)(1+1/2p)} (1 + K_i)^{1/p}.
%\end{split}
%\end{equation}
%The second term in (\ref{eq1}) is controlled by (\ref{s2}), and we obtained inequality (\ref{V2delta}).
%\end{proof}
%\begin{proof}[Proof of Proposition~\ref{p:deltaO}]
%Applying Corollary~\ref{cor:bo} with the information given by Lemma~\ref{l:deltaO}, we obtain that, up to a multiplicative constant that does not depend on $n$ and $i \le n$, $D(\mbx_{ni})$ is bounded by:
%\begin{equation}
%\label{eq2}
%\frac{\log(i)}{\sqrt{i}} + i^{(\alpha - 1)/2} (1 + K_i)^{1/(2p+1)} + i^{- (3 - 3\alpha)p/(2p+1)} K_i^{p/(2p+1)} + i^{-p/(2p+1)}.
%\end{equation}
%The first term can be disregarded, as it is dominated by $i^{-p/(2p+1)}$. Note also that, as $p \ge 1$ (in fact, $p \ge 1/4$ is sufficient), we have
%$$
%\frac{(3 - 3\alpha)p}{2p+1} \ge  \frac{1-\alpha}{2},
%$$
%and due to our assumption (\ref{condalpha}) on $\alpha$, we also have
%$$
%\frac{p}{2p+1} \ge \frac{1-\alpha}{2}.
%$$
%So multiplying (\ref{eq2}) by $i^{(1-\alpha)/2}$, we obtain
%$$
%K_i \le C (1 + K_i)^{1/(2p+1)} + C K_i^{p/(2p+1)},
%$$
%where we recall that the constant $C$ does not depend on $i$. Observing that the set $\{x \ge 0 : x \le C (1+x)^{1/(2p+1)} + C x^{p/(2p+1)} \}$ is bounded, we obtain that $K_i$ is a bounded sequence, so (\ref{deltaO}) is proved. The relation (\ref{V2}) then follows from (\ref{deltaO}) and (\ref{V2delta}).
%\end{proof}
%Remplacer $\kappa_n^2$ par $1$ dans la section précédente.
%\begin{prop}
%We have
%$$
%\limsup_{i \to + \infty} \ i^{(1-\alpha)/2} \ \delta(i) > 0.
%$$
%\end{prop}
%\begin{proof}
%Our aim is to contradict, by reductio ad absurdum, the claim that
%\begin{equation}
%\label{cond*}
%\delta(i) = o\left(i^{(1-\alpha)/2} \right)  \qquad (i \to + \infty).
%\end{equation}
%Let $\kappa_n > 0$ be a sequence satisfying 
%\begin{equation}
%\label{condkappa}	
%\kappa_n^2 = o \ll( n^\alpha \rr).
%\end{equation}
%Let $Z_1,\ldots,Z_n$ be independent standard Gaussian random variables, and $\xi_n$ be an independent centred Gaussian random variable with variance $\kappa_n^2$, all being independent of $\mbx_{n}$. Assuming (\ref{cond*}), we will contradict the fact that 
%\begin{equation}
%\label{contrad}	
%D(\mbx_n) = o \ll(n^{(\alpha - 1)/2} \rr).
%\end{equation}
%Let $W_{ni} = \sum_{j = {i+1}}^n Z_j + \xi_n$. Noting that $n^{-1/2} \sum_{j = 1}^n Z_j$ is a standard Gaussian random variable, and with the help of \cite[Lemma~1]{bo}, we learn that
%$$
%\ll| \P[W_{n0} \le 0] - \frac{1}{2} \rr| \le C \frac{\kappa_n}{\sqrt{n}},
%$$
%and similarly,
%$$
%\ll| \P[S_{nn} + \xi_n \le 0] - \frac{1}{2} \rr| \le C \ll(D(\mbx_n) + \frac{\kappa_n}{s(\mbx_{n})} \rr).
%$$
%Combining these two observations with (\ref{s2}), we thus obtain that
%\begin{equation}
%\label{decompSn}
%\P[S_{nn} + \xi \le 0] - \P[W_{n0} \le 0] \le C \ll( D(\mbx_n) + \frac{\kappa_n}{\sqrt{n}} \rr).
%\end{equation}
%Due to our assumption (\ref{condkappa}) on $\kappa_n$, we know that $\kappa_n/\sqrt{n} = o(n^{(\alpha - 1)/2})$. We decompose the l.h.s.\ of (\ref{decompSn}) as
%$$	
%\sum_{i = 1}^n \P[S_{n,i-1} + X_{ni} + W_{ni} \le 0] - \P[S_{n,i-1} + Z_i + W_{ni} \le 0].
%$$
%The random variable $W_{ni}$ is Gaussian with variance $\ov{\lambda}_{ni}^2 = n-i+\kappa_n^2$, and independent of $\mbx_n$, so the sum can be rewritten as
%\begin{equation}
%\label{sum}
%\sum_{i = 1}^n \E\ll[  \Phi\ll(-\frac{S_{n,i-1} + X_{ni}}{\ov{\lambda}_{ni}}\rr) - \Phi\ll(-\frac{S_{n,i-1} + Z_i}{\ov{\lambda}_{ni}}\rr)   \rr],
%\end{equation}
%where $\Phi(t) = \int_{-\infty}^t \phi(x) \ \d x$ and $\phi(x) = (2\pi)^{-1} e^{-x^2/2}$. We can replace
%\begin{equation}
%\label{eq3}
%\Phi\ll(-\frac{S_{n,i-1} + X_{ni}}{\ov{\lambda}_{ni}}\rr)	
%\end{equation}
%by its Taylor expansion
%\begin{multline}
%\label{taylor}
%\Phi\ll(-\frac{S_{n,i-1}}{\ov{\lambda}_{ni}}\rr) - \frac{X_{ni}}{\ov{\lambda}_{ni}} \phi\ll( -\frac{S_{n,i-1}}{\ov{\lambda}_{ni}} \rr) + \frac{X_{ni}^2}{2 \ov{\lambda}_{ni}^2} \phi'\ll( -\frac{S_{n,i-1}}{\ov{\lambda}_{ni}} \rr) \\
% + \frac{|X_{ni}|^3}{6\ov{\lambda}_{ni}^3} \phi''\ll( -\frac{S_{n,i-1} + \theta X_{ni}}{\ov{\lambda}_{ni}} \rr),
%\end{multline}
%where $\theta \in [0,1]$. 
%
%\medskip
%
%\noindent \emph{Step 1.} We show that the last term in (\ref{taylor}), after integration and summation over $i$, is $o(n^{(\alpha - 1)/2})$. Let us define $\Psi(x) = \sup_{|y| \le 1} |\phi''(x+y)|$. Because $X_{ni}$ is uniformly bounded, this term is bounded in absolute value by
%$$
%\frac{C}{\ov{\lambda}_{ni}^3} \Psi\ll( -\frac{S_{n,i-1}}{\ov{\lambda}_{ni}} \rr),
%$$
%and we learn from \cite[Lemma~2]{bo} that 
%$$
%\ll| \E\ll[ \Psi\ll( -\frac{S_{n,i-1}}{\ov{\lambda}_{ni}} \rr) \rr] \rr| \le C \delta(i-1) + C \frac{\ov{\lambda}_{ni}}{\sqrt{i-1}}.
%$$
%The error due to replacing (\ref{eq3}) by its second order Taylor expansion in (\ref{sum}) is therefore bounded, up to a constant, by
%\begin{equation}
%\label{sum2errors}	
%\sum_{i = 1}^n \frac{\delta(i-1)}{\ov{\lambda}_{ni}^3} + \sum_{i = 1}^n  \frac{1}{\ov{\lambda}_{ni}^2 \sqrt{i-1}}.
%\end{equation}
%Assuming (\ref{cond*}) and recalling that $\ov{\lambda}_{ni}^2 = n-i+\kappa_n^2$, the first sum in (\ref{sum2errors}) is bounded by
%$$
%\sum_{i = 1}^{n/2} \frac{1}{(n-i+\kappa_n^2)^{3/2}} + o\ll(n^{(\alpha - 1)/2} \rr) \sum_{i = n/2}^n \frac{1}{(n-i+\kappa_n^2)^{3/2}} = o\ll(n^{(\alpha - 1)/2} \rr).
%$$
%Choisir $\alpha > 1/2$ permet que ça passe, et sans utiliser Lemma 2.
%
%\medskip
%
%\noindent \emph{Step 2.} Same with $Z_i$.
%
%\medskip
%
%\noindent \emph{Step 3.} Combining the results of the two previous steps, we know  that up to a term of order $o\ll(n^{(\alpha - 1)/2}\rr)$, the sum in (\ref{sum}) can be replaced by
%$$
%\sum_{i = 1}^n \E\ll[ \frac{Z_i - X_{ni}}{\ov{\lambda}_{ni}} \phi\ll( -\frac{S_{n,i-1}}{\ov{\lambda}_{ni}} \rr) + \frac{X_{ni}^2 - Z_i^2}{2 \ov{\lambda}_{ni}^2} \phi'\ll( -\frac{S_{n,i-1}}{\ov{\lambda}_{ni}} \rr)   \rr].
%$$
%Conditionally on $S_{n,i-1}$, both $Z_i$ and $X_{ni}$ are centred random variables, so the first part of the summands vanishes, and there remains only
%\begin{equation}
%\label{sumcondi}
%\sum_{i = 1}^n \E\ll[ \frac{X_{ni}^2 - Z_i^2}{2 \ov{\lambda}_{ni}^2} \phi'\ll( -\frac{S_{n,i-1}}{\ov{\lambda}_{ni}} \rr)   \rr] = \sum_{i = 1}^n \E\ll[ \frac{\E[{X_{ni}^2 - 1 \ | \ S_{n,i-1}]}}{2 \ov{\lambda}_{ni}^2} \phi'\ll( -\frac{S_{n,i-1}}{\ov{\lambda}_{ni}} \rr)   \rr].
%\end{equation}
%From the definition of $X_{ni}$, we learn that $\E[X_{ni}^2 - 1 \ | \ S_{n,i-1}]$ is $0$ if $i \le n - n^\alpha$, and otherwise equals
%$$
%\ll|
%\begin{array}{ll}
%1/2 & \text{if } S_{n,i-1} \in I^+_{ni}, \\
%- 1/2 & \text{if } S_{n,i-1} \in I^-_{ni}, \\
%0 & \text{otherwise},
%\end{array}
%\rr.
%$$
%where $I^+_{ni}$ and $I^-_{ni}$ were defined in (\ref{defI}). From this observation, it is clear that each summand in the r.h.s.\ of (\ref{sumcondi}) is positive. 
%
%\medskip
%
%\noindent \emph{Step 4.} We show that the sum in the r.h.s.\ of (\ref{sumcondi}) cannot be $o(n^{(\alpha - 1)/2})$, by examining the contribution of the summands with index $i$ between $n - n^\alpha$ and $n - (n^\alpha)/2$. To this end, it suffices to prove that 
%\begin{equation}
%\label{probaS}
%\P[S_{n,i-1} \in I^+_{ni}] \ge ....
%\end{equation}
%Admitting temporarily that (\ref{probaS}), let us see how to conclude. Each of the summands in the r.h.s.\ of (\ref{sumcondi}) with index $i$ between $n - n^\alpha$ and $n - (n^\alpha)/2$ is larger than a constant times 
%$$
%....
%$$
%
%...
%
%\medskip
%
%\noindent \emph{Step 5.} There remains to show that (\ref{probaS}) is true, for $n - n^\alpha < i \le n - (n^\alpha)/2$. We have
%$$
%\ll|\P[S_{n,i-1} \in I^+_{ni}] - \int_{I^+_{ni}/s(\mbx_{ni})} \d \Phi  \rr| \le 2 \delta(i-1).
%$$
%Using inequality (\ref{s2}), and the fact that $\lambda_{ni} \ge C n^{\alpha/2}$ for $i \le n - (n^\alpha)/2$, it comes that
%$$
%\int_{I^+_{ni}/s(\mbx_{ni})} \d \Phi \ge C \frac{n^{\alpha/2}}{\sqrt{n}},
%$$
%while $\delta(i - 1) = o\ll(i^{(\alpha - 1)/2}\rr)$ by assumption (\ref{cond*}), and this proves (\ref{probaS}).
%
%\end{proof}


\medskip

\noindent \textbf{Acknowledgments.} I would like to thank an anonymous referee for his careful review, and for his mention of the reference \cite{joos}, which I was not aware of.


\begin{thebibliography}{99}

\bibitem[Bo82]{bo} E.~Bolthausen. Exact convergence rates in some martingale central limit theorems. \emph{Ann. Probab.} \textbf{10} (3), 672–688 (1982). 

\bibitem[Dv72]{dvo} A.~Dvoretzky. Asymptotic normality for sums of dependent random variables. \emph{Proceedings of the sixth Berkeley symposium on mathematical statistics and probability 1970/1971}, Vol.~II: Probability theory, 513–535 (1972).

\bibitem[Du]{durrett} R. Durrett. \emph{Probability: theory and examples.} Duxbury Press, second edition (1996).

\bibitem[Ha88]{ha88} E.~Haeusler. On the rate of convergence in the central limit theorem for martingales with discrete and continuous time. \emph{Ann.\ Probab.} \textbf{16} (1), 275-299 (1988).

\bibitem[HH]{hh} P.~Hall, C.C.~Heyde. \emph{Martingale limit theory and its application.}
Probability and mathematical statistics, Academic Press, Inc.\ (1980).

\bibitem[HB70]{hb} C.C.~Heyde, B.M.~Brown. On the departure from normality of a certain class of martingales. \emph{Ann. Math. Statist.} \textbf{41}, 2161–2165 (1970).

\bibitem[Jo89]{joos} K. Joos. \emph{Abschätzungen der Konvergenzgeschwindigkeit in asymptotischen Verteilungsaussagen für Martingale}. Ph.D. thesis, Ludwig-Maximilians-Universität München (1989).

\bibitem[Jo93]{pubjoos} K. Joos. Nonuniform convergence rates in the central limit theorem for martingales. \emph{Studia Sci. Math. Hungar.} \textbf{28} (1-2), 145–158 (1993).

%\bibitem[KV86]{kipvar} C.~Kipnis, S.R.S.~Varadhan. Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions, \emph{Comm. Math. Phys.} \textbf{104}, 1-19 (1986).

\bibitem[Mo11]{berry} J.-C.~Mourrat. A quantitative central limit theorem for the random walk among random conductances. Preprint, 	arXiv:1105.4485v1.

\end{thebibliography}

\end{document}








