text:
\section{Stability of the scalar potentials}\label{new:section}
   In this section we establish a log-log type estimate for the scalar
   potentials. We point out that the estimate from theorem
   \ref{stability:theorem} is independent of the scalar potentials.
   This is because the term involving the difference of said potentials
   is not the leading term in the assympotics \eqref{eq:GF:RHS}
   and it does not survive the process of dividing by $k$ and taking the
   limit as $k\to +\infty$. In the following lines, we reuse the
   techniques developed in the previous sections while following closely
   the ideas from Isakov and Sun in \cite{Isakov:Sun}.

    \begin{thm}\label{stability:theorem:2}
       Suppose that the vector and scalar potentials
       $\mathcal{A}^{(l)}=(A^{(l)}_{0},\dots,A^{(l)}_{n})$,
       $V^{(l)}$, $l=1,2,$
       are real valued, compactly supported and
       $C^{\infty}$ in $t$ and $x$.
       Let $V = V^{(1)} - V^{(2)}$, $ \mathcal{A} = (A_{0},A_{1},\dots,A_{n})$,
       where $ A_{j} = A_{j}^{(1)} - A_{j}^{(2)} $
       and suppose that the following divergence condition holds
       \begin{equation*}
          \mathrm{div}\thinspace\mathcal{A} =
             \partial_{t}A_{0}(t,x) +
             \sum_{j=1}^n{} \partial_{x_{j}}A_{j}(t,x) = 0,
       \end{equation*}
       and that the entries of the vector potential satisfy
      \begin{equation*}
          \mathrm{sup}
             \Big| \int_{-\infty}^{\infty} \big( A_{0} + \sum_{j=0}^{n} \omega_{j} A_{j} \big)
                   (t+s,x+s\omega) \thinspace\mathrm{d}s \Big| < 2\pi,
       \end{equation*}
       where the supremum is taken over $(t,x;\omega) \in [T_{1},T_{2}]\times\Omega\times S^{n-1}$.

       If $\Lambda_{l}$ represents the Dirichlet to Neumann
       operator associated to the hyperbolic problem (1)-(4),
       then for $\Lambda_{1}$, $\Lambda_{2}$ satisfying
       $|||\Lambda_{1} - \Lambda_{2} ||| << 1$, the following
       stability estimates hold
    \begin{align*}
       \big|\big|\big|
       \, \mathcal{A} \,
       \big|\big|\big|_{0}
       & \le C\,\Big( \log
             \frac{ 1 }{|||\Lambda_{1} - \Lambda_{2} |||}
       \Big)^{-1} , \\
       \big|\big| \, V \,
       \big|\big|_{L^{\infty}(\ERRE{}_{t}\times\ERRE{n}_{x})}
       & \le C\,\Big( \log \big( \log
             \frac{ 1 }{|||\Lambda_{1} - \Lambda_{2} |||} \big)
       \Big)^{-1} ,
    \end{align*}
    where
   \begin{equation*}
      ||| \,\mathcal{A}\, |||_{0} =
      ||| \mathcal{A}^{(1)} - \mathcal{A}^{(2)} |||_{0}
      := \max_{0\le j \le n} ||
         A^{(1)}_{j}(t,x) - A^{(2)}_{j}(t,x)
         ||_{L^{\infty}(\ERRE{}_{t}\times\ERRE{n}_{x})}.
   \end{equation*}
    \end{thm}
    \begin{proof}

   In view of our previous results, it is enough to obtain a uniform
   estimate for the X-ray transform along light rays of the difference
   of the scalar potentials.
   By theorem \ref{stability:theorem},
   for arbitrary smooth compactly supported scalar potentials
   $V^{(1)}\neq V^{(2)}$, we have
   \begin{equation}\label{estimate:short}
      ||| \,\mathcal{A}\, |||_{0}
      \le C \Big( \log \frac{1}{|||\Lambda_{1} - \Lambda_{2} |||} \Big)^{-1}.
   \end{equation}
   Green's formula \eqref{eqn:GF} with $u$ and $v$ solutions
   of the forward and backward hyperbolic problem respectively, as well
   as the triangle inequality give
   \begin{multline}\label{Greens:with:triangle}
      \big| \ELEDOTT{(V^{(1)}-V^{(2)})u}{v} \big| \le
      \big| \ELEDOT{(\Lambda_{1}-\Lambda_{2})u}{v}_{\TT{}\times\partial\Omega} \big| \\
          + \sum_{j=0}^{n} \big| \ELEDOTT{(A^{(1)}_{j}-A^{(2)}_{j})u}{(-\rmi\DXJ{j} v)} \big| \\
          + \sum_{j=0}^{n} \big| \ELEDOTT{(A^{(1)}_{j}-A^{(2)}_{j})(-\rmi\DXJ{j} u)}{v} \big| \\
          + \sum_{j=0}^{n} \big| \ELEDOTT{\big[ (A_{j}^{(2)} )^{2}
          - (A_{j}^{(1)} )^{2}\big]u}{v} \big| .
   \end{multline}
   When $u$ and $v$ are given by the GO anzats developed in section
   \ref{sec:review:prev:article}, the
   discussion of the assymptotics of the derivatives
   $\partial_{x_{j}}u,\partial_{x_{j}}v$, $0\le j \le n$,
   give the estimates
   \begin{equation*}
      \big| \ELEDOT{(\Lambda_{1}-\Lambda_{2})u}{v}_{\TT{}\times\partial\Omega} \big|
      \le C k \big( |||\Lambda_{1}-\Lambda_{2}||| + \mathcal{O}(k^{-1}) \big),
   \end{equation*}
   \begin{equation*}
      \big| \ELEDOTT{(A^{(1)}_{j}-A^{(2)}_{j})u}{(-\rmi\DXJ{j} v)} \big|
      \le C k \big( ||| \,\mathcal{A}\, |||_{0} + \mathcal{O}(k^{-1}) \big),
   \end{equation*}
   \begin{equation*}
      \big| \ELEDOTT{(A^{(1)}_{j}-A^{(2)}_{j})(-\rmi\DXJ{j} u)}{v} \big|
      \le C k \big( ||| \,\mathcal{A}\, |||_{0} + \mathcal{O}(k^{-1}) \big),
   \end{equation*}
   \begin{equation*}
      \big| \ELEDOTT{\big[ (A_{j}^{(2)} )^{2} - (A_{j}^{(1)} )^{2}\big]u}{v} \big|
      \le C ||| \,\mathcal{A}\, |||_{0} ,
   \end{equation*}
   where the last inequality follows from the fact that
   $|A^{(1)}_{j}(t,x)-A^{(2)}_{j}(t,x)| \le C$ for all
   $(t,x)\in\ERRE{}_{t}\times\ERRE{n}_{x}$.

   On the other hand,

   the LHS of \eqref{Greens:with:triangle} gives
   \begin{multline}\label{LHS:Greens:with:triangle}
        \Big| \int_{T_{1}}^{T_{2}}\int_{\Omega} V(t,x)u(t,x)\overline{v(t,x)} \, \rmd x \rmd t \Big|
        = \Big| \int_{T_{1}}^{T_{2}}\int_{\Omega}
       V(t,x) \chi_{1}(t,x)\chi_{2}(t,x)
              \thinspace \times \\
              \rme^{-i \int_{-\infty}^{\frac{1}{2} ( t+\omega\cdot x )}
                     \big( A_{0} + \sum_{j=1}^{n} \omega_{j}A_{j}\big)(t'+s,x'+s\omega) \thinspace \mathrm{d}s }
                     \thinspace \mathrm{d}x\thinspace \mathrm{d}t + \cdots \Big|
   \end{multline}
   where $(t',x')$ is the projection of $(t,x)$ onto $\Pi_{(1,\omega)}$ and
   ``$\cdots$'' represents terms of order $\mathcal{O}(k^{-1})$. Also,
   a simple analysis of $\rme^{iz}$ for small $|z|$ gives
   \begin{equation*}
      \rme^{-i \int_{-\infty}^{\frac{1}{2} ( t+\omega\cdot x )}
               \big( A_{0} + \sum_{j=1}^{n} \omega_{j}A_{j}\big)(t'+s,x'+s\omega) \thinspace \mathrm{d}s }
      = 1 + \mathcal{O}\big(||| \,\mathcal{A}\, |||_{0}\big)
   \end{equation*}
   and thus \eqref{Greens:with:triangle} leads to
   \begin{multline*}
      \Big| \int_{T_{1}}^{T_{2}}\int_{\Omega}
       V(t,x) \chi_{1}(t,x)\chi_{2}(t,x)
       \, \rmd x \rmd t \Big| \le \\
      C_{1}k \big(||| \,\mathcal{A}\, |||_{0} + |||\Lambda_{1}-\Lambda_{2}||| \big)
      + C_{2} ||| \,\mathcal{A}\, |||_{0} + \mathcal{O}(k^{-1})
   \end{multline*}
   As in previous cases, the fact that the functions $\chi_{j}$ are supported
   near light rays shows that for $k>0$ the following estimate holds
   \begin{multline}\label{Greens:improved:for:scalar}
      \Big| \int_{-\infty}^{\infty} V(t+s,x+s\omega) \, \rmd s \Big| \le \\
      C_{1}k \big(||| \,\mathcal{A}\, |||_{0} + |||\Lambda_{1}-\Lambda_{2}||| \big)
      + C_{2} ||| \,\mathcal{A}\, |||_{0} + \frac{C_{3}}{k}.
   \end{multline}
   Next we choose $k$ so that the first and last terms in the previous equation
   are comparable in size. To this end, let
   \begin{equation*}
   k  = \big( |||\Lambda_{1} - \Lambda_{2} ||| +
              ||| \,\mathcal{A}\, |||_{0} \big)^{-\frac{1}{2}},
   \end{equation*}
   then
   \begin{equation*}
      \big( |||\Lambda_{1} - \Lambda_{2} ||| +
              ||| \,\mathcal{A}\, |||_{0} \big)k
      = \frac{1}{k} \le C \big( |||\Lambda_{1} - \Lambda_{2} ||| +
              ||| \,\mathcal{A}\, |||_{0} \big)^{\frac{1}{2}},
   \end{equation*}
   and \eqref{Greens:improved:for:scalar} gives
   \begin{align*}
      \Big| \int_{-\infty}^{\infty} V(t+s,x+s\omega) \, \rmd s \Big|
       & \le C_{1} \big( |||\Lambda_{1}-\Lambda_{2}|||
	     + ||| \,\mathcal{A}\, |||_{0} \big)^{\frac{1}{2}}
             + C_{2} ||| \,\mathcal{A}\, |||_{0} \\
       & \le C \big( ||| \,\mathcal{A}\, |||^{\frac{1}{2}}_{0}
              + |||\Lambda_{1}-\Lambda_{2}|||^{\frac{1}{2}} \big),
   \end{align*}
   where the last inequality holds when both
   $|||\Lambda_{1} - \Lambda_{2}|||,||| \,\mathcal{A}\, |||_{0} < 1$
   (recall that if $0<\epsilon<1$, then $\epsilon < \sqrt{\epsilon} < 1$).
   Estimate \eqref{estimate:short} then gives
   \begin{align}\label{estimate:Xray:scalar:potentials} \nonumber
      \Big| \int_{-\infty}^{\infty} V(t+s,x+s\omega)\,\rmd s \Big|
          & \le C \Big[ \big( \log\frac{1}{|||\Lambda_{1}-\Lambda_{2}|||} \big)^{-\frac{1}{2}}
              + |||\Lambda_{1} - \Lambda_{2} |||^{\frac{1}{2}} \Big] \\
          & \le C \big( \log\frac{1}{|||\Lambda_{1}-\Lambda_{2}|||} \big)^{-\frac{1}{2}} .

   \end{align}
   As in section \ref{sec:stability:estimates} we get from \eqref{estimate:Xray:scalar:potentials}
   \begin{align*}
      \big|\big| \,V\, \big|\big|_{L^{\infty}(\ERRE{}_{t}\times\ERRE{n}_{x})}
       & \le C' \Big( \log \frac{1}{ C \big( \log
                \frac{1}{|||\Lambda_{1}-\Lambda_{2}|||} \big)^{-1/2}} \Big)^{-1} \\
       & \le C \Big( \log \big( \log \frac{1}{|||\Lambda_{1}-\Lambda_{2}|||}\big) \Big)^{-1}.
   \end{align*}

    \end{proof}


