On the Robbins–Monro Procedure in the Case of Several Roots

T. P. Krasulina

Teoriâ veroâtnostej i ee primeneniâ, Tome 12 (1967) no. 2, pp. 386-390

Résumé

Let $Y(x)$ be a family of random variables with distribution functions $H(y\mid x)$ and regression function $M(x)$. In this paper the Robbins–Monro procedure is considered $$ X_{n+1}=X_n+a\operatorname{sgn}(\alpha-Y(X_n)) $$ where $X_1$ is an arbitrary number and $a$ is some positive number. It is assumed that the equation $M(x)=\alpha$ has several roots. Suppose that \begin{gather*} \mathbf P(Y(X_n)>\alpha\mid X_n,M(Xn)>\alpha)\ge\frac12+\min(\zeta,\zeta|\alpha-M(X_n)|), \\ \mathbf P(Y(X_n)<\alpha\mid X_n,M(Xn)<\alpha)\ge\frac12+\min(\zeta,\zeta|\alpha-M(X_n)|) \end{gather*} Let the following conditions be satisfied \begin{gather*} |M(x)-\alpha|>K\rho(X,\Theta_1)^s,\quad\rho(X,\Theta_1)\le\tau, \\ |M(x)-\alpha|>M\quad\rho(X,\Theta_1)>\tau. \end{gather*} Then for any $\varepsilon>0$ $$ \limsup_{n\to\infty}\mathbf P(\rho(X_n,\theta)>\varepsilon)\le\eta(a),\quad\eta(a)\to0,\quad a\to0, $$ where $\rho(X_n,\Theta)=\inf\limits_{\theta_i\in\Theta}|X_n-\theta_i|$ and $\Theta$ is the set of roots of the the regression function in which it decreases.