Exakte Abschätzungen für die Konvergenzgeschwindigkeit allgemeiner stochastischer Approximationsverfahren in IR

Valery Koval^{∗}

Hochschule für Gerätebau Rusjkastraße 56 282001 Ternopil, Ukraine

Rainer Schwabe^{†}

Freie Universität Berlin 1. Mathematisches Institut Arnimallee 2–6 D-14 195 Berlin, Deutschland

Zusammenfassung

In dieser Arbeit werden für nichtlineare Differenzengleichungen der Form x_{n} = x_{n−1} −a_{n}f(x_{n−1})+b_{n}v_{n} exakte Raten und Konstanten für die Konvergenz von x_{n} gegen die Nullstelle θ der Funktion f unter sehr allgemeinen Voraussetzungen an die Schrittweiten a_{n} und die Gewichtungsfaktoren b_{n} der zufälligen Störungen, sowie an die Störungen v_{n} selbst, bestimmt und eine fast sichere Repräsentation der Abweichungen x_{n} − θ durch gewichtete Summen (unabhängiger) Zufallsgrößen hergeleitet.

1. Einleitung Wir betrachten in IR die Differenzengleichung

x_{n} = x_{n−1} − a_{n}f(x_{n−1}) + b_{n}v_{n},  n ≥ 1, x_{0} ∈ IR,  (1)

wobei a_{n} > 0, lim_{n→∞} a_{n} = 0, ∑_{n=1}^{∞} a_{n} = ∞, (b_{n}) ⊂ IR, (v_{n}) eine zufällige Folge ist und die Gleichung f(x) = 0 die Lösung θ besitzt. Es gelte x_{n} → θ f. s. (n → ∞). Wir wollen eine Folge von Konstanten (c_{n}) bestimmen, so daß

lim sup_{n→∞} c_{n}|x_{n} − θ| = 1 f. s.  (2)

∗Diese Arbeit entstand während eines durch den Deutschen Akademischen Austauschdienstes geförderten Aufenthaltes an der Freien Universität Berlin

†gefördert durch die Forschungsprojekte Ku719/2-1 und Ku719/2-2 der Deutschen Forschungsgemeinschaft

gilt. Außerdem wollen wir die Lösung (x_{n}) der Gleichung (1) durch eine gewichtete Summe von zufälligen Größen (ξ_{n}) approximieren, d. h.

|x_{n} − θ − ∑_{k=1}^{n} d_{nk}ξ_{k}| = o(s_{n}) f. s.  (3)

mit Konstanten (d_{nk}) und einer Folge von Konstanten (s_{n}) mit s_{n} → 0 (n → ∞).

Diese Probleme wurden von verschiedenen Wissenschaftlern sowohl in IR als auch in allgemeineren Räumen untersucht. Wir erwähnen hier nur die Arbeiten von Gaposhkin und Krasulina (1974), Korostelev (1983, 1984) für das Problem (2) und Kersting (1977), Ruppert (1982), Mark (1982) und Walk (1988, 1992) für beide Problemstellungen (2) und (3). In allen diesen Publikationen sahen die Folgen (a_{n}) und (b_{n}) im allgemeinsten Fall so aus: a_{n} = n^{−a}, 0 < a ≤ 1 und b_{n} = n^{−b} mit b ≥ a/2 (siehe z. B. Korostelev (1983, 1984) und Walk (1992)). Für die zufällige Folge (v_{n}) wurde üblicherweise vorausgesetzt, daß:

a) (v_{n}) eine Folge von unabhängigen, identisch verteilten zufälligen Größen ist (Korostelev (1983, 1984)),

b) (v_{n}) eine Martingaldifferenzfolge ist (Gaposhkin und Krasulina (1974)),

c) (v_{n}) einem log log-Invarianzprinzip genügt (Mark (1982), Walk (1988, 1992)), und ähnliches (siehe z. B. Ruppert (1982)).

In der vorliegenden Arbeit werden die Problemstellungen (2) und (3) für Lösungen der Gleichung (1) unter hinreichend allgemeinen Voraussetzungen an (a_{n}), (b_{n}) und (v_{n}), die die weiter oben vorgestellten Voraussetzungen umfassen, untersucht. Zusätzlich wurde häufig für die Funktion f(x) gefordert, daß f(x) = λ(x − θ) + O(|x − θ|^{1+δ}) für x → θ mit δ > 0 (siehe z. B. Kersting (1977) und Ruppert (1982)). Wir benutzen hier die schwächere Bedingung f(x) = λ(x − θ) + o(x − θ) für x → θ, d. h. f ist differenzierbar in θ. Wir werden auch die Beziehung (2) unter konkreteren Voraussetzungen an (v_{n}) untersuchen, um die Klasse der in Gleichung (1) zugelassenen Folgen (a_{n}) und (b_{n}) erweitern zu können.

2. Voraussetzungen Wir betrachten die Gleichung (1) und geben Voraussetzungen an, die wir im weiteren benutzen werden. Wir setzen voraus, daß

f(x) = λ(x − θ) + o(x − θ), für x → θ, mit λ > 0,  (4)

und

x_{n} → θ f. s. (n → ∞).  (5)

Bemerkung 1. Bedingung (4) ist schwächer als die übliche, die z. B. von Kersting (1977) und Ruppert (1982) benutzt wurde. Daher erhalten wir zwar eine schlechtere Genauigkeit der Approximation in (3), aber diese Approximation ist für die Lösung der Aufgabe (2) ausreichend (siehe auch Mark (1982), S. 59).