text:
\begin{document}

\title{The saturation number for Cayley's cubic surface}

\author{Yuchao Wang}

\address{
School of Mathematics, Shandong University, Jinan, 250100, China}

\email{yuchaowang@mail.sdu.edu.cn}

\begin{abstract}
We investigate the density of rational points on Cayley's cubic surface whose coordinates have few prime factors. The key tools used are the circle method and universal torsors.
\end{abstract}
\keywords{universal torsors, circle method}

\subjclass[2010]{11D25, 11P32, 11P55}

\maketitle

\section{Introduction}
Cayley's cubic surface is defined in $\mathbb{P}^3$ by the equation
\begin{equation*}
S_0:\ x_2x_3x_4+x_1x_3x_4+x_1x_2x_4+x_1x_2x_3=0.
\end{equation*}
It has singularity type $4\mathbf{A}_1$. Moreover, there are 9 lines in the surface, three of which have the form $x_i+x_j=x_k+x_l=0$, and the remaining six have the shape $x_i=x_j=0$. We shall write $U_0$ for the complement of these lines in the surface $S_0$.

Heath-Brown \cite{Hb} considered the density of rational points on Cayley's cubic surface. Let $\mathbb{Z}^4_{\text{prim}}$ be the set of vectors $\mathbf{x}=(x_1,x_2,x_3,x_4)\in\mathbb{Z}^4$ with $\text{gcd}(x_1,x_2,x_3,x_4)=1$. Then we set
\begin{equation*}
N(B)=\#\{\mathbf{x}\in \mathbb{Z}^4_{\text{prim}}:\ [\mathbf{x}]\in U_0, \max |x_i|\leq B \}.
\end{equation*}
Manin (see Batyrev and Manin \cite{BM}) has given a very general conjecture which would predict in this case that there is a suitable positive constant $c$ such that $N(B)\sim cB(\log B)^6$, as $B\rightarrow \infty$. Heath-Brown \cite{Hb} showed that
\begin{equation*}
B(\log B)^6\ll N(B)\ll B(\log B)^6.
\end{equation*}
The approach combines analytic methods with the theory of universal torsors. For details of universal torsors for singular del Pezzo surfaces, we refer the reader to Derenthal \cite{D}.

In this paper we are concerned with the almost prime integral points on Cayley's cubic surface. Let $P_r$ indicate an $r$-almost prime, which is a number with at most $r$ prime factors, counted with multiplicity. For any cubic surface $S$, we write $U$ for the complement of the lines in the surface $S$. Then we define the saturation number $r(S)$ to be the least number $r$ such that the set of $\mathbf{x}\in \mathbb{Z}^4_{\text{prim}}$ for which $[\mathbf{x}]\in U$ and $x_1x_2x_3x_4=P_r$ , is Zariski dense in $U$. The main aim of this paper is to show that $r(S_0)<\infty$.

Bourgain, Gamburd and Sarnak \cite{BGS} and Nevo and Sarnak \cite{NS} established upper bounds for saturation numbers for orbits of congruence subgroups of semi-simple groups acting linearly on affine space. Moreover, Liu and Sarnak \cite{LS} considered the saturation number for certain affine quadric surfaces. Note that Derenthal and Loughran \cite{DL,DL2} have shown that Cayley's cubic surface is not an equivariant compactification of a linear algebraic group. Thus the methods of \cite{BGS} or \cite{NS} do not apply to $S_0$.

To prove that a set of $[\mathbf{x}]\in U_0$ is Zariski dense, it suffices to prove that given $\varepsilon>0$ and any $\boldsymbol{\xi}\in\mathbb{R}^4$ satisfying $[\boldsymbol{\xi}]\in U_0$, there exists $B\in \mathbb{N}$ sufficiently large and at least one point $[\mathbf{x}]$ in the set, such that
\begin{equation*}
\left|\frac{\mathbf{x}}{B}-\boldsymbol{\xi}\right|< \varepsilon.
\end{equation*}
We will prove the following.
\begin{thm}
Let $[\boldsymbol{\xi}]\in U_0$ and define
\begin{equation*}
\begin{split}
M_{U_0}(\boldsymbol{\xi},B,r)=\# \{&\mathbf{x}\in\mathbb{Z}^4_{\text{prim}}:\ [\mathbf{x}]\in U_0,\  \left|\frac{\mathbf{x}}{B}-\boldsymbol{\xi}\right|\ll (\log B)^{-1},\\
&\ x_1x_2x_3 x_4=P_r\}.
\end{split}
\end{equation*}
Then for sufficiently large $B$, we have
\begin{equation*}
M_{U_0}(\boldsymbol{\xi},B,12)\gg B(\log B)^{-7}.
\end{equation*}
The implicit constants are allowed to depend on $\boldsymbol{\xi}$. In particular, the saturation number satisfies $r(S_0)\leq 12$.
\end{thm}
Define $\tilde{r}(S_0)$ to be the least number $\tilde{r}$ such that the set of $\mathbf{x}\in \mathbb{Z}^4_{\text{prim}}$ for which $[\mathbf{x}]\in U_0$ and the product $x_1x_2x_3x_4$ has at most $\tilde{r}$ distinct prime factors, is Zariski dense in $U_0$. Then it is worth pointing out that our methods give $\tilde{r}(S_0)\leq 4$.

The idea of the proof is to apply the theory of universal torsors to specify some integral solutions in a particular form, whose coordinates have few prime factors, and then give a lower bound for the number of such solutions which are close to some fixed real solution via the circle method. More precisely, we use the circle method to count the number of solutions to the equation
\begin{equation*}
\beta_1p_1+\beta_2p_2+\beta_3p_3+\beta_4p_4=0,
\end{equation*}
where $p_i$ are primes which lie in certain intervals and $\beta_i\in\{1,-1\}$, for $i=1,\dots,4$.

