This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
world:robbins_monro [2021/03/14 10:43] rdouc [Statement] |
world:robbins_monro [2023/02/10 18:17] (current) rdouc [Proof of $\mathbb{P}(A=0)=1$.] |
||
---|---|---|---|
Line 5: | Line 5: | ||
<WRAP center round box 80%> | <WRAP center round box 80%> | ||
* $f$ is a bounded and continuous function | * $f$ is a bounded and continuous function | ||
- | * $f(x)(x-x_*)>0$ for all $x\in \Xset$ | + | * $f(x)(x-x_*)>0$ for all $x\neq x_* \in \Xset$ |
</WRAP> | </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 | 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 | ||
Line 17: | Line 17: | ||
</WRAP> | </WRAP> | ||
- | Define iteratively the sequence <color red>$$X_{n+1}=X_{n}-\gamma_{n+1} U_{n+1}$$</color> where | + | 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)$. | $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 0$. We follow a version of the proof proposed by François Roueff. | + | 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 ====== | ====== Proof ====== | ||
Line 38: | Line 38: | ||
==== Convergence of $(X_n-x_*)^2$ ==== | ==== 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. | 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 | + | - 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$ | * $(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$. | * $\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$. | ||
Line 45: | Line 45: | ||
- | ==== Proof of $\mathbb{P}(A=0)=1$ ==== | + | ==== 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 | First, write the Doob decomposition for the submartingale $(S_n)$ that is: $S_n=M_n+W_n$ where | ||
Line 59: | Line 59: | ||
- $\lrcb{\delta/2 < |A| <\delta} \subset \lrcb{W_\infty\eqdef \lim_n W_n=\infty}$ | - $\lrcb{\delta/2 < |A| <\delta} \subset \lrcb{W_\infty\eqdef \lim_n W_n=\infty}$ | ||
- $\PP(W_\infty=\infty)=0$. | - $\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, $(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$. | + | 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$, | 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$, | ||
Line 67: | Line 67: | ||
and this implies that for all $\omega \in \lrcb{\delta/2 < |A| <\delta}$, | and this implies that for all $\omega \in \lrcb{\delta/2 < |A| <\delta}$, | ||
\begin{equation*} | \begin{equation*} | ||
- | W_\infty \geq \sum_{n=N(\omega)}^\infty \gamma_k f (X_{k-1}(\omega)) (X_{k-1}(\omega)-x_*) \geq \gamma \sum_{n=N(\omega)}^\infty \gamma_k=\infty | + | 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*} | \end{equation*} | ||
This shows that $\lrcb{\delta/2 < |A| <\delta} \subset \lrcb{W_\infty=\infty}$ and the proof is completed. | This shows that $\lrcb{\delta/2 < |A| <\delta} \subset \lrcb{W_\infty=\infty}$ and the proof is completed. |