Bemerkung 2. Voraussetzung (5) wird üblicherweise gefordert bei Untersuchungen der Probleme (2) und (3) für die nichtlineare Gleichung (1) (siehe z. B. Ruppert (1982), Mark (1982) und Korostelev (1984)). Die Beziehung (5) wurde auch von Ljung (1978) und Li (1994) unter allgemeinen Voraussetzungen an die Folgen (a_{n}) und (b_{n}) betrachtet.

Für die Folgen (a_{n}) und (b_{n}) werden folgende Abschätzungen vorausgesetzt:

b_{n}^{2}/a_{n} ≥ b_{n+1}^{2}/a_{n+1},  n ≥ n_{1} ≥ 1,  (6)

und

b_{n+1}^{2}/a_{n+1} ≥ (b_{n}^{2}/a_{n})(1 − λa_{n+1})^{ν}, n ≥ n_{2} ≥ 1, (7)

für ein ν ∈ [1, 2).

Bemerkung 3. Bedingung (7) ist eine Verallgemeinerung der Bedingung a_{n} ≥ a_{n−1}(1 − a_{n}), die von Ljung (1974) bei der Untersuchung der Gleichung x_{n} = x_{n−1} − a_{n}(x_{n−1}+v_{n}) benutzt wurde. Die Bedingungen (6) und (7) wurden von Koval (1994) bei der Lösung der Aufgabe (2) für lineare Gleichungen (1) im IR^{d} bei vorliegenden normalverteilten Störungen (v_{n}) verwendet.

Beispiel 1. Es sei a_{n} = n^{−a}, 0 < a < 1, und b_{n} = n^{−b} mit a/2 < b ≤ a (vgl. Korostelev (1984)). Dann sind die Bedingungen (6) und (7) erfüllt (sogar unter der abgeschwächten Voraussetzung b > a/2) mit ν = 1.

Beispiel 2. Es sei a_{n} = n^{−1} und b_{n} = n^{−(1+β)/2} mit β ≥ 0 und λ > β/2 (cgl. Walk (1992)). Dann gelten die Bedingungen (6) und (7). Wir möchten in diesem Zusammenhang anmerken, daß ν ≥ β/λ gelten muß, damit die Bedingung (7) erfüllt ist. Insbesondere muß γ nahe bei 2 für λ nahe bei β/2 sein.

Beispiel 3. Es sei a_{n} = b_{n} = 1/ log^{α} n, α > 0, n > 1. Dann gelten die Bedingungen (6) und (7) mit ν = 1.

Bemerkung 4. Aus Bedingung (7) folgt, daß b_{n} ≠ 0 für alle n ≥ n_{3} ist, sofern b_{n_{3}} ≠ 0 für n_{3} ≥ 1.

Wir setzen zusätzlich

sup_{n} |b_{n} − b_{n+1}|(a_{n+1}b_{n})^{−1} < ∞.  (8)

für die Folgen (a_{n}) und (b_{n}) voraus. Diese Bedingung kann auch umgeschrieben werden zu: b_{n+1} ≥ b_{n}(1 − ca_{n+1}), n ≥ n_{4}, für ein c > 0 (vgl. Bedingung (7)).

Beispiel 4. Für a_{n} = n^{−a}, mit 0 < a ≤ 1, und b_{n} = n^{−b}, mit b > 0, oder a_{n} = b_{n} = 1/ log^{α} n, n > 1, mit α > 0, ist Bedingung (8) erfüllt.

Wir betrachten als nächstes Voraussetzungen an die zufällige Folge (v_{n}). Ohne Beschränkung der Allgemeinheit können wir voraussetzen, daß

a_{n} < 1/λ, n ≥ 1.

Weiterhin setzen wir

p_{n} = ∏_{j=1}^{n}(1 − λa_{j}) ,

B_{n} = ∑_{k=1}^{n} b_{k}^{2}/p_{k}^{2} ,
σ_{n}^{2} = p_{n}^{2}B_{n} ,
L_{n} = log log B_{n} ,
χ_{n} = (2B_{n}L_{n})^{1/2} und
ℓ_{n} = log(∑_{j=1}^{n} a_{j}) .

Wir werden später zeigen, daß aus (6) und (7) lim_{n→∞} B_{n} = ∞ folgt.

Bemerkung 5. Wir möchten anmerken, daß B_{n} = V ar (∑_{k=1}^{n}(b_{k}/p_{k})v_{k}), wenn (v_{n}) z. B. eine Folge von unkorrelierten zufälligen Größen mit Ev_{n}^{2} = 1 ist. Alle Ergebnisse dieser Arbeit bleiben gültig, wenn wir statt (B_{n}) eine Folge (B′_{n}) betrachten mit B′_{n} ∼ B_{n} (n → ∞).

Für (v_{n}) setzen wir insbesondere voraus, daß

lim sup_{n→∞} χ_{n}^{−1} |∑_{k=1}^{n}(b_{k}/p_{k})v_{k}| < ∞ f. s.  (9)

Diese Voraussetzung ist erfüllt, wenn die Folge (∑_{k=1}^{n}(b_{k}/p_{k})v_{k}) dem Gesetz vom iterierten Logarithmus genügt (siehe z. B. Stout (1974) und Petrov (1995)). Da die Summanden (b_{n}/p_{n}) eine sehr spezielle Gestalt besitzen, können wir später ein Kriterium für die Gültigkeit der Beziehung (9) und der spezielleren Beziehung (13) (siehe unten) unter hinreichend allgemeinen Voraussetzungen angeben (siehe Lemma 6 im Paragraph 4). Eine andere Bedingung an (v_{n}) wird in (16) gestellt.

Wir können ohne Einschränkung voraussetzen, daß x_{0} = 0 ist, daß für die Lösung θ = 0 gilt und daß n_{1} = n_{2} = n_{3} = 1 gesetzt werden kann.

