Soumaya Idriss

Nabil Lasmar
email: nabillasmar@yahoo.fr

Limit Theorems for Stochastic Approximations Algorithms With Application to General Urn Models

. We give also application of these limit Theorem for some class of urn models proving the efficiency of this method.

Introduction

The Stochastic Approximation Algorithms

A stochastic approximation algorithm (SAA) is a sequence pX n q ně0 of an R d ´valued random vector pd ě 1q, defined on some probability space `Ω, F , P ˘by the following recursion:

X n`1 " X n `1{γ n`1 hpX n q (1)
where pγ n q ně1 is a real sequence and h : R d ÝÑ R d is called a drift function. The one dimensional (SAA) was first introduced by Robbins and Monroe [START_REF] Robbins | A Stochastic Approximation Method[END_REF] where they considered γ n as a sequence of positive constants such that ÿ ně1 1{γ n " 8 and ÿ ně1 1{γ 2 n ă 8, they also viewed h as a monotonous function. Their aim was to find the zero θ of the function h which was assumed to be ă 0 for x ă θ and hpxq ą 0 for x ą θ. Blum [Blu54] proved the almost sure convergence of X n to θ under suitable conditions. Several studies on (SAA) were exhibited, most of them deal with the fluctuation of the stochastic approximation procedure around the equilibrium point. For instance, Chung who was the first to provide a central limit Theorem for the sequence X n ´θ [START_REF] Chung | On a stochastic approximation method[END_REF] resorting to the method of moments, where X n is a real valued process. Due to some complications arising from the us of the moments' method, Chung's work was simplified by both Sacks [START_REF] Sacks | Asymptotic distribution of stochastic approximation procedures[END_REF]and Fabian [START_REF] Fabian | On asymptotic normality in stochastic approximation[END_REF] and was generalized to a multidimensional version of CLT. The standard adapted conditions state that the function h should be a smooth function and that all eigenvalues of ∇hpθq are to be with real parts ě 1 2 . The case where those eigenvalues are with real parts ă 1 2 was investigated by Major and Révész [START_REF] Major | A limit theorem for the robbins-monro approximation[END_REF] in the one dimensional case, following Blums' [START_REF] Blum | Approximation methods which converge with probability one[END_REF] conditions and using Sack's ideas. In this paper, relying on Renluund's one dimensional version of the (SAA), we exhibit a multidimensional (SAA) in order to provide the d-dimensional extensions of the limit Theorems found in [START_REF] Major | A limit theorem for the robbins-monro approximation[END_REF] and that by relaxing some of the conditions required in [START_REF] Fabian | On asymptotic normality in stochastic approximation[END_REF][START_REF] Renlund | Limit theorems for stochastic approximation algorithms[END_REF].

Definition 1. A multivariate stochastic approximation algorithm pZ n q ně0 is a stochastic process on some probability space pΩ, F , P q taking values in the cube r0, 1s d and adapted to a filtration pF n q ně0 and satisfying

Z n`1 " Z n `1{γ n`1 `hpZ n q `Yn`1 ˘, ( 2
)
where Y n , γ n P F n , h : r0, 1s d ÝÑ R d and the following conditions holds almost surely:

pS1q c ℓ {n ď 1{γ n ď c u {n, pS 2 q › › Y n › › 2 ď K Y , pS 3 q › › hpZ n q › › 2 ď K f , pS 4 q › › E `γn`1 Y n`1 ˇˇF n ˘}2 ď K e {n 2
where c ℓ , c u , K f , K e , K y are positive constants and denoting be } } 2 the Euclidian norm in R d .

The process pY n`1 q ně0 called the noise of (SAA) and is broadly assumed to be a martingale difference sequence (meaning E `Yn`1 ˇˇF n ˘" 0), that is Y n`1 is uncorrelated with the past of the process. Among methods to find zeros of the drift function h is the ordinary differential method (o.d.e method). This method consists to find the stable equilibrium points of the ordinary differential equation x 1 " hpxptqq Recall that the Euler method (deterministic) for numerical approximation of the trajectory of x 1 ptq " hpxptqq would be establishing the following discrimination Z n`1 " Z n `1{γhpZ n q with γ ą 0. The difference with the stochastic algorithms is that the time scale γ is replaced by a time varying step size γ n`1 , in addition, the presence of the noise Y n`1 . In the literature we found criteria of the existence of limit points of pZ n q ně using the differential equation method. Theses methods impose conditions on h, γ n , for example we have a version of almost sure convergence given by [START_REF] Duflo | Random Iterative Models[END_REF][START_REF] Laruelle | Randomized urn models revisited using stochastic approximation[END_REF] Theorem 1. Consider the stochastic approximation algorithm pZ n q ně0 on r0, 1s d Z n`1 " Z n `1{γ n`1 ´hpZ n q `Yn`1 where h : R d ÝÑ R d differentiable function, pY n`1 q ně0 is a martingale difference with respect with the filtration pF n q ně0 , pγ n q ně0 is a sequence of positive random variables pF n q ´measurable and satisfying the constraining conditions ÿ ně0 1{γ n " 8 and ÿ ně0 1{γ 2 n ă 8 almost surely.

(3)

Then the set of adherence values Θ 8 of pZ n q ně0 is a connected compact, and left stable by the flow of the ordinary differential equation 9 Θ " ´hpΘq. Furthermore if Θ ˚is a uniformly stable equilibrium on Θ 8 then Z n ÝÑ Θ ˚almost surely.

General urn Models

The general Pólya urn model (GPU) is a discrete time process with reinforcement defined as follow: an urn containing initially say T 0 balls of different colors, fix the number of colors to be an integer d ě 2. The (GPU) amounts to drawing a sample of m ě 1 balls from the urn at each discrete epoch of time , that is among m sampled balls, one has ξ piq balls of color i, i P t1, . . . , du. At the n th draw we observe the sample and then put back the balls in the urn according to a replacement rule, determined by a mapping R defined on the simplex

Σ pdq m " pv 1 , . . . , v d q P N d , d ÿ j"1 v j " m (
and taking values in Z d (meaning that the balls are to be added as well as to be removed). To ensure the durability of the process, that is regardless of the substraction of balls the urn is never empty. In other terms, the process never dies, we impose conditions (generally sufficient),on the replacement rule and on the initial composition of the urn called tenability conditions . See for example [START_REF] Konzem | Characterization and enumeration of certain classes of tenable pólya urns grown by drawing multisets of balls[END_REF] for the concept of tenability for linear urn models. Let us denote by ζ n " pξ p1q n , . . . , ξ pdq n q the vector composition of the drawing balls at the stage n, each component, i say, correspond to the number of drawn balls of color i. We denote also by M n " pX p1q n , . . . , X pdq n q the vector composition of the urn, and by T n the total number of balls in the urn, both after n draws. Therefore the evolution of the urn is determined by the following recursion:

M n`1 " M n `Rpζ n`1 q.
(4)

If pF n q ně0 designate the σ-field generated by the first n draws then, given pF n q, ζ n follows a multivariate hypergeometric distribution. Note that in the with-replacement case, one has

P `ζn`1 " pv 1 , . . . , v d q ˇˇF n ˘" 1 `Tn m ˘d ź i"1 ˆM piq n v i ˙,
while in the without-replacement case,

P `ζn`1 " pv 1 , . . . , v d q ˇˇF n ˘" ˆm v 1 , . . . , v d ˙d ź i"1 `Zpiq n ˘vi ,
where Z piq n :"

M piq n
T n refers to the proportion of the i-th color in the urn after n draws.

Several studies on one draw urn models used the method of Athreya and Karlin [START_REF] Athreya | Embedding of urn schemes into continuous time markov branching processes and related limit theorems[END_REF] and this method consist to embed the process into a continuous time Markov branching process. This process is determined by the same data of the urn and each ball of type i lives an exponentially distributed with mean 1 and when it dies it is replaced by r ij balls of type j. Janson [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF] developed this method for multi-type urn model when the replacement matrix is irreducible, that is every color is dominant [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF] in the following sense: it is possible to find balls of any type in the urn beginning with balls of an appropriate type.

A General Urn Model Viewed as a Stochastic Approximation Algorithm

Among recursive model with reinforcement we can adapt stochastic approximation algorithm to urn model by considering Z n as the normalized vector proportion of the number of balls of each color after n draws divided by the total number of balls. For the multicolored urn with replacement mapping R the proportion of balls Z n is solution of the following (SAA) [LMS16]

Z n`1 " Z n `1{T n`1 phpZ n q `∆M n`1 `ǫn`1 q
where the drift function h is given by

hpxq " ÿ νPΣ pdq n ˆm ν 1 , . . . , ν d ˙d ź i"1
x νi i pRpvq ´rpvqxq

with ∆M n`1 " Y n`1 ´E`Y n`1 ˇˇF n ˘where Y n`1 " Rpζ n`1 ´rpζ n`1 qqZ n .
The error term ǫ n`1 vanishes if the urn is with replacement but in any cases it has an order of O `1{T n`1 ˘. The tenability conditions dos not always guarantee the assumption 0 ă c 1 ď T n {n ď c 2 . For example the two colors urn with replacement matrix R " ˆ´1 2 1 ´2 ˙with initial composition p1, 0q is tenable and we have T n " Op1q. For that we impose additional assumptions such as lim inf T n {n ą 0. The last condition is unaffectedly realized if we suppose for example that }Rpvq} 1 :"

d ÿ j"1 R j pvq ě 1 for every v P Σ pdq m .
Higueras et al [START_REF] Higueras | Urn models and differential algebraic equations[END_REF][START_REF] Higueras | Central limit theorems for generalized polya urn models[END_REF] showed that the urn composition can be written as a (SAA) under some extra assumptions including the balance condition. Laruelle and Pages [START_REF] Laruelle | Randomized urn models revisited using stochastic approximation[END_REF][START_REF] Laruelle | Nonlinear Randomized Urn Models: a Stochastic Approximation Viewpoint[END_REF]studied the response-adaptive randomized process in clinical trials based on the randomized urn model yet studied by Bai and Hu [START_REF] Bai | Asymptotic theorems for urn models with nonhomogeneous generating matrices[END_REF][START_REF] Bai | Asymptotics in randomized urn models[END_REF].

Noticing that such model evolves with a time-depend replacement rule but converging almost surely to a stochastic matrix. Moreover in Laruelle and Pages in [START_REF] Laruelle | Nonlinear Randomized Urn Models: a Stochastic Approximation Viewpoint[END_REF] investigated the weighted urn witch the drawing rule is no longer uniform among the balls of the urn but the conditional probability of drawing a ball at time n is an empirical ratio of a function of the proportions of each color and this function is chosen generally with regular variation. They derives the almost sure convergence and the asymptotic normality of the vector composition of ball by allying stochastic approximations corresponding Theorems [START_REF] Duflo | Random Iterative Models[END_REF]. In order to reduce assumption in [START_REF] Laruelle | Randomized urn models revisited using stochastic approximation[END_REF] Zhang [START_REF] Zhang | Central limit theorems of a recursive stochastic algorithm with applications to adaptive designs[END_REF] presented a new central limit theorem for (SAA) by imposing assumptions on the error term. Renlund [START_REF] Renlund | Generalized pólya urns via stochastic approximation[END_REF][START_REF] Renlund | Limit theorems for stochastic approximation algorithms[END_REF] applied results of one dimensional stochastic algorithms to the two colors urn with one or two draws by reducing Fabian's limit Theorems [START_REF] Fabian | On asymptotic normality in stochastic approximation[END_REF] into one dimensional process.

Main Assumptions

Our basic assumptions are as follows:

(A1) h admits an unique stable equilibrium point Θ P r0, 1s d such that }Θ} 1 " 1.

(A2) h is smooth and all the eigenvalues of ∇hpΘq are within the region Repzq ą 0 ( .

(A3) There exist a zero Θ of h such that Z n ÝÑ Θ almost surely and there exist a real γ ą 0 such that

n{γ n " 1{γ `O`} Z n ´Θ} 2 `1{n ˘. (5)
We shall also impose the following additional assumptions on the martingale difference pY n q ně0 (A4) The Lindeberg's condition: for every ǫ ą 0

lim nÝÑ8 E `}Y n } 2 2 ½ }Yn}2ąǫ ˘" 0.
(A5) There exist a deterministic matrix Σ Y ‰ 0 such that lim

nÝÑ8 E `Yn Y 1 n ˇˇF n´1 ˘" Σ Y .
The Assumption (A3) has been used by Renlund [START_REF] Renlund | Limit theorems for stochastic approximation algorithms[END_REF] and this assumption is satisfied by manly urn models as balanced urn. Another example is the following when the replacement mapping is an invertible matrix (and in particular irreducible).

Example

Assume that R is a d ˆd invertible matrix. Then by the relation 1 we obtain

R ´1M n`1 ´R´1 M n " ζ n`1 . If Z n " M n T n converges to Θ then, d ÿ j"1 " R ´1Z n ‰ i " p1{T n q d ÿ j"1 " R ´1Z 0 ‰ i `mn{T n
where m ě 1 represents the number of drawn balls. Hence

mn{T n ´d ÿ j"1 " R ´1Θ ‰ i " d ÿ j"1 " R ´1`Z n ´Θ˘‰ i `O`1 {n ˘.
The condition (A1) dismiss the case of the convergence of the process to a non equilibrium point: If the conditions of Theorem 1 are satisfied and Θ is the unique stable zero of h then most Theorems of the limit in distribution give results on the fluctuation of Z n ´Θ. For the general urn models, the set of equilibrium points, if it exists, is generally known. In the next example that, we present an urn models for which we compute the set of stable zeros of the drift function h.

Example

Consider an irreducible and multicolored urn with replacement matrix R " pr ij q d i,j"1 such that for i ‰ j we have r ij ě 0. Here irreducibility of the urn refers to the replacement matrix being irreducible [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF], that is every color is a dominant one in the following sense: there exists n P N ˚such that after n draws, all the colors are accounted for in the urn. Perron Froebenius theory states that for large α, since the matrix R `αI d is positive, R has a largest real eigenvalue λ 1 such that, for all λ P sppRqztλ 1 u, we have Repλq ă λ 1 . We assume in the lines of this example that λ 1 ą 0. The drift function of the associated stochastic process is given by hpXq " RX ´|RX| 1 X where |X| 1 is the trace of the vector X.

(a) If λ 1 is simple and if V 1 denotes an eigenvector associated to λ 1 , with positive entries. It is easy to show that

Θ " V 1 |V 1 | 1
is a zero of h and is an isolated point in the set of zeros of h belonging in the affine hyperplane

H 1 " x " px 1 , . . . , x d q P R d , x 1 `. . . `xd " 1u.
Regardless of the other zeros of h, we prove that Θ is the unique stable equilibrium point of h. In fact, if we set A " ∇hpΘq then AH " pR ´λ1 I d qH ´|RH| 1 Θ. In particular ´λ1 is an eigenvalue of A with associated eigenvector ´Θ. Let us write R d " RΘ ' E d´1 where E d´1 is stable by A and let X P E d´1 an eigenvector of A associated to an eigenvalue µ ‰ ´λ1 . Then pR ´pλ 1 `µqI d qX " 0. Hence we have µ `λ1 P sppRqztλ 1 u. Therefore, Repµq ă 0. Since the set of stable zeros of h is connected, the result follows.

(b) If λ 1 is multiple, the set of zeros of h located on H 1 defined above is Zphq " kerpR ´λ1 I d q X H 1 . We show here that Zphq is exactly the set of the stable equilibrium of h: For fixed Θ " pθ 1 , . . . , θ d q P Zphq we have ∇hpΘq " R ´λ1 I d ´QΘ where Q Θ is the matrix with rank 1 with entries

" Q Θ ‰ ij " θ i |Re j | 1
where pe 1 , . . . , e d q denotes the canonical basis of R d . From the relation

d ÿ i"1 |Re i | 1 θ i " λ 1
we deduce that Θ is an eigenvector of Q Θ associate to λ 1 . Let P Θ a transition matrix of Q Θ , then the projection of P ´1 Θ ∇hpΘqP Θ on kerpQ Θ q is equal to R 1 ´λ1 I d´1 where R 1 is the pd ´1q ˆpd ´1q matrix given by

P ´1 Θ RP Θ " ˆλ1 0 0 R 1 ˙.
It is clear by this transformation that all the eigenvalues of ∇hpΘq are with real part ă 0.

Notations

For x " px i q i"1,...,d P R d , }x} 2 denotes the canonical Euclidian norm of the vector x, }x} 1 "

d ÿ i"1
x i the trace of

x. We also use the notation }A} 2 for an algebraic norm of the matrix A P M d pRq. sppAq defines the set of the eigenvalues of A. For a differentiable function h " ph 1 , . . . , h d q, we denote by ∇hpΘq its jacobian matrix with entries pB{Bx j h i pΘqq d i,j"1 where Θ is a zero of h. The matrix Γ " 1{γ∇hpΘq and its eigenvalues will play a essential role in this paper. The eigenvalues of ∇hpΘq are in the following order Repλ 1 q ě . . . Repλ r1 q ě γ{2 ą Repλ r1`1 q ě . . . Repλ r q.

since ∇hpθq is assumed o be diagonalizable over C we obtain the decomposition

C d " ' λPspp∇hpΘqq kerp∇hpΘq ´λI d q.
Let for λ P spp∇hpΘq, spλq be the dimension of kerp∇hpΘq ´λI d q and V 1 pλq, . . . , V s λ pλq the eigenvectors of ∇hpΘq generating the eigenspace kerp∇hpΘq ´λI d q. Define the corresponding real subspace F λ as follow: F λ " kerp∇hpΘq ´λI d q if this latter eigenspace is real and we set v 1 pλq " V 1 pλq, . . . v s λ pλq " V s λ pλq. Otherwise we let F λ the subspace of R d generated by the family of vectors pv i pλqq 2s λ i"1 as follow:

v 2i pλq " 1{2 `Vi pλq `V i pλq ˘and v 2i´1 pλq " 1{2i `Vi pλq ´V i pλq ˘.
We have a decomposition of R d into a direct sum

R d " ' λPspp∇hpΘqq F λ
and the projection of ∇hpΘq in the new basis is real and diagonal by blocks . Let P 1 the transition matrix of ∇hpΘq corresponding to this decomposition. Then P ´1 1 ΓP 1 is diagonal by blocks in the following form

P ´1 1 ΓP 1 " ¨Γpλ 1 q . . . Γpλ r q ‹ '
We let π 1 and π 2 to be the matrices of the projection on ' λ:Repλqěγ{2 F λ and ' λ:Repλqăγ{2 F λ respectively, Γ 1 "

π 1 P ´1 1 ΓP 1 and Γ 2 " π 2 P ´1 1 ΓP 1 . Then P ´1 1 ΓP 1 " ˆΓ1 0 0 Γ 2
˙and by this definition sp pΓ 1 q " tλ 1 {γ, . . . , λ r1 {γu and sp pΓ 2 q " tλ r1`1 {γ, . . . , λ r {γu.

We associate to Γ 1 (respectively Γ 2 ) the transition matrix

Q 1 (respectively Q 2 ) that diagonalizes Γ 1 (respectively Γ 2 ).
For later use, we define the sets Λ 1 " pi, jq P r1, ds 2 , Repλ i q ą γ{2 and Repλ j q ą γ{2 or if Repλ i q " γ{2 and λ j " λ i then rP Σ Y P 1 s ij " 0u, Λ 2 " pi, jq P r1, ds 2 , Repλ i q " γ{2 and λ j " λ i and rP Σ Y P 1 s ij ‰ 0u and Λ 3 " pi, jq P r1, ds 2 , Repλ i q ă γ{2 and Repλ j q ă γ{2u.

Further we define the matrix Σ P M d pRq by the entries

Σ ij " rQ ´1 1 π 1 P ´1 1 Σ Y P 1 1 ´1π 1 Q 1 1 ´1s ij γpλ i `λj ´γq ½ pi,jqPΛ1 `1 γ 2 rQ ´1 1 π 1 P ´1 1 Σ Y P 1 1 ´1π 1 Q 1 1 ´1s ij ½ pi,jqPΛ1 `rQ ´1 2 π 2 P ´1 1 Σ Y P 1 1 ´1π 2 Q 1 2 ´1s ij γpγ ´λi ´λj q ½ pi,jqPΛ3 `i, j P t1, . . . , du ˘.
Thus if Λ 3 " H then Q 1 " P and P 1 "

I d . Otherwise if Λ 1 Y Λ 2 " H then Q 2 " P and P 1 " I d .

Aim of the Paper

In the present work we give some theoretical results concerning the stochastic approximation algorithms following the definition 1 and satisfying the assumptions (A1)-(A5). Our motivation for the central limit Theorems is Sacks Theorem for triangular arrays [START_REF] Sacks | Asymptotic distribution of stochastic approximation procedures[END_REF]. For the refinement of the limit Theorems we are motivated by Major's Theorems for one dimensional stochastic approximation algorithm [START_REF] Major | A limit theorem for the robbins-monro approximation[END_REF]. These results find numerous applications in the field of randomized models with reinforcement. We improve results on pólya urns such as balanced Pólya process with irreducible replacement rule, the two colors urn with multiple drawing and refinement of limit theorems for cyclic urns.

Organization of the Paper

The paper is organized as follow: The section 2 we give the main results concerning the limit Theorems for stochastic approximation algorithms.

In section 3 deals with application to two types of urn models: the balanced Pólya process and the two colors urn with multiple drawing.

The section 4 is a preliminary section and the sections 5 and 6 are reserved to the proofs of main results. Finally we complete some examples on urns models.

Main Results

The following Theorem is an adaptation of the central limit Theorem for (SAA) of Sacks [START_REF] Sacks | Asymptotic distribution of stochastic approximation procedures[END_REF]. The adaptation consist in allowing γ n to be random instead of deterministic (A{n for some positive constant A). We also relax Fabian's central limit Theorem [START_REF] Fabian | On asymptotic normality in stochastic approximation[END_REF] of the orthogonality of transition matrix P and we do no need the positivity of Γ.

Theorem 2. Le pZ n q ně0 be a stochastic approximation algorithm according to definition 1. Assume that (A1)-(A5) holds.

1. If Repλ min q ě γ{2 and Λ 2 " H then

? n `Zn ´Θ˘D ÝÑ N `0, P ΣP 1 ˘. 2. If Λ 2 ‰ H then c n lnpnq `Zn ´Θ˘D ÝÑ N `0, P ΣP 1 ˘.
Theorem 3. Consider the stochastic approximation algorithm in definition 1. Assume that (A1),(A2) and(A3) hold. Suppose further Λ 1 Y Λ 2 " H.

If either h is linear or

Repλ min q ą 1{2Repλ max q, there exists a random variable

Z 1 in R d such that e lnpnqΓ `Zn ´Θ˘Ý Ñ Z 1 almost surely.
2. If for some j " 1, . . . , r ´1 we have 1{2Repλ j`1 q ă Repλ min q ď 1{2Repλ j q, there exists a random variable Z j P t0 d´sj u ˆRsj where s j denotes the dimension of the subspace ' r ℓ"j`1 ker `∇hpΘq ´λℓ I d ˘and such that for every 0 ă β ď Repλ min q we have almost surely

S pβq n;j `Zn ´Θ˘Ý Ñ Z j (6)
where S pβq n,j is d ˆd matrix given by the relation S pβq n,j P 1 " ¨nβ . . .

n β e lnpnqΓpλj`1q . . .

e lnpnqΓpλr q ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ' .
In the next Theorem we extend the results of Theorem 3 by giving a limit in distribution of Z n ´Θ in the case when Repλ min q ą 1{2Repλ max q. We put for N ě 1, L `" ! p P r1, ds : @ℓ " 1, . . . , N, @i 1 , . . . , i ℓ`1 P r1, ds, ÿ kě1 k λp{γ´pλi 1 `...`λi ℓ`1 q{γ `1{γ k`1 ´1{γk ˘ă 8

)

. For p P L `and any pi 1 , . . . , i ℓ`1 q P r1, ds ℓ`1 we define

ϕ p pi 1 , . . . , i ℓ`1 q " ÿ kě1 k λp{γ´pλi 1 `...`λi ℓ`1 q{γ `1{γ k`1 ´1{γk ȃnd Dppλ i1 , . . . , λ i ℓ `1q{γq " diag `ϕ1 pi 1 , . . . , i ℓ`1 q½ 1PL `, . . . , ϕ d pi 1 , . . . , i ℓ`1 q ˘½dPL `˘.
Denote by D `" pλ 1 {γ½ 1PL `, . . . , λ d {γ½ dPL `q and D ´" P ´1ΓP ´D`. Further, we set Γ `" P D `P ´1 and Γ ´" P D ´P ´1. For a complex number β we set, if it exists, p ď q such that Repλ p q ą Repβq or Repβq ą Repλ q q and if β P spp∇hpΘqq take β " λ p`1 " . . . " λ q´1 .

Theorem 4. Suppose that the stochastic approximation algorithms pZ n q ně0 given by the definition 1 satisfies the assumptions (A1)-(A5) and such that Repλ max q ă γ{2. Suppose further either h is linear or Repλ min q ą Repλ max q{2.There exists a pair of random variables Z 3 , Z 2 P R d such that ? n ´Zn ´Θ ´e´lnpnqΓ Z 3 ´Sn pN, Γ, Z 1 q ¯D ÝÑ N ´0, P ΣP 1 ´1w here N ě tRepλ max q{Repλ min qu `1 and S n pN, Γ, Z 1 q is given by the following sum

S n pN, Γ, Z 1 q " N ÿ ℓ"1 1{ℓ! ÿ i1,...,i ℓ`1 W i1 . . . W i ℓ`1 P Dppλ i1 `. . . `λi ℓ`1 q{γqP ´1D ℓ hpΘqpV i1 , . . . , V i ℓ qV i ℓ`1 `N ÿ ℓ"2 1 γℓ! d ÿ i1,...,i ℓ "1 W i1 . . . W i ℓ D n ppλ i1 `. . . `λiℓ q{γ, ΓqH pλi 1 {γ`...`λi ℓ {γq pΓqD ℓ hpΘq `Vi1 , . . . , V i ℓ ˘.
Here W 1 , . . . , W d are the complex components of the vector Z 1 in the basis of eigenvectors pV 1 , . . . , V d q. The matrices H β pΓq and D n pβ, Γq pβ P Cq are given by P ´1H β pΓqP " diag `ζp1 `β ´λ1 q, . . . , ζp1 `β ´λp q, 1, . . . , 1, 1{pλ q ´βq, . . . , 1{pλ d ´βq ȃnd In what follows we present a limit Theorem for the stochastic approximation algorithm pZ n q ně0 regardless of where the spectrum of Γ is located. We set σ " maxtRepλq, λ P spp∇hpΘqq and Repλq ă γ{2u and N " tσ{Repλ min qu `1.

P ´1D n pβ, ΓqP " diag `n´λ1 , . . . ,
Theorem 5. Consider the stochastic approximation algorithm pZ n q ně0 mentioned in definition 1. Suppose that assumptions (A1)-(A5) are satisfied. Suppose further Λ 2 " H. If Repλ min q ą σ{2 then there exists a pair of random variables Z p2q 1 and Z

p2q 2 P π 2 R d such that ? n `Zn ´Θ ´P1 ´0 , e ´lnpnqΓ2 Z p2q 2 ´e´lnpnqΓ2 S n pN, Γ 2 , Z p2q 1 q ¯1 ˘D ÝÑ N `0, P 1 ΣP 1 1 ˘.
3 Application to Urn Models

Multiple Color Balanced Pólya Process.

Consider a d-color urn for an integer d ě 2. At each discrete time step, a ball is drawn (uniformly), observe its color and then put it back in the urn together with new balls according to a replacement rule given by the d ˆd matrix R " `rij ˘1ďijďd . Denoting by M n " `M p1q n , . . . , M pdq n ˘1 the vector composition of the urn after n experiments with M 0 corresponding to the initial composition. We assume that the entries r ij ě 0 for i ‰ j and we allow to diagonal entries to be negative (meaning that we can remove balls from the urn), provided that the urn in question is tenable. This kind of urn model was investigated by many different authors with different approaches. For example, Janson [Jan04] Mailler [START_REF] Mailler | Describing the asymptotic behaviour of multicolour Pz'olya urns via smoothing systems analysis[END_REF] and Pouyanne [START_REF] Pouyanne | An algebraic approach to pólya processes[END_REF] by an algebraic approach and the theory of branching processes, Pages [START_REF] Laruelle | Randomized urn models revisited using stochastic approximation[END_REF] by using the stochastic approximation methods. The two-color balanced urn model was studied by Flajolet [START_REF] Flajolet | Analytic urns[END_REF] relying on analytic methods. In the present section we assume that the urn is irreducible and balanced with balance S ě 1. By the Perron-Frobenius theory of positive matrices R `AI d , for a large positive constant A, has a large real eigenvalue λ 1 and all the other eigenvalues are with real parts ď λ 1 . Using the terminology in [START_REF] Pouyanne | An algebraic approach to pólya processes[END_REF][START_REF] Janson | Moment convergence of balanced Pz'olya processes[END_REF] we say that the Pólya urn is large if λ 1 is simple and all other eigenvalues satisfy Repλq ě 1{2Repλ 1 q. The urn is said to be small if λ 1 is simple and for all i ě 2, Repλ i q ď 1{2Repλ 1 q. We say that the process is critically small if it is small and there exists an eigenvalue λ with real part " λ 1 {2. Theorem 6. Suppose that the urn is irreducible and R is diagonalizable over C.

If the urn is small but

Λ 2 " H, then M n ´nSV 1 ? n D ÝÑ N `0, P 1 ΣP 1 1 where Σ " ˆ1{S 2 π 1 P ´1 1 Σ Y P ´1 1 π 1 1 0 0 Q 1 WQ 1 1 ˙(7)
and W is the complex matrix with entries given by

rWs kℓ " rQ ´1 1 π 2 P ´1 1 Σ Y P 1 1 ´1π 1 2 Q 1 1 ´1s kℓ SpS ´λk ´λℓ q p2 ď k, ℓ ď dq and with Σ Y " R `1{SI d ´1{S 2 ½ b ½ ˘R1
where ½ b ½ is the matrix with entries equal to 1.

If the urn is small but

Λ 2 ‰ H then 1 a n lnpnq `Mn ´nSV 1 ˘D ÝÑ N `0, P 1 ΣP 1 1
where Σ is the matrix with ranks ď 2CardpΛ 2 q with entries

Σ ij " 1{S 2 rQ ´1 1 π 2 P ´1 1 Σ Y P 1 1 ´1π 1 2 Q 1 1 ´1s ij ½ ppi,jqPΛ2q .
3. If the urn is large then there exist a random variable Z such that e 1{S lnpnqR `Mn ´nSV 1 ˘ÝÑ Z almost surely. Furthermore we have the limit in distribution

1 ? n `Mn ´nSV 1 ´e1{S lnpnqR Z ˘D ÝÑ N `0, S 2 ΣQ 1 2
where Σ is the complex matrix

Σ " ¨π1 P ´1 1 Σ Y P 1 1 ´1π 1 1 rπ 1 P ´1 1 Σ Y P 1 1 ´1π 1 3 Q 1 2 ´1s k Sλ k rπ 1 P ´1 1 Σ Y P 1 1 ´1π 1 3 Q 1 3 ´1s k Sλ k rQ ´1 2 π 3 P ´1 1 Σ Y P 1 1 ´1π 1 3 Q 1 2 ´1s k Spλ k `λℓ ´Sq ‹ ‹ ' . ( 8
)
Noticing that the term e ´1{S lnpnqR Z is the oscillating term since if W 1 , . . . , W d are the components of Z is the basis of eigenvectors V 1 , . . . , V d we get e ´1{S lnpnqR Z "

d ÿ k"1 n ´λk {S W k V k .
The next Theorem is a limit Theorem for balanced Pólya process.

Theorem 7. Suppose that the urn is irreducible, balanced and R is diagonalizable over C and that Λ 2 " H. There exist a vector random variable Z " `0, 0, Z p3q ˘such that

1 ? n ´Mn ´nSV 1 ´P1 `0, 0, e ´lnpnqΓ2 Z 3 ˘¯D ÝÑ N `0, P 1 ΣP 1 1 ˘.

Multiple drawing Non-Balanced Two-Color Urn Model

This model is defined as follow: Starting with a two-color urn, containing initially W 0 white balls and B 0 black balls such that T 0 " W 0 `B0 ě m with m is an integer ě 1. At each stage of the process, we draw without replacement m balls from the urn and count the number of the sampled white balls (say k white balls). Then, we return the balls in the urn with a m´k white balls and b m´k black balls where a k , b k P Z, 0 ď k ď m. We denote the replacement rule by

R " ¨a0 b 0 a 1 b 1 . . . . . . a m b m ‹ ‹ ‹ ' .
We designate by W n and B n the number of white and black balls after n draws. The total number of balls of both colors will be T n " W n `Bn . The multiple drawing urn model has been originally introduced by Chen an Wei [START_REF] Chen | A new urn model[END_REF] with a k " cpm ´kq and b k " ck where c is a positive integer. They proved by the martingale theory the almost sure convergence of W n after suitable normalization to a positive random variable W 8 and showing the absolute convergence of W 8 . Chen and Kuba [START_REF] Chen | On generalized Pólya urn models[END_REF] gaves the moments of the random variable W 8 . Kuba and Sulzbach [START_REF] Kuba | On martingale tail sums in affine two-color urn models with multiple drawings[END_REF] generalized the model of Chen and Wei to a general two-color model under the affinity (EpW n`1 ˇˇF n q " a n W n `bn ) and the balance (a k `bk " σ ě 1 0 ď k ď m) conditions. Kuba and Mahmoud [KMP13] studied the limit in distribution with a k " Cpm ´kq and b k " Ck where C P N ˚and in [START_REF] Kuba | Two-color balanced affine urn models with multiple drawings[END_REF] under the affinity condition.

In this section we improve the results of [START_REF] Lasmar | Multiple drawing multi-colour urns by stochastic approximation[END_REF] for two color unbalanced urn proved using Renlund's stochastic approximation Theorems [START_REF] Renlund | Limit theorems for stochastic approximation algorithms[END_REF]. The major problem is to control the rate of convergence of the T n {n to its limit. We state by giving the tenability conditions for the model with multiple drawing m ě 2 [KS15, LMS16].

Lemma 1. Consider the urn process with initial composition pW 0 , B 0 q 1 and replacement function R. Assume that m ě 2 and we denote by a (respectively b) the greatest common divisor of ta 1 , .

h pℓq p1q ℓpℓ ´1q n ´ℓλ Z ℓ ¸D ÝÑ N ˆ0, σ 2 1 ´2λ ˙.

Preliminaries

The following lemma is a simple version of Chung's lemma [START_REF] Chung | On a stochastic approximation method[END_REF][START_REF] Major | A limit theorem for the robbins-monro approximation[END_REF] Lemma 2. Let b n be a sequence of positive numbers such that the following recursion holds

Proof. Let P be a transition matrix of M with P ´1M P " diag `λ1 , . . . , λ d ˘. Applying the relations 1 ´λℓ j " e ´λℓ {j`Op1{j 2 q n ÿ j"m

1 j " ln `n{m ˘`O `1{m ˘and n ÿ j"m 1 j 2 " Op1{mq
we obtain

P m,n " P diag `n ź j"m ´1 ´λℓ j ¯, 1 ď ℓ ď d ˘P ´1 " P diag `e´λ ℓ lnpm{nq `1 `O`p 1 m ˘˘˘P ´1 " P diag `e´λ ℓ lnpm{nq ˘P ´1`1 `O`p 1 m ˘˘" exp `´lnpm{nqM ˘`1 `O`1 {m ˘˘.
Lemma 4. If M P M d pRq is an invertible matrix and diagonalizable over C. P denotes a transition matrix of M such that P ´1M P " diag `λ1 , . . . , λ d ˘such that 1 ą Repλ 1 q ě . . . ě Repλ d q. For a complex number β we let, if it exists, a pair of positive integers p ď q such that Repλ p q ą Repβq or Repβq ą Repλ q q and if β P sppM q take β " λ p`1 " . . . " λ q´1 . Then

n ÿ j"1 1 j β`1 e lnpj{nqM " D n pβqH β `1 `Op1{nq ˘" H β pM qD n pβ, M q `1 `Op1{nq ˘(10)
where D n pβ, M q and H p β, M q are already defined in Theorem 4.

The next lemma is a version of the Bauer-Fike Theorem for matrices. This Theorem gives results on the perturbation of the spectrum of a diagonalizable complex matrices. In our current work we deal only with hermitian matrices.

Lemma 5. (Weyl's Perturbation Theorem [START_REF] Bhatia | Matrix Analysis[END_REF]) Let A and B be C dˆd hermitian matrices and let λ 1 ě λ 2 ě . . . ě λ d (respectively µ 1 ě µ 2 . . . ě µ d ) be the eigenvalues of A (respectively B). Then @j " 1, . . . , d : ˇˇλ j ´µj ˇˇď › › A ´B› › 2 . Lemma 6. Given a stochastic approximation algorithm pZ n q ně0 as defined in definition 1. Assume that the drift function h satisfies the conditions (A1),(A2) and (A3). Also we suppose that ∇hpΘq is diagonalizable over C and let P the matrix such that P ´1∇hpΘqP " diagpλ 1 , . . . , λ d q. For every ε ą 0, δ ą 0 there exists a measurable set F such that P pF q ą 1 ´δ such that if Re `λmin ˘ă γ{2 we have,

E `› › P ´1`Z n ´Θ˘› › 2 2 ˘" O `1{n 2Repλmin{γq´ε ˘, ( 11
)
where λ min is the eigenvalue of ∇hpΘq with minimal real part and if Re `λmin ˘ě γ{2 we have,

E `› › P ´1`Z n ´Θ˘› › 2 2 ˘" O `1{n 1´2ǫ ˘. ( 12
)
Proof. Putting z n " Z n ´Θ and applying Taylor expansion to h at Θ we obtain, P ´1hpZ n q " P ´1∇hpΘqz n P ´1E n pΘqz n . Denoting by Γ n " 1{γ n`1 P ´1`∇ hpΘq `En pΘq ˘P and using the mean square norm on (2)

E `}P ´1z n } 2 2 ˘ď E `› › I d ´Γn › › 2 2 }P ´1z n } 2 2 q `2E ´ ´Id ´Γn ¯P ´1z n , P ´1Y n`1 γ n`1 ¯`E `}P ´1Y n`1 {γ n`1 } 2 2 ˘, ď E ´› › ›Id ´Γn › › › 2 2 }P ´1z n } 2 2 ¯`2E ´ ´Id ´Γn ¯P ´1z n , E `P ´1Y n`1 {γ n`1 ˇˇF n ˘ ¯`c 2 K Y {n 2 , ď E `› › I d ´Γn › › › 2 2 }P ´1z n } 2 2 ˘`K 1 {n 2 . ( 13
)
where K 1 is a positive constant. The remainder P ´1E n pΘq converges almost surely to 0 then by Egoroff Theorem [START_REF] Gut | Probability: A Graduate Course[END_REF] for every ε ą 0, δ ą 0 there exists a measurable set F such that P pF q ą 1 ´δ such that uniformly on F , }E n pΘq} 2 ă ε{2. In term of eigenvectors we have uniformly on F , |λ n pΘq| ă ε{2 where λ n pΘq P sppE n pΘqq.

In the other hand, for every unite vector X in R d we have,

pI d ´Γn q X, pI d ´Γn q X " `Id ´Γn ˘`I d ´Γ1 n ˘X, X ď λ max pnq,
where λ max pnq denotes the largest eigenvalue of pI d ´Γn q `Id ´Γ1 n ˘. The last inequality is not only an increase of the Rayleigh quotient of `Id ´Γn ˘`I d ´Γ1 n ˘ [START_REF] Bhatia | Matrix Analysis[END_REF]. By Bauer-Fike Theorem for hermitian matrices (lemma 5) we have |λ max pnq ´2Repλ min q| ď }E n pΘq} 2 ď ε.

Thus on F we have uniformly, λ max pnq ě 2Repλ min q ´ε. Through this inequality, relation (13) becomes,

E `› › P ´1z n`1 › › 2 2 ˘ď ´1 ´`2Repλ min {γq ´ε˘{ n ¯E`› › P ´1z n › › 2 2 ˘`K 3 {n 2 , ( 14
)
for some positive constant K 3 . Assume that Repλ min q ě γ{2, then by the first part of Chung's lemma (lemma 2) we obtain the first bound, and if Re `λmin ˘ă γ{2 we obtain the second bound using Chung's lemma with p " 1.

Remark: Some immediate consequences of lemma 6 are:

EpZ n q " Θ `O`1 {n Repλmin´ǫ0q ˘,
for some ǫ 0 Ps0, Repλ min qr and we have the following control of the rate of convergence of Z n to its limit

Z n " Θ `O`l npnq{n Repλmin´ǫ0 ˘almost surely . ( 15
)
To prove this statement, it is enough to show it for the component Z piq n ´Θpiq , i P t1, . . . , du. By the inequality, VarpZ piq n q ď VarppZ piq n ´Θpiq q½ F q `cδ for some positive c we obtain VarpZ piq n q ď A{n Repλmin´ǫq `cδ for every ǫ ă ǫ 0 where A ě 0 and since δ is arbitrarily we get VarpZ piq n q ď A{n Repλmin´ǫ0q . Now by Kolmogorov's maximal inequality [START_REF] Longnecker | General moment and probability inequalities for the maximum partial sum[END_REF] we obtain the bound

E ´max 1ďkďn ˇˇk ÿ ℓ"1 ℓ 1{2`Repλmin´ǫ0q `Zpiq ℓ ´EpZ piq ℓ q ˘´pℓ ´1q 1{2`Repλmin´ǫ0q `Zpiq ℓ´1 ´EpZ piq ℓ´1 q ˘ˇˇ¯ď A 1 n
The last inequality allows us to apply the strong law of large numbers [START_REF] Fazekas | A general approach to the strong law of large numbers[END_REF] then,

n 1{2 lnpnqS piq n ÝÑ 0 almost surely, where S piq n " n ÿ ℓ"1 ℓ 1{2`Repλmin´ǫ0q Z piq ℓ ´pℓ ´1q 1{2`Repλmin´ǫ0q Z piq ℓ´1 .
Lemma 7. Let pΩ, F , P q a probability space. pY n q ně1 be an adapted sequence in R d such that almost surely

ÿ ně0 E `}Y n } 2 2 ˘ă 8 and ÿ ně1 › › E `Yn ˇˇF n´1 ˘› › 2 ă 8. Then ÿ ně0 Y n is almost surely convergent.
Proof. It suffice to show the convergence for one component which follows from [START_REF] Renlund | Limit theorems for stochastic approximation algorithms[END_REF].

Lemma 8. [START_REF] James | Limit theorems for correlated bernoulli random variables[END_REF] Let pX n , F n q ně1 be a sequence of bounded martingale difference. Assume that there exists a sequence of positive constants pW n q ně1 such that

W n ÝÑ 8, W n {W n`1 ÝÑ 1 and 1 W 2 n n ÿ k"1 E `X2 k ˇˇF k´1 ˘ÝÑ 1 almost surely.
Then almost surely

lim inf nÝÑ8 1 a 2W 2 n ln lnpW 2 n q n ÿ k"1 X k " ´1 and lim sup nÝÑ8 1 a 2W 2 n ln lnpW 2 n q n ÿ k"1 X k " 1.
The next lemma proposed by [START_REF] Sacks | Asymptotic distribution of stochastic approximation procedures[END_REF] is a central limit Theorem for a sum of vector valued random variables.

Lemma 9. [START_REF] Sacks | Asymptotic distribution of stochastic approximation procedures[END_REF] Let pU nk q k,ně1 a family of double array of vector random variables and U n "

ÿ kě1 U nk . Suppose that (i) E `Unk ˇˇU n1 , U n2 , . . . , U n,k´1 ˘" 0 a.s (ii) lim nÝÑ8 8 ÿ k"1 E › › ›E `Unk U 1 nk ˇˇU n1 , U n2 . . . , U n,k´1 ˘´E `Unk U 1 nk ˘› › › 2 " 0. (iii) sup ně1 ÿ kě1 E `}U nk } 2 2 ˘ă 8 (iv) For every ǫ ą 0, lim nÝÑ8 ÿ kě1 E `}U nk } 2 2 ½ `}U nk }2ąǫ ˘˘" 0. If ÿ kě1 E `Unk U 1 nk ˘ÝÑ Σ then U n is

asymptotically normal with null mean and covariance matrix Σ.

A corollary of this lemma is the following.

Corollary 1. Let pY n q ně0 be a bounded martingale difference in R d and adapted with respect to the filtration pF n q ně0 . For any invertible matrices M and P such that M is a real matrix and P ´1M P " diagpλ 1 , . . . , λ d q.

Assume that 0 ă Repλ min q ď Repλ max q ă γ{2 where λ min (resp λ max ) is the eigenvalue of M with minimal (resp maximal) real part.If pY n q ně0 satisfies the conditions (A4) and (A5) then

?
n 1´λ k ´λℓ j 2´λ k ´λℓ " P ´1EpY j Y 1 j qP 1 ´1‰ kℓ " ÿ jěn n 1´λ k ´λℓ j 2´λ k ´λℓ " P ´1`Σ Y `op1q ˘P 1 ´1‰ kℓ " " P ´1Σ Y P 1 ´1‰ 1 ´λk ´λℓ `1 `op1q ˘.
In order to prove the condition (ii) of lemma 9 we shall show that

lim nÝÑ8 E › › E `Yn Y 1 n ˇˇF n ˘´E `Yn Y 1 n ˘› › 2 " 0.
But this limit follows from Convergence dominate Theorem of Lebésgue since the terms between absolute value are uniformly bounded and we have already the assumption (A5).

Corollary 2. With the assumptions of corollary 1 but here we assume that for every λ P spp∇hpΘqq we have Repλq ě γ{2 and that Λ 2 ‰ H. Then

c n lnpnq e ´lnpnqM n ÿ j"1 e lnpjqM j Y j D ÝÑ N `0, P ΣP 1 q.
where Σ is the matrix of rank ď 2CardpΛ 2 q with entries Σ ij " "

P ´1Σ Y P 1 ´1‰ ij ½ ppi,jqPΛ2q .
Corollary 3. With the assumptions of corollary 2 but we assume that Λ 2 " H we have

? ne ´lnpnqM n ÿ j"1 e lnpjqM j Y j D ÝÑ N `0, P ΣP 1 where " Σs kℓ " " P ´1Σ Y P 1 ´1‰ kℓ λ k `λℓ ´1 .

Proof of Limit Theorems

In lieu of working with (2) directly, we consider the modified equation by application of Taylor expansion of the drift function h at point Θ. Putting z n " Z n ´Θ and expanding h at Θ, the recurrence (2) becomes

z n`1 " ´Id ´Γ n ¯zn `´1{γ n`1 ´1{pnγq ¯∇hpΘqz n `1{γ n`1 E n pΘqz n `Ŷ n`1 n `1 (16)
where E n pΘqz n is the remainder term in Taylor expansion of h and Ŷn`1

" n γ n`1 Y n`1 .
Following Major [START_REF] Major | A limit theorem for the robbins-monro approximation[END_REF] we iterate (16) from n `1 to m `m to have

z n`m`1 " n`m ź k"n`1 ´Id ´Γ k ¯zn `n`m ÿ k"n`1 n`m ź j"k`1 ´Id ´Γ j ¯´1{γ k`1 ´1{pkγq ¯∇hpΘqz k `n`m ÿ k"n`1 n`m ź j"k`1 ´Id ´Γ j ¯Ek pΘqz k γ k`1 `n`m ÿ k"n`1 n`m ź j"k`1 ´Id ´Γ j ¯Ŷ k`1 k `1 . ( 17
)
Using the asymptotic expansion in lemma 3 to get

e lnpn`mqΓ z n`m`1 " e lnpnqΓ z n `1 `Op1{nq ˘`n`m ÿ k"n`1 e lnpkqΓ ´1{γ k`1 ´1{pkγq ¯∇hpΘqz k `1 `Op1{kqq n`m ÿ k"n`1 e lnpkqΓ E k pΘqz k γ k`1 `1 `Op1{kqq ˘`n`m ÿ k"n`1 e lnpkqΓ Ŷk`1 k `1 `1 `Op1{kqq (18)

Proof of Theorem 2

Assume that all the eigenvalues of ∇hpΘq are with real parts ě γ{2. Using the expansion (18) with n " 1

? mz m`2 " ? m m`1 ÿ k"2 e lnpk{mqΓ ´1{γ k`1 ´1{pkγq ¯∇hpΘqz k `1 `Op1{kqq ?m m`1 ÿ k"2 e lnpk{mqΓ E k pΘqz k γ k`1 `1 `Op1{kqq ˘`? m m`1 ÿ k"2 e lnpk{mqΓ Ŷk`1 k `1 `1 `Op1{kqq
Since h assumed to be at least twice differentiable we have

E m pΘqz m " O `}z m } 2 2 ˘" O `}P ´1z m } 2 2 ˘.
Then by (15) we have the bound

? m{γ j`1 › › ›e lnpj{mqΓ E j pΘqz j › › › 2 ď C ? mpj{mq Repλminq 1{j 1`2Repλminq´ε " C m 1{2´Repλminq j 1`Repλminq´ε .
Thus the term

? me ´lnpm`1qΓ m`1 ÿ j"2
e lnpjqΓ E j pΘqz j γ j`1 converges to 0 with probability 1. By assumption (A3) and using the same arguments as previously done, the third term converges almost surely to 0.

The convergence in distribution of the term

? me ´lnpm`2qΓ m`1 ÿ j"2
e lnpjqΓ j Ŷj follows by corollary 3 in the case Λ 2 " H. Now assume that Λ 2 ‰ H. Using the expansion (18) and as in the proof of Theorem 2. We have already proved that the second and the third terms in the RHS of (18) with n " 1 converges almost surely to 0. By another hand

we have E ´n ÿ j"1 e lnpj{nqΓ j 2 Y j Y 1 j e lnpj{nqΓ ¯" P Σ n P 1 where Σ n is the symmetric matrix with entries

" Σ n ‰ kℓ " n ´λk {γ´λ ℓ {γ n ÿ j"1 j λ k {γ`λ ℓ {γ´2 " P ´1EpY j Y 1 j qP 1 ´1‰ kℓ " $ ' ' & ' ' % " P ´1Σ Y P 1 ´1‰ kℓ λ k {γ `λℓ {γ ´1 p1 `op1qq, if pk, ℓq P Λ 1 " P ´1Σ Y P 1 ´1‰ kℓ `lnpnq `Op1q ˘˘, if pk, ℓq P Λ 2 .
The limit in distribution of c n lnpnq n ÿ j"1 e lnpj{nqΓ j Y j follows by lemma 9 and it is too similar, in the form, to the proof of corollary1. The rest of the proof yields by Slutsky's Theorem.

Proof of Theorem 3.

Assume that Repλ min q ą 1{2Repλ max q. The sums shown in the relation (18) with n " 1 are almost surely convergent, indeed the term

m`1 ÿ k"2 e lnpkq pp1{γ k`1 ´1{γkq ∇hpΘqz k `1{γ k`1 E k pΘqz k q is convergent by condition (A3) and (15)
and the term

m`1 ÿ k"2 1{γ k`1 e lnpkqΓ Y k`1 converges by lemma 7.
Now assume that Repλ min q ď 1{2Repλ max q and we transform the relation (18) with n " 1 by multiplying each member by P ´1 1 . Let for each j " 1, . . . , r, U pjq n " π j P ´1 1 z n . The process `U pjq n ˘ně0 satisfies the following (SAA)

U pjq n`1 " ´πj ´Γpλ j q n ¯U pjq n `p1{γ n`1 ´1{nγq Γpλ j qU pjq n `1 γ n`1 π j P ´1 1 E n pΘqz n `1 n `1 π j pP ´1 1 Ŷn`1 q.
Iterating as we made with pz n q ně0 to obtain

e lnpn`1qΓpλj q U pjq n`2 " U pjq 1 `n`1 ÿ k"2 e lnpkqΓpλj q p1{γ k`1 ´1{kγq Γpλ j qU pjq k `1 `Op1{kq n`1 ÿ k"2 1{γ k`1 e lnpkqΓpλj q π j P ´1 1 E k pΘqz k `1 `Op1{kq ˘`n`1 ÿ k"2 e lnpkqΓpλj q π j P ´1 1 Ŷk`1 k `1 `1 `Op1{kq ˘.
The sum

n`1 ÿ k"2
e lnpkqΓpλr q k π j P ´1 1 Ŷk`1 is convergent by condition pS 4 q and lemma 7. Let j an index such that Repλ j q{2 ă Repλ min q ď Repλ j q. For any ℓ we have by the estimate (15) }U pℓq n } 2 2 ď 1 n 2Repλminq´ε0 and we have by the assumption (A3) and the estimate (15)

› › › ´1{γ k`1 ´1{pkγq ¯elnpkqΓpλ ℓ q Γpλ ℓ qU pℓq k › › › 2 ď C }U pℓq k z k } 2 k 1´Repλ ℓ q ď 1 k 1`Rep2λminq´Repλ ℓ q´ε0 .
for some positive constant C. Thus if ℓ ě j`1 the series

ÿ kě2 › › e lnpkqΓpλ ℓ q ´1{γ k`1 ´1{pkγq ¯Γpλ ℓ qU pℓq k › ›
2 is almost surely absolutely convergent. Similar bounds leads to the convergence of the series ÿ ně1 1{γ n`1 e lnpnqΓpλ ℓ q π ℓ P ´1 1 E n pΘqz n .

Now for ℓ ď j we have for any β ă Repλ min q;

n β e ´lnpnqΓpλ ℓ q n ÿ k"2 ´1{γ k`1 ´1{pkγq ¯elnpkqΓ ℓ Γpλ ℓ qU pℓq k " O ˆnβ´Repλ ℓ q n 2Repλminq´Repλ ℓ q´ε0
ȧnd we have also a similar estimate for the sum

n ÿ k"1 1{γ k`1 e lnpkqΓpλ ℓ q π ℓ P ´1 1 E k pΘqz k .. Let Z
pℓq 1 the limit of e ´lnpnqΓpλr q `πℓ P ´1 1 pZ n ´Θq ˘and Z j " `0, . . . , 0, Z pjq j`1 , . . . , Z pjq r ˘1 then S pβq n,j `Zn ´Θ˘c onverges almost surely to Z j .

Proof of Theorem 4

The Taylor expansion of the remainder term E n pΘqz n is given by

E n pΘqz n " N ÿ ℓ"2 1{ℓ!D ℓ hpΘqpz n , . . . , z n q `EN n pΘq
where the residue E N n pΘq is Op}z n } N `1 2 q. Plug in this relation into (18) to have the form

Q n`m " Q n `n`m ÿ k"n`1 e lnpkqΓ E N k pΘq `n`m ÿ k"n`1 e lnpkqΓ Ŷk`1 k `1 (19)
where for every n ě 1: ¨0 Γ 1 Γ 2 '. Further we let π 1 , π 2 and π 3 to be the projections on the subspaces kerpR ´SI d q, F 1 and F 2 respectively. The stochastic process z n :" P ´1 1 pZ n ´V1 q is solution of the following (SAA)

Q n " e lnpnqΓ z n `N ÿ ℓ"1 1{ℓ! n ÿ k"2 e lnpkqΓ p1{γ k`1 ´1{kγq `Dh ℓ pΘqpz k , . . . , z k qz k ˘`N ÿ ℓ"2 1{ℓ! n ÿ k"2 1{kγe lnpkqΓ Dh ℓ pΘqpz k , . . . , z k qz k " e lnpnqΓ z n `N ÿ ℓ"1 1{ℓ! n ÿ k"2 e lnpkqΓ ´p1{γ k`1 ´1{kγq `Dh ℓ pΘqpz k , . . . , z k qz k N ÿ ℓ"1 1{ℓ! n ÿ k"2 e lnpkqΓ `p1{γ k`1 ´1{kγq `Dh ℓ pΘqpz k , . . . , z k qz k ˘`N ÿ ℓ"2 1{ℓ! n ÿ k"2 1{kγe lnpkqΓ Dh ℓ pΘqpz k , . . . ,
z n`1 " pI d ´p1{nqΓ n q z n `1{pnS `T0 qP ´1 1 Y n`1 with Y n`1 " Rpζ n`1 ´Zn q and Γ n " nS T 0 `nS ¨0 Γ 1 Γ 2 '. Writing z n " pz p1q
n , z p2q n , z p3q n q where z p1q n is a real stochastic process following z p1q n`1 " z p1q n `1{pnS `T0 qπ 1 P ´1 1 Y n`1 and for i " 2, 3

z piq n`1 " pπ i ´1{npnS{pT 0 `nSqqΓ i q z piq n `1{pnS `T0 qπ i P ´1 1 Y n`1 . Applying lemma 9 to z p1q n to get ? nz p1q n D ÝÑ N `0, 1{S 2 π 1 P ´1 1 Σ Y P 1 ´1 1 π 1 1 ˘.
The process z p3q n satisfy the conditions of Theorem 3 then there exist a random vector Z 3 such that e lnpnqΓ2 z p3q n ÝÑ Z 3 almost surely. and via Theorem 4 (noticing that D 2 phq " 0)

´zp3q n ´e´lnpnqΓ2 Z 3 ¯D ÝÑ N `0, Q 2 Σ 2 Q 1 2 where Q 2 is the complex valued matrix such that Q ´1 2 Γ 2 Q 2 " diagpλ, λ P sppRq, Repλq ă S{2q and the matrix Σ 2 is given by the entries rΣ 2 s k,ℓ " rQ ´1 2 π 2 P ´1 1 Σ Y π 1 2 P 1 1 ´1Q 1 2 ´1s
S 2 p1 ´µk ´µℓ q , pµ k , µ ℓ P sppΓ 2 qq Define the process X n " ? n pz n ´sn q with s n " ´0, 0, e ´lnpnqΓ2 Z 3 ¯1 Then by the recurrence (18) we can write

X n " ÿ jě1 U nj where U nj " $ & % ? n{pSj `T0 q ´0, e lnpj{nqΓ1 π 2 P ´1 1 Y j , 0 ¯1 if j ď n ? n{pSj `T0 q ´π1 P ´1 1 Y j , 0, e lnpj{nqΓ2 π 3 P ´1 1 Y j ¯1 if j ě n `1
The Martingale difference p ? n{pSj `T0 qY j q jě0 satisfies the conditions of lemma 9, and so for the sequence `Unj ˘ně1,jě1 . If the urn is small then π 3 " 0 and by a straightforward computation as in the proof of Theorem 4 we have

Σ n :" ÿ jě1 E `Unj U 1 nj ˇˇF j´1 ˘" ˆ1{S 2 π 1 P ´1 1 Σ Y P ´1 1 π 1 1 0 0 Q 1 W n Q 1 1 ẇhere
W n is the matrix defined by the entries

rW n s kℓ " $ & % rQ ´1 1 π 2 P ´1 1 Σ Y P 1 1 ´1π 1 2 Q 1 1 ´1s kℓ S 2 pµ k `µℓ ´1q p1 `op1qq if Λ 2 " H 1{S 2 rQ ´1 1 π 2 P ´1 1 Σ Y P 1 1 ´1π 1 2 Q 1 1 ´1s kℓ `lnpnq `Op1q ˘if Λ 2 ‰ H. ( 21
)
and the parts 1 and 2 of Theorem 6 follows merely.

If the urn is large then π 2 " 0 and we have Σ n "

ÿ jě1 E `Unj U 1 nj ˇˇF j´1 ˘" Q 2 ΣQ 1 2 p1 `op1qq
where Σ is given by (8) and this complete the proof of Theorem 6.

For general urn we have Σ n "

¨1{S 2 π 1 P ´1 1 Σ Y P 1 1 ´1π 1 1 0 rπ 1 P ´1 1 Σ Y P 1 1 ´1π 1 3 Q 1 2 ´1s k S 2 p1 ´µk q 0 W n 0 rπ 1 P ´1 1 Σ Y P 1 1 ´1π 1 3 Q 1 2 ´1s k S 2 p1 ´µk q 0 rQ ´1 2 π 3 P ´1 1 Σ Y P 1 1 ´1π 1 3 Q 1 2 ´1s k S p 1 ´µk ´µℓ q ‹ ‹ ‹ ‹ '
where W n is given by ( 21) and this proves Theorem 7

Proof of Theorem 8

The number of white balls after n draws satisfies W n`1 " W n `am´ξn`1 where given F n , the σ-field generated by the first n draw, the random variable ξ n`1 has a hypergeometric distribution with parameters `m, W n {T n , T n ˘.

Lemma Furthermore we have the bound

T n {n ´w " O ´1{n n ÿ k"0 ˇˇZ k ´θˇˇ`l n lnpnq{ ? n ¯. Proof. Writing c k " a k `bk , 0 ď k ď m. We have T n " T 0 `n ÿ j"0 c m´ξj`1 " T 0 `n ÿ j"0 c m´ξj ´E `cm´ξj`1 ˇˇF j ˘`m ÿ j"0 E `cm´ξj`1 ˇˇF j ˘´w.
The sequence `cm´ξj ´E`c m´ξj`1 ˇˇF j ˘˘jě0 is a bounded martingale difference and we have

E ´`c m´ξj ´E`c m´ξj`1 ˇˇF j ˘˘2 ˇˇF j ¯" E `c2 m´ξj`1 ˇˇF j ˘´´E `cm´ξj`1 ˇˇF j ˘¯2 " m ÿ k"0 ˆk m ˙c2 m´k Z k j p1 ´Zj q m´k ´´m ÿ k"0 ˆk m ˙cm´k Z k j p1 ´Zj q m´k ¯2 `Op1{jq " m ÿ k"0 ˆk m ˙c2 m´k Z k j p1 ´Zj q m´k ´w2 `Op1{jq ": w 1 ´w2 `Op1{jq.
The lemma 8 is applicable with W n " pw 1 ´w2 qn and thus almost surely

1 n n ÿ j"0 c m´ξj`1 ´E`c m´ξj`1 ˇˇF j ˘" o `ln lnpnq{ ? n ˘.
By another hand using the inequality ˇˇˇˇm ź

k"0 x k ´m ź k"0 y k ˇˇˇˇď m ÿ k"0 ˇˇx k ´yk ˇˇsatisfied by complex numbers x k , y k , 0 ď k ď m owing the closed unit disk to get ˇˇE `cm´ξj`1 ˇˇF j ˘´w ˇˇ" ˇˇˇˇm ÿ k"0 ˆm k ˙cm´j `Zk j p1 ´Zj q m´k ´θj p1 ´θq m´j ˘ˇˇˇˇď m m ÿ k"0 ˆm k ˙cm´k ˇˇZ j ´θˇˇ.
The stochastic process Z n satisfies the conditions of the definition 1. Furthermore the conditions (A1),(A2) are satisfied. Then the part (a) and (b) follows from Theorems 2 and ??. The part (c) follows by Theorem 3 with d " 1 for the almost sure convergence and the limit in distribution by Theorem 4 with d " 1 and with H β reduced to 1{pβ ´λq.

Examples

m-ary Search Trees

Chauvin [START_REF] Chauvin | m-ary search trees when m ě 27: A strong asymptotics for the space requirements[END_REF] represented the m-ary tree as a pólya urn with m ´1 colors starting with a ball of color W 1 and where the replacement matrix is as follows,

R " ¨´1 2 ´2 3 . . . ´pm ´2q m ´1 m ´pm ´1q ‹ ‹ ‹ ‹ ‹ ' .
This urn is tenable and irreducible. The drift function h is a linear mapping given by hpXq " pR ´Im´1 qX. Assume that m ě 27 and rearrange the eigenvalues of R as follows: 1 ě Repλ 2 q ě . . . Repλ rm q ą 1{2 ą Repλ rm`1 q ą . . . Repλ m´1 q. π 1 , π 2 and π 3 will be the projections on the subspaces VectpV 1 q, F 1 and F 2 (π 1 `π2 `π3 " I m´1 .) By Theorem 6 there exists a random variable Z P R rm´1 such that almost surely e lnpnqΓ2 π 2 `Mn ´V1 ˘ÝÑ Z.

Moreover, by Theorem 7 we have the limit in distribution

? n ´Mn ´V1 ´P1 `0, e lnpnqΓ2 Z, 0 ˘1¯D ÝÑ N p0, Σq ,
where Σ is given in Theorem 7.

Cyclic Urn

A cyclic urn is an urn where balls are with m colors 0, 1 . . . m ´1 say with replacement matrix R "

¨0 1 0 0 1 1 1 0 ‹ ‹ ‹ ‹ ' .
The cyclic urn starts with one ball of an arbitrarily type. For simplicity we can suppose that we start with a ball of type 0. A ball is drawn from the urn say of color j is returned together with a ball of color j `1 modulo m. Let M n the vector composition of the urn after n draws (the components of M n constitute a random partition of 1, n `1 ). This same model used by Janson [START_REF] Janson | Congruence properties of depths in some random trees[END_REF] in order to study the asymptotic behavior of the profile modulo m of a recursive trees: For a recursive tree T with n nodes let X j pT q be the number of nodes at level j of T . We let for j " 0, . . . , m ´1, X j pT q " ÿ k"jrms X k pT q. Now let X pmq pT q " pX 0 pT q, . . . , X m´1 pT qq. Janson [START_REF] Janson | Congruence properties of depths in some random trees[END_REF] shows that the asymptotic distribution of X pmq pT q is determined by the asymptotic behavior of M n . The asymptotic in distribution of M n has been identified in Janson [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF][START_REF] Janson | Congruence properties of depths in some random trees[END_REF][START_REF] Pouyanne | Classification of large Pólya-Eggenberger urns with regard to their asymptotics[END_REF]. That is for 2 ď m ď 6, M n is asymptotically multivariate normal and for m ě 7 there is no limit in distribution since there will be oscillations (coming

Two colors urn with one draw

Now, we shall apply results of Theorem 8 to the urn with m " 1. The urn evolves with the replacement rule R " ˆa b c d ˙with c, d ě 0 and the condition minpa `b, c `dq ě 1. If pW n , B n q denotes the composition of the urn after n draws and pW 0 , B 0 q is the initial composition. Let T n be the total number of balls after n draws. We have the stochastic recurrence describing the evolution of the urn " W n`1 " W n `a½ Wn `c½ Bn " c `pa ´cq½ Wn B n`1 " W n `b½ Wn `d½ Bn " d `pb ´dq½ Wn .

(23)

The drift function of the stochastic approximation algorithm Z n " W n {T n is hpxq " S 1 x 2 ´S2 x `c where S 1 " c `d ´a ´b and S 2 " 2c ´a `d. We have hp0q " c ě 0 and hp1q " ´b ď 0. Then hpxq " 0 admits a zero θ P p0, 1q. We may suppose that S 1 ě 1 then θ " 1{2S 1 `S2 ´bS 2 2 ´4cS 1 ˘. Since minpa `b, c `dq ě 1, we have lim inf T n {n ą 0. Then the conditions of definition 1 are satisfied and we have W n {T n ÝÑ θ almost surely. By the recurrence (23) we obtain the combination pa ´cqB n ´pb ´dqW n " pcb ´adqn `Op1q and dividing by T n we get under the condition ad ‰ bc The cases θ " 0 or θ " 1 correspond to c " 0, and ad " 0 or b " 0 and ad " 0. For example, if b " d " 0 (hence a, c ě 1 then the number of blue balls is constant (" B 0 ) and W n " W n `a½ W pnq `c½ B0 pnq. Such case was studied by Janson [START_REF] Janson | Limit theorems for triangular urn schemes[END_REF] and we have by Theorem 1.5(iii) 1 a lnpnq ˆWn ´an ´c ´a a B 0 lnpnq ˙D ÝÑ N ˆ0, pc ´aq 2 a B 0 ˙.

T
The case when h 1 pθq " 0 (hence θ " c c S 1 and this means that a " d and bc " 0) corresponds to the touch point. Now assume that θ R t0, 1u and that S 2 2 ‰ 4cS 1 (hence h 1 pθq " 2S 1 θ ´S2 ă 0.) Putting w " lim T n {n and λ " pS 2 ´2S 1 θq{w and σ 2 " 1{w 2 `p1 ´θqpc ´θdq 2 `θpa ´θbq 2 ˘. We have the following

Discussion

In this paper we generalized the limit Theorems of stochastic approximation algorithms given by Robins and Revuez [START_REF] Major | A limit theorem for the robbins-monro approximation[END_REF]. We used a smooth drift function with diagonalizable jacobian matrix over C. We proved the efficiency of applying our results on General urn model by extending classical results in such field of research. We always stress on the conditions that all the eigenvalues of the jacobian matrix of the drift function are with real parts ą 0. The problem that we encountered is when the stable point is a touch point. We needed a limit Theorem in such situation. For example, in the two-color urn model with triangular replacement matrix we did not tackle the case d " a for which pd´aq{pd´a`cq is a touch point. We think that the limit Theorems of this paper can be applied to general reinforced processes such as reinforced random walks. For more elaboration see Pemantle Survey [START_REF] Pemantle | A survey of random processes with reinforcement[END_REF]. We also think that these results can be extended to infinite dimensional stochastic processes in Banach Fields such as infinite reinforced urn model. A natural question arising these results is to find the distribution of the random variables Z 1 , Z 2 in Theorems 4 and 5, their moments, the continuity. . .

  b n`1 ď ´1 ´c{n ¯bn `V {n 1`p with c, p ą 0 and V ą 0. If c ą p then b n " O `1{n p ˘and if p " 1 with 0 ă c ă 1 then b n " O `1{n c ˘. Lemma 3. Let M P M d pRq be a diagonalizable matrix over C.If P m,n denotes the product

such that ln 2 pnq n ˆWn ´a2 n c lnpnq ´a2 n lnplnpnqq c ln 2

 2 the previous case was treated by Pemantle[START_REF] Pemantle | Vertex-reinforced random walk on z has finite range[END_REF] or Janson.[START_REF] Janson | Limit theorems for triangular urn schemes[END_REF]. It was proved the existence of a random variable Z pnq ˙ÝÑ Z.

  (a) If λ ą 1{2 and ad ‰ bc then 1 ? n ˆWn ´pad ´bcqθ a ´c ´θS 1 n ˙D ÝÑ N ˆ0, pa ´cq 2 σ 2 pad ´bcq 2 p2λ ´1q (b)

  ´N, rB 0 s 2 P r´ℓs 2 , r´ℓ `1s 2 , . . . , rm `b ´1s 2 ( ) where for all integer ℓ, rℓs 1 p respectively rℓs 2 q denotes the remainder of the division of ℓ by a p respectively bq. Assume that the tenability conditions are satisfied and that lim inf T n {n ą 0. Suppose there exists θ P r0, 1s such that the proportion of white balls, denoted by Z n converges almost surely to θ.

				D ÝÑ N ˆ0,	σ 2 2λ ´1 ˙,
	pbq if λ " 1{2 then	c n lnpnq	pZ n ´θq
	? n ˜Zn ´θ ´n´λ Z ´h1 pθq	m`1 ÿ ℓ"2
			!
	b m P ´m ´b `1, ℓ P Theorem 8. Let w " ´m˘Y ´m, 8 X m ÿ k"0 ˆm k ˙θk p1 ´θq m´k pa m´k `bm´k q, λ " ´h1 pθq w	and σ 2 "	Hpθq w 2 where
	Hpxq "	m ÿ k"0 ˆm k	˙xk p1 ´xq m´k pa m´k ´xb m´k q 2 .
	and
	hpxq "

. . , a m´1 u p respectively tb 1 , . . . , b m´1 uq. The urn is tenable if and only if for every 1 ď k ď m ´1 we have, a k ě ´a and b k ě ´b and the additional conditions a m P ´m ´a `1, ´m˘Y ´m, 8 X ! ℓ P ´N, rW 0 s 1 P r´ℓs 1 , r´ℓ `1s 1 , . . . , rm `a ´1s 1 ( ) m ÿ k"0 ˆm k ˙`a m´k ´xpa m´k `bm´k q ˘xk p1 ´xq m´k

Assuming that a m ‰ 0 if θ " 0 and b 0 ‰ a 0 if θ " 1. Then

paq if λ ą 1{2 then ? n pZ n ´θq D ÝÑ N p0, σ 2 q,

pcq if λ ă 1{2 then there exists a random variable Z such that n λ pZ n ´θq ÝÑ Z almost surely. Also we have

  λ1 , . . . , pj{nq λ d ˘P ´1EpY j Y 1 j qP 1 ´1diag `pj{nq λ1 , . . . , pj{nq λ d Then the entry rΣ n s kℓ satisfy rΣ n s kℓ " ÿ

	Proof. Putting Σ n " P	´1 ÿ jěn	n j 2 E `elnpj{nqM Y j Y 1 j e lnpj{nqM 1 ˘P 1 ´1 then
	Σ n "	ÿ
	jěn
			ne ´lnpnqM	ÿ jěn	1 j	e lnpjqM Y j

D

ÝÑ N `0, P ΣP 1 where Σ is the complex matrix with entries

Σ ij " . rP ´1Σ Y P 1´1 s ij 1 ´λi ´λj . jěn diag `pj{nq

  10. Assume that lim inf nÝÑ8 T n {n ą 0. The proportion of white balls, Z n " W n {T n satisfies (SAA) with m´k ´xpa m´k `bm´k q ˘xk p1 ´xq m´k .The noise is Y n`1 " a n´ξn`1 ´`a m´ξ m´k `bm´ξ m´k ˘´hpZ n q `Op1{nq. There exist θ P p0, 1q such that Z n ÝÑ θ almost surely and we have hpθq " 0 and h 1 pθq ď 0.

	γ n`1 " 1{T n`1 and drift function
	hpxq " ˙`a Lemma 11. Assume that lim inf m ÿ k"0 ˆm k nÝÑ8 T n {n ą 0, then T n {n converges almost surely to
	w "	n ÿ k"0 ˆk m	˙pa m´k `bm´k qθ k p1 ´θq m´k .

  The zero V 1 " p1{m ´1, . . . , 1{m ´1q of h is the unique stable equilibrium point satisfying }V 1 } 1 " 1. The eigenvalues of R are the roots of the characteristic equation All of the eigenvalues of the matrix R are simple. R has a 1 as eigenvalue with the largest real part and those different from 1 have a real part ă 1{2 if and only if m ă 26. It is pointed out that for all eigenvalue λ we have Repλq ‰ 1{2 . Thus if m ă 26 then we can apply the result in the first part of the Theorem 6 with S " 1 and Σ Y " R `1{pm ´1qI m´1 ´1{pm ´1q 2 ½ b ½ ˘R1 . Noticing that the matrix P ´1 1 RP 1 is a block wise matrix with blocks of sizes ď 2. A block of P ´11 RP 1 corresponding to a complex eigenvalue λ is given by Γ λ "

	m´1
	ź k"1	pk `xq ´m! " 0.
		Impλq Repλq ˆRepλq ´Impλq	˙.

  Now if ad " bc the sequence pa ´cqB n ´pb ´dqW n is constant " S 0 and by substituting T n ´Wn we find

			n n	"	bc ´ad pa ´c `b ´dqθ `a	´c `op1q almost surely.
					Z n "	a b ´d `a ´c	´c	`O`1 {n	.
	The total is given by
	T n " `1	`b a	´c ˘´nc `W0 ´d	´S0 a ´c `pa ´cq	Then
	with θ R t0, 1u we obtain by lemma 8 (with W 2 n " pθ ´θ2 qn)
			T n n	"	a ´c `b a ´c	´d	pθa `p1 ´θqcq	`O`l npnq{	? n	˘.

n ÿ k"1 `½W k ´Zk ˘`pa ´cq n ÿ k"1 Z k .

  S 2 1 pθa `p1 ´θqcq 2 σ 2 pa ´c ´θS 1 q 2 p2λ ´1q (c) if λ " 1{2 and ad ‰ bc then 1{2 and ad ‰ bc, there exist a random variable W 8 such that n λ´1

		1 n lnpnq a	ˆWn	´pad ´bcqθ a ´c ´θS 1	n ˙D ÝÑ N ˆ0,	pad ´bcq 2 p2λ ´1q pa ´cq 2 σ 2	(d)
	if λ " 1{2 and ad " bc then
						W n n lnpnq a	D ÝÑ N ˆ0,	S 2 pa ´c ´θS 1 q 2 p2λ ´1q 1 pθa `p1 ´θqcq 2 σ 2	(e)
	if λ ă ˆWn almost surely and we have	´pad ´bcqθ pa ´cq ´θS 1	n ˙ÝÑ W 8
	1 ? n	ˆWn	´pad ´bcqθ pa ´cq ´θS 1	n ´n1´λ wW 8 ˙D ÝÑ N ˆ0,	pad ´bcq 2 p2λ ´1q pa ´cq 2 σ 2	(f)
	if λ ă 1{2 and ad " bc then
	? n ˆ1	´a	´c S 1	θ	´a	´c S 1	n ´λW 8 ˙Wn	D ÝÑ N ˆ0,	S 2 pa ´c ´θS 1 q 2 p2λ ´1q 1 pθa `p1 ´θqcq 2 σ 2	˙.

if λ ą 1{2 and ad " bc then

W n ? n D ÝÑ N ˆ0,

Acknowledgement

The second Author thanks Professor Mohsen ben Salem for his algebraic comments.

Assuming that Repλ min q ą 1{2Repλ max q and by applying the result of Theorem 3. Then using the coordinates of Z 1 " `W1 , . . . , W d ˘in the basis pV 1 , . . . , V d q we find N ÿ ℓ"2 1{ℓ!D ℓ hpΘqpz n , . . . , z n q " N ÿ ℓ"2 1{ℓ!D ℓ hpΘqpe ´lnpnqΓ Z 1 , . . . , e ´lnpnqΓ Z 1 q `1 `op1q " N ÿ ℓ"1 d ÿ i1,...,i ℓ "1 1{ℓ!W i1 . . . W i ℓ D ℓ hpΘq `e´lnpnqΓ V i1 , . . . , e ´lnpnqΓ V i d ˘`1 `op1q " N ÿ ℓ"2 d ÿ i1,...,i ℓ "1 1{ℓ!W i1 . . . W i ℓ n ´pλi 1 `...λi ℓ q{γ D ℓ hpΘq `Vi1 , . . . , V i ℓ ˘p1 `op1qq.

Connect this expansion into (21) and using in passage lemma 4 to get M 0 pnq :"

We are going to identify the oscillation of the term

Like before we apply the Taylor expansion of h to get

By the same manner we prove by (15) that the divergent term

Finally, by the choice of N and the estimates (15) the sum ? n ÿ

jěn`1

e ´lnpj{nqΓ E N j pΘq γ j converges to 0 with probability 1.

Proof of Theorem 5.

The stochastic processes z p1q n " π 1 P ´1 1 z n and z p2q n " π 2 P ´1 1 z n are solution of the following (SAA)

Show that pz p2q n q ně0 satisfies the conditions of Theorems 3 and 4, there exist a random vectors Z p2q 1 and Z

and

The sequence ´?n ÿ jě1 A nj ¯ně1 converge to 0 with probability 1. The sequence p ? nU nj q ně1,jě1 satisfies the conditions of lemma 9 and if we put Σ n "

Since Λ 2 " H, the entries of Σ p1q n satisfy

By the the same way we have

λr`1{γ , . . . , pj{nq λ d {γq and the entries of Σ p2q n are given by n

γpγ ´λk ´λℓ q p1 `op1qq

6 Proofs of Theorems 6,7 8.

Proof of Theorems 6 and 7.

The drift function of the associated (SAA) is given by hpXq " pR ´SI d qX. The eigenvector V 1 " p1{S, . . . , 1{Sq is the unique zero of h owing the affine hyperplane H 1 " x 1 `. . . `xd " 1 ( and we have ∇hpV 1 q " R ´SI d . Putting µ i " 1 ´λi {S, i " 1, . . . , d. The main Theorem of this paper are not directly applicable since 0 is an eigenvalue of ∇hpV 1 q. We will use the decomposition of R in the following form: Let for every λ P sppRq, E λ " kerpR ´λI d q and pV 1 pλq, . . . , V s λ pλqq a basis of E λ . Now let F λ the subspace of R d given by F λ " E λ if λ is real and if λ is not real F λ is the subspace generated by the family of vectors pvpλq 1 , . . . , v 2s λ pλqq where v 2i pλq " 1{2pV i pλq `V i pλqq and v 2i´1 pλq " 1{2ipV i pλq ´V i pλqq.

By this construction we have R d " ' λPsppRq F λ . Define the subspaces F 1 " ' λ,λ‰S RepλqěS{2 F λ and F 2 " ' λ, RepλqăS{2 F λ . The projections of R on F 1 and F 2 are real matrices and denotes respectively by Γ 1 and Γ 2 and let P 1 the transition matrix such that 1{SP ´1 1 ∇hpV 1 qP 1 " from complex eigenvalues of R) around a periodic vector. Müller [START_REF] Müller | Refined Asymptotics for the Composition of Cyclic Urns[END_REF] identify the asymptotic fluctuation of M n ´EpM n q around this periodic random vector. The drift function of the corresponding (SAA) is given by hpxq " pR ´Im qx then the unique zero belonging to the hyperplane tx : }x} 1 " 1u is Θ " 1{m½ m where ½ m " p1, . . . , 1q 1 . This zero is the equilibrium stable of h and if we denote by w m " expp2iπ{mq the elementary root of unity modulo m, then the eigenvalues of ∇hpΘq are λ k " 1 `wk m " 1 ´cosp2kπ{mq ´i sinp2kπ{mq, k " 0, . . . , m ´1. Apart λ 0 " 0, theses eigenvalues are located in the region tz : Repzq ě 1{2u if and only if 2 ď m ď 6. Noticing in passage that the covariance matrix of the corresponding noise is Σ Y " I m ´½ b ½.

The transition matrix of R is P " Vandermonde r1, w 1 , . . . , w m´1 s and we have P ´1 " 1{mP

1 . From P the transition matrix P 1 is determined by its columns as follow: If m is odd then P 1 " p½ m , v 1 RP 1 is diagonal by blocks of sizes ď 2 and each block of length 2 is associated to a complex eigenvalue λ 1 and this block consists to a matrix of rotation of angle 2πk{m. The transition matrix

is also given by blocks

and rΣs 1,1 " m 2 ´m and for ℓ ‰ k `1, rΣs k,ℓ " 0.

(a) Assume that 2 ď m ď 5. Then 1 ? n `Mn ´n{m½ m ˘D ÝÑ N `0, P ΣP 1 ˘.

where Σ is the matrix with rank 2 and given by Σ 6 " ? 3 12

(c) If m ě 7 and 6|m, then there exist a random variable Z such that 1 a n lnpnq `Mn ´n{mI m´1 ´P1 p0, 0, e ´lnpnqπ3pIm´1´P ´1 1 RP1q Z ˘D ÝÑ N p0, P 1 ΣP 1 1 q

where Σ is a matrix of rank 2 with entries Σ m{3,2m{3 " Σ 2m{3,m{3 " 1 and Σ ij " 0 for pi, jq R tpm{3, 2m{3q, p2m{3, m{3qu.

(d) if m ě 7 and 6 ∤ m. Then there exist a random variable Z such that 1{ ? n `Mn ´n{mI m´1 ´nP 1 p0, 0, e ´lnpnqπ3pIm´1´P ´1 1 RP1q Z ˘D ÝÑ N p0, P 1 ΣP 1 1 q

where Σ with rank m ´1 given by Σ "