Welcome to Randal Douc's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
{{page>:defs}}

====== Statement ======
We set $\Xset =\rset$, $\Xsigma=\mc{B}(\Xset)$ and we let $f:\Xset \to \Xset$ and $x_*\in \Xset$ such that 
 <WRAP center round box 80%>
  * $f$ is a bounded and continuous function 
  * $f(x)(x-x_*)>0$ for all $x\neq x_* \in \Xset$
</WRAP>
We assume there exist a Markov kernel $K$ on $\Xset \times  \Xsigma$ and a sequence $\seq{\gamma_k}{k\in\nset}$ of real numbers such that

 <WRAP center round box 80%>
  * $\int y K(x, \rmd y)=f(x)$
  * $\gamma_k>0$ for all $k\geq 0$
  * $\sum_{k=0}^\infty \gamma_k=\infty$
  * $\sum_{k=0}^\infty \gamma_k^2<\infty$ 
  * there exists $M$ such that for all $x\in \Xset$, $\int y^2 K(x,\rmd y)\leq M<\infty$.
</WRAP>

Let $X_0$ be a random variable such that $\PE[X^2_0]<\infty$. Define iteratively the sequence <color red>$$X_{n+1}=X_{n}-\gamma_{n+1} U_{n+1}$$</color> where
$U_{n+1}|_{\mcf_n}\sim K (X_n,\cdot)$ and $\mcf_n=\sigma(X_0,\ldots,X_n)$. 
The aim of this short note is to prove that $X_n \psconv x_*$. We follow a version of the proof proposed by François Roueff. 

====== Proof ======

==== The intermediate quantity $S_n$ ====

Write
$$
(X_{n+1}-x_*)^2=(X_{n}-x_*)^2-2 \gamma_{n+1} U_{n+1}
\lr{X_n-x_*} + \gamma_{n+1}^2 U_{n+1}^2.
$$
and set 
\begin{equation} \label{eq:def:Sn}
S_n=2\sum_{k=1}^n \gamma_k U_k (X_{k-1}-x_*)=
(X_0-x_*)^2-(X_n-x_*)^2+\sum_{k=1}^n \gamma_k^2 U_k^2.
\end{equation}

==== Convergence of $(X_n-x_*)^2$ ====
Considering \eqref{eq:def:Sn}, to obtain the convergence of $(X_n-x_*)^2$, we only need to prove that $S_n$ and $\sum_{k=1}^n \gamma_k^2 U_k^2$ converge $\PP$-a.s. as $n$ goes to infinity. 
  - The convergence of $(S_n)$ follows from (see [[world:martingale#submartingale|some results on limits of martingales]])
      * $(S_n)$ is a submartingale since  $\CPE{S_n-S_{n-1}}{\mcf_{n-1}}=2\gamma_n f (X_{n-1}) (X_{n-1}-x_*) \geq 0$
      * $\sup_n \PE[S_n^+] \leq \PE[(X_0-x_*)^2]+\sum_{k=1}^n \gamma_k^2 \underbrace{\PE[U_k^2]}_{\leq M}<\infty$.  
  - The convergence of $\sum_{k=1}^n \gamma_k^2 U_k^2$ follows from $\PE[\sum_{k=1}^\infty \gamma_k^2 U_k^2]=\sum_{k=1}^\infty \gamma_k^2 \PE[U_k^2]<\infty$.
Finally, \eqref{eq:def:Sn} implies that $(X_n-x_*)^2 \asconv{\PP} A$ for some $\PP$-a.s. finite random variable $A$. To complete the proof, it remains to show that $A$ is almost surely null.


==== Proof of $\mathbb{P}(A=0)=1$. ====

First, write the Doob decomposition for the submartingale $(S_n)$ that is: $S_n=M_n+W_n$ where
\begin{align*}
  & M_n=2\sum_{k=1}^n \lr{\gamma_k U_k (X_{k-1}-x_*)-\gamma_k f
    (X_{k-1}) (X_{k-1}-x_*)}\\
   & W_n=2\sum_{k=1}^n \gamma_k f (X_{k-1}) (X_{k-1}-x_*)
\end{align*}
Note that $(W_n)$ is a non-decreasing previsible non-negative process
and that $(M_n)$ is a martingale.

To conclude, it is sufficient to prove that for any $\delta>0$, $\PP(\delta/2 < |A| <\delta)=0$. To this aim, we will show that
  - $\lrcb{\delta/2 < |A| <\delta} \subset \lrcb{W_\infty\eqdef \lim_n W_n=\infty}$
  - $\PP(W_\infty=\infty)=0$. 
To get the second property (2), note that $M_n\leq S_n$ so that $\sup_{n\in\nset} \PE[M_n^+]\leq \sup_{n\in\nset} \PE[S_n^+]<\infty$. Finally, $(M_n)$ is a martingale, with a positive part which is uniformly bounded in $L^1$. Therefore (see for example [[https://wiki.randaldouc.xyz/doku.php?id=world:martingale| some convergence properties for martingales]], $(M_n)$ converges $\PP$-a.s. And since $W_n=S_n-M_n$, it also implies that $(W_n)$ converges a.s. so that $\PP(W_\infty=\infty)=0$.   

We now turn to the first property (1). Let $\omega \in \lrcb{\delta/2 < |A| <\delta}$. Then, there exists $N(\omega)$ such that for all $n\geq N(\omega)$, $X_n\in B$ where $B=\set{x\in\Xset}{\delta/2 <(x-x_*)^2<\delta}$. Moreover, by continuity of $f$,  
\begin{equation*}
    \gamma\eqdef \inf_{x\in B} f(x)(x-x_*) >0
\end{equation*}
and this implies that for all $\omega \in \lrcb{\delta/2 < |A| <\delta}$, 
\begin{equation*}
    W_\infty \geq \sum_{n=N(\omega)+1}^\infty \gamma_k f (X_{k-1}(\omega)) (X_{k-1}(\omega)-x_*) \geq \gamma \sum_{n=N(\omega)+1}^\infty \gamma_k=\infty
\end{equation*}
This shows that $\lrcb{\delta/2 < |A| <\delta} \subset \lrcb{W_\infty=\infty}$ and the proof is completed.
Welcome to Randal Douc's wiki

User Tools

Site Tools

Page Tools
