Robbins Monro Trial

The Robbins-Monro process is a stochastic process with the help of which the zero of an unknown regression function can be approximated stochastically . It was introduced in 1951 by Herbert Robbins and Sutton Monro .

definition

Be a family of random variables and a measurable function, so that: . Also be given a clear solution so that . Then the sequence of random variables is called given by ${\displaystyle Y_{x}:\mathbb {R} \rightarrow \mathbb {R} }$ ${\displaystyle M:\mathbb {R} \rightarrow \mathbb {R} }$ ${\displaystyle M(x)=\mathbb {E} (Y_{x})}$ ${\displaystyle \theta \in \mathbb {R} }$ ${\displaystyle M(\theta )=0\ }$ ${\displaystyle (X_{n})_{n\in \mathbb {N} }}$

${\displaystyle X_{n+1}=X_{n}-a_{n}(Y_{X_{n}})}$

Robbins-Monro process , where an arbitrary real constant and a sequence of real constants are with . ${\displaystyle X_{1}}$ ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ ${\displaystyle a_{n}>0}$

Convergence of X _n to θ

Converges into against under the following four conditions  : ${\displaystyle X_{n}}$ ${\displaystyle L^{2}}$ ${\displaystyle \theta }$

• ${\displaystyle \exists {C>0}\forall {x\in \mathbb {R} }\ (P[\left|Y_{x}\right|\leq C]=1)}$,
• ${\displaystyle M(x)}$ is growing monotonously,
• ${\displaystyle M'(\theta )>0}$ exists,
• ${\displaystyle a_{n}}$ satisfies the following conditions:

${\displaystyle \qquad \sum _{n=0}^{\infty }a_{n}=\infty \quad {\text{und}}\quad \sum _{n=0}^{\infty }a_{n}^{2}<\infty \quad }$

Simple example

Let be shifted sine functions between and with random fluctuations that are continued linearly at the edges. ${\displaystyle Y_{x_{n}}}$ ${\displaystyle 1/2}$ ${\displaystyle -\pi /3}$ ${\displaystyle \pi /3}$ ${\displaystyle \varepsilon _{n}}$

${\displaystyle Y_{x_{n}}={\begin{cases}\ \;\,\ x_{n}+\sin(\pi /3)-\pi /3-{\frac {1}{2}}+\varepsilon _{n}&{\text{für }}x_{n}>\pi /3\\\ \;\,\ \sin(x_{n})-{\frac {1}{2}}+\varepsilon _{n}&{\text{für }}-\pi /3\leq x_{n}\leq \pi /3\\\ \;\,\ x_{n}-\sin(\pi /3)+\pi /3-{\frac {1}{2}}+\varepsilon _{n}&{\text{für }}x_{n}<-\pi /3\end{cases}}}$

Whereby independent, uniformly distributed random variables are in. Also be and . Then converges against . ${\displaystyle \varepsilon _{n}}$ ${\displaystyle \left(-{\tfrac {1}{4}},{\tfrac {1}{4}}\right)}$ ${\displaystyle a_{n}={\tfrac {1}{n+1}}}$ ${\displaystyle X_{1}={\tfrac {1}{2}}}$ ${\displaystyle X_{n+1}=X_{n}-a_{n}(Y_{X_{n}})}$ ${\displaystyle \pi /6}$

• 

  Diagram with 5 different paths and 300 iterations. The dashed line indicates the limit value . ${\displaystyle \pi /6}$

Individual evidence

1. ^ Herbert Robbins, Sutton Monro: A Stochastic Approximation Method. In: The Annals of Mathematical Statistics. 22, No. 3, 1951, p. 405 Theorem 2.

literature

• Herbert Robbins, Sutton Monro: A Stochastic Approximation Method. In: The Annals of Mathematical Statistics. 22, No. 3, 1951, pp. 400-407 ( PDF file; 514KB ).
• Marie Duflo: Random Iterative Models , Springer Verlag, 1997.