3. Hauptresultate

Satz 1. Sind die Bedingungen (4) bis (7) und (9) erfüllt, dann gilt

lim_{n→∞} |x_{n}/(2σ_{n}^{2}ℓ_{n})^{1/2} − χ_{n}^{−1} ∑_{k=1}^{n}(b_{k}/p_{k})v_{k}| = 0 f. s.  (10)

und

|x_{n} − p_{n} ∑_{k=1}^{n}(b_{k}/p_{k})v_{k}| = o ((b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2}) f. s.  (11)

Beziehung (11) stellt eine Lösung des Problems 3 dar (vgl. Ruppert (1982) für den Fall a_{n} = n^{−1}).

Bemerkung 6. Betrachten wir die lineare Differenzengleichung

y_{n} = y_{n−1} − a_{n}λy_{n−1} + b_{n}v_{n},  n ≥ 1, y_{0} = 0,  (12)

dann gilt y_{n} = p_{n} ∑_{k=1}^{n}(b_{k}/p_{k})v_{k} und wir können die Beziehung (12) wie folgt umschreiben

|x_{n} − y_{n}| = o ((b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2}) f. s.

Satz 2. Sind die Bedingungen (4) bis (7) erfüllt und ist zusätzlich

lim sup_{n→∞} χ_{n}^{−1} |∑_{k=1}^{n}(b_{k}/p_{k})v_{k}| = 1 f. s.,  (13)

dann gilt

lim sup_{n→∞} |x_{n}|/(2σ_{n}^{2}ℓ_{n})^{1/2} = 1 f. s.  (14)

Beispiel 5. Es sei a_{n} = n^{−1}, b_{n} = n^{−(1+β)/2} mit β ≥ 0, λ > β/2. Dann kann man nachrechnen, daß

σ_{n}^{2} ∼ n^{−β}/(2λ − β) (n → ∞),

und

ℓ_{n} ∼ log log n (n → ∞)

gilt. Somit erhalten wir aus (14)

lim sup_{n→∞} |x_{n}|/(n^{−β} log log n)^{1/2} = (\frac{2}{2λ−β} )^{1/2} f. s.

(Für den Fall β = 1 vgl. Gaposhkin und Krasulina (1974) und Kersting (1977), für 0 < β ≤ 1, λ > 1/2 vgl. Korostelev (1984) und Ruppert (1982), und im allgemeinen Fall siehe auch Walk (1992)). Wir möchten hier noch anmerken, daß β > 0 gelten muß, um x_{n} → 0 f. s. zu sichern.

Beispiel 6. Es sei a_{n} = n^{−a}, 0 < a < 1, und b_{n} = n_{−b}, b > a/2. Dann kann man berechnen, daß

σ_{n}^{2} ∼ n^{a−2b}/2λ (n → ∞)

und

ℓ_{n} ∼ (1 − a) log n (n → ∞)

gilt. Somit erhalten wir aus (14)

lim sup_{n→∞} |x_{n}|/(n^{a−2b} log n)^{1/2} = (\frac{1−a}{λ})^{1/2} f. s.

(Für den Fall a/2 < b ≤ a vgl. Korostelev (1984)).

Die Berechnung von σ_{n}^{2} in (14) bereitet im allgemeinen Fall einige technische Schwierigkeiten. Jedoch reicht es in einigen Situationen aus, lediglich eine obere und untere Abschätzung für lim sup_{n→∞} |x_{n}|/(2σ_{2}^{n}ℓ_{n})^{1/2} zu finden. Dazu kann man die folgende Behauptung benutzen:

Folgerung 1. Sind die Bedingungen (4) bis (7) und (13) erfüllt, dann gilt

1/λ^{1/2} ≤ lim sup_{n→∞} |x_{n}|/(b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2} ≤ (\frac{2}{λ(2−ν)})^{1/2} f. s.  (15)

In der Beziehung (11) wird die Lösung (x_{n}) der Diffenrenzengleichung (1) durch eine gewichtete Summe der zufälligen Größen (v_{n}) approximiert. Im allgemeinen Fall können diese zufälligen Größen abhängig sein. Wir möchten daher die Lösung (x_{n}) auch durch eine gewichtete Summe von unabhängigen zufälligen Größen approximieren.

Satz 3. Es seien die Bedingungen (4) bis (8) erfüllt und es existiere eine Folge von unabhängigen, standard-normalverteilten Zufallsfgrößen (γ_{n}) mit

|∑_{i=1}^{n} v_{i} − ∑_{i=1}^{n} γ_{i}| = o ((a_{n}^{−1}ℓ_{n})^{1/2}) f. s.  (16)

Dann gilt

|x_{n} − p_{n} ∑_{k=1}^{n}(b_{k}/p_{k})γ_{k}| = o ((b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2}) f. s.  (17)

Sei die Folge (z_{n}) Lösung der linearen Differenzengleichung

z_{n} = (1 − λa_{n})z_{n−1} + b_{n}γ_{n},  n ≥ 1, z_{0} = 0,  (18)

dann kann man (17) folgendermaßen umschreiben

|x_{n} − z_{n}| = o ((b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2}) f. s.  (19)

Wir möchten hier anmerken, daß (z_{n}) wegen (18) ein zentrierter Gaußscher Markov-Prozeß mit diskreter Zeit ist.

Ähnliche Problemstellungen zu (17) und (19) wurden im Fall a_{n} = n^{−1} von Kersting (1977) und Walk (1988, 1992) und im Fall a_{n} = n^{−a}, 0 < a < 1, von Schwabe und Walk (1995) für die Lösung (y_{n}) der linearen Gleichung (12) untersucht.