It seems likely that similar methods will apply to several other singular cubic surfaces. Let $S_1\subset \mathbb{P}^3$ be the cubic surface given by the equation
\begin{equation*}
x_1x_2x_3=x_4(x_1+x_2+x_3)^2.
\end{equation*}
There is a unique singular point which is of type $D_4$. The density of rational points of bounded height on $S_1$ has been studied by Browning \cite{Br} and Le Boudec \cite{Le}. Arguing similarly as in this paper, we can show that $r(S_1)\leq 12$.
\begin{ack}
\emph{The author wishes to express his sincere appreciation to Tim Browning for introducing him to this problem and giving him various suggestions. This work was carried out while the author was a visiting PhD student at University of Bristol. The author is grateful for the hospitality. While working on this paper the author was supported by the China Scholarship Council.}
\end{ack}
\section{The circle method}
Suppose
\begin{equation*}
F(t_1,t_2,t_3,t_4)=\beta_1t_1+\beta_2t_2+\beta_3t_3+\beta_4t_4
\end{equation*}
is a linear form, with the coefficients $\beta_i\in \{-1,1\}$.
Suppose $\eta_1$, $\dots$, $\eta_4$ are fixed positive real numbers, satisfying
\begin{equation*}
F(\eta_1,\eta_2,\eta_3,\eta_4)=\beta_1\eta_1+\beta_2\eta_2+\beta_3\eta_3+\beta_4\eta_4=0.
\end{equation*}
Write
\begin{equation*}
I_j=[\eta_j B^{\frac{1}{3}}-B^{\frac{1}{3}}(\log B)^{-1},\eta_jB^{\frac{1}{3}}+B^{\frac{1}{3}}(\log B)^{-1}],
\end{equation*}
for $j=1,2,3,4$, where $B$ is a sufficiently large parameter. Furthermore, set
\begin{equation*}
R(B)=\sum_{\stackrel{p_j\in I_j}{F(p_1,p_2,p_3,p_4)=0}}(\log p_1)(\log p_2)(\log p_3)(\log p_4).
\end{equation*}
In this section, we use the circle method to prove the following lemma.
\begin{lem}
For any $A>0$, we have
\begin{equation*}
R(B)=J(B)\mathfrak{S}+O(B(\log B)^{-A}),
\end{equation*}
where $J(B)$ is the number of solutions of
\begin{equation*}
F(m_1,m_2,m_3,m_4)=0
\end{equation*}
with $m_j\in I_j $ and
\begin{equation*}
\mathfrak{S}=\prod_{p}\Big(1+\frac{1}{(p-1)^3}\Big).
\end{equation*}
Moreover, we have $J(B)\gg B(\log B)^{-3}$ and $\mathfrak{S}\gg1$.
\end{lem}
\begin{proof}
Write
\begin{equation*}
L=\log B,\qquad P=L^D, \qquad Q=B^{\frac{1}{3}}P^{-3},
\end{equation*}
where $D$ is a sufficiently large parameter to be chosen later. Furthermore, denote
\begin{equation*}
S_j(\alpha)=\sum_{p_j\in I_j}\log p_j e(\beta_jp_j\alpha ).
\end{equation*}
Then we have
\begin{equation*}
R(B)=\int_{\frac{1}{Q}}^{1+\frac{1}{Q}}S_1(\alpha)S_2(\alpha)S_3(\alpha)S_4(\alpha)d \alpha.
\end{equation*}
By Dirichlet's lemma on rational approximation, each $\alpha\in (\frac{1}{Q},1+\frac{1}{Q}]$ may be written in the form
\begin{equation*}
\alpha=\frac{a}{q}+\lambda,\quad |\lambda|<\frac{1}{qQ},
\end{equation*}
for some integers $a$, $q$ with $1\leq a\leq q\leq Q$ and $(a,q)=1$. Now we define the sets of major and minor arcs as follows:
\begin{equation*}
\mathfrak{M}=\bigcup_{q\leq P}\bigcup_{\stackrel{1\leq a\leq q}{(a,q)=1}}\Big[\frac{a}{q}-\frac{1}{qQ},\frac{a}{q}+\frac{1}{qQ}\Big], \quad \mathfrak{m}=\big(\frac{1}{Q},1+\frac{1}{Q}\big]\setminus \mathfrak{M}.
\end{equation*}
Then
\begin{equation*}
R(B)=\int_{\mathfrak{M}}S_1(\alpha)S_2(\alpha)S_3(\alpha)S_4(\alpha)d \alpha+\int_{\mathfrak{m}}S_1(\alpha)S_2(\alpha)S_3(\alpha)S_4(\alpha)d \alpha.
\end{equation*}
\subsection{The major arcs}
We first estimate the contribution of the integral over the major arcs. For any $\alpha\in\mathfrak{M}$, there exist integers $a$ and $q$ such that
\begin{equation*}
\alpha=\frac{a}{q}+\lambda,\quad 1\leq q \leq P,\quad (a,q)=1 \quad \text{and}\quad |\lambda|<\frac{1}{qQ}.
\end{equation*}
Hence
\begin{equation*}
\begin{split}
S_j(\alpha)&=\sum_{p_j\in I_j}\log p_j e\Big(\frac{\beta_jap_j}{q}\Big)e(\beta_j\lambda p_j)\\
&=\frac{1}{\phi(q)}\sum_{\chi\  \text{mod}\  q}\sum_{\stackrel{h=1}{(h,q)=1}}^{q}e\Big(\frac{\beta_jah}{q}\Big)\bar{\chi}(h)\sum_{p_j\in I_j}\log p_j\chi(p_j)e(\beta_j\lambda p_j).
\end{split}
\end{equation*}
Let
\begin{equation*}
W_j(\chi,\lambda)=\sum_{m_j\in I_j}(\Lambda(m_j)\chi(m_j)-\delta_{\chi})e(\beta_j\lambda m_j),
\end{equation*}
and
\begin{equation*}
\widehat{W}_j(\chi,\lambda)=\sum_{p_j\in I_j}\log p_j \chi(p_j)e(\beta_j\lambda p_j)-\sum_{m_j\in I_j}\delta_{\chi}e(\beta_j\lambda m_j),
\end{equation*}
where $\delta_{\chi}=1$ or $0$ according as $\chi$ is principal or not. Then we have
\begin{equation}
W_j(\chi,\lambda)-\widehat{W}_j(\chi,\lambda)=\sum_{k\geq2}\sum_{p_j^k\in I_j}\log p_j \chi(p_j^k)e(\beta_j\lambda p_j^k)\ll B^{\frac{1}{6}}L.
\end{equation}
Thus
\begin{equation}
\begin{split}
&S_j(\alpha)-\frac{\mu(q)}{\phi(q)}\sum_{m_j\in I_j}e(\beta_j\lambda m_j)\\
=&\frac{1}{\phi(q)}\sum_{\chi\,\text{mod}\,q}\sum_{\stackrel{h=1}{(h,q)=1}}^q e\Big(\frac{\beta_jah}{q}\Big)\bar{\chi}(h)\widehat{W}_j(\chi,\lambda)\\
=&\frac{1}{\phi(q)}\sum_{\chi\,\text{mod}\,q}\sum_{\stackrel{h=1}{(h,q)=1}}^q e\Big(\frac{\beta_jah}{q}\Big)\bar{\chi}(h)(\widehat{W}_j(\chi,\lambda)-W_j(\chi,\lambda))\\
&+\frac{1}{\phi(q)}\sum_{\chi\,\text{mod}\,q}\sum_{\stackrel{h=1}{(h,q)=1}}^q e\Big(\frac{\beta_jah}{q}\Big)\bar{\chi}(h)W_j(\chi,\lambda).
\end{split}
\end{equation}
The main tool here is a short intervals version of Siegel-Walfisz theorem. Using (6) in Perelli and Pintz \cite{P}, we see that
\begin{equation*}
\sum_{m_j\in I_j}\Lambda(m_j)\chi(m_j)=\sum_{m_j\in I_j}\delta_{\chi}+O(B^{\frac{1}{3}}L^{-1-5D}).
\end{equation*}
Therefore, integration by parts gives
\begin{equation*}
\begin{split}
W_j(\chi,\lambda)=&\int_{I_j}e(\beta_j\lambda u)d\big( \sum_{m_j\leq u,m_j\in I_j}(\Lambda(m_j)\chi(m_j)-\delta_{\chi})\big)\\
\ll& \big|\sum_{m_j\in I_j}(\Lambda(m_j)\chi(m_j)-\delta_{\chi})\big|\\
&+\Big|\lambda\int_{I_j}e(\beta_j\lambda u)\big( \sum_{m_j\leq u,m_j\in I_j}(\Lambda(m_j)\chi(m_j)-\delta_{\chi})\big) du\Big|\\
\ll& (1+|\lambda|B^{\frac{1}{3}}L^{-1})B^{\frac{1}{3}}L^{-1-5D}.
\end{split}
\end{equation*}
Thus we obtain
\begin{equation}
W_j(\chi,\lambda)\ll (1+|\lambda|B^{\frac{1}{3}}L^{-1})B^{\frac{1}{3}}L^{-1-5D}\ll B^{\frac{1}{3}}L^{-2-2D}.
\end{equation}
Combining (2.1), (2.2) and (2.3), we get
\begin{equation*}
S_j(\alpha)=\frac{\mu(q)}{\phi(q)}\sum_{m_j\in I_j}e(\beta_j\lambda m_j)+O(B^{\frac{1}{3}}L^{-2D}).
\end{equation*}
We have similar results for $S_2(\alpha)$, $S_3(\alpha)$ and $S_4(\alpha)$. Thus we obtain
\begin{equation}
\begin{split}
&\int_{\mathfrak{M}}S_1(\alpha)S_2(\alpha)S_3(\alpha)S_4(\alpha)d \alpha \\
&-\sum_{q\leq P}\frac{{\mu}^2(q)}{{\phi}^4(q)}\sum_{\stackrel{a=1}{(a,q)=1}}^{q}\int_{-\frac{1}{qQ}}^{\frac{1}{qQ}}\sum_{m_j\in I_j}e(\lambda F(m_1,m_2,m_3,m_4))d\lambda\\
&\ll BL^{-D}.
\end{split}
\end{equation}
Note that
\begin{equation*}
\begin{split}
&\int_{-\frac{1}{2}}^{\frac{1}{2}}\sum_{m_j\in I_j}e(\lambda F(m_1,m_2,m_3,m_4))d\lambda\\
&-\int_{-\frac{1}{qQ}}^{\frac{1}{qQ}}\sum_{m_j\in I_j}e(\lambda F(m_1,m_2,m_3,m_4))d\lambda\ll BL^{-D}.
\end{split}
\end{equation*}
Inserting this into (2.4), we obtain
\begin{equation}
\int_{\mathfrak{M}}S_1(\alpha)S_2(\alpha)S_3(\alpha)S_4(\alpha)d \alpha=J(B)\mathfrak{S}(P)+O(BL^{-D}),
\end{equation}
where
\begin{equation*}
\mathfrak{S}(P)=\sum_{q=1}^{P}\frac{{\mu(q)}^2}{{\phi(q)}^3}.
\end{equation*}
\subsection{The minor arcs}
Now we estimate the contribution of the integral over the minor arcs. For any $\alpha\in\mathfrak{m}$, there exist integers $a$ and $q$ such that
\begin{equation*}
P\leq q\leq Q,\quad (a,q)=1 \quad \text{and} \quad \Big| \alpha-\frac{a}{q}\Big|<\frac{1}{qQ}.
\end{equation*}
Using the non-trivial upper bound for the exponential sums over primes in short intervals, we get
\begin{equation*}
S_1(\alpha)\ll B^{\frac{1}{3}}(\log B)^{-A},
\end{equation*}
provided $D$ is chosen to be sufficiently large. Such a result can be found in several references, for example see Theorem 2 in Zhan \cite{Z}. Also, we have the following mean-value estimate:
\begin{equation*}
\int_{\frac{1}{Q}}^{1+\frac{1}{Q}}|S_j(\alpha)|^2 d\alpha \ll B^{\frac{1}{3}}.
\end{equation*}
By Cauchy's inequality, we obtain
\begin{equation*}
\int_{\frac{1}{Q}}^{1+\frac{1}{Q}}|S_2(\alpha)S_3(\alpha)| d\alpha \ll B^{\frac{1}{3}}.
\end{equation*}
Thus we have
\begin{equation}
\int_{\mathfrak{m}}S_1(\alpha)S_2(\alpha)S_3(\alpha)S_4(\alpha)d \alpha\ll BL^{-A}.
\end{equation}
Combining (2.5) and (2.6), we get
\begin{equation*}
R(B)=J(B)\mathfrak{S}(P)+O(BL^{-A}).
\end{equation*}
\subsection{The singular series}
For the singular series, we have
\begin{equation*}
\Big|\frac{{\mu(q)}^2}{{\phi(q)}^3}\Big|\leq \frac{1}{{\phi(q)}^3}.
\end{equation*}
Note that
\begin{equation*}
\mathfrak{S}=\prod_{p}\Big(1+\frac{1}{(p-1)^3}\Big)=\sum_{q=1}^{\infty}\frac{{\mu(q)}^2}{{\phi(q)}^3}\gg 1.
\end{equation*}
Thus we obtain
\begin{equation*}
\mathfrak{S}(P)-\mathfrak{S}\ll\sum_{q>P}\frac{1}{{\phi(q)}^3}\ll L^{-D}.
\end{equation*}
Since $J(B)\ll B(\log B)^{-3}$, then we have
\begin{equation*}
R(B)=J(B)\mathfrak{S}+O(B(\log B)^{-A}).
\end{equation*}
Now we establish the lower bound for $J(B)$. For $j=1,2,3$, we fix $m_j\in[\eta_j B^{\frac{1}{3}}-\frac{1}{3}B^{\frac{1}{3}}(\log B)^{-1},\eta_jB^{\frac{1}{3}}+\frac{1}{3}B^{\frac{1}{3}}(\log B)^{-1}]$. Recall that
\begin{equation*}
\beta_1\eta_1+\beta_2\eta_2+\beta_3\eta_3+\beta_4\eta_4=0,
\end{equation*}
thus we have
\begin{equation*}
\beta_1 m_1+\beta_2 m_2+\beta_3 m_3\in[-\beta_4\eta_4 B^{\frac{1}{3}}-B^{\frac{1}{3}}(\log B)^{-1},-\beta_4\eta_4B^{\frac{1}{3}}+B^{\frac{1}{3}}(\log B)^{-1}].
\end{equation*}
Since
\begin{equation*}
I_4=[\eta_4 B^{\frac{1}{3}}-B^{\frac{1}{3}}(\log B)^{-1},\eta_4B^{\frac{1}{3}}+B^{\frac{1}{3}}(\log B)^{-1}],
\end{equation*}
then we obtain
\begin{equation*}
J(B)\gg B(\log B)^{-3}.
\end{equation*}
Therefore we prove the lemma.
\end{proof}
\section{The universal torsor}
In this section, we use a passage to the universal torsor for Cayley's cubic surface. Details can be found in Section 2 of Heath-Brown \cite{Hb}. It is shown that the universal torsor for Cayley's cubic surface is an open subvariety in
\begin{equation*}
\mathbb{A}^{13}=\text{Spec}\mathbb{Z}[v_{12},v_{13},v_{14},y_1,y_2,y_3,y_4,z_{12},z_{13},z_{14},z_{23},z_{24},z_{34}],
\end{equation*}
defined by six equations of the form
\begin{equation*}
z_{ik}z_{il}y_j+z_{jk}z_{jl}y_i=z_{ij}v_{ij}
\end{equation*}
and three equations of the form
\begin{equation*}
v_{ij}v_{ik}=z_{il}^2y_jy_k-z_{jk}^2y_iy_l,
\end{equation*}
where
\begin{equation*}
z_{ij}=z_{ji},\quad v_{ij}=v_{ji},\quad and \quad v_{ij}=-v_{kl}.
\end{equation*}
In fact, we are not working with the full universal torsor. We need the following lemma, which is essentially a restatement of Lemma 1 in Heath-Brown \cite{Hb}.
\begin{lem}
Let $[\mathbf{x}]\in U_0$ be a primitive integral solution. Then either $\mathbf{x}$ or $-\mathbf{x}$ takes the form
\begin{equation*}
\begin{split}
&x_1=z_{12}z_{13}z_{14}y_2y_3y_4,\\
&x_2=z_{12}z_{23}z_{24}y_1y_3y_4,\\
&x_3=z_{13}z_{23}z_{34}y_1y_2y_4,\\
&x_4=z_{14}z_{24}z_{34}y_1y_2y_3,
\end{split}
\end{equation*}
with non-zero integer variables $y_i$ and positive integer variables $z_{ij}$ constrained by the conditions
\begin{equation*}
\text{gcd}(y_i,y_j)=1,
\end{equation*}
\begin{equation*}
\text{gcd}(y_i,z_{ij})=1,
\end{equation*}
\begin{equation*}
\text{gcd}(z_{ab},z_{cd})=1,
\end{equation*}
for $\{a,b\}$, $\{c,d\}$ distinct, and satisfying the equation
\begin{equation*}
z_{23}z_{24}z_{34}y_1+z_{13}z_{14}z_{34}y_2+z_{12}z_{14}z_{24}y_3+z_{12}z_{13}z_{23}y_4=0.
\end{equation*}
Moreover, none of $z_{23}z_{24}z_{34}y_1+z_{13}z_{14}z_{34}y_2$, $z_{23}z_{24}z_{34}y_1+z_{12}z_{14}z_{24}y_3$ or $z_{23}z_{24}z_{34}y_1+z_{12}z_{13}z_{23}y_4$ may vanish. Conversely, if $y_i$ and $z_{ij}$ are as above, then the vector $\mathbf{x}$ taking the above form, will be a primitive integral solution lying on $U_0$.
\end{lem}
\section{The proof of the theorem}
Recall that $[\boldsymbol{\xi}]\in U_0$. Thus we get $\xi_1\xi_2\xi_3\xi_4\neq0$, and $\xi_k+\xi_l\neq0$ for $k\neq l$. Now fix
\begin{equation*}
\eta_j=\Big|\frac{\sqrt[3]{\xi_1\xi_2\xi_3\xi_4}}{\xi_j}\Big|,\quad \beta_j=\text{sgn}\Big(\frac{\sqrt[3]{\xi_1\xi_2\xi_3\xi_4}}{\xi_j}\Big),
\end{equation*}
for $j=1,2,3,4$. Then we obtain that $\eta_1$, $\eta_2$, $\eta_3$ and $\eta_4$ are positive numbers, satisfying
\begin{equation*}
\beta_k\eta_k+\beta_l\eta_l\neq0,
\end{equation*}
for $k\neq l$, and
\begin{equation*}
\beta_1\eta_1+\beta_2\eta_2+\beta_3\eta_3+\beta_4\eta_4=0.
\end{equation*}
By Lemma 2, we obtain that for sufficiently large $B$, there exists a suitable positive constant $c$, such that there are at least $cB(\log B)^{-7}$ solutions to the equation
\begin{equation*}
\beta_1p_1+\beta_2p_2+\beta_3p_3+\beta_4p_4=0,
\end{equation*}
with $p_j\in I_j$. Among these solutions, there are at most $O(B^{\frac{2}{3}}(\log B)^{-2})$ ones with $\mu(p_1p_2p_3p_4)=0$. Thus we still have at least $c'B(\log B)^{-7}$ solutions satisfying $\mu(p_1p_2p_3p_4)\neq0$, where $c'$ is a positive constant. In Lemma 3, we fix $z_{12}=z_{13}=z_{14}=z_{23}=z_{24}=z_{34}=1$. Then the relations become
\begin{equation*}
y_1+y_2+y_3+y_4=0,
\end{equation*}
\begin{equation*}
\text{gcd}(y_i,y_j)=1,
\end{equation*}
and none if $y_1+y_2$, $y_1+y_3$ or $y_1+y_4$ may vanish. We also have
\begin{equation*}
\begin{split}
&x_1=y_2y_3y_4,\\
&x_2=y_1y_3y_4,\\
&x_3=y_1y_2y_4,\\
&x_4=y_1y_2y_3.
\end{split}
\end{equation*}
Now we set $y_j= \beta_jp_j$. Thus we obtain
\begin{equation*}
x_i=\prod\limits_{\stackrel{j=1}{j\neq i}}^{4}\beta_jp_j.
\end{equation*}
Obviously, we get $\mathbf{x}\in \mathbb{Z}^4_{\text{prim}}$, $[\mathbf{x}]\in U_0$ and $\mathbf{x}$ primitive. For $x_1$, we have
\begin{equation*}
\left|\frac{x_1}{B}-\beta_2\beta_3\beta_4\eta_2\eta_3\eta_4\right|\ll (\log B)^{-1}.
\end{equation*}
Note that $\beta_2\beta_3\beta_4\eta_2\eta_3\eta_4=\xi_1$, then
\begin{equation*}
\left|\frac{x_1}{B}-\xi_1\right|\ll (\log B)^{-1}.
\end{equation*}
Arguing similarly as above, we get
\begin{equation*}
\left|\frac{\mathbf{x}}{B}-\boldsymbol{\xi}\right|\ll (\log B)^{-1}.
\end{equation*}
Thus the proof is concluded.

