Deviation inequalities for stochastic approximation by averaging

A large amount of probability inequalities under dependence may be found in the literature, see [13] and more recently [15], [17] as well as in [24], [25], [6], [7], [11], or [12]. Many papers involve inequalities for Markov chains and recent martingale based techniques provide reasonable ones for contractive Markov chains as in [8]; such contractive Markov chains are weakly dependent. The above references mainly correspond to the time homogeneous contractive cases, and we aim at proving results for time non-homogeneous Markov chains. This is the setting of the large class of models introduced in Section 1.1. Different situations of stochastic algorithms [19] and unit roots [20] correspond to such varying contraction coefficients tending either to 0 or to 1 as n . Several relevant models fitting such conditions are considered in Section 1.2.