Wir wollen jetzt die Bedingung (16) etwas genauer betrachten. Insbesondere möchten wir bemerken, daß diese Bedingung nur von der Folge (a_{n}) abhängt. Diese Bedingung sagt aus, daß wir strengere Anforderungen an die Genauigkeit Δ_{n} der Approximation der Summe V_{n} = ∑_{i=1}^{n} v_{i} durch die Summe Γ_{n} = ∑_{i=1}^{n} γ_{i} stellen müssen, wenn wir die Schrittweite (a_{n}) in der Gleichung (1) vergrößern, zum Beispiel:

a) für a_{n} = n^{−1} muß Δ_{n} = o ((log log n)^{1/2})

b) für a_{n} = n^{−a}, 0 < a < 1, muß Δ_{n} = o ((n^{a} log n)^{1/2})

c) für a_{n} = 1/ log^{α} n), α > 1 muß Δ_{n} = o ((log n)^{(1+α)/2}) gelten. Aussagen über die Möglichkeit der Approximation von V_{n} durch Γ_{n} in den Fällen a), b) und c) kann man (unter verschiedenen Forderungen an die Folge (v_{n})) z. B. bei Berger (1990), Philipp und Stout (1975), Komlós, Major und Tusnady (1975, 1976) und Major (1976,1979) finden (siehe auch Bingham (1986) und Shao (1993)).

Satz 4. Sind die Bedingungen (4) bis (8) und (16) erfüllt, dann gilt (14).

Um die Klasse der zugelassenen Folgen (a_{n}) und (b_{n}) in Gleichung (1) zu erweitern, muß man konkretere Voraussetzungen an die statistischen Eigenschaften der Folge (v_{n}) machen. Wir betrachten zuerst Folgen von unabhängigen, identisch verteilten zufälligen Größen. In diesem Fall läßt sich wegen (13) das Problem (14) auf das Gesetz vom iterierten Logarithmus für gewichtete Summen von unabhängigen, identisch verteilten zufälligen Größen zurückführen (siehe z. B. Klesov (1987)).

Behauptung 1. Es sei (v_{n}) eine Folge von unabhängigen, identisch verteilten zufälligen Größen mit Ev_{1} = 0, E|v_{1}|^{2/γ} < ∞ für ein γ ∈ (\frac{2}{3}, 1], die Bedingungen (4) bis (7) seien erfüllt und es gelte

sup_{n} a_{n}n^{γ}/ℓ_{n} < ∞,  (20)

dann gilt (14).

Aus (20) folgt, daß man a_{n} = n^{−1} wählen muß, wenn γ = 1 ist, d. h. wenn nur das zweite Moment Ev_{1}^{2} existiert.

Wir möchten uns jetzt für den Fall interessieren, daß die Schrittweite (a_{n}) größer als n^{−1} gewählt werden kann.

Behauptung 2. Es sei (v_{n}) eine Folge von unabhängigen, identisch verteilten zufälligen Größen mit Ev_{1} = 0, E|v_{1}|^{2+δ} < ∞ für ein δ > 0, die Bedingungen (4) bis (7) seien erfüllt und es gelte

sup_{n} a_{n}ℓ_{n}(∑_{j=1}^{n} a_{j})^{2/δ} < ∞,  (21)

dann gilt (14).

Bemerkung 7. Die Bedingungen (20) und (21) hängen, wie (16), nur von der Folge (a_{n}) ab.

Beispiel 7. Es sei a_{n} = n^{−a}, 0 < a < 1, dann ist (21) für δ > 2(1 − a)/a erfüllt. Wir bemerken noch, daß δ ↑ ∞ wenn a ↓ 0.

Die Bedingung (21) ist z. B. dann nicht erfüllt, wenn a_{n} = 1/ log^{α} n, α > 0.

Wir möchten uns als nächstes dafür interessieren, was wir erhalten, wenn die zufälligen Größen (v_{n}) alle absoluten Momente besitzen, z. B. wenn sie beschränkte oder wenn sie normalverteilte zufällige Größen sind.

Behauptung 3. Es sei (v_{n}) eine Folge von unabhängigen zufälligen Größen mit Ev_{n} = 0 und |v_{n}| ≤ c < ∞ f. s., die Bedingungen (4) bis (7) seien erfüllt und es gelte

a_{n}ℓ_{n} → 0 (n → ∞),

dann gilt (14).

Behauptung 4. Es sei (v_{n}) eine Folge unabhängiger standard-normalverteilter zufälliger Größen und die Bedingungen (4) bis (7) seien erfüllt, dann gilt (14).

Beispiel 8. Es sei a_{n} = b_{n} = 1/ log^{α} n, α > 0. Dann sind die Voraussetzungen (6) und (7) erfüllt und wir erhalten (unter Ausnutzung der Ungleichung (15))

λ^{−1/2} ≤ lim sup_{n→∞} |x_{n}|(log n)^{(α−1)/2} ≤ (2/λ)^{1/2} f. s.

Wir möchten hier noch anmerken, daß α > 1 sein muß, um x_{n} → 0 f. s. zu sichern.

4. Hilfsresultate Lemma 1. Unter den Voraussetzungen (6) und (7) gilt

\frac{1}{2λ} \frac{b_{n}^{2}}{a_{n}} (1 + o(1)) ≤ σ_{n}^{2} ≤ \frac{1}{(2−ν)λ} \frac{b_{n}^{2}}{a_{n}} .

Beweis. Wir beweisen zuerst, daß

σ_{n}^{2} ≥ (2λ)^{−1} (1 + o(1)) b_{n}^{2}/a_{n}.  (22)

Dazu benutzen wir die Bedingung (6). Wir vereinbaren ∏_{j=n+1}^{n}(1 − λa_{j}) = 1.

