1. Introduction
In this paper the following problem is solved: To find a fixed point 
of the operator 
in other words, to find a solution 
of the equation
(1.1)
where 
is a Lipschitz continuous mapping, 
is a Hilbert space, 
is a closed convex subset. We suppose that 
exists, i.e., the fixed point set 
of 
is nonempty. Note in different particular cases of the Equation (1.1), for example, when 
the solution existence and solution uniqueness can be proved under some additional assumptions.
We separately consider two classes of mappings T: the class of weakly contractive maps and more general class of nonexpansive ones. Let us recall their definitions.
Definition 1.1. A mapping 
is said to be weakly contractive of class 
on a closed convex subset 
if there exists a continuous and increasing function 
defined on 
such that 
is positive on 
and for all
(1.2)
Remark 1.2. It follows from (1.2) that 
and in real problems an argument 
of the function 
doesn’t necessary approaches to 
obeying the condition 
(see the example in Remark 3.4).
Definition 1.3. A mapping 
is said to be nonexpansive on the closed convex subset 
if for all 
It is obvious that the class of weakly contractive maps is contained in the class of nonexpansive maps because the right-hand side of (1.2) is estimated as
(1.3)
and it contains the class of strongly contractive maps because 
with 
gives us
(1.4)
We study the following algorithm of stochastic approximation:
(1.5)
where 
is the metric projection operator from 
onto G and deterministic step-parameters 
satisfy the standard conditions:
(1.6)
The factor 
in (1.5) is an infinite-dimensional vector of random observations of the clearance operator 
at random points 
given for all 
on the same probability space 
We set
(1.7)
where 
and 
is a sequence of independent random vectors with the conditions
(1.8)
Here 
is a symbol of the mathematical expectation. In order to calculate conditional mathematical expectations of different random variables we define the 
- subalgebra 
on 
And then 
means 
function with the following property: for any 
We also assume in the sequel that 
is An-measurable for all 
Let us recall the mean square convergence and almost sure (a.s.) convergence.
We say that the sequence 
of random variables 
converges in mean square to 
if 
exists and
The sequence 
converges to 
almost surely or with probability 1 if
Almost sure convergence and convergence in mean square imply convergence in the sense of probability: The sequence 
of random variables 
converges in the sense of probability to 
if for all 
So, we consider iterative processes of stochastic approximation in the form (1.5) for finding fixed points of weakly contractive (Definition 1.1) and nonexpansive (Definition 1.3) mappings in Hilbert spaces under the conditions (1.8). We prove mean square convergence and convergence almost sure of iterative approximations and establish both asymptotic and nonasymptotic estimates of the convergence rate. Perhaps, we present here the first results of this sort for fixed point problems. Formerly the stochastic approximation methods were studied mainly to find minimal and maximal points in optimization problems (see, for example, [1-6] and references within).
2. Auxiliary Recurrent Inequalities
Lemma 2.1. [3,4] Let 
be sequences of nonnegative real numbers satisfying the recurrent inequality.
(2.1)
Assume that 
and 
Then 
is bounded and converges to some limit.
Lemma 2.2. [3,4] Let 
be sequences of nonnegative real numbers satisfying the recurrent inequality.
(2.2)
where 
and either 
or
(2.3)
Assume that 
is continuous and increasing function defined on 
such that 
is positive on
, 
Then 
There exists an infinite subsequence 
such that
where 
In the following two lemmas we want to present nonasymptotic estimates for the whole sequence 
For this the stronger requirements are made of parameters 
and function 
in the recurrent inequality.
Suppose that 
such that 
and
are antiderivatives from 
and 
respectively, with arbitrary constants 
(without loss of generality, one can put
), i.e.
Observe that 
has the following properties:
i) 
ii) 
is strictly increasing on 
and 
as 
iii) The function 
is decreasing;
iv) 
as 
Introduce the following denotations:
1) 
and 
are the inverse functions to 
and 
respectively;
2) 
is a fixed control parameter;
3) 
4) 
5) 
where
is an arbitrary fixed number;
We present now the based condition (P): The graphs of the scalar functions 
and 
with any fixed 
are intersected on the interval 
not more than at two points 
and 
(we do not consider contact points as intersection ones excepting 
if any).
For example, the graphs of the functions 
and
calculated for 
and 
satisfy the condition (P).
Lemma 2.3. [3,4] Assume that 1) the property (P) is carried out for the function 
and
2) 
as 
3) the control parameter 
is chosen such that
(2.4)
Then for the sequence 
generated by the inequality
(2.5)
it follows: 
and for all 
(2.6)
Lemma 2.4. [3,4] Assume that 1) the property (P) is carried out for all the function 
and 
2) 
as 
Then for the sequence 
generated by the inequality (2.5) 
In additiona) if 
and the control parameter 
is chosen such that 
as 
then for all 
(2.7)
b) in all remaining cases
(2.8)
(2.9)
where 
is a unique root of the equation
(2.10)
on the interval
.
The following lemmas deal with another sort of recurrent inequalities:
Lemma 2.5. [7,8] Let 
be sequences of non-negative real numbers satisfying the recurrence inequality.
(2.11)
Assume that
Then:
i) There exists an infinite subsequence 
such that
(2.12)
and, consequently, 
ii) if 
and there exists 
such that
(2.13)
for all
, then 
Lemma 2.6. [7,8] Let 
be sequences of non-negative real numbers satisfying the recurrence inequality (2.11). Assume that 
and (2.3) is satisfied. Then there exists an infinite subsequence 
such that 
3. Mean Square Convergence of Stochastic Approximations
Theorem 3.1. Assume that 
is a weakly contractive mapping of the class 
is a convex function with respect to 
and
Then the sequence 
generated by (1.5)-(1.7) converges in mean square to a unique fixed point 
of 
There exists an infinite subsequence 
such that
(3.1)
where 
and some positive constant 
satisfies the inequality
(3.2)
Remark 3.2. 
exists in view of the second condition in (1.6).
Proof. First of all, we note that the method (1.5)-(1.7) guarantees inclusion 
for all 
Since the metric projection operator 
is nonexpansive in a Hilbert space and 
exists, we can write
(3.3)
Let us evaluate the first scalar product in (3.3). We have
(3.4)
We remember that 
Then the inequalities (3.3) and (3.4) yield
(3.5)
Applying the conditional expectation with respect to 
to the both sides of (3.5) we obtain
(3.6)
It is easy to see that
(3.7)
Since 
is weakly contractive and therefore nonexpansive, one gets
Taking into account (3.7), the inequality (3.9) is estimated as follows:
(3.8)
Now the unconditional expectation implies
(3.9)
Next we need the Jensen inequality for a convex function 
(see [9,10]). This allows us to rewrite (3.9) in the form
(3.10)
because of
Denoting 
we have
(3.11)
where in view of Definition 1.1, 
is a continuous and increasing function with 
Due to (6), from Lemma 2.2 it follows
and the estimate (3.1) holds too. The theorem is proved. □
Remark 3.3. If a fixed point of weakly contractive mapping 
exists, then it is unique [11].
Remark 3.4. The following example was presented in [11]: Let 
and 
It has been shown in [11] that
for all 
Then
Definition 3.5. Let a nonexpansive mapping
have a unique fixed point
. T is said to be weakly sub-contractive on the closed convex subset 
if there exists continuous and increasing function 
defined on 
such that 
is positive on
, 
, 
such that for all
.
(3.12)
Theorem 3.6. Assume that a mapping 
is weakly sub-contractive and the function 
in (3.12) is convex on 
Then the results of Theorem 3.1 holds for the sequence 
generated by (1.5)-(1.7).
The second inequality in (1.6) can be omitted if we assume not less than linear growth of 
“on infinity” and put 
as 
Theorem 3.7. Assume that a mapping 
is weakly sub-contractive and the function 
in (3.12) is convex on 
Suppose that instead of (1.6) the conditions
(3.13)
hold. In addition, let 
and
(3.14)
Then the sequence 
generated by (1.5), (1.7) and (3.13) converges in mean square to 
There exists an infinite subsequence 
such that
where
(3.15)
Proof. Consider the inequality ( 11) in the form
(3.16)
where 
Observe that it is derived by making use of (3.4) and the nonexpansivity property of 
We shall show that 
are bounded for all 
Indeed, since 
is a convex increasing continuous function, we conclude that
is nondecreasing and since (3.14) holdsthe inequality 
has a solution 
where 
is the unique root of the scalar equ0 ation 
Together with this, (3.4) and (3.14) are co-ordinated by the parameter 
Only one alternative can happen for each 
either
or
Denote 
and
. It is clear that 
From the hypothesis 
it arises
and then 
for all 
From the hypothesis 
we have: 
for all 
Consider all the possible cases:
1) 
Then 
for all 
2) 
Then 
for all 
3) Let 
and 
Then 
for 
By (3.16), 
It is obvious that 
for 
Therefore, 
for all 
4) Let 
and 
Then 
for 
and 
for 
Thus, 
for all 
5) Let 
and 
be unbounded sets. Consider an arbitrary interval
where 
It is easy to be sure that 
and 
for all 
6) The other situations of bounded and unbounded sets 
and 
are covered by the items 1)-5). Consequently, we have the final result: 
for all 
Thus, we obtain the inequality
(3.17)
where 
is defined by (3.15). Now Lemma 2.2 with the condition (2.3) implies the result. □
Remark 3.8. For a linear function 
which is convex and concave at the same time we suppose 
Remark 3.9. If 
is bounded or more generally 
is bounded, then the inequality (3.17) (with some different constant
) immediately follows from (3.16).
4. Estimates of the Mean Square Convergence Rate
Using Lemmas 2.3 and 2.4 we are able to give two general theorems on the nonasymptotic estimates of the mean square convergence rate for sequence 
generated by the stochastic approximation algorithm (1.5)- (1.7).
Again we introduce denotations 1)-5) from Section 2 induced now by the recurrent inequality (3.11):
1) 
and 
are the inverse functions to 
and 
respectively;
2) 
is a fixed control parameter;
3) 
4) 
5) 
Introduce also the basic condition (P).
Theorem 4.1. Assume that all the conditions of Theorem 3.1 are fulfiled and i) the condition (P) holds for the functions
and 
ii) 
as 
iii) 
is chosen such that 
as 
Then the sequence 
generated by (1.5)-(1.7) converges in average to a unique fixed point 
of 
and for all 
(4.1)
Theorem 4.2. Assume that all the conditions of Theorem 3.1 are fulfiled and i) the condition (P) holds for the functions 
and 
with any fixed 
ii) 
as 
iii) If 
and 
is chosen such that 
as 
then the sequence 
generated by (1.5)-(1.7) converges in average to a unique fixed point 
of 
and for all 
(4.2)
iv) In all the remaining cases, (4.1) holds for 
and (4.2) for 
where 
is a unique root of the equation 
on the interval
.
Let us provide the examples of functions 
and 
suitable for Theorems 4.1 and 4.2 (see [12,13]).
1) Below in Corollaries 4.3-4.6 we use the functions 
with 
For them
(4.3)
and
(4.4)
2) If 
then
3) If 
then
4) If 
then
In this example we are unable to define 
in analitical form, therefore suggest to calculate it numerically by computer.
We next present very important corollaries from Theorems 4.1 and 4.2, where their assumptions automatically guarantee accomplishment of the condition (P) (see [4]). The functions 
coincide with the point 1) above.
Corollary 4.3. Assume that 
is a strongly contractive mapping, that is, (1.4) is satisfied with
Let in (1.5) 
Then
I. Suppose that 
and 
Then
and 1) If 
and 
we have for all 
(4.5)
2) In all the remain cases
(4.6)
and
(4.7)
where 
is a unique root of the equation
on the interval
.
II. Suppose that 
and 
Then 
and the estimate (4.6) holds for all 
Corollary 4.4. Assume that 
is a strongly contractive mapping, that is, in (1.4) is satisfied with
Let in (1.5) 
Then
Suppose that 
Then 
and 1) If 
and 
we have for all
(4.8)
2) In all the remain cases the estimates (4.6) and (4.7) hold.
Corollary 4.5. Assume that 
is a weakly contractive mapping of the class 
that is, in Theorem 3.1 
Let in (1.5)
Then
If 
is chosen from the condition
then 
and for all 
(4.9)
Corollary 4.6. Assume that 
is a weakly contractive mapping of the class 
that is, in Theorem 3.1 
Let in (1.5)
Then
I. Suppose that
1) If 
and 
is chosen from the condition
then 
and for all 
(4.10)
2) In all the remain cases the estimates (4.6) and (4.7) hold.
II. Suppose that
If 
is chosen from the condition
then 
and for all 
(4.11)
In addition to the examples presented in this section, we produce the functions 
and 
which have 
as a tangency point of the infinite degree multiplicity and given logarithmic estimates of the convergence rate.
We define the function 
by the following way:
where 
is differentiable and decreasing function,
and
where 
denote the derivative degrees of the function
It is easy to see that
and
In particulari) 
We have
and 
We have to verify that 
is convex. In fact, it is true because
Beside this, it is easy to see that 
at least, on the interval
. In the next examples we leave to readers to check these properties.
ii) 
We have 
and 
iii) 
We have
and 
5. Almost Sure Convergence of Stochastic Approximations for Nonexpansive Mappings
Consider next the almost surely convergence of stochastic approximations. First of all, we need the stochastic analogy of Lemma 2.5:
Lemma 5.1. Let 
be sequences of non-negative real numbers and 
be sequence of random 
measurable variables, a.s. nonnegative for all 
Assume that
If 
and there exists 
such that for all
(5.1)
then 
a.s.
The proof can be provided by the scheme of nonstochastic case (see Proposition 2 in [8]) or as it was done in [5].
We need also the following lemma from [14] as applied to our case of Hilbert spaces (the concepts of modulus of convexity 
of Banach spaces B or Hilbert spaces 
can be found in [15] and [16]).
Lemma 5.2. If 
with a nonexpansive mapping 
then for all 
where
If 
and 
with 
then 
and
Theorem 5.3. Assume that a mapping 
is nonexpansive and its fixed point set 
is nonempty. If
(1.8) holds and 
then the sequence
generated by (1.5)-(1.7) weakly almost surely converges to some 
Proof. Let 
We next use Lemma 5.2 and the estimate (see [17], p. 49)
to get
In this case the inequality (3.3) implies
(5.2)
Similarly to (3.10), we have
(5.3)
Denote 
and 
and apply the unconditional expectation to both sides of (5.3). Then
(5.4)
It follows from this that
Since 
and due to Lemma 2.1, we conclude that 
is bounded. Consequently, 
is bounded a.s. that follows from the theory of convergent quasimartingales (see [5,18]).
We now need Lemma 5.1. It is not difficult to see that
(5.5)
The last gives us
Next we evaluate the following difference:
It is easy to see that 
is bounded a.s. Indeed, since 
a.s., there exists a constant 
such that
Therefore
It is obviously that
Thus,
By Lemma 5.1, 
a.s. as 
Since 
is bounded a.s., there is a subsequence 
weakly convergent to some point 
Since 
is convex and closed, consequently, weakly closed, we assert that 
It is known that a nonexpansive mapping 
is weakly demiclosed, therefore, 
a.s. Weak almost surely convergence of whole sequence 
is shown by the standard way [8]. □
Corollary 5.4. Assume that 
is a weakly contractive mapping of the class 
If 
and 
then the sequence
generated by (1.5)-(1.7) strongly almost surely converges to unique fixed point 
of 
Proof. We have from (3.4)
(5.6)
Since 
is bounded a.s. and 
a.s.
as 
we conclude that 
a.s.
The proof follows due to the properties of the function 
□
Remark 5.5. It is clear that all the results remain still valid for self-mappings 
However, in this case, unlike any deterministic situation, the algorithm (1.5)-(1.7) must use the projection operator 
because the vector 
not always belongs to G. If 
for all 
and 
then (1.5) can be replaced by
