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

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

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

Konvergenz von X_n gegen θ

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

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

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

Einfaches Beispiel

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

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

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

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

Einzelnachweise

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

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.