σ_{n}^{2} = ∑_{k=1}^{n} b_{k}^{2} ∏_{j=k+1}^{n}(1 − λa_{j})^{2}
= ∑_{k=1}^{n}(b_{k}^{2}/a_{k})a_{k} ∏_{j=k+1}^{n}(1 − λa_{j})^{2}
≥ (b_{k}^{2}/a_{n}) ∑_{k=1}^{n} \frac{a_{k}}{1−(1−λa_{k})^{2}} (∏_{j=k+1}^{n}(1 − λa_{j})^{2} − ∏_{j=k}^{n}(1 − λa_{j})^{2})
≥ (b_{n}^{2}/a_{n})(2λ)^{−1} ∑_{k=1}^{n} (∏_{j=k+1}^{n}(1 − λa_{j})^{2} − ∏_{j=k}^{n}(1 − λa_{j})^{2})
= (2λ)^{−1}(b_{n}^{2}/a_{n}) (1 − ∏_{j=1}^{n}(1 − λa_{j})^{2}) .

Daraus folgt (22), da ∏_{j=1}^{n}(1 − λa_{j})^{2} → 0 (n → ∞) auf Grund der Voraussetzung ∑_{j=1}^{∞} a_{j} = ∞.

Wir beweisen jetzt, daß

σ_{n}^{2} ≤ ((2 − ν)λ)^{−1} b_{n}^{2}/a_{n}

gilt. Dazu benutzen wir

∏_{j=k+1}^{n}(1 − λa_{j})^{ν}b_{k}^{2}/a_{k} ≤ b_{n}^{2}/a_{n}, 1 ≤ k ≤ n,

was durch Iteration aus Bedingung (7) folgt. Damit gilt

σ_{n}^{2} = ∑_{k=1}^{n} (∏_{j=k+1}^{n}(1 − λa_{j})^{ν}b_{k}^{2}/a_{k}) a_{k} ∏_{j=k+1}^{n}(1 − λa_{j})^{2−ν}
≤ (b_{n}^{2}/a_{n}) ∑_{k=1}^{n} \frac{a_{k}}{1−(1−λa_{k})^{2−ν}} (∏_{j=k+1}^{n}(1 − λa_{j})^{2−ν} − ∏_{j=k}^{n}(1 − λa_{j})^{2−ν})
≤ ((2 − ν)λ)^{−1} (b_{n}^{2}/a_{n}) ∑_{k=1}^{n} (∏_{j=k+1}^{n}(1 − λa_{j})^{2−ν} − ∏_{j=k}^{n}(1 − λa_{j})^{2−ν})
= ((2 − ν)λ)^{−1} (b_{n}^{2}/a_{n}) (1 − ∏_{j=1}^{n}(1 − λa_{j})^{2−ν})
≤ ((2 − ν)λ)^{−1} (b_{n}^{2}/a_{n}) ,

für alle n ≥ 1. □

Bemerkung 8. In manchen Situationen ist es ausreichend, lediglich eine Abschätzung σ_{n}^{2} ≥ (a_{1}/2)b_{n}^{2}/a_{n}, für alle n ≥ 1, zu erhalten.

Lemma 2. Unter den Bedingungen (6) und (7) gilt B_{n} → ∞ (n → ∞).

Beweis. Es gilt

B_{n} = σ_{n}^{2}/p_{n}^{2}
≥ (a_{1}/2)b_{n}^{2}a_{n}^{−1} ∏_{j=1}^{n}(1 − λa_{j})^{−ν} ∏_{j=1}^{n}(1 − λa_{j})^{ν−2}
≥ (4λ(1 − λa_{1})^{ν})^{−1} b_{1}^{2} ∏_{j=1}^{n}(1 − λa_{j})^{ν−2} .  (23)

Daraus folgt die Behauptung des Lemmas, da ν − 2 < 0 und ∑_{j=1}^{∞} a_{j} = ∞. □ Im weiteren bezeichnen wir mit M, M_{1}, M_{2}, … geeignete positive Konstanten. Lemma 3. Unter den Bedingungen (6) und (7) gilt L_{n} ∼ ℓ_{n} (n → ∞). Beweis. Nach Definiton gilt L_{n} = log log B_{n} = log log(σ_{n}^{2}/p_{n}^{2}). Weiterhin gilt

einerseits (siehe (23))

B_{n} ≥ M_{1} ∏_{j=1}^{n}(1 − λa_{j})^{ν−2} ≥ M_{1} exp ((2 − ν)λ ∑_{j=1}^{n} a_{j})

und andererseits (siehe Lemma 1 und (6))

B_{n} ≤ M_{2}b_{n}^{2}a_{n}^{−1}p_{n}^{−2} ≤ M_{2}a_{1}^{−1}b_{1}^{2} ∏_{j=1}^{n}(1 − λa_{j})^{−2} ≤ M_{3} exp ((2λ + ε) ∑_{j=1}^{n} a_{j}) , für ein ε > 0, da lim_{j→∞} a_{j} = 0. Somit ist für große n L′_{n} := log(log M_{1} + (2 − ν)λ ∑_{j=1}^{n} a_{j}) ≤ L_{n} ≤ log(log M_{3} + (2λ + ε) ∑_{j=1}^{n} a_{j}) =: L′′_{n}. Wegen L′_{n} ∼ ℓ_{n} und L′′_{n} ∼ ℓ_{n} (n → ∞) folgt die Behauptung des Lemmas. □

Lemma 4. Ist (z_{n}) Lösung der Differenzengleichung (18), dann gilt unter den Voraussetzungen (6) und (7)

