Robbins-Monro-Prozess

Der Robbins-Monro-Prozess ist ein stochastischer Prozess, mit dessen Hilfe die Nullstelle einer unbekannten Regressionsfunktion stochastisch approximiert werden kann. Er wurde 1951 von Herbert Robbins und Sutton Monro vorgestellt.

Definition

Sei $Y_{x}:\mathbb {R} \rightarrow \mathbb {R}$ eine Familie von Zufallsvariablen und $M:\mathbb {R} \rightarrow \mathbb {R}$ eine messbare Funktion, sodass gilt: $M(x)=\mathbb {E} (Y_{x})$. Sei zudem eine eindeutige Lösung $\theta \in \mathbb {R}$ gegeben, sodass $M(\theta )=0\$. Dann heißt die Folge $(X_{n})_{n\in \mathbb {N} }$ von Zufallsvariablen gegeben durch

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

Robbins-Monro-Prozess, wobei $X_{1}$ eine beliebige reelle Konstante und $(a_{n})_{n\in \mathbb {N} }$ eine Folge reeller Konstanten mit $a_{n}>0$ sei.

Konvergenz von X_n gegen θ

Unter den folgenden vier Bedingungen konvergiert $X_{n}$ in $L^{2}$ gegen $\theta$:

• $\exists {C>0}\forall {x\in \mathbb {R} }\ (P[\left|Y_{x}\right|\leq C]=1)$,
• $M(x)$ ist monoton wachsend,
• $M'(\theta )>0$ existiert,
• $a_{n}$ genügt folgenden Bedingungen:

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

Einfaches Beispiel

Seien $Y_{x_{n}}$ um $1/2$ verschobene Sinusfunktionen zwischen $-\pi /3$ und $\pi /3$ mit zufälligen Schwankungen $\varepsilon _{n}$, die an den Rändern linear fortgesetzt werden.

$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}}$

Wobei $\varepsilon _{n}$ unabhängige, gleichverteilte Zufallsvariablen in $\left(-{\tfrac {1}{4}},{\tfrac {1}{4}}\right)$ sind. Sei außerdem $a_{n}={\tfrac {1}{n+1}}$ und $X_{1}={\tfrac {1}{2}}$. Dann konvergiert $X_{n+1}=X_{n}-a_{n}(Y_{X_{n}})$ gegen $\pi /6$.

• 
  Schaubild mit 5 verschiedenen Pfaden und 300 Iterationen. Die gestrichelte Linie bezeichnet dabei den Grenzwert $\pi /6$.

Literatur

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