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:ℝ\to ℝ$ eine Familie von Zufallsvariablen und $M:ℝ\to ℝ$ eine messbare Funktion, sodass gilt: $M(x)=𝔼(Y_x)$. Sei zudem eine eindeutige Lösung $\theta \in ℝ$ 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$:

• $\mathrm{\exists }C>0\mathrm{\forall }x\in ℝ(P[\left|Y_x\right|\le C]=1)$,
• $M(x)$ ist monoton wachsend,
• $M^{\prime }(\theta )>0$ existiert,
• $a_n$ genügt folgenden Bedingungen:

$\sum _{n=0}^{\mathrm{\infty }}{a}_n=\mathrm{\infty }\text{und}\sum _{n=0}^{\mathrm{\infty }}{a}_n^2<\mathrm{\infty }$

Einfaches Beispiel

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

$Y_{x_n}=\{\begin{array}{cc}{x}_n+\sin (\pi /3)-\pi /3-\frac{1}{2}+{\epsilon }_n& \text{für }{x}_n>\pi /3\\ \sin (x_n)-\frac{1}{2}+{\epsilon }_n& \text{für }-\pi /3\le x_n\le \pi /3\\ x_n-\sin (\pi /3)+\pi /3-\frac{1}{2}+{\epsilon }_n& \text{für }{x}_n<-\pi /3\end{array}$

Wobei ${\epsilon }_n$ unabhängige, gleichverteilte Zufallsvariablen in $(-\frac{1}{4},\frac{1}{4})$ sind. Sei außerdem $a_n=\frac{1}{n+1}$ und $X_1=\frac{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 π/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.