lim sup_{n→∞} |z_{n}|/(2σ_{n}^{2}ℓ_{n})^{1/2} = 1 f. s.

Beweis. Wir schreiben z_{n} als z_{n} = p_{n}z̃_{n}, wobei z̃_{n} = ∑_{k=1}^{n}(b_{k}/p_{k})γ_{k}. Dann gilt z̃_{n} = W (B_{n}), wobei W (·) eine standardisierte Brownsche Bewegung ist. Weiter gilt B_{n} → ∞ (n → ∞) auf Grund von Lemma 2.

Wegen Bedingung (6) gilt 1 ≤ B_{n+1}/B_{n} = 1 + b_{n+1}^{2} ∏_{j=1}^{n+1}(1 − λa_{j})^{−2}B_{n}^{−1} = 1+b_{n+1}^{2}(1−λa_{n+1})^{−2}σ_{n}^{−2} ≤ 1+Ma_{n}b_{n+1}^{2}b_{n}^{2} ≤ 1+Ma_{n+1}, woraus mit lim_{n→∞} a_{n} = 0

lim_{n→∞} B_{n+1}/B_{n} = 1  (24)

für das Wachstum von B_{n} folgt.

Daher folgt aus dem Gesetz vom iterierten Logarithmus für die Brownsche Bewegung mit Zeit t = B_{n} (siehe z. B. Gut (1986))

lim sup_{n→∞} |z̃_{n}|/(2B_{n} log log B_{n})^{1/2} = 1 f. s.

bzw.

lim sup_{n→∞} |z_{n}|/(2σ_{n}^{2}L_{n})^{1/2} = 1 f. s.

Aus dieser Beziehung und Lemma 3 folgt die Behauptung von Lemma 4. □

Lemma 5. Es seien (y_{n}) und (z_{n}) Lösungen der Differenzengleichungen (12) bzw. (18). Sind die Bedingungen (7), (8) und (16) erfüllt, dann gilt

|y_{n} − z_{n}| = o ((b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2}) f. s.  (25)

Beweis. Wir setzen V_{n} = ∑_{i=1}^{n} v_{i}, Γ_{n} = ∑_{i=1}^{n} γ_{i} und benutzen die Abelsche Identität:

y_{n} − z_{n} = ∑_{k=1}^{n} b_{k} ∏_{j=k+1}^{n}(1 − λa_{j})(v_{k} − γ_{k})

= ∑_{k=1}^{n−1} (b_{k} ∏_{j=k+1}^{n}(1 − λa_{j}) − b_{k+1} ∏_{j=k+2}^{n}(1 − λa_{j})) (V_{k} − Γ_{k}) + b_{n}(V_{n} − Γ_{n})
= ∑_{k=1}^{n−1} ∏_{j=k+2}^{n}(1 − λa_{j})b_{k}a_{k+1} (\frac{b_{k}−b_{k+1}}{a_{k+1}b_{k}} − λ) (ℓ_{k}/a_{k})^{1/2} ((V_{k} − Γ_{k})(a_{k}/ℓ_{k})^{1/2})
+ b_{n}(V_{n} − Γ_{n}) .

Wir setzen

δ_{n} = |V_{n} − Γ_{n}|(a_{n}/ℓ_{n})^{1/2}.

Auf Grund der Bedingung (16) gilt

δ_{n} → 0 f. s. (n → ∞). (26)

Im weiteren benutzen wir (8) und die Bedingung

|b_{k}|a_{k}^{−1/2} ∏_{j=k+2}^{n}(1 − λa_{j})^{ν/2} ≤ M_{1}|b_{n}|a_{n}^{−1/2},

die aus (7) folgt, und erhalten

|y_{n} − z_{n}| ≤ ∑_{k=1}^{n−1} |b_{k}|a_{k+1} ∏_{j=k+2}^{n}(1 − λa_{j}) (|\frac{b_{k}−b_{k+1}}{a_{k+1}b_{k}} | + λ) (ℓ_{k}/a_{k})^{1/2}δ_{k}

+ (b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2}δ_{n}

≤ M_{2}ℓ_{n}^{1/2} ∑_{k=1}^{n} (|b_{k}|a_{k}^{−1/2} ∏_{j=k+2}^{n}(1 − λa_{j})^{ν/2}) a_{k+1} ∏_{j=k+2}^{n}(1 − λa_{j})^{1−(ν/2)}δ_{k}
+ (b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2}δ_{n}
≤ M_{3}(b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2} (∑_{k=1}^{n−1} a_{k+1} ∏_{j=k+2}^{n}(1 − λa_{j})^{1−(ν/2)}δ_{k} + δ_{n}) .

Also gilt insgesamt

|y_{n} − z_{n}| ≤ M_{3}(b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2}(T_{n} + δ_{n})  (27)

mit

T_{n} = ∑_{k=1}^{n−1} a_{k+1} ∏_{j=k+2}^{n}(1 − λa_{j})^{1−(ν/2)}δ_{k} .

Wir zeigen als nächstes, daß T_{n} → 0 f. s. (n → ∞). Dazu setzen wir

c_{nk} = a_{k+1} ∏_{j=k+2}^{n}(1 − λa_{j})^{α} , 1 ≤ k ≤ n − 1.

Hier ist α = 1 − (ν/2) und folglich α ∈ (0, 1/2]. T_{n} läßt sich schreiben als T_{n} = ∑_{k=1}^{n−1} c_{nk}δ_{k}.

Insbesondere erhalten wir c_{nk} ≥ 0 und

c_{nk} → 0 (n → ∞) für jedes k ≥ 1.  (28)

Weiterhin gilt

