world:robbins_monro
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
world:robbins_monro [2021/03/15 01:20] rdouc [Statement] |
world:robbins_monro [2022/03/16 07:40] 127.0.0.1 external edit |
||
|---|---|---|---|
| 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> | ||
| - | 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 | + | 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$. | ||
world/robbins_monro.txt · Last modified: 2023/02/10 18:17 by rdouc
Page Tools
