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 <math>Y_x: \mathbb{R} \rightarrow \mathbb{R}</math> eine Familie von Zufallsvariablen und <math>M: \mathbb{R} \rightarrow \mathbb{R}</math> eine messbare Funktion, sodass gilt: <math>M(x)=\mathbb{E}(Y_x)</math>. Sei zudem eine eindeutige Lösung <math>\theta \in \mathbb{R}</math> gegeben, sodass <math>M(\theta)=0 \ </math>. Dann heißt die Folge <math>(X_n)_{n\in \mathbb{N}}</math> von Zufallsvariablen gegeben durch
- <math>X_{n+1} = X_n-a_n(Y_{X_n})</math>
Robbins-Monro-Prozess, wobei <math>X_1</math> eine beliebige reelle Konstante und <math>(a_n)_{n\in \mathbb{N}}</math> eine Folge reeller Konstanten mit <math>a_n > 0</math> sei.
Konvergenz von Xn gegen θ
Unter den folgenden vier Bedingungen konvergiert <math>X_n</math> in <math>L^2</math> gegen <math>\theta</math><ref>Herbert Robbins, Sutton Monro: A Stochastic Approximation Method. In: The Annals of Mathematical Statistics. 22, Nr. 3, 1951, S. 405 Theorem 2.</ref>:
- <math>\exists{C>0} \forall{x \in \mathbb{R}} \ ( P[\left| Y_x \right| \leq C] = 1)</math>,
- <math>M(x)</math> ist monoton wachsend,
- <math>M'(\theta)>0</math> existiert,
- <math>a_n</math> genügt folgenden Bedingungen:
- <math>\qquad \sum^{\infty}_{n=0}a_n = \infty \quad \text{und} \quad \sum^{\infty}_{n=0}a^2_n < \infty \quad </math>
Einfaches Beispiel
Seien <math>Y_{x_n}</math> um <math>1/2</math> verschobene Sinusfunktionen zwischen <math>-\pi/3</math> und <math>\pi/3</math> mit zufälligen Schwankungen <math>\varepsilon_n</math>, die an den Rändern linear fortgesetzt werden.
- <math> Y_Vorlage: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} </math> Wobei <math>\varepsilon_n</math> unabhängige, gleichverteilte Zufallsvariablen in <math>\left(-\tfrac{1}{4}, \tfrac{1}{4}\right)</math> sind. Sei außerdem <math>a_n = \tfrac{1}{n+1}</math> und <math>X_1 = \tfrac{1}{2}</math>. Dann konvergiert <math>X_{n+1} = X_n-a_n(Y_{X_n})</math> gegen <math>\pi/6</math>.
-
Schaubild mit 5 verschiedenen Pfaden und 300 Iterationen. Die gestrichelte Linie bezeichnet dabei den Grenzwert <math>\pi/6</math>.
Einzelnachweise
<references/>
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.