∑_{k=1}^{n−1} c_{nk} ∑_{k=1}^{n−1} \frac{a_{k+1}}{1−(1−λa_{k+1})^{α}} (∏_{j=k+2}^{n}(1 − λa_{j})^{α} − ∏_{j=k+1}^{n}(1 − λa_{j})^{α})

≤ (λα)^{−1} ∑_{k=1}^{n−1} (∏_{j=k+2}^{n}(1 − λa_{j})^{α} − ∏_{j=k+1}^{n}(1 − λa_{j})^{α})
= (λα)^{−1} (1 − ∏_{j=2}^{n}(1 − λa_{j})^{α})
≤ (λα)^{−1} < ∞ .  (29)

Aus den Beziehungen (26), (28) und (29) und dem Lemma von Toeplitz folgt

T_{n} → 0 f. s. (n → ∞)

Hieraus und aus (26) folgt die Behauptung des Lemmas mit Hilfe der Ungleichung (27). □

Lemma 6. Sind die Bedingungen (6) bis (8) und (16) erfüllt, dann gilt (13). Beweis. Auf Grund von Lemma 3 und 4 sowie 1 und 5 erhalten wir

lim sup_{n→∞} |χ_{n}^{−1} ∑_{k=1}^{n}(b_{k}/p_{k})v_{k} − z_{n}/(2σ_{n}^{2}ℓ_{n})^{1/2}|
≤ lim sup_{n→∞} |y_{n} − z_{n}|/(2σ_{n}^{2}ℓ_{n})^{1/2}
≤ λ^{1/2} lim sup_{n→∞} |y_{n} − z_{n}|/(b_{n}^{2}a_{n}^{−1}ℓ_{n})^{1/2} = 0 f. s.

Aus dieser Beziehung, Lemma 4 und der Dreiecks-Ungleichung

|lim sup_{n→∞} |s′_{n}| − lim sup_{n→∞} |s′′_{n}|| ≤ lim sup_{n→∞} |s′_{n} − s′′_{n}|

erhalten wir

lim sup_{n→∞} χ_{n}^{−1} |∑_{k=1}^{n}(b_{k}/p_{k})v_{k}| = lim sup_{n→∞} |z_{n}|/(2σ_{n}^{2}ℓ_{n})^{1/2} = 1 f. s.

□

5. Beweise der Hauptresultate

Beweis des Satzes 1. Aus den Bedingungen (4) und (5) folgt

f(x_{n}) = λx_{n} + δ_{n}x_{n},

wobei

δ_{n} → 0 f. s. (n → ∞).

Dann ist

x_{n} = (1 − λa_{n})x_{n−1} + a_{n}δ_{n−1}x_{n−1} + b_{n}v_{n}, n ≥ 1,

und

x_{n}/p_{n} = ∑_{k=1}^{n}(b_{k}/p_{k})v_{k} + ∑_{k=1}^{n−1}(a_{k+1}/p_{k+1})δ_{k}x_{k}.

Wir teilen die letzte Zeile durch (B_{n}ℓ_{n})^{1/2}: x_{n}/(σ_{n}^{2}ℓ_{n})^{1/2} = ∑_{k=1}^{n}(b_{k}/p_{k})v_{k}/(B_{n}ℓ_{n})^{1/2} + ∑_{k=1}^{n−1} \frac{a_{k+1}}{1−λa_{k+1}} (\frac{B_{k}ℓ_{k}}{B_{n}ℓ_{n}} )^{1/2} δ_{k}x_{k}/(σ_{k}^{2}ℓ_{k})^{1/2} und setzen

x̃_{n} = x_{n}/(σ_{n}^{2}ℓ_{n})^{1/2},

sowie

R_{n} = ∑_{k=1}^{n}(b_{k}/p_{k})v_{k}/(B_{n}ℓ_{n})^{1/2} ,
G_{n,k} = \frac{a_{k+1}}{1−λa_{k+1}} (\frac{B_{k}ℓ_{k}}{B_{n}ℓ_{n}} )^{1/2} δ_{k}, 1 ≤ k ≤ n − 1.

Dann läßt sich x̃_{n} darstellen als

x̃_{n} = R_{n} + ∑_{k=1}^{n−1} G_{n,k}x̃_{k} .

Zuerst wollen wir zeigen, daß

sup_{n} |x̃_{n}| < ∞ f. s.

gilt. Wegen (2B_{n}ℓ_{n})^{1/2} ∼ χ_{n} (Lemma 3), folgt aus Bedingung (9)

sup_{n} |R_{n}| < ∞ f. s.  (30)

Als nächstes wollen wir zeigen, daß

lim_{n→∞} ∑_{k=1}^{n−1} |G_{n,k}| = 0 f. s.  (31)

gilt. Dazu schätzen wir wie folgt ab

∑_{k=1}^{n−1} |G_{n,k}| ≤ ∑_{k=1}^{n−1} \frac{a_{k+1}}{1−λa_{k+1}} \frac{p_{n}}{p_{k}} \frac{σ_{k}}{σ_{n}} |δ_{k}|
≤ M ∑_{k=1}^{n−1} \frac{a_{k+1}}{1−λa_{k+1}} \frac{p_{n}}{p_{k}} \frac{|b_{k}|}{|b_{n}|} \frac{a_{n}^{1/2}}{a_{k}^{1/2}} |δ_{k}|
= M (a_{n}^{1/2}/|b_{n}|) ∑_{k=1}^{n−1} a_{k+1} ∏_{j=k+2}^{n}(1 − λa_{j}) (|b_{k}|/a_{k}^{1/2}) |δ_{k}| .

Weiter verfahren wir wie im Beweis von Lemma 5 und erhalten die Beziehung (31). Aus (30), (31) und Lemma 2 von Walk und Zsidó (1989) folgt