config: arxiv


text:
\begin{document}
\title{Density estimation for RWRE}
\author{A. Havet }
\address{Centre de Math\'ematiques Appliqu\'ees, \'Ecole polytechnique, CNRS Universit\'e Paris-Saclay}
\email{antoine.havet@polytechnique.edu}
\author{ M. Lerasle}\address{Laboratoire de Math\'ematiques d'Orsay, Univ. Paris-Sud, CNRS, Universit\'e Paris Saclay}
\email{matthieu.lerasle@polytechnique.edu}
\author{\'Eric Moulines}\address{Centre de Math\'ematiques Appliqu\'ees, \'Ecole polytechnique, CNRS Universit\'e Paris-Saclay}
\email{eric.moulines@polytechnique.edu}
\maketitle

\begin{abstract}
 We consider the problem of non-parametric density estimation of a random environment from the observation of a single trajectory of a random walk in this environment. We first construct a density estimator using the beta-moments.  We then show that the Goldenshluger-Lepski method can be used to select the beta-moment. We prove non-asymptotic bounds for the supremum norm of these estimators for both the recurrent and the transient to the right case.  A simulation study supports our theoretical findings.
\end{abstract}
\section{Introduction}

A random walk in random environment (RWRE) provides a simple model to describe various problems, for example the propagation of heat, diffusion of  matter through a physical medium, or DNA-unzipping experiments. In many situations of practical interest,  the medium in which the system evolve is very irregular. In these cases, it is  natural  to model these irregularities as a random environment. The definition of an RWRE involves two ingredients: (i) the environment, which is an \iid\ sample of some unknown disribution $\nu$ and (ii) the random-walk whose transition probabilities are dermined by the environment.  This paper considers the problem of recovering the density $\tdens$ of the distribution $\nu$ of the environment of a RWRE on $\relatif$ based on the observation of a single trajectory of the RWRE.

Since their introduction by Chernov \cite{Chernov:1967}, RWRE have been widely studied in the probability literature; see for example \cite{Zei:2012} for a recent overview of probabilistic results on RWRE in $\relatif$ and more generally in $\relatif^d$. On the other hand, statistical inference for RWRE has emerged only recently with the appearance of RWRE in several statistical models such as DNA-unzipping experiments or DNA- polymerase phenomenon \cite{Alemany2012, Baldazzi2007, Baldazzi2006, Huguet2009, Koch2002}. In these applications, the main task is usually to recover the environment itself and, when it is the case, an estimator of $\nu$ can be considered as a preliminary  step in the construction of a an empirical Bayes estimator.

More precisely, the problem of recovering $\nu$ was originally considered in \cite{Ade_Enr:2004} who introduced an estimator of the moments of the distribution. The article \cite{Ade_Enr:2004} considered random walks in general state spaces but the estimators they deduced had poor statistical performance. More recently, \cite{Fal_Lou_Mat:2014, Fal_Glo_Lou:2014, comets:falconnet:2014,Comets2016Maximum} considered the random walk on $\relatif$ and studied the parametric estimation of $\nu$. More precisely, they proved consistency and asymptotic normality of the maximum likelihood estimator in the ballistic and sub-ballistic regimes as well as its efficiency in the ballistic regime (see Section~\ref{sec:setting} for details regarding these notions). Some of these consistency results have been extended to i.i.d. environments in recurrent regimes in \cite{Comets2016Maximum} for a slightly different estimator and also to Markovian environments in \cite{AndLouMat2015}.

It is shown in \cite{comets:falconnet:2014} and \cite{diel:lerasle:2016}  that the beta-moments of the distribution $\nu$ can be estimated consistently from a single trajectory of the RWRE. In \cite{diel:lerasle:2016}, these estimators of moments are used to construct an estimator of the cumulative distribution function (c.d.f.) of the random environment. In this paper, we use these moment estimators to construct estimators of the probability density.

Recovering the probability density  of a distribution from its moment is a classical problem in statistics called \textit{moment reconstruction} \cite{akhiezer:1965}. Density estimators of a distribution based on its beta-moments (also referred to as beta-kernel estimators) have already been studied in the classical i.i.d. direct  observation setting, where a sample $(Z_1,\dots,Z_n)$ of the unknown distribution is available for the inference (see for example \cite{chen1999BetaKernel,bouezmarni:rolin:2003,mnatsakanov:2008} and the references therein). In the direct observation setting, \cite{chen:1999} proposed to estimate the density  $f$ at a point $x \in \ccint{0,1}$  by a single appropriately chosen $\beta$-moment
\[
\hat{f}_h(x)= \frac{1}{n} \sum_{i=1}^n \betaker{\frac{x}{h}+1}{\frac{1-x}{h}+1}(Z_i) \eqsp,
\]
where $h$ is the smoothing bandwidth and for any $(a,b)$ in $\reel_+^*\times\reel_+^*$,  $\betaker{a}{b}$ is the beta function
\begin{equation}
\label{def:BetaKer}
\betaker{a}{b}(u) = \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)} u^{a-1} (1-u)^{b-1} \indic{0\leqslant u \leqslant 1} \eqsp.
\end{equation}
\cite{chen1999BetaKernel} introduced this estimator for a density function on $\ccint{0,1}$ in order to remove the boundary bias of the standard kernel estimator. He proved that this estimator is free of boundary bias.  This beta-kernel density estimator has later been shown to be minimax under classical regularity assumptions on the density $f$ by \cite{bertin:klutchnikoff:2010}.  \cite{bertin:klutchnikoff:2010}.

Our contribution is threefold. First, we propose a non-parametric density estimator for the random environment of a RWRE. To our best knowledge, this is the first density estimator of the distribution of the environment. Our proposed methodolgy follows the same steps than the classical density estimation problem but our construction is not a "kernel" estimator, contrary to the "direct-observation" case.
The unknown density $f$ of $\nu$ is first approximated at every point $x\in(0,1)$ by a sequence of properly chosen beta kernels following  \cite{chen1999BetaKernel,mnatsakanov:2008}. The $\beta$-moments are estimated using the methods outlined in \cite{diel:lerasle:2016}. The proposed density estimator is a function of  bandwidth parameter. We propose and analyze a method to choose automatically this bandwidth parameter, based on the Goldenshluger-Lepski algorithm \cite{goldenshluger:lepski:2008}. This extra step of selection is crucial here to optimize our bound without any prior knowledge of the regime of the walk or the regularity of the unknown density (see Section~\ref{sec:MainRes} for details). The Goldenshluger-Lepski method was also used in \cite{bertin:klutchnikoff:2014} to build adaptive estimators in the i.i.d. setting based on the minimax estimators of \cite{bertin:klutchnikoff:2010}.

Our second contribution is a derivation of the first non-parametric risk bounds for any density estimator of $f$ based on the observation of a single trajectory of a RWRE. These are exploiting the results recently developed in \cite{diel:lerasle:2016} for the stochastic part of the risk. We are of course also using some of the results on the beta-kernel estimator presented in \cite{Bouezmarni2003Consistency,mnatsakanov:2008,bertin:klutchnikoff:2010}.
Our rates do not match minimax rates of density estimation in i.i.d. setting.

Nevertheless, our results outperform those obtained in \cite{Comets2016Maximum} in the recurrent regime where only consistency results for very particular densities were derived. Furthermore, our estimator does not require a prior knowledge on the regime of the walk contrary to that of \cite{Comets2016Maximum} - the results in this work presuppose that RWRE is recurrent, which is not required here.

We finally investigate the numerical behaviour of our estimator in a Monte Carlo experiment.

It is interesting to notice that our estimator behaves reasonably

in ballistic regimes even if the chain has a linear drift. This emphasizes the difference between population and individual parameters estimation problems. It is clear that recovering the environment itself is impossible in the ballistic regime, yet estimating the law of the random environment is still possible.

Related results  have already been reported in a parametric setting for example in \cite{Fal_Lou_Mat:2014} but it comes perhaps as a surprise that the same behaviour is observed in the  non-parametric setting.
Both theoretical results and this first simulations consider the case where the chain is observed until it reaches a fixed site $n$. Depending on the regime, the number of observed steps of the random walk can therefore be very different, it is typically $O(n)$ in the ballistic regime and $\rme^{O(\sqrt{n})}$ in the recurrent regime. Our simulations also illustrate how the quality of estimation deteriorates when going from nearly recurrent regime to nearly ballistic regime.

The paper is organised as follows. In Section~\ref{sec:setting}, we summarize some basic results on RWRE on $\relatif$ and on the likelihood of the observations before defining our basic estimator.
In~\Cref{sec:estimator-construction}, we introduce our estimator. In Section~\ref{sec:MainRes}, we state our main results : convergence rates for the basic estimators and for the Goldenshluger-Lepski estimator derived from these. Section~\ref{sec:SimStud} presents Monte Carlo experiment supporting our theoretical claims. Proofs of the main results are gathered in Section~\ref{sec:Proof}.

\section{Random walks in random environment (RWRE)}\label{sec:setting}
\input{setting}
\section{Estimator construction}
\label{sec:estimator-construction}

All along the paper, we assume that $\nu$ is absolutely continuous and has density $\tdens$ with respect to the Lebesgue measure.\

Let $\beta>0$, $L>0$ and $m= \sup\set{\ell \in \relatif_+}{\ell < \beta}$. The set $\Sigma(\beta,L)$ is the set of $m$ times differentiable functions $g : \intff{0}{1} \mapsto \reelp$ satisfying for all $(x,x') \in \intff{0}{1}^2$
\begin{equation}\label{eq:def-Holder}
\abs{g^{(m)}(x) - g^{(m)}(x')}
\leqslant L \abs{x-x'}^{\beta-m} \eqsp.
\end{equation}
The following section provides the construction of basic density estimators.

As suggested by \eqref{eq:ker1}, the moments of $\nu$ provide the natural information available for our estimation problem. Recovering a density function from its moments is a classical instance of the Hausdorff  moment problem; see \cite{akhiezer:1965}.

For any $j \in \relatif_+$, let $\mu_{j}[\nu]$ denote the $j$-th moment of the random environment distribution
\[
\mu_{j}[\nu] = \int_0^1 t^j \nu(\rmd t)=\int_0^1t^jf(t)\rmd t

 \eqsp.
\]
The moment problem is said to have unique solution if for two distributions $\nu$ and $\nu'$ over $\intoo{0}{1}$, the equations
$\mu_j[\nu]= \mu_j[\nu']$ for any $j\geqslant 1$ imply that $\nu= \nu'$. If the distribution $\nu$ satisfies this property, it is said to be moment determinate. It is shown that a sufficient condition for $\nu$ to be moment determinate is that the distribution $\nu$ on $(0,1)$ has a continuous density; see \cite{mnastakanov:ruymgaart:2003,mnatsakanov:2008}.

When $\nu$ is moment determinates, the operator mapping the c.d.f. of $\nu$ into $\po\mu_{j}[\nu]\pf_{j \in \relatif_+}$ is therefore invertible. Given $\param\in\relatif_+$, it has been shown in \cite{mnatsakanov:2008} that  its inverse can be approximated by
\begin{equation}\label{eq:DefKM}
\nu_M([0,x])= \sum_{k=0}^{\lfloor \param x\rfloor} \sum_{j=k}^\param \binom{\param}{j}\binom{j}{k} (-1)^{j-k} \mu_{j}[\nu] \eqsp.
\end{equation}
It is shown in \cite{mnatsakanov:2008} that $\lim_{M \to \infty}\nu_M([0,x]) = \nu([0,x])$ at every point $x \in (0,1)$ where the c.d.f. is continuous.

If $\nu$ has a density $f$, we consider then the following approximation, defined for any $x\in[0,1]$ by
\begin{equation}
\label{eq:estim-density}
\tdens^{\param}(x) = (\param+1) \left(\nu_\param\left(\left[0,x+\param^{-1}\right]\right)-\nu_\param\left(\left[0,x\right]\right)\right) \eqsp .
\end{equation}
\cite[Theorem~1]{mnatsakanov:2008} ensures that, when $f$ is continuous, $\tdens^{\param}$ converges uniformly to $\tdens$. More precisely, we establish in \cref{lem:ControleBias} that if $\tdens \in \Sigma(\beta,L)$ with $\beta \in \intof{0}{2}$ then for any $x \in \intff{0}{1}$
$$
\abs{\tdens(x) - \adens(x)} \leqslant \cstholder \param^{-\beta/2} \eqsp.
$$
In the following, we do not use the expression \eqref{eq:DefKM} to construct our estimator.
For any $(a,b)$ in $\reel_+^*\times\reel_+^*$,
benote by $\targetmoment^{a,b}$ the following beta-moments
\begin{equation}
 \label{eq:def-betamoment}
\targetmoment^{a,b} = \Ebb^\nu\crochet{\omega_0^a(1-\omega_0)^b} = \int_0^1 u^a (1-u)^b \tdens(u) \rmd u \eqsp
\end{equation}
where  $\betaker{a}{b}$ is the beta-kernel defined in \eqref{def:BetaKer}.
Using these notations, the approximation $\tdens^\param$ of the density may be written \cite[Eq~(12)]{mnatsakanov:2008}
\begin{align}
\label{eq:expr-approx-density}
\adens(x)
&= \int_0^1 \betaker{\lfloor \param x \rfloor + 1}{\param-\lfloor \param x \rfloor + 1}(u) \tdens(u) \rmd u
= (\param+1) \binom{\param}{\pent{\param x}} \targetmoment^{\pent{\param x},\param-\pent{\param x}} \eqsp .
\end{align}
When $a$ and $b$ are integers, the moments $\targetmoment^{a,b}$ can be consistently estimated as shown in \cite{diel:lerasle:2016}. Using the convention $0/0=0$, denote for all $(i,j) \in \relatif_+$
\begin{gather}\label{eq:def-phi}
\phi^{a,b}(i,j) = \frac{\binom{i+j-(a+b)}{i-a}}{\binom{i+j}{i}} \indic{\{i\geqslant a, j\geqslant b\}}
\quad  \text{ and } \quad
N_n^a = \sumforce{\etat=1}{n} \indic{\{Z_{\etat-1}^n\geqslant a\}} \eqsp ,\\
\label{eq:def-estim-moment}
\momentestim_n^{a,b} = \frac{1}{N_n^a}\sumforce{\etat=1}{n}\phi^{a,b}(Z_{\etat-1}^n,Z_\etat^n)\eqsp,
\end{gather}
where $(Z_\etat^n)$ is defined in \eqref{eq:definition-Z-y^n}.
Therefore, an estimator of $f(x)$ might be obtained by plugging an estimator of the beta moment in \eqref{eq:expr-approx-density}.
\begin{equation}\label{eq:def-estim-density}
\forall x \in \intff{0}{1},\qquad \edens_n^\param(x) =
(\param+1) \binom{\param}{\pent{\param x}} \momentestim_n^{\pent{\param x},\param-\pent{\param x}} \eqsp .
\end{equation}
Statistical properties of these estimators are provided in Theorem~\ref{Thm:NonAdaptive}.

\section{Main results}\label{sec:MainRes}
Let us first derive convergence rates of the basic estimators $\edens_n^\param$ for fixed values of the regularization parameter $\param$.

\begin{theorem}\label{Thm:NonAdaptive}
Assume that the distribution $\nu$ of the random environment  has a density $\tdens\in\Sigma(\beta,L)$ for some $\beta\in\intof{0}{2}$ and $L\geqslant 1$.
\begin{enumerate}[(i)]
\item Assume \Cref{assum:recurrent}. For any $M\geqslant 1$, there exists a constant $C_\nu$ such that
\begin{equation}\label{eq:NABRecurrent}
\Ebf^\nu\crochet{\norm{\infty}{\tdens - \edens_n^{M}}}
\leqslant C_{\nu}\parenth{L\param^{-\beta/2} +
M\frac{\log n}{\sqrt{n}}}\eqsp,
\end{equation}
\item Assume \Cref{assum:transient-to-right}. For any $M\geqslant 1$

\begin{equation}\label{eq:NABTransient}
\Ebf^\nu\crochet{\norm{\infty}{\tdens - \edens_n^{M}}}
\leqslant C_{\nu}\parenth{L\param^{-\beta/2} +
M^{1+\kappa}\sqrt{\frac{\log n}{n}}}\eqsp
\end{equation}
where $\kappa$ is defined in \Cref{assum:transient-to-right}.
\end{enumerate}
\end{theorem}

Theorem~\ref{Thm:NonAdaptive} provides the first rates of convergence for  non-parametric density estimation of the random environment of a random walk. An important feature is that these rates are achieved by the same estimator in the recurrent and transient regimes. On the other hand, the value $\param_n$ optimizing these rates highly depends on both the regime of the walk and the regularity $\beta$ of $f$ that are both unknown in practice.
\begin{corollary}
\begin{enumerate}[(i)]
\item Assume \Cref{assum:recurrent}. Then, taking $\param_n = \lfloor \po\sqrt{n}/\log(n) \pf^{2/(\beta+2)} \rfloor$,
$$
\Ebf^\nu\crochet{\norm{\infty}{\tdens - \edens_n^{\param_n}}}
\leqslant
C_{\nu} \po \frac{\log(n)}{\sqrt{n}} \pf^{\beta/(\beta + 2)}\eqsp .
$$
\item Assume \Cref{assum:transient-to-right}. Then, taking $\param_n =  \po \lfloor n / \log(n) \pf^{\frac1{\beta + 2(1+\kappa)}} \rfloor$,,
$$
\Ebf^\nu\crochet{\norm{\infty}{\tdens - \edens_n^{\param_n}}}
\leqslant
C_{\nu}\po \frac{\log(n)}{n} \pf^{\frac{ \beta}{2(\beta + 2(1+\kappa))}} \eqsp.
$$
\end{enumerate}
\end{corollary}
We will next propose a method to construct  an estimator which is adaptive to the regime (recurrence / transience) and the regularity of the density of the random environment. To that purpose, we follow the Goldenshluger-Lepski strategy \cite{goldenshluger:lepski:2008} to obtain a data-driven choice of the beta-moment order $\lepskiparam_n$.

In the proof of Theorem~\ref{Thm:NonAdaptive}, we build confidence regions for $\tdens$. More precisely, it follows from Eq.~\eqref{eq:DecBasique} and Lemmas~\ref{lem:ControleBias},~\ref{lem:ForLepski} that there exists an event $\Omega_0$ with probability larger than $1-n^{-2}$, such that for all $M\in\{1,\ldots,n-1\}$,
\begin{equation}
\label{eq:intervalle-confiance}
\norm{\infty}{\tdens - \edens_n^\param}\leqslant
31L\param^{-\beta/2} +
\frac{M+1}{N_n^{\param}}\sqrt{3n\log n}\eqsp .
\end{equation}
Define, for any $M\in \{1,\ldots,n-1\}$,
\begin{align*}
B(M)&=31L\param^{-\beta/2} \quad V_n(M)=\frac{M+1}{N_n^{\param}}\sqrt{3n\log n}\eqsp,\\
C_n(M)&=\sup_{M'\in \{1,\ldots,n-1\}}\accol{\norm{\infty}{\edens_n^M-\edens_n^{M\vee M'}}-2V_n(M')}\eqsp.
\end{align*}
Goldenshluger-Lepski's choice of $M$ is defined by
\begin{equation}\label{eq:GLEst}
 \lepskiparam_n\in \argmin{M\in \{1,\ldots,n-1\}}{C_n(M)+2V_n(M)}\eqsp.
\end{equation}

The estimator satisfies the following lemma, whose proof is given for completeness.
\begin{lemma}\label{lem:GL}
On the event $\Omega_{0}$, for any $M\in \{1,\ldots,n-1\}$
\[
\norm{\infty}{\tdens-\edens_n^{\lepskiparam_n}}\leqslant 5B(M)+5V_n(M)\eqsp.
\]
\end{lemma}
\begin{proof}
Denote $d(\tdens,g)= \norm{\infty}{f-g}$.
By repeated applications of the triangular inequality, one obtains, for any $M\in \{1,\ldots,n-1\}$, on $\Omega_0$,
\begin{align*}

 d(\tdens,\edens_n^{{\lepskiparam_n}})&\leqslant d(\tdens,\edens_n^{M})+d(\edens_n^{M},\edens_n^{M\vee{\lepskiparam_n}})+
 d(\edens_n^{M\vee{\lepskiparam_n}},\edens_n^{{\lepskiparam_n}})\\
 &\leqslant B(M)+V_n(M)+C_n(M)+2V_n({\lepskiparam_n})+C_n({\lepskiparam_n})+2V_n(M)\\
 &\leqslant B(M)+V_n(M)+C_n(M)+2V_n(M)+C_n(M)+2V_n(M)\\
 &\leqslant B(M)+5V_n(M)+2C_n(M)\enspace.
\end{align*}
Now, for any $M\in \{1,\ldots,n-1\}$, $B$ being non increasing and $V_n$ being non decreasing, on $\Omega_0$
\begin{align*}
 C_n(M)&\leqslant 0\vee \sup_{M'>M}\accol{d(\tdens,\edens_n^M)+d(\tdens,\edens_n^{M'})-2V_n(M')}\\
 &\leqslant0\vee \sup_{M'>M}\accol{ B(M)+B(M')+V_n(M)-V_n(M')}\leqslant 2B(M)\enspace.
\end{align*}
\end{proof}
Using \Cref{lem:GL} together with \eqref{eq:intervalle-confiance} yields the following Theorem:
\begin{theorem}\label{Thm:Adaptive}
Let $\beta\in\intof{0}{2}$ and $L\geqslant 1$.
Assume that $\tdens\in\Sigma(\beta,L)$ holds.
\begin{enumerate}[(i)]
\item Assume \Cref{assum:recurrent}. Then, there exists a constant $C_\nu$ such that
$$
\Pbf^\nu\parenth{\norm{\infty}{\tdens - \edens_n^{\lepskiparam_n}}
\leqslant
C_{\nu} \po \frac{\log(n)}{\sqrt{n}} \pf^{\beta/(\beta + 2)}}\geqslant 1-C_\nu\frac{\log n}{\sqrt n}\eqsp .
$$
\item Assume \Cref{assum:transient-to-right}. Then, there exists a constant $C_\nu$ such that
$$
\Ebf^\nu\crochet{{\norm{\infty}{\tdens - \edens_n^{\lepskiparam_n}}}}
\leqslant
C_{\nu}\po \frac{\log(n)}{n} \pf^{\frac{\beta}{2(\beta + 2(1+\kappa))}}\eqsp ,
$$
\end{enumerate}
\end{theorem}
The estimator $\edens_n^{\lepskiparam_n}$ achieves simultaneously the optimal rates of Theorem~\ref{Thm:NonAdaptive} in every regime. It is in this sense adaptive to the regime and the regularity of $\tdens$.

The result holds in expectation in transient regimes and only with large probability in the recurrent regime. The reason is that the term $N_n^M$ cannot be handled in the same way in transient regimes where the Markov chain $(Z_k)$ admits a unique invariant probability and in recurrent regimes where it does not.

The rates do not match those one could reach if the environment $\omega$ is observed \cite{bertin:klutchnikoff:2010}. When the chain is recurrent, it visits typically more than $n$ times almost all sites  \cite[Lemma 10]{diel:lerasle:2016}. Therefore, one can probably estimate the environment itself and plug these estimators in any standard density estimator. This might improve the rates in the recurrent regime but it would certainly provide a poor estimator in transient regimes. The problem of recovering the distribution of the environment is in general harder if one observes only one trajectory of the walk than if the environment is observed directly. It is not clear whether a single estimator can recover minimax rates of the i.i.d. setting in the recurrent regime and our rates in transient regimes.

\section{Simulation Study}\label{sec:SimStud}

In this section, we illustrate our theoretical results. We  consider RWRE in different regimes (recurrent, transient ballistic and sub-ballistic). We also investigate the impact of the regularity of the density of the environment

The number of steps of the random walk that are observed depend on the regime. It follows from our discussion in \Cref{sec:setting}, that if the RWRE is transient to the right ($\Ebb^\nu[\log \rho_0] < 0$ where $\rho_0$ is defined in \eqref{eq:definition-rho-0}) then either
\begin{enumerate}
\item $T_n/n \to (1 + \Ebb^\nu[\rho_0])/(1-\Ebb^\nu[\rho_0])$ $\Pbf^\nu$-a.s. in the ballistic regime $\Ebb^\nu[\rho_0] < 1$, in which case the number of time steps grow linearly with $n$
\item $T_n/n \to \infty $ converges $\Pbf^\nu$-a.s.  in the sub-ballistic regime $\Ebb^\nu[\rho_0] \geq 1$, showing that the number of time steps grow superlinearly with $n$. In the sub-ballistic case, the fluctuations of $T_n$ are controlled by the parameter $\kappa$ defined in \eqref{eq:kappa}.
\end{enumerate}

We then compare the performance of our estimator in three sub-ballistic regime but with different $\kappa$. In both parts, we consider our estimation procedure for different values of the parameter $M$.

\subsection{Influence of the regularity}
In this section, we consider 3 different distributions for the environment.
\begin{itemize}
 \item The first example is the Beta distribution $B(3,3)$ whose density $\betaker{3}{3}$ is defined in \eqref{def:BetaKer}.
 \item The second example is the distribution with density
\begin{equation*}
x \mapsto 4 \left(1-\frac{\abs{2x-0.6}}{0.15}\right) \indic{\intff{0.225}{0.325}}(x)
+ \frac{14}{3} \left(1-\frac{\abs{2x-1.2}}{0.3}\right) \indic{\intff{0.45}{0.75}}(x)\eqsp .
\end{equation*}
\item The last example is the distribution with density

\begin{equation*}
x \mapsto 0.6 \betaker{3}{3}(2x) \indic{\ccint{0,0.5}}(x) + 1.4 \betaker{3}{3}(2x-1) \indic{\ocint{0.5,1}}(x)\eqsp .
\end{equation*}
\end{itemize}

These densities are plotted in black in Figure~\ref{BoxplotRegimes}. In the first example, the chain is recurrent, in the second and the third, it is sub-ballistic with a value of $\kappa$ respectively equal to $0.17$ and $0.57$.

\medskip

For each distribution of the environment, $100$ trajectories of the RWRE have been simulated until the chain reaches $100$.

In each case, our (piecewise constant) estimator $\edens_n^M$, defined in \eqref{eq:def-estim-density}, built for $M\in\{25,50,75\}$ is compared with the actual density $\tdens$.

More precisely, figure \ref{BoxplotRegimes} shows for each considered environment and for $\param$ in $\{25,50,75\}$ a graphic representation of the true density (solid black line) and in each point $x \in \intoo{0}{1}$ the median of the estimator $\edens_n^M(x)$ (dashed-dotted blue line), its interquartile range (greyed area) and its lower and upper hinges (dotted blue line).

According to our theoretical bounds, the estimator $\edens_n^M$ performs better when the true density is regular as in Examples 1 and 3 than in the non regular Example 2. The estimator $\edens_n^M$, based on a polynomial approximation, cannot properly approximate the two triangles shaped density of Example 2. More precisely, the regularization parameter $M$ should probably be much larger for the bias of the estimator to be small.

\begin{figure}
\includegraphics[scale=0.33]{bxplt100_betarec-picstrans-bossestrans_25-50-75.pdf}
\caption{\label{BoxplotRegimes}
True density (solid black line) and in each point $x \in \intoo{0}{1}$ the median of the estimator $\edens_n^M(x)$ (dashed-dotted blue line), its interquartile range (greyed area) and its lower and upper hinges (dotted blue line) of the estimator $\edens_{100}^\param$ for the three considered environment (one environment per column) and for $M\in \{25,50,75\}$.}
\end{figure}

\subsection{Influence of the regime}
We now consider trajectories from RWRE that all are transient to right and sub-ballistic.
The environment is drawn  from the distribution with density
\begin{equation}\label{def:density-bossestele}
x \mapsto 0.8 \betaker{3}{3}(0.5+2(x-c_1)) + 1.2 \betaker{3}{3}(0.5+2(x-c_2))
\end{equation}
and for three set of the parameters $c_1$ and $c_2$ such that the parameter $\kappa$ associated to the sub-ballistic RWRE takes values near the extreme values of this regime. In the following table, the chosen sets of parameters are provided with the corresponding (numerically approximated) values of $\kappa$.
\[
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$\kappa$ & 0.04

& 0.35

& 1\\
\hline
$c_1$ & 0.27 & 0.3 & 0.38\\
\hline
$c_2$ & 0.67 & 0.7 & 0.7\\
\hline
\end{tabular}
\]

For each set of parameters for the environment distribution, 100 trajectories until the RWRE reaches $100$ for the first time have been generated.

Figure~\ref{fig:boxplot-estim-bossestele} illustrates the variability of the estimator $\edens_{100}^\param$. For the densities defined in~\ref{def:density-bossestele} with $\kappa$ in $\{0.04, 0.35, 1\}$, we plot the true density of the environment as well as

the interquartile range and lower and upper hinges of $\edens_{100}^M$  computed over the $100$ trajectories and for $M\in\{25,50,75\}$.\\

As expected from our theoretical results, the variability of the estimator deteriorates
with $\kappa$.
When $\kappa = 0.04$ or $\kappa=0.35$, the estimator shows better bias and worse variability when $\param$ grows. The situation in the nearly ballistic case ($\kappa=1$) is different : the walk reaches faster $n=100$ and the trajectory is thus shorter, one single trajectory reaching $n=100$ does not seem sufficient to obtain a reliable estimator of $\tdens$.

\begin{figure}
\includegraphics[scale=0.33]{bxplt100_zero-moins-un_25-50-75.pdf}
\caption{\label{fig:boxplot-estim-bossestele}
True density (in black) and boxplot (median, first and third quartiles as well as lower and upper hinge) of the estimator $\edens_{100}^\param$ for three different values of parameter $\param$ ($25$, $50$ and $75$) and $\kappa$ ($0.04$, $0.35$ and $1$)

}
\end{figure}

\section{Proof}\label{sec:Proof}

\subsection{Proof of Theorem~\ref{Thm:NonAdaptive}}
By the triangular inequality
\begin{align}\label{eq:DecBasique}
\norm{\infty}{\tdens - \edens_n^\param}
& \leqslant
\norm{\infty}{\adens - \tdens} +\norm{\infty}{\adens - \edens_n^\param}\eqsp .
\end{align}
The first term in the right-hand side is deterministic and called the bias, the second is stochastic and called the variance. Lemma \ref{lem:ControleBias} provides an upper bound for the bias. Random bounds on the variance, valid in any regime, are provided in Lemma~\ref{lem:ForLepski}.  Lemma~\ref{lem:VarianceBasique} uses these random bounds to derive deterministic bounds on the variance that, once plugged in \eqref{eq:DecBasique} together with the result of Lemma \ref{lem:ControleBias} allow to conclude the proof of \eqref{eq:NABTransient} and \eqref{eq:NABRecurrent}. The choice of $\param_n$ optimizing the bounds is then immediate.
\begin{lemma}\label{lem:ControleBias}
Let $\beta\in\intof{0}{2}$ and $L\geqslant 1$. Assume that$\tdens\in\Sigma(\beta,L)$.  Then

\begin{equation}\label{eq:ControleBias}
\norm{\infty}{\tdens - \adens} \leqslant 31L\param^{-\beta/2} \eqsp.
\end{equation}

\end{lemma}

\begin{proof}
Let $x\in[0,1]$ and let $B_{(\param,x)}$ be a beta distributed random variable with parameters $\pent{\param x}+1$ and $\param-\pent{\param x}+1$ on a probability space $\left(\Omega,\mathcal{A},\Pbb\right)$. By definition,
\begin{align*}
\adens(x) - \tdens(x)
& =
\int_0^1 \tdens(u) \betaker{\pent{\param x}+1}{\param-\pent{\param x}+1}(u) \mathrm{d}u - \tdens(x)

=
\esp{\tdens(B_{(\param,x)}) - \tdens(x)} \eqsp.
\end{align*}

Consider first the case $0 < \beta \leqslant 1$.

Since $f$ is $(\beta,L)$-Hölder, by Jensen's inequality,
$$
\abs{\adens(x) - \tdens(x)}
\leqslant
\esp{\abs{\tdens(B_{(\param,x)}) - \tdens(x)}}
\leqslant
L\esp{\abs{B_{(\param,x)} - x}^\beta}
\leqslant
L\esp{\abs{B_{(\param,x)} - x}}^\beta \eqsp .
$$
For any $\eta > 0$, it holds
\begin{equation}\label{eq:BoundBias1}
 \esp{\abs{B_{(\param,x)} - x}}
\leqslant
\eta + \esp{\abs{B_{(\param,x)} - x}\indic{\{\abs{B_{(\param,x)} - x}>\eta\}}} \eqsp .
\end{equation}
By Cauchy-Schwarz and Markov inequalities,
\begin{align}
\notag\esp{\abs{B_{(\param,x)} - x}\indic{\{\abs{B_{(\param,x)} - x}>\eta\}}}&
\leqslant \sqrt{\esp{\parenth{B_{(\param,x)} - x}^2}\prob{\abs{B_{(\param,x)} - x}>\eta\}}}\\
\label{eq:inequality-CauchyMarkovBias}
&\leqslant
\sqrt{\po \var{B_{(\param,x)}} + \po \esp{B_{(\param,x)}} - x \pf^2 \pf \frac{\var{B_{(\param,x)}}}{\eta^2}}\eqsp .
\end{align}
One has
\begin{equation*}
\esp{B_{(\param,x)}}
=
\frac{\pent{\param x}+1}{\param+2} \quad \text{ and } \quad \var{B_{(\param,x)}}
=
\frac{(\pent{\param x}+1)(M-\pent{\param x}+1)}{(\param+2)^2(\param+3)}
\eqsp \eqsp .
\end{equation*}
Therefore,
\begin{equation}\label{eq:inequality-esp-beta}
\abs{\esp{B_{(\param,x)}} - x} \leqslant \frac{2}{M+2} \quad \text{ and } \quad \var{B_{(\param,x)}}
\leqslant
\frac{1}{4 \param} \eqsp .
\end{equation}
Plugging \eqref{eq:inequality-esp-beta} in \eqref{eq:inequality-CauchyMarkovBias} yields:
\begin{align*}
\esp{\abs{B_{(\param,x)} - x}\indic{\{\abs{B_{(\param,x)} - x}>\eta\}}}
\leqslant
\sqrt{\po \frac{1}{4\param} + \frac{4}{\param^2} \pf \frac{1}{4 M \eta^2}}
\leqslant
\frac{1}{\eta} \frac{\sqrt{17}}{4 M} \eqsp .
\end{align*}
Plugging this bound in \eqref{eq:BoundBias1} and optimizing in $\eta > 0$ yields
$$
\abs{\adens(x) - \tdens(x)}
\leqslant
17^{\beta/4} L \, \param^{-\beta/2} \eqsp .
$$

Consider then the case $1 < \beta \leqslant 2$. Since $\tdens$ is differentiable, by the mean-value theorem, there exists a random variable $\tilde{B}_{(\param,x)}$ such that
$$
\abs{\tilde{B}_{(\param,x)} - x} \leqslant \abs{B_{(\param,x)} - x}
\quad \text{and} \quad
\tdens(B_{(\param,x)}) - \tdens(x)=f'(\tilde{B}_{(\param,x)}) (B_{(\param,x)} - x)\enspace.
$$
Therefore
\begin{align*}
\abs{\adens(x) - \tdens(x)}
& = \abs{\esp{f'(x) (B_{(\param,x)} - x) + \po f'(\tilde{B}_{(\param,x)})-f'(x)\pf (B_{(\param,x)} - x)}}\\
& \leqslant
\abs{f'(x)} \abs{\esp{B_{(\param,x)}} - x} + \esp{\abs{f'(\tilde{B}_{(\param,x)})-f'(x)} \abs{B_{(\param,x)} - x}} \eqsp .
\end{align*}
Using that $f$ is $(\beta,L)$-Hölder and \eqref{eq:inequality-esp-beta}, one gets
$$
\abs{\adens(x) - \tdens(x)}
\leqslant
\norm{\infty}{f'} \frac{2}{M} + L\esp{\abs{B_{(\param,x)} - x}^\beta} \eqsp .
$$
Furthermore,
\begin{align*}
\esp{\abs{B_{(\param,x)} - x}^\beta}
& \leqslant
\esp{\abs{B_{(\param,x)} -\esp{B_{(\param,x)}} +\esp{B_{(\param,x)}} - x}^\beta}\\
& \leqslant
2^{\beta-1} \po \esp{\abs{B_{(\param,x)} -\esp{B_{(\param,x)}}}^\beta} +\abs{\esp{B_{(\param,x)}} - x}^\beta \pf \eqsp .
\end{align*}
By \eqref{eq:inequality-esp-beta},
\begin{align*}
\esp{\abs{B_{(\param,x)} - x}^\beta}
&\leqslant
2^{\beta-1} \po \var{B_{(\param,x)}}^{\beta/2} +\abs{\esp{B_{(\param,x)}} - x}^\beta \pf\\
& \leqslant
2^{\beta-1} \po \frac{2^{\beta/2}}{\param^{\beta/2}} +\frac{2^\beta}{\param^\beta} \pf
\leqslant
\frac{4^\beta}{\param^{\beta/2}} \eqsp .
\end{align*}

By \cite[Theorem~1.1]{tsybakov:2009},
$$
\norm{\infty}{f'}\leqslant \frac{3}{\sqrt{4-\sqrt{13}}} \; \frac{L+\beta+1}{\beta+1} \leqslant 7.2 L\eqsp .
$$
It thus finally holds:
$$
\abs{\adens(x) - \tdens(x)}
\leqslant
31L \param^{-\beta/2}\eqsp.
$$
As this result holds for all $x\in[0,1]$, the proof is complete.
\end{proof}
Let us now turn to the random part of the risk. We start with a random upper bound.
\begin{lemma}\label{lem:ForLepski}
 Assuming \Cref{assum:transient-to-right} or \Cref{assum:recurrent} , then, for any $z>0$,
  \[
\Pbf^\nu\parenth{\norm{\infty}{\adens - \edens_n^\param }>\frac{M+1}{N_n^{\param}}\sqrt{\frac{n(z+\log \param)}{2}}}\leqslant 2e^{-z}\enspace.
 \]

\end{lemma}
\begin{proof}
By definition, one has
\[
\adens(x) - \edens_n^\param(x)=(\param+1) \binom{\param}{\pent{\param x}}\parenth{ \targetmoment^{\pent{\param x},\param-\pent{\param x}}- \momentestim_n^{\pent{\param x},\param-\pent{\param x}} }
\]
 By \cite[Theorem 4]{diel:lerasle:2016}, for any $z>0$,
 \[
\Pbf^\nu\parenth{\abs{ \targetmoment^{\pent{\param x},\param-\pent{\param x}}- \momentestim_n^{\pent{\param x},\param-\pent{\param x}} }>\frac{n}{N_n^{\pent{\param x}}}\binom{\param}{\pent{\param x}}^{-1}\sqrt{\frac{z}{2n}}}\leqslant 2e^{-z}\enspace.
 \]
It remains to remark that $N_n^{\pent{\param x}}\geqslant N_n^{\param}$ and to apply a union bound to conclude the proof.
\end{proof}
The following lemma provides deterministic rates of convergence that derive from Lemma~\ref{lem:ForLepski}.
\begin{lemma}\label{lem:VarianceBasique}
Under \Cref{assum:transient-to-right}, $X$ is transient and
  \[
\Ebf^\nu\crochet{\norm{\infty}{\adens - \edens_n^\param }}\leqslant C_{\nu}M^{1+\kappa} \sqrt{\frac{\log n}{n}}\eqsp.
 \]
Under \Cref{assum:recurrent}, $X$ is recurrent and
  \[
\Ebf^\nu\crochet{\norm{\infty}{\adens - \edens_n^\param }}\leqslant C_{\nu}M\frac{\log n}{\sqrt{n}}\eqsp.
 \]

\end{lemma}
\begin{proof}
Fix some $M\geqslant 1$.
If the chain is transient, by \cite[Lemmas 8 and 9]{diel:lerasle:2016}
, there exists a constant $C_\nu$ such that, for any $z>0$,
\[
\Pbf^\nu\parenth{\frac{N_n^{\param}}n\geqslant \frac{1}{C_{\nu}}\parenth{\frac1{ M^\kappa}-\frac{C_\nu\sqrt{z}}{\sqrt{n}}}}\geqslant 1-2e^{-z }\enspace.
\]

Therefore,
\begin{equation}\label{eq:BoundNnM}
\Pbf^\nu\parenth{\frac{N_n^{\param}}n\geqslant \frac{1}{C_{\nu} M^{\kappa}}} \geqslant1-2e^{-n/C_\nu^2M^{2\kappa}} \eqsp.
\end{equation}

Combining \eqref{eq:BoundNnM} with Lemma~\ref{lem:ForLepski} yields, for any $z\in\intof{0}{n/4C_\nu^2M^{2\kappa}}$,
\begin{equation}\label{eq:probBound}
\Pbf^\nu\parenth{\norm{\infty}{\adens - \edens_n^\param }>C_{\nu} M^{(1+\kappa)}\sqrt{\frac{z+\log M}{n}}}\leqslant 4e^{-z}\enspace.
\end{equation}
By \eqref{eq:def-phi} and \eqref{eq:def-estim-moment}, both $\adens$ and $\edens_n^\param$ are uniformly upper-bounded by $\param + 1$. One can therefore integrate \eqref{eq:probBound} to get, for any $M\leqslant n^{1/2\kappa}$,

\[
\Ebf^\nu\crochet{\norm{\infty}{\adens - \edens_n^\param }}\leqslant C_{\nu}M^{1+\kappa} \sqrt{\frac{\log M}{n}}\eqsp.
\]
As the bound also holds obviously for $M\geqslant n^{1/2\kappa}$ the proof of the transient case is complete.

Assume now that the chain is recurrent, then \cite[Lemma 10]{diel:lerasle:2016} states that there exists $C_{\nu}$ such that,
\begin{equation}\label{eq:NnMRec}
\Pbf^\nu\parenth{N_n^{n}\leqslant \frac n2}\leqslant C_{\nu}\frac{\log n}{\sqrt n}\eqsp.
\end{equation}
Combining \eqref{eq:NnMRec} with that of Lemma~\ref{lem:ForLepski} implies that, for any $M\in\{1,\ldots,n\}$,
  \[
\Pbf^\nu\parenth{\norm{\infty}{\adens - \edens_n^\param }>(M+1)\sqrt{\frac{2(z+\log \param)}{n}}}\leqslant 2e^{-z}+C_{\nu}\frac{\log n}{\sqrt n}\eqsp.
 \]
Choosing $z=\log n$ and noticing that $\norm{\infty}{\adens}\vee \norm{\infty}{\edens_n^\param}\leqslant M+1$ concludes the proof.
\end{proof}
\paragraph{Conclusion of the proof of Theorem~\ref{Thm:NonAdaptive}} Plugging the conclusions of Lemmas~\ref{lem:ControleBias} and ~\ref{lem:VarianceBasique} in \eqref{eq:DecBasique} yields, if $X$ is transient,
\begin{align*}
\Ebf^\nu\crochet{\norm{\infty}{\tdens - \edens_n^\param}}
& \leqslant
31L\param^{-\beta/2} +
C_{\nu} M^{1+\kappa}\sqrt{\frac{\log n}{n}}\eqsp .
\end{align*}
If $X$ is recurrent,
\begin{align*}
\Ebf^\nu\crochet{\norm{\infty}{\tdens - \edens_n^\param}}
& \leqslant
31L\param^{-\beta/2} +
C_{\nu} M\frac{\log n}{\sqrt{n}}\eqsp .
\end{align*}The proof of Theorem~\ref{Thm:NonAdaptive} is complete.
\subsection{Proof of Theorem~\ref{Thm:Adaptive}}

\subsubsection{Conclusion of the proof} As $B(M)$ and $V(M)$ are non-negative and respectively non-increasing and non-decreasing, Lemma~\ref{lem:GL} applies and one has therefore, on $\Omega$,
\[
\norm{\infty}{\tdens - \edens_n^{\widehat{M}_n}}\leqslant 5 \inf_{M\in\{1,\ldots,n-1\}}\accol{31L\param^{-\beta/2}+\frac{M+1}{N_n^{\param}}\sqrt{3n\log(n+1)}}\eqsp.
\]
Let $M_{\max}\leqslant (n/3 C_\nu\log n)^{1/2\kappa}$. A union bound in \eqref{eq:BoundNnM} gives that, if $X$ is transient,
\[
\Pbf^\nu\parenth{\forall M\in\{1,\ldots,M_{\max}\},\quad \frac{N_n^M}n\geqslant \frac1{C_\nu M^{\kappa}}}\geqslant 1-\sum_{M=1}^{M_{\max}}e^{-n/C_\nu M^{2\kappa}}\geqslant 1-M_{\max}e^{-3 \log n}\enspace.
\]
Therefore, on an event with probability larger than $1-(M_{\max}+1)e^{-3 \log n}-n^{-2}\geqslant 1-2n^{-2}$,
\begin{align*}
\norm{\infty}{\tdens - \edens_n^{\widehat{M}_n}}&\leqslant \inf_{M\in\{1,\ldots,M_{\max}\}}\accol{31L\param^{-\beta/2}+C_\nu M^{\kappa+1}\sqrt{\frac{\log n}{n}}}\\
&\leqslant C_{\nu,\alpha}\parenth{\frac{\log n}n}^{\beta/(4+4\kappa+2\beta)}\eqsp.
\end{align*}

The proof is concluded in the transient case since $\norm{\infty}{\edens_n^{\widehat{M}_n}}\leqslant n+1$.

Since $N_n^{\param}\geqslant N_n^n$ for any $\param\in\{1,\ldots,n-1\}$, in the recurrent case, one has therefore, by \eqref{eq:NnMRec}, on an event with probability larger than $1-C_{\nu}\log n/\sqrt{n}$,
\begin{align*}
\norm{\infty}{\tdens - \edens_n^{\widehat{M}_n}}&\leqslant \inf_{M\in\{1,\ldots,n-1\}}\accol{31L\param^{-\beta/2}+C_\nu M\frac{\log n}{\sqrt{n}}}\\
&\leqslant C_{\nu}\parenth{\frac{(\log n)^2}n}^{\beta/(2\beta+4)}\eqsp.
\end{align*}

\section*{Acknowledgements}
The work of Antoine Havet was supported by a public grant as part of the \textit{Investissement d’avenir} project, reference ANR-11-LABX-0056-LMH, LabEx LMH.\\
The work of Matthieu Lerasle was supported by a public grant from FAST-BIG project ANR-17-CE23-0011.
\bibliographystyle{abbrvnat}
\bibliography{BiblioSource}

\end{document}


TITLE: Linear Transformation of an Inner Product Space
QUESTION [0 upvotes]: My professor posted a question asking.
"Let V be an inner product space with a subspace W having B as an orthonormal basis. Show that the function T: V → W is a linear transformation. T is called the orthogonal projection of V onto W."
I have begun to answer the question by trying to prove vector addition and scalar multiplication but I am having trouble understanding how to begin.

REPLY [0 votes]: Extend $B$ to a basis of V by appending necessary elements. Then the span of such added elements will form an orthogonal complement of $W$ call it $U$. Hence $V = U \oplus W$. Then each $v \in V$ can be written uniquely as $v = u + w$.
Let $\alpha, \beta$ be scalars. Let $v_{1}, v_{2} \in V$. Then $v_{1} = u_{1} + w_{1}$ and $v_{2} = u_{2} + w_{2}$.
Then $T(\alpha v_{1} + \beta v_{2}) = T((\alpha u_{1} + \beta u_{2}) + (\alpha w_{1} + \beta w_{2})) = ?$


TITLE: How to calculate volume change from price and gross margin?
QUESTION [0 upvotes]: I have a matrix that looks like this:
           Gross Margin
           10% 15% 20% 25% 30%
    Price  Volume
    1%     -9% -6% -5% -4% -3%
    2%     -17% -12% -9% -7% -6%
    5%
    10%
    15%

The matrix is not all filled out, but you read it as this:
If the price goes up by 1%, and you want to keep you your Gross Margin at 10%, you can manage a -9% decrease in volume.
Likewise, if you experience a -17% volume loss, you must increase price by 2% in order to keep your Gross Margin at 10%.
Now, I can't figure out how to calculate the Changes in volume, only based on price and gross margin percentages?

REPLY [0 votes]: The only way I can understand the table is to assume the price increase is on the selling price, the buying price stays the same, your current gross margin percentage is the value at the top of the table, and you are trying to maintain the currency value (not percentage) of your gross margin.  In that case, taking the upper left corner entry as an example, the price going up by $1\%$ means your gross margin percentage goes up to $11\%$.  If your volume goes down by $9\%$, you are selling $0.91$ times as much as before, but you keep $0.11 \cdot 0.91 =1.001$ times as much cash as before.  They round this off to $1.00$
To get the formula, let $g$ be your current gross margin, $p$ be the price increase, and $v$ be the volume decrease.  The new income is $(g+p)(1-v)$ and we want that to match the current income of $g$, so we set
$$(g+p)(1-v)=g\\1-v=\frac g{g+p}\\v=1-\frac g{g+p}=\frac p{g+p}$$
With that formula I was able to reproduce all the values you have once they were rounded to the nearest percent.


TITLE: Curvature gravity and a falling apple?
QUESTION [3 upvotes]: I know very little of physics after Einstein.
I am aware of that Einstein's gravity theory says that the existence of matters creates curvature of a space-time, so that our Earth orbits our Sun. I can grasp this idea.
But I do not see how to use the language of general relativity theory to justify why an apple can fall?

REPLY [9 votes]: The path in spacetime followed by a freely moving object is given by the geodesic equation:
$$ {d^2 x^\mu \over d\tau^2} + \Gamma^\mu_{\alpha\beta} {dx^\alpha \over d\tau} {dx^\beta \over d\tau} = 0 \tag{1} $$
Now this looks absolutely horrible, but it's a lot simpler than it looks.
The variable $x$ is a vector that gives a position in spacetime. So if we use $x$, $y$ and $z$ for the position in space and $t$ for the position in time then the vector $\vec{x}$ has components $(t, x, y, z)$. The superscript, e.g. $x^\mu$, isn't a power but instead tells us which component it is. So $x^0$ would be $t$, $x^1$ would be $x$, $x^2$ would be $y$ and $x^3$ would be $z$.
The variable $\tau$ is called the proper time, and is the time shown on a clock carried by the moving object. That is, if you were the one moving through spacetime $\tau$ is just the time shown on your wristwatch.
So the expression $d^2 x^\mu/d\tau^2$ is just an acceleration e.g. when $\mu=2$ it's just $d^2y/d\tau^2$ or the acceleration in the $y$ direction. Similarly the expression $dx^\mu/d\tau$ is a velocity, so when $\mu=3$ it's just $dz/d\tau$ or the velocity in the $z$ direction.
The symbols $\Gamma^\mu_{\alpha\beta}$ are called Christoffel symbols, and they basically describe how spacetime is curved. In flat spacetime, i.e. no gravity, the Christoffel symbols are all zero$^1$. In curved spacetimes the Christoffel symbols are non-zero.
And now we're ready to go. Let's see what happens if you release your apple in flat spacetime. For flat spacetime the Christoffel symbols are zero and equation (1) becomes:
$$ {d^2 x^\mu \over d\tau^2} = 0 $$
and this is really four equations, one for each value of $\mu$:
$$\begin{align}
 {d^2 t \over d\tau^2} &= 0  \\
 {d^2 x \over d\tau^2} &= 0  \\
 {d^2 y \over d\tau^2} &= 0  \\
 {d^2 z \over d\tau^2} &= 0
\end{align}$$
So what this tells us is that the acceleration in all directions is zero. In other words the apple stays where it is. And of course that's quite correct. If you're floating in space far from any masses and you let go of the apple it will stay where it is.
A quick aside before I get on to what happens in curved spacetime. You may be wondering what on Earth $d^2t/d\tau^2$ is. Well the time coordinate $t$ is what we measure while we're watching the apple and the time coordinate $\tau$ is what the apple measures on its wristwatch. If the apple is stationary relative to us the $t$ and $\tau$ are the same. But if the apple is moving there will be time dilation and $t$ and $\tau$ will not be the same. The velocity $dt/d\tau$ is just the time dilation, and the acceleration $d^2t/d\tau^2$ is the rate of change of time dilation.
Anyhow let's go back to your apple and see why equation (1) tells us it will fall.
Actually calculating the trajectory is quite hard. If you really want to see how it's done this article has the gory details. I'm not going to do the calculation, I'm just going to show you why GR tells us the apple must move. To do this I'll use the geodesic equation to calculate the acceleration at the instant we release the apple, and to show it is non-zero.
We start with the apple stationary so the velocities $dx/d\tau$, $dy/d\tau$ and $dz/d\tau$ are all zero. Though the apple isn't moving in space it is moving in time at one second per second, so at the moment the apple is released $dt/d\tau = 1$ (actually it's $c$, but we tend to use units in which $c = 1$.
So looking back at equation (1), the velocities $dx^\alpha/d\tau$ and $dx^\beta/d\tau$ are zero except when $\alpha = \beta = 0$. So equation (1) simplifies to (remember this is only at the moment the apple is released):
$$ {d^2 x^\mu \over d\tau^2} + \Gamma^\mu_{00} = 0 \tag{2} $$
The trouble is that the coordinates I've chosen, $(t, x, y, z)$, aren't ideal for (roughly) spherically symmetric gravitational fields like the one round the Earth. So I'm going to cheat a bit and assume I can use the Rindler metric to describe the curvature in the small region around the apple and us. We'll take $z$ to be the height, so $x$ and $y$ will be the position on the ground.
With these coordinates the only non-zero Christoffel symbol $\Gamma^\mu_{00}$ is when $\mu = 3$, i.e. $\Gamma^3_{00}$, and this has the value (at the moment the apple is released):
$$ \Gamma^3_{00} = \frac{g}{c^2} $$
where $g$ is the gravitational acceleration (and remember we're using units where $c = 1$). Plug this into equation (2) and expand it into the four separate equations and we get:
$$\begin{align}
 {d^2 t \over d\tau^2} &= 0  \\
 {d^2 x \over d\tau^2} &= 0  \\
 {d^2 y \over d\tau^2} &= 0  \\
 {d^2 z \over d\tau^2} &= -g
\end{align}$$
And there's our result. So the apple doesn't accelerate sideways, i.e. in the $x$ or $y$ directions, but it does accelerate downwards in the $-z$ direction. And the acceleration downwards is just $g$ i.e. the gravitational acceleration.

$^1$ even in flat spacetime the Christoffel symbols will be non-zero if you're using curved coordinates e.g. polar coordinates. We'll gloss over that for the purposes of this discussion.


TITLE: Lagrange Multiplier In Proving AM-GM inequality
QUESTION [2 upvotes]: I am dealing with a question in Stewart Calculus Book which states the following:
Using Lagrange multiplier, find the maximum of the function $$f(x_1,x_2,...,x_n)=(x_1x_2...x_n)^{1/n}$$subject to the constraint$$\sum_{i=1}^{n} x_i=c$$,where $x_i$'s are all positive, and use this to prove the AM-GM inequality. Actually in AM-GM inequality, it holds for all nonnegative numbers, but I think the author wants to get rid of the case where $x_i$'s are all zero, where Lagrange multiplier can no longer be applied.
And the result I obtained is: $f$ will have its maximum/minimum (the arithmetic mean), or even saddle point at $(\frac{c}{n},\frac{c}{n},...,\frac{c}{n})$, since Lagrange method gives no definiteness on the behaviour of the critical points found (whether max, min, or saddle).
And my question is: In this case, how do we show that the point I found gives the maximum value of the function? My teacher gave me an argument that said "the minimum value would be some place very near to $0$, so the arithmetic mean will not be the minimum value". But I think the argument is not persuasive enough to explain why the arithmetic mean is the maximum value. So, I hope that there will someone who are willing to give their opinions on this. Thanks.

REPLY [1 votes]: Let $A$ be the set of $(x_1, x_2, ..., x_n)$ such that
$$\sum x_i = c$$
and $x_i \geq 0$ for all $i$. On a point $x$ of the boundary of $A$, there is always a component $x_i$ of $x$ which is equal to zero, hence $f = 0$ on the boundary. As $f$ is continuous and $A$ is compact, $f$ has a global maximum on $A$. Denote by $x^\ast$ one such maximum. The fact that $f = 0$ on the boundary of $A$ implies that $x^\ast$ is in the interior of $A$. Then what you have done with Lagrange multipliers shows that
$$x^\ast = (\frac{x_1}{c}, ..., \frac{x_n}{c})$$
as it is the only extremum of $f$ in the interior of $A$.
EDIT : Let me clarify my notations. Write
$$\mathbb{R}^n_+ = \{ x = (x_1, ..., x_n), \ x_i \geq 0 \text{ for } i = 1, 2, ... n \}$$
$${\mathbb{R}^n_+}^\ast = \{ x = (x_1, ..., x_n), \ x_i > 0 \text{ for } i = 1, 2, ... n \}$$
and
$$h(x) = \sum x_i - c.$$
Then $f$ has a maximum $x^\ast$ on the compact
$$\{x \in \mathbb{R}^n_+, \ h(x) = 0 \}$$
and in fact
$$ x^\ast \in \{x \in {\mathbb{R}^n_+}^\ast, \ h(x) = 0 \}$$
One can conclude using Lagange multipliers in this last set.