sup_{n} |x̃_{n}| < ∞ f. s.

Damit gilt

|x̃_{n} − R_{n}| ≤ ∑_{k=1}^{n−1} |G_{n,k}| sup_{n} |x̃_{n}| ,

woraus mit (31) die Beziehung (10) folgt. Beziehung (11) ergibt sich schließlich aus (10) und Lemma 1. □

Der Beweis des Satzes 2 folgt unmittelbar aus den Beziehungen (10) und (13).

Beweis des Satzes 3. Unter den Bedingungen des Satzes gelten Lemma 5 und 6 sowie Satz 1. Damit folgt die Behauptung (17) aus den Beziehungen (11) und (25) (vgl. Bemerkung 6 und die Definition (18) von z_{n}). □

Der Beweis des Satzes 4 folgt aus Beziehung (17) (Satz 3) und Lemma 4 bzw. aus Lemma 6 und Satz 2.

Der Beweis der Folgerung 1 folgt aus Beziehung (14) (Satz 2) und Lemma 1.

Die Beweise der Behauptungen 1 und 2 werden auf die Überprüfung der Bedingungen entsprechender Ergebnisse (Folgerung 4 und Beziehung (6)) in der Arbeit von Klesov (1987) zurückgeführt. (Dabei muß für Folgerung 4 die Beziehung (24) ausgenutzt werden.)

Der Beweis der Behauptung 3 kann auf die Überprüfung der Bedingungen des klassischen Gesetzes vom iterierten Logarithmus von Kolmogorov (siehe z. B. Petrov (1995)) zurückgeführt werden.

Der Beweis der Behauptung 4 folgt aus Satz 2 und Lemma 4, da in diesem Fall v_{n} = γ_{n}, n ≥ 1, in Gleichung (1) gesetzt werden kann.

Literatur

[1] Berger, E. (1990). An almost sure invariance principle for stationary ergodic sequences of Banach space valued random variables. Probab. Theory Related Fields 84 161–201.

[2] Bingham, N. H. (1986). Variants on the law of the iterated logarithm. Bull. London Math. Soc. 18 433–467.

[3] Gaposhkin, V. F. und Krasulina, T. P. (1974). On the law of the iterated logarithm in stochastic approximation processes. Theory Probab. Appl. 19 844–850.

[4] Gut, A. (1986). The law of the iterated logarithm for subsequences. Probab. Math. Statist. 7 27–58.

[5] Kersting, G. (1977). Almost sure approximation of the Robbins-Monro process by sums of independent random variables. Ann. Probab. 5 954–965.

[6] Klesov, O. J. (1987). The law of the iterated logarithm for weighted sums of independent identically distributed random variables. Theory Probab. Appl. 31 337–342.

[7] Komlós, J., Major, P. und Tusnády, G. (1975, 1976). An Approximation of partial sums of independent RV’s, and the sample DF, I, II. Z. Wahrscheinlichkeitstheorie

verw. Geb. 32 111–131, 34 33–58.

[8] Korostelev, A. P. (1983). On upper functions for stochastic approximation procedures. Theory Probab. Appl. 28 806–811.

[9] Korostelev, A. P. (1984). Stochastic recursive procedures (local properties). Nauka, Moskau (auf russisch).

[10] Koval, V. A. (1994). On the rate of convergence for stochastic approximation procedures. Ukrain. Math. Journ. 46 997–1002 (auf russisch).

[11] Li, G. (1994). Almost sure convergence of stochastic approximation procedures. Statist. Sinica 4 361–372.

[12] Ljung, L. (1974). Convergence of recursive stochastic algorithms. Report 7403, Dept. of Automatic Control, Lund Institute of Technology.

[13] Ljung, L. (1978). Strong convergence of a stochastic approximation algorithm. Ann. Statist. 6 680–696.

[14] Major, P. (1976). The approximation of partial sums of independent rv’s. Z. Wahrscheinlichkeitstheorie verw. Geb. 35 213–220.

[15] Major, P. (1979). An improvement of Strassen’s invariance principle. Ann. Probab. 7 55–61.

[16] Mark, G.(1982). Loglog-Invarianzprinzipien für Prozesse der stochastischen Approximation. Mitteilungen Math. Sem. Gießen 153.

[17] Petrov, V. V. (1995). Limit theorems of probability theory: sequences of independent random variables. Clarendon, Oxford.

[18] Philipp, W. und Stout, W. (1975). Almost sure invariance principles for partial sums of weakly dependent random variables. Mem. Am. Math. Soc. 161.

[19] Ruppert, D. (1982). Almost sure approximation to the Robbins-Monro and Kiefer-Wolfowitz processes with dependent noise. Ann. Probab. 10 178–187.

[20] Schwabe, R. und Walk, H. (1995). On a stochastic approximation procedure based on averaging. Metrika (im Druck).

[20] Shao, Q.-M. (1993). Almost sure invariance principles for mixing sequences of random variables. Stochastic Processes Appl. 48 319–334.

[21] Stout, W. (1974). Almost sure convergence. Academic Press, New York.

[22] Walk, H. (1988). Limit behaviour of stochastic approximation processes. Statist. Decis. 6 109–128.

[23] Walk, H. (1992). Foundations of stochastic approximation. In: L. Ljung, G. Pflug und H. Walk: Stochastic Approximation and Optimization of Random Systems, DMV Seminar Blaubeuren, May 28-June 4, 1989. DMV Seminar 17. Birkhäuser, Basel, 1–51.

[24] Walk, H. und Zsidó, L. (1989). Convergence of the Robbins-Monro method for linear problems in a Banach space. J. Math. Anal. Appl. 139 152–177.