Nicolas Pouyanne
email: pouyanne@math.uvsq.fr

An algebraic approach to Pólya processes

Pólya processes are natural generalization of Pólya-Eggenberger urn models. This article presents a new approach of their asymptotic behaviour via moments, based on the spectral decomposition of a suitable finite difference transition operator on polynomial functions. Especially, it provides new results for large processes (a Pólya process is called small when 1 is simple eigenvalue of its replacement matrix and when any other eigenvalue has a real part ≤ 1/2; otherwise, it is called large).

Résumé

Les processus de Pólya sont une généralisation naturelle des modèles d'urnes de Pólya-Eggenberger. Cet article présente une nouvelle approche de leur comportement asymptotique via les moments, basée sur la décomposition spectrale d'un opérateur aux différences finies sur des espaces de polynômes. En particulier, elle fournit de nouveaux résultats sur les grands processus (un processus de Pólya est dit petit lorsque 1 est valeur propre simple de sa matrice de remplacement et lorsque toutes les autres valeurs propres ont une partie réelle ≤ 1/2 ; sinon, on dit qu'il est grand).

Introduction

Take an urn (with infinite capacity) containing first finitely many balls of s different colours named 1, . . . , s. This initial composition of the urn can be described by an s-dimensional vector U 1 , the k-th coordinate of U 1 being the number of balls of colour k at time 1. Proceed then to successive draws of one ball at random in the urn, any ball being at any time equally likely drawn. After each draw, inspect the colour of the ball, put it back into the urn and add new balls following at any time the same rule. This rule, summed up by the so-called replacement matrix R = (r i,j ) 1≤i,j≤s ∈ M s (Z) consists in adding (algebraically), for any j ∈ {1, . . . , s}, r i,j balls of colour j when a ball of colour i has been drawn. In particular, a negative entry of R corresponds to subtraction of balls from the urn, when it is possible. The urn process is the sequence (U n ) n≥1 of random vectors with nonnegative integer coordinates, the kth coordinate of U n being the number of balls of colour k at time n, i.e. after the (n -1)-st draw.

Such urn models seem to appear for the first time in [START_REF] Eggenberger | Pólya Ueber die Statistik verketter Vorgänge[END_REF]. In 1930, in its original article Sur quelques points de la théorie des probabilités ( [START_REF]Pólya Sur quelques points de la théorie des probabilités[END_REF]), G. Pólya makes a complete study of the two-colour urn process having a replacement matrix of the form S. Id 2 , S ∈ Z ≥1 .

We will only consider balanced urns. This means that all rows of R have a constant entries' sum, say S. Under this assumption, the number of added balls N. Pouyanne: Pólya processes, April 2005; revised September 2006 is S at any time, so that the total number of balls at time n is non random. Furthermore, we will only consider replacement matrices having nonnegative offdiagonal entries. Any diagonal entries may be negative but subtraction of balls of a given colour may become impossible. In order to avoid this extinction, one classically adds an arithmetical assumption to the column of any negative diagonal entry in R (see Definition 1.1 and related comments). An urn process submitted to all these hypotheses will be called Pólya-Eggenberger, in reference to the work of these authors.

A Pólya-Eggenberger urn process can be viewed as a Markovian random walk in the first quadrant of R s with finitely many possible increments (the rows of R), the conditional transition probabilities between times n and n + 1 being linear functions of the coordinates of the vector at time n. This point of view leads to the following natural generalization: we will name Pólya process such a random walk in R s with normalized balance (S = 1), even if it does not come from an urn process, i.e. even if U 1 and R have non-integer values. Note that a Pólya process as it is defined just below looks very much like a Pólya-Eggenberger urn process, with the only difference that instead of counting a number of balls, we deal with a positive real quantity l k (X n ) associated with each colour k (corresponding to the "number of balls" of this colour at time n), which gives the propensity to pick this colour at the next step. In this setting, w k is the vector in R s defined by the fact that, when colour k has been drawn, then for all j ∈ {1, . . . , s}, one adds l j (w k ) "balls" of colour j to the urn. Pólya processes generalize Pólya-Eggenberger urns only because this propensity may be real-valued (see comments after Definition 1.1). Definition 1.1 Let V be a real vector space of finite dimension s ≥ 1. Let X 1 , w 1 , . . . , w s be vectors of V and (l k ) 1≤k≤s be a basis of linear forms on V satisfying the following assumptions: i-(initialization hypothesis) X 1 = 0 and ∀k ∈ {1, . . . , s}, l k (X 1 ) ≥ 0;

(1)

ii-(balance hypothesis) for all k ∈ {1, . . . , s},

s j=1 l j (w k ) = 1; (2)
iii-(sufficient conditions of tenability 1 ) for all k, k ′ ∈ {1, . . . , s},

     k = k ′ =⇒ l k (w k ′ ) ≥ 0, (3.a)
l k (w k ) ≥ 0 or l k (X 1 )Z + s j=1 l k (w j )Z = l k (w k )Z. (3.b) (3)
1 Some authors prefer the vocable viability instead of tenability. This last word has been chosen in reference to recent literature on the subject.

N. Pouyanne: Pólya processes, April 2005; revised September 2006

The (discrete and finite dimensional) Pólya process associated with these data is the V-valued random walk (X n ) n∈Z ≥1 with increments in the finite set {w 1 , . . . , w s }, defined by X 1 and the induction: for every n ≥ 1 and k ∈ {1, . . . , s},

Prob (X n+1 = X n + w k |X n ) = l k (X n ) n + τ 1 -1 (4)
where τ 1 is the positive real number defined by

τ 1 = s k=1 l k (X 1 ). ( 5
)
The process is defined on the space of all trajectories of X 1 + 1≤k≤s Z ≥0 w k endowed with the natural filtration (F n ) n≥0 where F n is the σ-field generated by X 1 , . . . , X n . It is Markovian 2 and the transition conditional probabilities between times n and n+1 depend linearly on the state at time n, as stated in equations [START_REF] Chauvin | Pouyanne m-ary search trees when m ≥ 27: a strong asymptotics for the space requirements[END_REF]. Conditions (1) and ( 2) are necessary and sufficient for the random vector X 2 to be well defined by Relation (4); a readily induction shows the deterministic relation

∀n ≥ 1, s k=1 l k (X n ) = n + τ 1 -1. ( 6
)
Condition [START_REF] Billingsley | Probability and measure[END_REF] suffices to guarantee that the process is well defined, i.e. that the numbers l k (X n ) do not become negative so that the process does not extinguish as can be checked by an elementary induction. The arithmetical assumption (3.b), which has become classical (compare with [START_REF] Gouet | Strong Convergence of Proportions in a Multicolor Pòlya urn[END_REF], [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF], [START_REF] Flajolet | Pekari Analytic urns[END_REF] for urns) is equivalent to the following one: l k (w k ) is nonnegative, or it divides l k (X 1 ) and all the l k (w j ) as real numbers. Actually, if conditioned on non extinction, all the results about Pólya processes in this article remain valid when conditions (3) are removed from the definition.

Pólya processes are natural generalizations of Pólya-Eggenberger urns in the following sense (see [START_REF] Bagchi | Pal Asymptotic normality in the generalized Pólya-Eggenberger urn model, with an application to computer data structures[END_REF], [START_REF] Gouet | Strong Convergence of Proportions in a Multicolor Pòlya urn[END_REF], [START_REF] Flajolet | Pekari Analytic urns[END_REF], [START_REF] Puyhaubert | Modèles d'urnes et phénomènes de seuils en combinatoire analytique[END_REF] for base references on Pólya-Eggenberger urns). Take a Pólya-Eggenberger s-colour urn process having replacement matrix R and vector U 1 as initial composition; let S be the common sum of R's rows, assumed to be nonzero. The data consisting in taking the rows of 1 S R as vectors w k 's, the coordinate forms as forms l k 's and X 1 = 1 S U 1 as initial vector define a Pólya process (X n ) n on R s , the random vector X n being 1/S times the 1×s matrix U n whose entries are the numbers of balls of different colours after n -1 draws. We will name this process standardized urn process. Conversely, if one considers the forms l k of a Pólya process as being the coordinate forms of V (choice of a basis of V ), the matrix whose rows are the coordinates of the w k 's satisfies all 2 The time-homogeneity of the process is more explicit when one reads condition (4) with denominator P k l k (Xn) instead of n + τ 1 -1 (use Relation ( 6)).

N. Pouyanne: Pólya processes, April 2005; revised September 2006 hypotheses of a Pólya-Eggenberger urn's replacement matrix with balance S = 1, except that its entries are not integers but real numbers. This matrix will still be called replacement matrix of the process. Note that the balance property is expressed in Relation [START_REF] Bagchi | Pal Asymptotic normality in the generalized Pólya-Eggenberger urn model, with an application to computer data structures[END_REF]. The definition of Pólya processes is readily stable after linear change of coordinates, when urn processes do not have this property.

The present text deals with Pólya processes, so that all its results are valid for Pólya-Eggenberger urn processes. Such a process being given, different natural questions arise: what is the distribution of the vector at any time n? Can the random vector be renormalized to get convergence? What kind (and speed) of convergence is obtained? What is the asymptotic distribution of the process?

Since the work of Pólya and Eggenberger, many authors have considered such models, sometimes with more general hypotheses, often with restrictive assumptions. Direct combinatoric attacks in some particular cases were first intended ( [START_REF]Pólya Sur quelques points de la théorie des probabilités[END_REF], [START_REF] Eggenberger | Pólya Ueber die Statistik verketter Vorgänge[END_REF], [START_REF] Friedman | A simple urn model[END_REF] for example). In the last years, they have been considerably refined by analytic considerations on generating functions in low dimensions by much more general methods ( [START_REF] Flajolet | Pekari Analytic urns[END_REF], [START_REF] Puyhaubert | Modèles d'urnes et phénomènes de seuils en combinatoire analytique[END_REF]). A second approach was first introduced in [1] and developed in [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF] and [START_REF] Janson | Limit theorems for triangular urn schemes[END_REF], viewing such urns as multitype branching processes. It consists in embedding the process in continuous time, using martingale arguments and coming back to discrete time. This method provides convergence results. One can find in [START_REF] Flajolet | Pekari Analytic urns[END_REF], [START_REF] Puyhaubert | Modèles d'urnes et phénomènes de seuils en combinatoire analytique[END_REF] and [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF] good surveys and references on the subject.

A Pólya process will be called small when 1 is simple eigenvalue of the replacement matrix R and when every other eigenvalue of R has a real part ≤ 1/2. Otherwise, it will be said large.

Under some assumptions of irreducibility on R, it is well known that if (X n ) n is a small Pólya process, a normalization (X nnv 1 )/ n log ν n converges in law to a centered Gaussian vector, v 1 being a deterministic vector and ν a nonnegative integer that depends only on the conjugacy class of R -see [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF] for a complete statement of that fact. In the case of reducible small processes, convergence in law after normalization has been shown for several families of processes in low dimensions; this concerns for instance urns with triangular replacement matrix ( [START_REF] Flajolet | Pekari Analytic urns[END_REF], [START_REF] Janson | Limit theorems for triangular urn schemes[END_REF], [START_REF] Puyhaubert | Modèles d'urnes et phénomènes de seuils en combinatoire analytique[END_REF], Example 2-in Subsection 7.2). Found limit laws in these studies are most often non normal.

In the case of large Pólya processes, a suitable normalization of the random vector X n leads to an almost sure asymptotics, as shown in Theorems 3.5 and 3.6, main results of the paper. These results do not require any irreducibility assumption. This asymptotics is described by finitely-many random variables W k that appear as limits of martingales. Joint moments of the W k are computed in terms of so-called reduced polynomials (Q α ) α∈(Z ≥0 ) s that will be defined later and initial conditions of the process. We give hereunder a simplified version of the result: suppose that the replacement matrix R has 1 and λ 2 as simple eigenvalues and that any other eigenvalue is the conjugate λ 2 or has a real part < Re(λ 2 ). Such a N. Pouyanne: Pólya processes, April 2005; revised September 2006 process will be called generic 3 .

Asymptotics of generic large Pólya processes If (X n ) n is a generic large Pólya process, there exist some complex-valued random variable W and non random complex vectors v 1 and v 2 such that

X n = nv 1 + ℜ n λ2 W v 2 + o n ℜ(λ2) ,
the small o being almost sure and in any L p , p ≥ 1. Furthermore, any joint moment of the variables W and its complex conjugate W is given by the formula

E W p W q = Γ(τ 1 ) Γ(τ 1 + pλ 2 + qλ 2 ) Q (0,p,q,0,... ) (X 1 )
where Γ is Euler's function.

The positive number τ 1 , defined by ( 5), depends on initial condition X 1 . Vectors v 1 and v 2 are here eigenvectors of the replacement matrix respectively associated with the eigenvalues 1 and λ 2 . In particular, the second order term is oscillating when λ 2 is non real, giving a complete answer to the already observed non convergence of any non trivial normalization (X n -EX n )/n z , z ∈ C (see [START_REF] Chern | Phase changes in random m-ary search trees and generalized quicksort[END_REF] and related papers for example).

The method used here to establish the general asymptotics of large Pólya processes also leads to results on distributions at finite time (exact expressions for moments for example) but we do not focus on this point of view. It relies on asymptotic estimates of suitable moments of X n . Hence, the first step is to express, for general functions f , the expectation Ef (X n ) in terms of initial condition X 1 and of iterations of a finite difference operator Φ, namely, by Proposition 4.1,

Ef (X n ) = γ τ1,n (Φ)(f )(X 1 )
where γ τ1,n is the polynomial defined by γ τ1,1 = 1 and, for any n ≥ 2,

γ τ1,n (t) = n-1 k=1 1 + t k + τ 1 -1 ; (7)
Φ is the transition operator associated with the process, defined on the space of all functions f : V → R (or more generally on the space of all functions f : V → W where W is any real vector space) by: ∀v ∈ V ,

Φ(f )(v) = 1≤k≤s l k (v) f (v + w k ) -f (v) . (8)
The second step is to study this linear operator Φ on its restriction to the space of linear forms on V , which leads to set a corresponding Jordan basis (u k ) 1≤k≤s of this space, with corresponding eigenvalues (λ k ) 1≤k≤s (Definition 2.3). The third step consists in observing, as done in Proposition 3.1, that Φ stabilizes, for any α ∈ (Z ≥0 ) s , the finite dimensional polynomial subspace S α = Span{u β , β ≤ α} where, for all β = (β 1 , . . . , β s ) ∈ (Z ≥0 ) s , u β = 1≤k≤s u β k k and ≤ is the degreeantialphabetical order on s-uples of integers, defined below by [START_REF]Pólya Sur quelques points de la théorie des probabilités[END_REF]. Therefore, it is subsequently possible to decompose any u-monomial u α , α ∈ (Z ≥0 ) s as a sum of functions in the characteristic subspaces 4

ker(Φ -z) ∞ = n≥0 ker(Φ -z) n , z ∈ C.
If one denotes λ = (λ 1 , . . . , λ s ) and α, λ = 1≤k≤s α k λ k for any α ∈ (Z ≥0 ) s , it turns out that the eigenvalues of the restriction of Φ to stable finite dimensional polynomial spaces are precisely the α, λ , as justified in Section 3. The projection of any u α on ker(Φα, λ ) ∞ parallel to z = α,λ ker(Φz) ∞ will be denoted by Q α and named reduced polynomial of Φ of rank α. The reduced polynomials of rank ≤ α constitute a basis of S α and any u α can be written

u α = Q α + β<α, β,λ = α,λ q α,β Q β (9)
as proved in Proposition 4.8. This leads to an asymptotic estimate of the moments E u α (X n ) (Theorem 3.4) since, for any z ∈ C and any f ∈ ker(Φz) ∞ , there exists an integer

ν ≥ 0 such that Ef (X n ) ∼ n→+∞ n z log ν n ν! Γ(τ 1 ) Γ(τ 1 + z) (Φ -z) ν (f )(X 1 ) (10)
as it is proven in Corollary 4.2. The asymptotic estimate in Theorem 3.4 is based on the determination of the indices β in expansion (9) that contribute to the leading term of E u α (X n ); this is the object of the whole Subsections 4.4 and 4.5. To this end, Theorem 4.20 enables to refine Relation [START_REF] Flajolet | Pekari Analytic urns[END_REF]: it implies that a coefficient q α,β does not vanish only if β belongs to a convex polyhedron (A α -Σ) ∩ (R ≥0 ) s of R s , where A α is a the set of nonnegative integer points of a certain rational cone with vertex α that depends on the Pólya process and Σ a universal rational cone (universal means here that Σ is the same one for any Pólya process). Definitions of Σ and A α are respectively given by ( 35) and (39). Formula (9) can thus be refined into

u α = Q α + β∈Aα-Σ, β,λ = α,λ q α,β Q β (11)
which is the same as Relation (44). We will say that α = (α 1 , . . . , α s ) ∈ (Z ≥0 ) s is a power of large projections whenever α k = 0 for all indices k such that ℜ(λ k ) ≤ 1/2; similarly, α will be called power of small projections whenever α k = 0 for all indices k such that ℜ(λ k ) > 1/2. Now, if α is a power of large projections, Propositions 4.15 1-and 4.19 imply that ℜ β, λ < ℜ α, λ whenever β ∈ A α -Σ, β, λ = α, λ . Therefore, thanks to Relation [START_REF] Friedman | A simple urn model[END_REF], the leading term of E u α (X n ) in Formula (11) will come from EQ α (X n ) only, with an order of magnitude of the form n α,λ log ν n, the number ℜ α, λ being > |α|/2. Similarly, Propositions 4.15 2-implies that, if α is a power of small projections, this order of magnitude never exceeds n |α|/2 log ν n for some nonnegative integer ν. A precise statement of these moments' asymptotics is given in Theorem 3.4. Note that the intervention of Σ can be bypassed by a self-sufficient argument that have been suggested by the anonymous referee (see Remark 5.5).

Section 2 is devoted to Jordan decomposition of Φ's restriction to linear forms and related definitions and notations. The main results of the paper are introduced and completely stated in Section 3 while the action of transition operator Φ on polynomials is studied in Section 4. This is done in three steps: first, the stability of the filtration (S α ) α of subspaces is established as well as its consequences on reduced polynomials; cone Σ and polyhedra A α are then introduced in the space (R ≥0 ) s of exponents; afterwards, consequences of these geometrical considerations are drawn to refine Φ's action. Main Theorems 3.4, 3.5 and 3.6 are proved in Sections 5 and 6. At last, Section 7 contains diverse remarks and examples. The author is very grateful to the anonymous referee whose careful reading of a preprint version of this paper and helpful comments on it greatly improved its quality.

Preliminaries, notations and definitions

Definition of Pólya processes in a real vector space V of finite dimension s ≥ 1 was given in Definition 1.1. We associate with any process its replacement endomorphism that will be denoted by A in reference to literature on the subject ( [START_REF] Athreya | Embedding of urn schemes into continuous time Markov branching processes and related limit theorems[END_REF], [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF] for example). Let

V C = V ⊗ R C be the complexified space of V . Definition 2.1 If (X n ) n is a Pólya process, its replacement endomorphism is, with notations of Definition 1.1, the endomorphism A = 1≤k≤s l k ⊗ w k ∈ V * ⊗ V ≃ End(V ), defined as A(v) = 1≤k≤s l k (v)w k for every v in V .
Note that the transpose of A is the restriction of the transition operator Φ to linear forms on V . When the process is a Pólya-Eggenberger urn process, the matrix of N. Pouyanne: Pólya processes, April 2005; revised September 2006 A in the dual basis of (l k ) k is the transpose of the normalized urn's replacement matrix 1 S R (notations of Section 1). With this definition, the expectation of X n+1 conditionally to X n is readily expressed as (I + A n+τ1-1 )X n , so that the expectation of X n equals

EX n = γ τ1,n (A)(X 1 ) (straightforward induction).
One of the first tools used to describe the asymptotics of a Pólya process is the reduction of its replacement endomorphism A (or of its transpose on the dual vector space of V ). Because of condition (2), the linear form u 1 = s k=1 l k satisfies u 1 • A = u 1 , which shows that 1 is always eigenvalue of A. The whole assumptions (1),( 2) and (3), allows us to say more on A's spectral decomposition. Even if these properties can be proved using Perron-Frobenius theory, we give a proof's hint of Proposition 2.2. Proposition 2.2 Any complex eigenvalue λ of A equals 1 or satisfies ℜλ < 1. Moreover, dim ker(A -1) equals the multiplicity of 1 as eigenvalue of A.

Proof. Replace A by its matrix in the dual basis of (l k ) k . Suppose first that all entries of A are nonnegative. The space of all s × s matrices having nonnegative entries and columns with entries' sum 1 is bounded (for the norms' topology) and stable for multiplication. This forces the sequence (A n ) n≥0 to be bounded, which implies both results (for the second one, consider Jordan's decomposition of A and note that the positive powers of I + N constitute an unbounded sequence if N is a nilpotent nonzero matrix). If A has at least one negative diagonal entry, apply the results to (A + a)/(1 + a) for any positive a such that A + a has nonnegative entries.

In the whole paper, a Pólya process with replacement endomorphism A being given, we will denote by σ 2 the real number ≤ 1 defined by

σ 2 =    1 if 1 is multiple eigenvalue of A; max{ℜλ, λ ∈ Sp(A), λ = 1} otherwise, (12)
where Sp(A) is the set of eigenvalues of A.

Jordan basis of linear forms of the process

The present subsection is devoted to notations and vocabulary related to spectral properties of the replacement endomorphism A.

N. Pouyanne: Pólya processes, April 2005; revised September 2006 Definition 2.3 If (X n ) n is a Pólya process of dimension s, a basis (u k ) 1≤k≤s of linear forms on V C is called a Jordan basis of linear forms of the process or shortlier a Jordan basis when 1-

u 1 = 1≤k≤s l k ; 2-u k • A = λ k u k + ε k u k-1 for all k ≥ 2
, where the λ k are complex numbers (necessarily eigenvalues of A) and where the ε k are numbers in {0, 1} that satisfy

λ k = λ k-1 =⇒ ε k = 0.
In other words, the matrix of the transposed endomorphism t A in a Jordan basis of linear forms has a block-diagonal form Diag (1, J p1 (λ k1 ), . . . , J pt (λ kt )) where J p (z) denotes the p-dimensional square matrix

J p (z) =       z 1 z . . . . . . 1 z       .
A (real or complex) linear form u k will be called eigenform of the process when

u k • A = λ k u k , i.e.
when ε k = 0. An eigenform of the process is an eigenvector of t A; some authors call these linear forms left eigenvectors of A, refering to matrix operations.

Definition 2.4 A Jordan basis of linear forms being chosen with notations as above, a subset J ⊆ {1, . . . , s} is called a monogenic block of indices when J has the form J = {m, m + 1, . . . , m + r} (r ≥ 0, m ≥ 1, m + r ≤ s) with ε m = 0, ε k = 1 for every k ∈ {m + 1, . . . , m + r} and J is maximal for this property. Any monogenic block of indices J is associated with a unique eigenvalue of A that will be denoted by λ(J).

In other words, J is monogenic when the subspace Span{u j , j ∈ J} is A-stable and when the matrix of the endomorphism of Span{u j , j ∈ J} induced by t A in the Jordan basis is one of the Jordan blocks mentioned above with number λ(J) on its diagonal. The adjective monogenic has been chosen because this means that the subspace Span{u j , j ∈ J} = C[ t A].u m+r is a monogenic sub-C[t]-module of the dual space V * C for the usual C[t]-module structure induced by t A.

Definition 2.5 A monogenic block of indices J is called a principal block when ℜλ(J) = σ 2 and J has maximal size among the monogenic blocks J ′ such that ℜλ(J ′ ) = σ 2 (see [START_REF] Graham | Concrete Mathematics[END_REF] for σ 2 's definition).

A Jordan basis (u k ) 1≤k≤s of linear forms of the process being chosen,

(v k ) 1≤k≤s (13)
N. Pouyanne: Pólya processes, April 2005; revised September 2006 will denote its dual basis, made of the vectors of V C that satisfy u k (v l ) = δ k,l (Kronecker notation) for any k and l, and

λ = (λ 1 , . . . , λ s ) (14)
the s-uple of eigenvalues (distinct or not) respectively associated with u 1 , . . . , u s (or v 1 , . . . , v s ). In particular, λ 1 = 1 for any Jordan basis of linear forms. The eigenvalues λ 1 , . . . , λ s of A are called roots of the process. For any k, we also denote by π k the projection on the line Cv k relative to the decomposition V C = 1≤l≤s Cv l ; these projections satisfy

Id = 1≤k≤s π k and π k = u k .v k . ( 15
)
Note that the π k commute with each other (π k π l = δ k,l π k ) but do not commute with A. Nevertheless, A commutes with j∈J π j , the sum being extended to any monogenic block of indices J (these sums are polynomials in A). This fact will be used in the proofs of Theorems 3.5 and 3.6. The lines spanned by the vectors v k can be seen as principal directions of the process, the word principal being here used in physicists' sense.

Semisimplicity, large and small projections

For every Jordan basis (u k ) 1≤k≤s of linear forms, and for every α = (α k ) 1≤k≤s ∈ Z s , we adopt the notations

|α| = 1≤k≤s α k (total degree) α, λ = 1≤k≤s α k λ k (16)
and, when all the α k are nonnegative integers

u α = 1≤k≤s u α k k ,
u α being a homogeneous polynomial function of degree |α|.

Given a Jordan basis (u k ) 1≤k≤s of linear forms of the process, we adopt the following definitions.

Definition 2.6 A Pólya process is called semisimple when its replacement endomorphism A is semisimple, i.e. when A admits a basis of eigenvectors in V C (this means that all the u k are real or complex eigenforms of A). The process is called principally semisimple when all principal blocks have size one (for any choice of a Jordan basis).

N. Pouyanne: Pólya processes, April 2005; revised September 2006

The four following assertions are readily equivalent: i) the process is principally semisimple; ii) for any k ∈ {1, . . . , s},

ℜλ k = σ 2 =⇒ u k is eigenform ; iii) the induced endomorphism {k, ℜλ k =σ2} π k A is diagonalizable over C; iv) if r ≥ 1 and if {λ k , k ≥ r + 1}
are the roots of the process having a real part < σ 2 , the matrix of t A in the Jordan basis has a block-diagonal form Diag (1, λ 2 , . . . , λ r , J p1 (λ k1 ), . . . , J pt (λ kt )). Note that Proposition 2.2 asserts that any u k associated with root 1 is eigenform of A. Definition 2.7 A root of the process is called small when its real part is ≤ 1/2; otherwise, its is said large. The process is called small when σ 2 ≤ 1/2, which means that 1 is simple root and all other roots are small; when the process is not small, it is said large. Definition 2.8 Let α = (α 1 , . . . , α s ) ∈ (Z ≥0 ) s . 1-α is called power of large projections when u α is a product of linear forms associated with large roots, i.e. when for all k ∈ {1, . . . , s}, α k = 0 =⇒ ℜλ k > 1/2 . 2-α is called power of small projections when u α is a product of linear forms associated with small roots, i.e. when for all k ∈ {1, . . . , s}, α k = 0 =⇒ ℜλ k ≤ 1/2 . 3-α is called semisimple power when u α is a product of eigenforms, i.e. when for all k ∈ {1, . . . , s}, α k = 0 =⇒ u k is eigenform of the process . 4-α is called monogenic power when its support in contained in a monogenic block of indices.

In the whole text, the canonical basis of Z s (or of R s ) will be denoted by

(δ k ) 1≤k≤s (17)
and the symbol α ≤ β

on s-uples of nonnegative integers will denote the degree-antialphabetical (total) order, defined by α = (α 1 , . . . , α s ) < β = (β 1 , . . . , β s ) when |α| < |β| or |α| = |β| and ∃r ∈ {1, . . . , s} such that α r < β r and α t = β t for any t > r . For this order,

δ 1 < δ 2 < • • • < δ s < 2δ 1 < δ 1 + δ 2 • • • . When α = (α 1 , . . . , α s ) is a s-uple

Main results

As it was briefly explained in Section 1, the method used to study the asymptotics of a Pólya process (X n ) n relies on estimates of its moments in a Jordan basis, namely E u α (X n ), α ∈ (Z ≥0 ) s . To this end, as it is developed in Subsection 4.1, it is natural to consider the transition operator Φ as it was defined by Equation ( 8). Proposition 3.1 is the first result on the action of Φ on polynomials. One can find a proof of it in Subsection 4.2.

Proposition 3.1 For any choice of a Jordan basis (u k ) 1≤k≤s of linear forms of a Pólya process and for every α

∈ (Z ≥0 ) s , Φ(u α ) -α, λ u α ∈ Span{u β , β < α}.
The complex numbers α, λ were defined in ( 16). An immediate consequence of this proposition is the Φ-stability of the finite-dimensional polynomial subspace

S α = Span{u β , β ≤ α} (19)
for any α ∈ (Z ≥0 ) s . These subspaces form an increasing sequence whose union is the space S(V ) of all polynomial functions on V , so that Proposition 3.1 asserts that the eigenvalues of Φ on S(V ) are exactly all numbers α, λ , α ∈ (Z ≥0 ) s (in the (ordered) basis (u β ) β≤α of any S α , the matrix of Φ is triangular).

Notation: if Ψ is an endomorphism of any vector space, we will denote by ker Ψ ∞ the characteristic space of Ψ associated with zero, that is

ker Ψ ∞ = p≥0 ker Ψ p . ( 20
)
We will use the notation Φ to refer to Φ itself as well as to the endomorphism induced by Φ on S(V ) or on some stable subspace. Decomposition of all S α as direct sums of characteristic subspaces of Φ leads to the splitting

S(V ) = z∈C ker(Φ -z) ∞ .
As it was announced in Section 1, we can now properly define the reduced polynomials.

Definition 3.2 For any choice of a Jordan basis (u k ) 1≤k≤s of linear forms of a Pólya process and for any

α ∈ (Z ≥0 ) s , the reduced polynomial of rank α is the projection of u α on ker(Φ -α, λ ) ∞ parallel to z = α,λ ker(Φ -z) ∞ . It will be denoted by Q α .
N. Pouyanne: Pólya processes, April 2005; revised September 2006

Properties of reduced polynomial will be further developed in Section 4. In particular, it will be explained how one can compute them inductively (see (32)). They admit sometimes closed formulae (see (33), [START_REF] Pouyanne | Classification of large Pólya-Eggenberger urns with regard to their asymptotics[END_REF] and (58)). It follows from its definition that Q α belongs to ker(Φα, λ ) ∞ ; the number ν α defined just below is its index of nilpotence in this characteristic space. In particular, ν α = 0 if, and only if Q α is eigenvector of Φ. Proposition 5.6 in Subection 5.2 shows how one can easily compute this number for any power of large projections.

Definition 3.3 For every α ∈ (Z ≥0 ) s , the nonnegative integer ν α is defined by

ν α = max{p ≥ 0, (Φ -α, λ ) p (Q α ) = 0}. ( 21
)
These facts, definitions and notations being given, we claim the following three main results of the article. Theorem 3.4 (Joint moments of small or large projections) Let (u k ) 1≤k≤s be a Jordan basis of linear forms of a Pólya process

(X n ) n . Let α ∈ (Z ≥0 ) s .
1-If α is a power of small projections, then there exists some nonnegative integer ν such that

E u α (X n ) ∈ O n |α|/2 log ν n
as n tends to infinity. 2-If α is a power of large projections, then there exists a complex number c such that

E u α (X n ) = cn α,λ log να n + o n ℜ α,λ log να n
as n tends to infinity.

3-If α is a semisimple power of large projections, then

E u α (X n ) = n α,λ Γ(τ 1 ) Γ(τ 1 + α, λ ) Q α (X 1 ) + o n ℜ α,λ
as n tends to infinity, where Q α is the reduced polynomial of rank α relative to the Jordan basis (u k ) 1≤k≤s .

Constant c in Assertion 2-has an explicit form given in Remark 5.3. The proof of Theorem 3.4 can be found in Section 5. It is based on a careful study of coordinates of the u-monomials in the basis of reduced polynomials, which is developed in Subsections 4.4 and 4.5.

Although it is not formally necessary, we give two different statements on the asymptotics of large Pólya processes, respectively when the process is principally semisimple or not. Their proofs can be found in Section 6. They are based on Theorem 3.4 and use martingale techniques (quadratic variation, Burkholder Inequality). N. Pouyanne: Pólya processes, April 2005; revised September 2006 Theorem 3.5 (Asymptotics of large and principally semisimple Pólya processes) Suppose that a Pólya process (X n ) n is large and principally semisimple. Fix a Jordan basis (u k ) 1≤k≤s of linear forms such that u 1 , . . . , u r (2 ≤ r ≤ s) are all the eigenforms of the basis that are associated with roots5 λ 1 = 1, λ 2 , . . . , λ r having a real part ≥ σ 2 .

Then, with notations ( 13) and ( 14) of Section 2, there exist unique (complexvalued) random variables W 2 , . . . , W r such that

X n = nv 1 + 2≤k≤r n λ k W k v k + o (n σ2 ) , ( 22
)
the small o being almost sure and in L p for every p ≥ 1. Furthermore, if one denotes by (Q α ) α∈(Z ≥0 ) s the reduced polynomials relative to the Jordan basis (u k ) k , all joint moments of the random variables W 2 , . . . , W r exist and are given by: for all α 2 , . . . , α r ∈ Z ≥0 ,

E   2≤k≤r W α k k   = Γ(τ 1 ) Γ(τ 1 + α, λ ) Q α (X 1 )
where α = 2≤k≤r α k δ k = (0, α 2 , . . . , α r , 0, . . . ).

Theorem 3.6 (Asymptotics of large and principally nonsemisimple Pólya processes) Suppose that the Pólya process (X n ) n is large and principally nonsemisimple. Fix a Jordan basis (u k ) 1≤k≤s of linear forms; let J 2 , . . . , J r be the principal blocks of indices 6 and ν + 1 the common size of the J k 's (ν ≥ 1).

Then, with notations ( 13) and ( 14) of Section 2, there exist unique (complexvalued) random variables W 2 , . . . , W r such that

X n = nv 1 + 1 ν! log ν n 2≤k≤r n λ(J k ) W k v max J k + o (n σ2 log ν n) , (23)
the small o being almost sure and in L p for every p ≥ 1. Furthermore, if one denotes by (Q α ) α∈(Z ≥0 ) s the reduced polynomials relative to the Jordan basis (u k ) k , all joint moments of the random variables W 2 , . . . , W r exist and are given by: for all α 2 , . . . , α r ∈ Z ≥0 ,

E   2≤k≤r W α k k   = Γ(τ 1 ) Γ(τ 1 + α, λ ) Q α (X 1 )
where α = 2≤k≤r α k δ min J k .

Let (X n ) n be a Pólya process given by its increment vectors (w k ) 1≤k≤s and its basis of linear forms (l k ) 1≤k≤s submitted to hypotheses of Definition 1.1. We recall here the definition of its associated transition operator Φ as it was given in Section 1: if f : V → W is any W -valued function where W is any real vector space, ∀v ∈ V ,

Φ(f )(v) = 1≤k≤s l k (v) f (v + w k ) -f (v) .

Transition operator Φ and computation of moments

Proposition 4.1 expresses the expectation of any f (X n ) in terms of f , of iterations of the transition operator Φ and of X 1 , initial value of the process. Polynomials γ τ1,n with rational coefficients and one variable were defined by Equation ( 7).

Proposition 4.1 If f : V → W is any measurable function taking values in some real (or complex) vector space W , then for all n ≥ 1,

Ef (X n ) = γ τ1,n (Φ)(f )(X 1 ). ( 24
)
Proof. It follows immediately from (4) that the expectation of f (X n+1 ) conditionally to the state at time n is

E Fn f (X n+1 ) = 1≤k≤s 1 n + τ 1 -1 l k (X n )f (X n + w k ) = f (X n ) + 1 n + τ 1 -1 1≤k≤s l k (X n ) f (X n + w k ) -f (X n ) .
By definition of the transition operator Φ, this formula can be written as

E Fn f (X n+1 ) = Id + 1 n + τ 1 -1 Φ (f )(X n ); (25)
taking the expectation leads to the result after a straightforward induction.

It follows from Proposition 4.1 that the asymptotic weak behaviour of the process, or at least the asymptotic behaviour of its moments is reachable by decompositions of the operator Φ on suitable function spaces. Corollary 4.2 is the first step in this direction, stating the result for functions that belong to finite dimensional stable subpaces. N. Pouyanne: Pólya processes, April 2005; revised September 2006 Corollary 4.2 Let f : V → W be a measurable function taking values in some real (or complex) vector space W .

1-If f is an eigenfunction of Φ associated with the (real or complex) eigenvalue z, that is if

Φ(f ) = zf , then Ef (X n ) = n z Γ(τ 1 ) Γ(τ 1 + z) f (X 1 ) + O n z-1
as n tends to infinity (Γ is Euler's function). 2-Assume that f is nonzero and belongs to some Φ-stable subspace S of measurable functions V → W and that the operator induced by Φ on S is a sum z Id S +Φ N , where Φ N is a nonzero nilpotent operator on S and z a complex number. Let ν be the positive integer such that

Φ ν N (f ) = 0 and Φ ν+1 N (f ) = 0. Then, Ef (X n ) = n z log ν n ν! Γ(τ 1 ) Γ(τ 1 + z) Φ ν N (f )(X 1 ) + O n z log ν-1 n
as n tends to infinity.

Proof. 1-It follows from Proposition 4.1 that Ef (X n ) = γ τ1,n (z) × f (X 1
). Note that, as soon as the terms are defined,

γ τ1,n (t) = Γ(τ 1 ) Γ(τ 1 + t) Γ(n + τ 1 -1 + t) Γ(n + τ 1 -1) , (26)
so that the result is a consequence of Stirling Formula.

2-Taylor expansion of γ τ1,n (z Id +Φ N ) leads to

Ef (X n ) = p≥0 1 p! γ (p) τ1,n (z)Φ p N (f )(X 1 )
(finite sum), where γ

(p)
τ1,n denotes the p-th derivative of γ τ1,n . Besides, if p is any positive integer,

γ (p) τ1,n (z) = n z log p n Γ(τ 1 ) Γ(τ 1 + z) + O n z log p-1 n (27)
when n tends to infinity, as can be shown by Stirling formula (see ( 26)) and an elementary induction starting from the computation of γ τ1,n 's logarithmic derivative. These two facts imply the result.

Remark 4.3

As it is written, Corollary 4.2 is valid only if the complex number τ 1 + z is not a nonpositive integer. We adopt the convention 1/Γ(w) = 0 when w ∈ Z ≤0 , so that this corollary is valid in all cases.

Remark 4.4 If f : V → W is linear, formula (8) implies that Φ(f ) = f • A. In that particular case, formula (24) gives Ef (X n ) = f • γ τ1,n (A)(X 1 )
. This fact will be used in the proofs of Theorems 3.5 an 3.6 when f is a linear combination of projections π k (see Section 6).

N. Pouyanne: Pólya processes, April 2005; revised September 2006

Action of Φ on polynomials

Because of Condition [START_REF] Bagchi | Pal Asymptotic normality in the generalized Pólya-Eggenberger urn model, with an application to computer data structures[END_REF] in the definition of a Pólya process, none of the vectors w k is zero. For any k, if f is a function defined on V , we denote by ∂f /∂w k , when it exists, the derivative of f along the direction carried by the vector w k . With this notation, we associate with the finite difference operator Φ the differential operator Φ ∂ defined by

Φ ∂ (f )(v) = 1≤k≤s l k (v) ∂f ∂w k (v) (28)
for every function f defined on V and derivable at each point along the directions carried by the vectors w k 's. When f is differentiable, Φ ∂ (f ) can be viewed as a "first approximation" of Φ(f ). As derivation behaves good with respect to product of functions when finite differentiation does not, Φ ∂ (f ) is helpful for the understanding of Φ's action on polynomials.

α ∈ (Z ≥0 ) s , Φ ∂ (u α ) -α, λ u α ∈ Span{u β , β < α}; 2-if α ∈ (Z ≥0 ) s is a semisimple power, then Φ ∂ (u α ) = α, λ u α .
Proof. Φ ∂ is a derivation, as can be seen directly or from Remark 4.5. In particular, for any α

∈ (Z ≥0 ) s , Φ ∂ (u α ) = s k=1 α k u α-δ k Φ ∂ (u k ). (29)
Besides, as any

u k is linear, Φ ∂ (u k ) = u k • A.
The conclusion follows from Jordan basis' Definition 2.3 (the degree-antialphabetical order on s-uples is defined in [START_REF]Pólya Sur quelques points de la théorie des probabilités[END_REF] at the end of Subsection 2.2). We can now prove Proposition 3.1, as it was announced in Section 3. It appears as a direct consequence of Proposition 4.6.

Proof of Proposition 3.1. The family (u β ) |β|≤|α|-1 constitutes a basis of polynomials of degree ≤ |α| -1. Hence, if F denotes the subspace F = Span{u β , β < α}, Taylor formula implies that (Φ-Φ ∂ )(u α ) ∈ F . Moreover, Φ ∂ (u α )-α, λ u α ∈ F because of Proposition 4.6. This completes the proof.

Reduced polynomials

Choose a Jordan basis of linear forms (u k ) 1≤k≤s of a Pólya process. For any α ∈ (Z ≥0 ) s , the reduced polynomial of rank α, denoted by Q α , was defined in Definition 3.2 as the projection of u α on ker(Φ-α, λ ) ∞ parallel to z = α,λ ker(Φ-z) ∞ (see [START_REF] Puyhaubert | Modèles d'urnes et phénomènes de seuils en combinatoire analytique[END_REF] for the meaning of notation ker ψ ∞ ). Properties of these polynomials that are listed in Proposition 4.8 will be used in the sequel. Subspaces S α were defined in [START_REF] Pouyanne | Classification of large Pólya-Eggenberger urns with regard to their asymptotics[END_REF].

Proposition 4.8 Let α ∈ (Z ≥0 ) s . (1) Q 0 = 1 and Q α = u α if |α| = 1; (2) {Q β , β ≤ α} is a basis of S α ; (3) for every z ∈ C, {Q α , α, λ = z} is a basis of ker(Φ -z) ∞ ; (4) Q α -u α ∈ Span{Q β , β < α, β, λ = α, λ }; (5) Φ(Q α ) -α, λ Q α ∈ Span{Q β , β < α, β, λ = α, λ }.
Proof. (1) comes directly from the definition of a Jordan basis and (2) from the Φ-stability of subspaces S α (see [START_REF] Pouyanne | Classification of large Pólya-Eggenberger urns with regard to their asymptotics[END_REF]). Any Q α belongs to the characteristic space ker(Φα, λ ) ∞ and the eigenvalues of the restriction of Φ on polynomials are exactly the α, λ (see Section 3, consequences of Proposition 3.1). These facts imply (3). Property (4) is obvious from Q α 's definition, when (5) follows from (3) and Proposition 3.1.

Assertions (4) and (5) in Proposition 4.8 can be used to compute the reduced polynomials inductively (see Remark 4.9 below). Let's define, as it was announced in Section 1, the complex numbers q α,β by the relations u α = Q α + β<α q α,β Q β , their existence and unicity being guaranteed by Assertions (2) and (4) in Proposition 4.8. Moreover, because of (4), q α,β = 0 as soon as β, λ = α, λ , so that

u α = Q α + β<α, β,λ = α,λ q α,β Q β . ( 30
)
This relation, still too rough to lead to the main results on asymptotics of large Pólya processes, will be refined in Subsection 4.5.

N. Pouyanne: Pólya processes, April 2005; revised September 2006

We end the present subsection by giving two remarks concerning the inductive computation of all reduced polynomials and a closed form for projections of the powers of u 1 .

Remark 4.9 Inductive computation of Q α 's. In the general case, the numbers q α,β and the numbers p α,β defined by [START_REF] Chern | Phase changes in random m-ary search trees and generalized quicksort[END_REF] in Proposition 4.8) can be inductively computed (and implemented) the following way. We denote by r α,β the complex numbers defined by

(Φ -α, λ )(Q α ) = β<α p α,β Q β = β<α, β,λ = α,λ p α,β Q β (see
(Φ -α, λ )(u α ) = β<α r α,β Q β , (31)
that can be deduced by plain computation of (Φα, λ )(u α ) and its expansion in the (Q β ) β<α basis with the help of formula (30), the corresponding numbers q β,γ being known by induction. Write two expressions of (Φ-α, λ )(u α ) with formulae (30) and (31) and identify the coordinates in the (Q β ) basis. This provides the following equations with p α,β and q α,β as unknowns:

   β, λ = α, λ =⇒ r α,β = p α,β β, λ = α, λ =⇒ r α,β = ( β, λ -α, λ ) q α,β + β<γ<α q α,γ p γ,β . (32)
The expansion of Q α in the (u β ) basis can be obtained by reversing the triangular system written in (30). All these computations can be handled by means of symbolic computation.

Remark 4.10 Closed formula for Q pδ1 's.

An immediate computation shows that the reduced polynomials corresponding to powers of u 1 are the same ones for all Pólya processes: for any integer p ≥ 0, Φ [u 1 (u 1 + 1) . . . (u 1 + p -1)] = pu 1 (u 1 + 1) . . . (u 1 + p -1), so that if follows from Proposition 4.8 that Q pδ1 = u 1 (u 1 + 1) . . . (u 1 + p -1). The powers of u 1 are thus always expressed in terms of reduced polynomials Q pδ1 's by means of Stirling numbers of the second kind (for this inversion formula, see e.g. [START_REF] Graham | Concrete Mathematics[END_REF]):

u p 1 = p k=1 (-1) p-k p k Q kδ1 . (33)
This common formula has to be related to the non random drift, consequence of (6

): ∀n, u 1 (X n ) = n + τ 1 -1.
N. Pouyanne: Pólya processes, April 2005; revised September 2006

Cones in the space of powers

As it was explained in Section 1, it follows from reduced polynomial's definition that the behaviour of the EQ β (X n ) are ruled by Corollary 4.2. Thus, the asymptotics of the u-moment

E u α (X n ) = EQ α (X n ) + β<α, β,λ = α,λ q α,β EQ β (X n ), (34)
when n goes off to infinity, depends on the answer to the following two questions:

(1) which q α,β are zero in Relation (30)?

(2) For a given α, which ℜ β, λ is maximal among indices β < α such that q α,β = 0?

Optimal answer for the most general Pólya process is expressed in terms of a rational cone Σ and a rational polyhedron A α in the "space of powers" R s = Z s ⊗R.

The two following paragraphs are devoted to these subsets; at the end of each of them, we give properties of the number β, λ when β belongs respectively to Σ or some A α (Propositions 4.15 and 4.19). Note, as suggested by the anonymous referee, that the argument given in Remark 5.5 enables one to by-pass Sections 4.4.1 and 4.5 giving the construction of the cone Σ and the study of its properties.

Cone Σ

Notations: if I ⊆ {1, . . . , s} and (i, j) ∈ {1, . . . , s} 2 , we adopt the notations

δ I = 1≤i≤s δ i + i∈I δ i ∈ R s and δ * I = 1≤i≤s dx i + i∈I dx i ∈ R s * , δ (i,j) = 2δ i -δ j ∈ R s and δ * (i,j) = 2dx i -dx j ∈ R s *
where dx k denotes the k-th coordinate form (x 1 , . . . , x s ) → x k in the dual space R s * and where δ k is the k-th vector of the canonical basis of R s , already defined in [START_REF] Mahmoud | Evolution of random search trees[END_REF]. Definition 4.11 We denote by Σ the polyhedral cone of R s spanned by the s(s-1) vectors δ (i,j) for all ordered pairs (i, j) of distinct elements, i.e.

Σ = (i,j)∈{1,...s}, i =j R ≥0 δ (i,j) . ( 35
)
This cone is convex, and the half-lines spanned by vectors δ (i,j) are extremal (edges). As usual, we define the dual cone Σ of Σ as

Σ = {x ∈ R s , ∀y ∈ Σ, x, y ≥ 0},
N. Pouyanne: Pólya processes, April 2005; revised September 2006 identified to the cone of all linear forms on R s that are nonnegative on Σ, via the bijective linear application x ∈ R s → x, . ∈ R s * (the symbol x, y denotes the standard scalar product of x and y in R s ). Lemma 4.12 describes the dual cone Σ as a minimal intersection of hyperplanes (faces) and gives a system of minimal generators (edges). Corollary 4.14 just transcribes Lemma 4.12 in the Σ-side and gives the equations of the faces of Σ. We give a complete geometrical description of Σ; it presents some "universal" character, as shown in Remark 4.16.

Lemma 4.12 (faces and edges of Σ)

Σ = (i,j)∈{1,...s}, i =j {x ∈ R s , δ * (i,j) (x) ≥ 0} = I⊆{1,...,s} 1≤#I≤s-1 R ≥0 δ I .
Proof. The first equality that describes the faces of Σ comes directly from (35). For every permutation w ∈ S s , let τ w be the simplicial cone defined by

τ w = {x ∈ R s , x w(s) ≤ x w(s-1) ≤ • • • ≤ x w(1) ≤ 2x w(s) }.
The cones τ w provide a subdivision of Σ in s! simplicial cones -this subdivision is the intersection of Σ with the barycentric subdivision of the first quadrant of R s . Each τ w is the image of τ 1 = τ Id by the permutation of coordinates induced by w (and τ 1 is a fundamental domain for the group action of S s on Σ by permutations of coordinates). Because of the elementary computation

(x 1 , x 2 , x 3 , x 4 ) = (2x 4 -x 1 )(1, 1, 1, 1) +(x 1 -x 2 )(2, 1, 1, 1) +(x 2 -x 3 )(2, 2, 1, 1) +(x 3 -x 4 )(2, 2, 2, 1)
that can be straightforwardly generalized in all dimensions, one sees that the edges of τ 1 are spanned by (1, . . . , 1) = δ ∅ and δ {1} , δ {1,2} ,. . . , δ {1,...,s-1} . The images of these last s -1 vectors under permutations of coordinates are exactly the δ I , where I = ∅ and I = {1, . . . , s}. This completes the proof.

Remark 4.13 Vectors δ ∅ = 1≤k≤s δ k and δ {1,...,s} = 2δ ∅ belong to Σ, and this fact will be used in the sequel. They do not appear in the second sum of Lemma 4.12 because they do not span an edge of Σ. On the contrary, the vector δ I spans an edge of Σ when I is neither empty nor the whole {1, . . . , s}. In dimension two, Σ is spanned by (2, -1), and (-1, 2) and Σ by the forms 2dx 1 +dx 2 and dx 1 +2dx 2 . In dimension three, Σ is spanned by (2, -1, 0), (-1, 2, 0), (2, 0, -1), (-1, 0, 2), (0, 2, -1) and (0, -1, 2) and the coordinates of the spanning forms of Σ are (2, 1, 1), (1, 2, 1), (1, 1, 2), (2, 2, 1), (2, 1, 2) and (1, 2, 2) in the canonical basis (dx 1 , dx 2 , dx 3 ). The numbers of edges of Σ and Σ coincide only in dimensions 2 and 3. Figures 1 and2 give pictures of Σ in dimensions 2 and 3; in these figures, the comments that contain occurences of the greek letter η refer to further developments (see Remark 4.21 in Subsection 4.5).

Σ Σ α {α -η, η ≥ 0, |η| ≥ 2} α α -Σ {α -η + δ k , η ≥ 0, |η| ≥ 2, k ∈ {1, 2}}
Figure 1: cone Σ and related sets in dimension 2 . . , λ s ) its root's s-uple (see [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF]). Let α ∈ (Z ≥0 ) s and β ∈ (Z ≥0 ) s ∩ (α -Σ).

δ 1 δ 2 δ 3 (0, 2, -1) (2, 0, -1) (2, -1, 0) (0, -1, 2) (-1, 0, 2) (-1, 2, 0)
1-If α is a power of large projections, then α = β or ℜ β, λ < ℜ α, λ . 2-If α is a power of small projections, then ℜ β, λ ≤ 1 2 |α|. Proof. See Definition 2.8 in Subsection 2.2 for definitions of powers of large or small projections. We denote σ = αβ ∈ Σ and split {1, . . . , s} into the three disjoint subsets

I = {k, ℜ(λ k ) ≥ 1 2 , σ k ≤ 0}, J = {k, ℜ(λ k ) ≥ 1 2 , σ k > 0} and K = {k, ℜ(λ k ) < 1 2 }. 1-If α is a power of large projections, then any α k (k ∈ K) vanishes. Since α -σ ≥ 0, this implies that σ k ≤ 0 for all k ∈ K. Thus, ℜ σ, λ ≥ k∈I σ k + 1 2 k∈J σ k + 1 2 k∈K σ k = 1 2 δ * I (σ). ( 38
)
Since σ lies in Σ, the number δ * I (σ) is nonnegative (see (36)). Besides, σ k ≤ 0 for any k ∈ K so that there exists some k ∈ I ∪ J such that σ k > 0 because the only point of Σ with only nonpositive coordinates is 0, as can be seen on Σ's equations (Corollary 4.14). Thus J = ∅ and the inequality of (38) is strict.

2-If α is a power of small projections, then k ∈ I ∪ J =⇒ α k = 0. Thus β, λ ≤ 1 2 k∈K (α k -σ k ) - 1 2 k∈J σ k - k∈I σ k = 1 2 |α| - 1 2 δ * I (σ).
Since σ lies in Σ, the number δ * I (σ) is nonnegative.

Remark 4.16 Assertion 1-of Proposition 4.15 is not far from being an equivalence in the following sense.

Claim For any α = (α 1 , . . . , α s ) ∈ (R ≥0 ) s , the following are equivalent:

(1) ∀k ∈ {1, . . . , s},

ℜ(λ k ) ≤ 1/2 =⇒ α k = 0; (2) ∀β ∈ (R ≥0 ) s ∩ (α -Σ), ℜ β, λ < ℜ α, λ . Proof. Note first that (2) is readily equivalent to (2'): ∀σ ∈ Σ, α -σ ≥ 0 =⇒ ℜ σ, λ > 0. The proof of implication (1)⇒(2'
) is essentially the same as in Proposition 4.15. To show the contrapositive of (2')⇒( 1), let k be such that

ℜ(λ k ) ≤ 1/2 and α k > 0. Let σ = 1 2 α k (2δ k -δ 1 ). It follows immediately from (35) that σ ∈ Σ. Furthermore, α -σ ≥ 0 and ℜ σ, λ = α k (ℜ(λ k ) - 1
2 ) ≤ 0. This claim gives another "universal" aspect of the cone Σ in the phase transition phenomena between small and large processes (see Relation (34), Theorem 4.20 and proof of Theorem 3.4).

Polyhedra A α

Take a Pólya process and fix a Jordan basis of linear forms (u k ) 1≤k≤s . Notations relative to this basis are defined in Section 2. Remember that δ k is the k-th vector N. Pouyanne: Pólya processes, April 2005; revised September 2006 of the canonical basis of R s . Definition 4.17 For any α ∈ (Z ≥0 ) s , let A α be the subset of (Z ≥0 ) s defined by

A α = (α -D α ) ∩ (Z ≥0 ) s , ( 39
)
where D α is the set of R ≥0 -linear combinations of all vectors δ kδ k-1 such that α k ≥ 1 and ε k = 1 (as in (37), α -D α denotes {αd, d ∈ D α }).

These subsets are finite because β < βδ k + δ k-1 for the degree-antialphabetical order defined by [START_REF]Pólya Sur quelques points de la théorie des probabilités[END_REF]. Geometrically speaking, A α is the set of integer points of the convex compact polyhedron of codimension ≥ 2 defined by intersection of (R ≥0 ) s with the rational cone α-D α (and A α itself is abusively called polyhedron).

When α is a semisimple power, all ε k vanish so that D α = (0) and A α = {α}. The polyhedra A α play thus a role only for non semisimple Pólya processes. Properties of A α 's that will be used in the sequel are listed in the following proposition. Definition of the differential operator Φ ∂ was given in (28).

Proposition 4.18 Let α ∈ (Z ≥0 ) s . 1-If α is a semisimple power, then A α = {α}.
2-If α is a power of large (respectively small) projections, then every element of A α is a power of large (resp. small) projections.

3

-α ∈ A α and Span{u β , β ∈ A α } is Φ ∂ -stable.
Proof. Justification of 1-was given just before Proposition 4.18. If α is a power of large (respectively small) projections, Assertion 2-can be deduced from A α 's definition (39) by induction on α (degree-antialphabetical order): if α k ≥ 1 and ε k = 1, then αδ k + δ k-1 is < α and a power of large (resp. small) projections. It remains to prove 3-. Assertion α ∈ A α is an obvious consequence of Definition 4.17. Moreover, Jordan basis properties (see Subsection 2.1) imply that Φ ∂ (u

1 ) = u 1 and Φ ∂ (u k ) = λ k u k + ε k u k-1 if k ≥ 2
, where ε k ∈ {0, 1}. Formula (29) shows that for every β, Φ ∂ (u β )-β, λ u β is linear combination of polynomials u γ , where

γ = β-δ k +δ k-1 for integers k ≥ 2 such that β k ≥ 1 and ε k = 1 (hence λ k = λ k-1
). These considerations suffice to prove 3-.

Proposition 4.19 Take a Pólya process, choose any Jordan basis and denote λ = (λ 1 , . . . , λ s ) its root's s-uple (see [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF]). Then, for every α, α ′ ∈ (Z ≥0 ) s ,

α ′ ∈ A α =⇒ α ′ , λ = α, λ (40
S ′ α = Span{u β , β ∈ A α -Σ}. ( 41
)
Theorem 4.20 Take a Pólya process, choose a Jordan basis (u k ) 1≤k≤s and let

(Q α ) α∈(Z ≥0 ) s be the corresponding reduced polynomials. 1-For any α ∈ (Z ≥0 ) s , S ′ α is Φ -stable; ( 42
)
S ′ α = Span{Q β , β ∈ A α -Σ}. (43) 2-If α is a power of large projections, then Φ(Q α ) ∈ Span{Q β , β ∈ A α }.
Consequently, Relations (30) can be refined in the general case by means of (43) and Proposition 4.8; this provides straightforwardly

u α = Q α + β∈Aα-Σ, β,λ = α,λ q α,β Q β . ( 44
) Proof. 1-We first prove that S ′ α is Φ-stable. Let β ∈ A α -Σ; let α ′ ∈ A α and σ ∈ Σ such that β = α ′ -σ. We show that both Φ ∂ (u β ) and (Φ -Φ ∂ )(u β ) belong to S ′ α . • As in Proposition 4.18's proof, Φ ∂ (u β ) -β, λ u β is a linear combination of polynomials u γ , where γ = β -δ k + δ k-1 for integers k ≥ 2 such that β k ≥ 1 and ε k = 1 (hence λ k = λ k-1 ). If γ is such a power, we claim that γ ∈ A α -Σ, which shows that Φ ∂ (u β ) ∈ S ′ α . If α ′ k ≥ 1, just write γ = α ′′ -σ where α ′′ = α ′ -δ k + δ k-1 ∈ A α . If α ′ k = 0, this α ′′ is not in A α because it is not nonnegative; in this case, write γ = α ′ -σ ′ where σ ′ = σ + δ k -δ k-1 .
(σ ′ ) = δ * I (σ)-1 = δ * I∪{k} (σ)-σ k -1; but σ k = -β k ≤ -1 because β k ≥ 1. Thus δ * I (σ ′ ) ≥ δ * I∪{k} (σ)
≥ 0 since σ ∈ Σ (note that this last inequality is true even if I ∪ {k} = {1, . . . , s} because (1, . . . , 1) ∈ Σ, see Remark 4.13).

• Taylor formula implies that (Φ -Φ ∂ )(u β ) is linear combination of polynomials u γ = u β-η+δ k with 1 ≤ k ≤ s, η ≥ 0, |η| ≥ 2, βη ≥ 0 (the η-terms correspond to partial derivatives of order ≥ 2 of u β , the δ k -terms come from the expansion of linear forms l k in the Jordan basis (u k ) k ). If γ = βη + δ k is such a power and if δ * I is the equation of any one of the defining hyperplanes of Σ where I is a proper subset of {1, . . . , s} (see Corollary 4.14), then 1 and2 for a representation of powers βγ = ηδ k that appear in this computation).

δ * I (β -γ) = δ * I (η -δ k ) = |η| -1 + i∈I η i -1 k∈I ≥ 1 -1 k∈I + i∈I η i ≥ 0.
Φ -Φ ∂ )(u β ) belongs to Span{u γ , |γ| ≤ |β| -1, γ ∈ β -Σ}. If γ = β -σ ′ ∈ β -Σ, then γ = α ′ -(σ + σ ′ ) ∈ α ′ -Σ because the cone Σ is stable under addition. This shows that (Φ -Φ ∂ )(u β ) ∈ S ′ α (see Figures
Thus, S ′ α is a Φ-stable subspace of S α . For any

β ∈ A α -Σ, the projection of u β on S ′ α ∩ ker(Φ -β, λ ) ∞ parallel to S ′ α ∩ z = β,λ ker(Φ -z) ∞ equals Q β because
of the unicity of the decomposition on characteristic spaces. Hence Q β ∈ S ′ α (another way to show that fact consists in noting that the projections on these characteristic spaces are polynomial functions of the restriction of Φ to S ′ α ). Thus, Span{Q β , β ∈ A α -Σ} is a subspace of S ′ α ; as these two subspaces have the same finite dimension, they are equal. The proof of 1-is complete.

2-Because of Assertion (5) in Proposition 4.8 and of the Φ-stability of

S ′ α , Φ(Q α ) ∈ Span{Q β , α < β, β ∈ A α -Σ, β, λ = α, λ }.
Conclude with 1-of Proposition 4.15 and Proposition 4.19.

Remark 4.21 (On the minimality of cone Σ and polyhedra A α ) Cone Σ appears in a natural way in the proof of Theorem 4.20 to ensure the Φ-stability of a (minimal) subspace that contains some given u α . Indeed, suppose for simplicity that α is a semisimple power. Then Φ(u α ) is the sum of α, λ u α and of a linear combination of polynomials u α-η+δ k where η ≥ 0, |η| ≥ 2 and 1 ≤ k ≤ s. The iterations of Φ on such polynomials force to consider the least (for inclusion) set of powers that contains these ηδ k and that is stable under addition (and contains zero); this least set is Σ. For an illustration of this fact, see Figures 1 and2. If α is not semisimple, the situation is complicated by other powers α ′ of same total degree and leads to consider the polyhedron A α .

Suppose that B ⊆ (Z ≥0 ) s is such that α ∈ B and Span{u β , β ∈ B} is Φ ∂stable. As in the end of Proposition 4.18's proof, Formula (29) shows that A α ⊆ B, so that A α is minimal for properties 3-of Proposition 4.18. These properties are necessary to imply Formulae (43) and (44). The optimality of A α , announced in the introduction of Subsection 4.4, consists in that fact.

A shorter proof of Theorem 3.4 can nevertheless be given without considering Σ. See Remark 5.5.

Proof of Theorem 3.4, asymptotics of moments

The proof of Theorem 3.4 relies on Formula (44) in which the expectation of the value at X n is taken, providing We first use Corollary 4.2 to make asymptotics of reduced moments EQ β (X n ) precise in Proposition 5.1 before giving a proof of Theorem 3.4. Numbers ν α were defined by ( 21) and appear naturally in Theorem 3.4; Subsection 5.2 is devoted to their computation in the case of powers of large projections.

E u α (X n ) = EQ α (X n ) + β∈Aα-Σ, β,λ = α,λ q α,β EQ β (X n ). ( 45
5.1 Proof of Theorem 3.4

Proposition 5.1 (Asymptotics of reduced moments)

Let α ∈ (Z ≥0 ) s . 1-If ν α = 0, i.e. if Q α is eigenfunction of Φ, then, as n tends to infinity, EQ α (X n ) = n α,λ Γ(τ 1 ) Γ(τ 1 + α, λ ) Q α (X 1 ) + O(n α,λ -1 ).
2-If ν α ≥ 1, then, as n tends to infinity,

EQ α (X n ) = n α,λ log να n ν α ! Γ(τ 1 ) Γ(τ 1 + α, λ ) (Φ -α, λ ) να (Q α )(X 1 ) + O(n α,λ log να-1 n).
Proof. Q α belongs to the Φ-stable subspace S(α) = ker(Φα, λ ) ∞ and the operator induced by Φ on S(α) is the sum of α, λ Id S(α) and of the nilpotent operator induced on S(α) by Φα, λ . This facts being considered, Proposition 5.1 is a straightforward consequence of Corollary 4.2.

Remark 5.2 Even if α is a semisimple power, Q α may not be an eigenfunction of Φ. This happens only if α, λ = β, λ for some β < α because this implies that both Q α and Q β are in the same characteristic subspace of Φ. When all roots λ k are incommensurable, i.e. whenever they admit no non trivial linear relation with rational coefficients, all numbers α, λ are distinct, so that every Q α is an eigenfunction of Φ.

Proof of Theorem 3.4. Proposition 5.1 asserts in particular that for all β ≤ α, there exists ν ≥ 0 such that EQ β (X n ) ∈ O n ℜ β,λ log ν n . 1-If α is a power of small projections, then any α ′ ∈ A α satisfies |α ′ | = |α| and is a power of small projections (Proposition 4.18). Hence n β,λ ∈ O n |α|/2 if β ∈ α ′ -Σ, as can be deduced from Proposition 4.15.

2-If α is a power of large projections, then any α ′ ∈ A α satisfies α ′ , λ = α, λ and is power of large projections. Hence, for every β ∈ α ′ -Σ, α ′ = β or ℜ β, λ < ℜ α, λ (Proposition 4.15 and Proposition 4.19). Thus, Formula (45), implies that

E u α (X n ) = EQ α (X n ) + o n ℜ α,
c = 1 ν α ! Γ(τ 1 ) Γ(τ 1 + α, λ ) (Φ -α, λ ) να (Q α )(X 1 ).
This follows from Proposition 5.1 and from Theorem 3.4's proof.

Remark 5.4 More precision on the small o of Assertion 3-in Theorem 3.4 can be deduced from its proof: one can replace it by O (n a ) where

a = max {ℜ β, λ , β = α, β ∈ α -Σ} ∪ {ℜ α, λ -1} .
Remark 5.5 One can give a shorter proof of Theorem 3.4 without explicitely considering Σ. The following arguments, that provide a self-sufficient independent proof, have been suggested by the anonymous referee. For any β = (β 1 , . . . , β s ) ∈ (Z ≥0 ) s and any z ∈ C, let's define β [z] = 1≤k≤s, λ k =z β k (this number being 0 by convention if there is no k such that λ k = z), and let

Γ =    β ∈ (Z ≥0 ) s , z, β [z] ≥0 β [z] + 2 z, β [z] ≤0 β [z] ≥ 0    .
Then Γ is stable under addition (it is a convex cone) and the subspace

F α = Span{u β , β ∈ (Z ≥0 ) s ∩(α-Γ)
} is thus Φ-stable as can be seen from Equation (29) and from the proof of Proposition 3.1, page 19. The fact that F α is Φ-stable implies that Q β ∈ F α for all β ∈ (Z + ) s ∩ (α -Γ); indeed, Q β can be seen as the projection of u β on F α ∩ ker(Φβ, λ ) ∞ parallel to F α ∩ z = β,λ ker(Φz) ∞ , because of the unicity of the decomposition on characteristic spaces. Therefore,

F α = Span{Q β , β ∈ (Z ≥0 ) s ∩(α-Γ)}.
Besides, Γ has the following two properties: (a) if α is a power of large projections, then β ∈ α -Γ and

β, λ = α, λ imply ℜ β, λ < ℜ α, λ ; (b) if α is a power of small projections, then ℜ β, λ ≤ |α|/2 for any β ∈ (Z ≥0 ) s ∩ (α -Γ). [Proof of (a): if γ = α -β is such that (γ [z] ) z∈C = 0, then ℜ γ, λ = γ k ≥0 γ k ℜλ k + γ k ≤0 γ k ℜλ k > 1 2 γ k ≥0 γ k + γ k ≤0 γ k ≥ 0.
β , β ∈ A α or β = α -σ, σ ∈ Γ, (σ [z] ) z∈C = 0} is Φ-stable.
In any case, Σ ⊆ Γ. When all roots of the process are distincts, then Γ = Σ. Otherwise, the cone Γ (more precisely Γ ⊗ R) is not strictly convex (it contains a nonzero vector subspace of R s ). Consequently, since Σ is strictly convex, Γ = Σ if and only if all roots of the process are distinct. Compare this fact with the minimality of Σ asserted in Remark 4.21.

Computation of nilpotence indices ν α

For any α ∈ (Z ≥0 ) s , the number ν α has been defined in Section 3 as the nilpotence index of Q α for Φ, i.e.

ν α = max{p ≥ 0, (Φ -α, λ ) p (Q α ) = 0}.
It appears in the expression of the leading term of the u-moment E u α (X n ) as n tends to infinity, when α is a power of large projections (Theorem 3.4).

In several problems where these moments' asymptotics are needed, it is useful to compute them explicitely. To this end, iterations of the finite difference operator Φ are not easily handled; furthermore, a calculation of ν α from its definition supposes that the reduced polynomial Q α has already been computed. These two facts make a direct computation of ν α rather intricate. Whenever α is a power of large projections, Proposition 5.6 asserts that ν α is the nilpotence index of u α for the differential operator Φ ∂ , making its computation much easier.

Proposition 5.6 (Computation of ν α )

1-If α is a power of large projections, then

ν α = max{q ≥ 0, (Φ ∂ -α, λ ) q (u α ) = 0}.
2-If α = (α 1 , . . . , α s ) is a monogenic power of large projections whose support is contained in the monogenic block of indices J = {m, . . . , m + r} (r ≥ 0), then

ν α = r k=0 kα m+k .
Proof. 1-There is nothing to prove if α is a semisimple power. We thus suppose that α is a large and not semisimple power. We denote by k α the index k α = min{k ≥ 3, α k ≥ 1, ε k = 1} and p(α) the element of A α defined by p(α) = αδ kα + δ kα-1 ; it is the predecessor of α for the degree-antialphabetical order restricted to A α . As a direct computation of Φ ∂ (u α ) shows (see (29) in the proof of Proposition 4.6), Proposition 4.18 implies that where Y n = πX n and Z n = π ′ X n .

(Φ ∂ -α, λ )(u α ) -α kα u p(α) ∈ Span{u β , β ∈ A α , β < p(α)}. (46)
• First term π 1 X n Definitions of the Jordan basis (u k ) k of linear forms and of its dual basis (v k ) k of vectors imply readily that π 1 (v) = u 1 (v)v 1 for any vector v. Thus, because of Relation (6), π 1 X n = nv 1 + O(1) as n tends to infinity; this projection is non random.

• Second term Y n

As follows from [START_REF] Janson | Congruence properties of depths in some random trees[END_REF],

Y n = r k=2 u k (X n )v k . Take any k ∈ {2, . . . , r}. Compu- tation of the expectation of u k (X n+1 ) conditionally to the state at time n gives E Fn u k (X n+1 ) = (1 + λ k /(n + τ 1 -1))u k (X n ) for any positive integer n (see (25), u k is an eigenform of the process); this implies that (γ τ1,n (λ k ) -1 u k (X n )) n is a martingale (one can divide by γ τ1,n (λ k ) because λ k is not a negative integer).
As u k (complex conjugacy) is an eigenform associated to the eigenvalue λ k , it is a linear combination of eigenforms u l 's, all associated with λ k . Thus, if q ≥ 1 is an integer, |u 2q k | is a linear combination of polynomials u α 's for some suitable semisimple powers of large projections α's such that α, λ = 2qσ 2 . This implies, thanks to Theorem 3.4, that

E|u 2q k (X n )| = O(n 2qσ2 ).
Note that this is valid even if λ k is real. The martingales γ τ1,n (λ k ) -1 u k (X n ) are consequently all convergent in every L p space, p ≥ 1.

For every k ∈ {2, . . . , r}, let W k be the (complex) random variable defined by

W k = lim n→+∞ u k (X n ) γ τ1,n (λ k ) Γ(τ 1 ) Γ(τ 1 + λ k ) = lim n→+∞ u k X n /n λ k
the second equality coming from Stirling's asymptotics as n tends to infinity:

γ τ1,n (λ)Γ(τ 1 + λ) = Γ(τ 1 )n λ (1 + o(1)),
for every λ / ∈ -τ 1 + Z ≤0 . This shows that

Y n = 2≤k≤r n λ k W k v k + o(n σ2
), the small o being almost sure and in L p for any p ≥ 1.

Computation of joint moments' limits: if α = (0, α 2 , . . . , α r , 0, . . . ) ∈ (Z ≥0 ) s , α is a semisimple power of large projections and if one denotes

W α = k W α k k , Theorem 3.4 implies that EW α = lim n→+∞ 1 n α,λ E u α (X n ) = Γ(τ 1 ) Γ(τ 1 + α, λ ) Q α (X 1 ). • Third term Z n Z n = k≥r+1 u k (X n )v k .
We show that n -σ2 u k (X n ) converges to zero almost surely and in every L p space (p ≥ 1), for every k ≥ r + 1. Take any k ≥ r + 1 and any integer q ≥ 1. As above, u k is a linear combination of u l 's, all associated with the root λ k (even if u k and the u l 's are not necessarily eigenforms). Thus, N. Pouyanne: Pólya processes, April 2005; revised September 2006

|u 2q
k | is a linear combination of polynomials u α 's for some suitable α's that are powers of large (respectively small) projections if ℜλ k > 1/2 (resp. if ℜλ k ≤ 1/2), such that α, λ = 2qℜλ k . Because of Theorem 3.4, this implies in any case that

E|u 2p k (X n )| ∈ o(n 2pσ2
), which gives the L p convergence. Furthermore, let p be any positive integer such that 1/p < 2(σ 2 -ℜλ k ) if ℜλ k > 1/2 or such that 1/p < 2σ 2 -1 if not; for such a p, the series

n E 1 n σ2 u k (X n ) 2p
converges. The almost sure convergence to zero of n -σ2 u k (X n ) follows thus from the almost sure convergence of the series of nonnegative random variables

n 1 n σ2 u k (X n ) 2p ,
and the proof of Theorem 3.5 is complete.

Proof of Theorem 3.6. We adopt the notations of Section 2. For any monogenic block of indices J, we denote by π J the projection π J = k∈J π k .

• Claim If J is a monogenic block of indices associated with a root λ having a real part σ > 1/2, then γ τ1,n (π J A) is invertible and γ τ1,n (π J A) -1 π J X n is a martingale that converges in L p for every p ≥ 1 (thus almost surely). If M J denotes the limit of this martingale and if ν = #J -1, then

π J X n = n λ log ν n ν! Γ(τ 1 ) Γ(τ 1 + λ) u min J (M J )v max J + o (n σ log ν n) ( 50
)
as n tends to infinity, the small o being almost sure and in L p for every p ≥ 1. Furthermore, almost surely and in L p for every p ≥ 1,

u min J (M J ) = Γ(τ 1 + λ) Γ(τ 1 ) × lim n→∞ u min J (X n ) n λ . ( 51
)
• Proof of the claim. The endomorphism γ τ1,n (π J A) is invertible because every Id +π J A/(k + τ 1 -1) is (its unique eigenvalue has a real part > 1). Since J is a monogenic block of indices, A and π J commute. Thus M n = γ τ1,n (π J A) -1 π J X n is a martingale (see (25) with f = π J and Remark 4.4 in Subsection 4.1). We show that for any k ∈ J, the quadratic variation of the martingale u k (M n ) is almost surely bounded, which suffices, thanks to Burkholder's Inequality for discrete time martingales (see [START_REF] Hall | Martingale Limit Theory and Its Applications[END_REF] for example), to ensure that the projection u k (M n ) is bounded in L p for every p ≥ 1, hence the validity of the convergence part of the claim.

u k (M n+1 ) -u k (M n ) ∈ O log k-2 n n ℜλ
almost surely as n tends to infinity. In particular, |u k (M n+1 )u k (M n )| 2 is almost surely the general term of a convergent series: the quadratic variation of the martingale (u k (M n )) n is almost surely bounded and the convergence part of the claim is proved. Almost surely and in L p for every p ≥ 1,

π J X n = γ τ1,n (π J A) γ τ1,n (π J A) -1 π J X n = γ τ1,n (π J A)(M J + o(1))
as n tends to infinity. As for equation ( 52), one has

γ τ1,n (π J A) = γ τ1,n (λ + N )π J = ν+2 k=2 k-2 q=0 1 q! γ (q) τ1,n (λ)u k-q v k
and the asymptotics of the derivatives of γ τ1,n (see ( 27)) implies

π J X n = n λ log ν n ν! Γ(τ 1 ) Γ(τ 1 + λ) u 2 (M J )v ν+2 + o (n σ log ν n)
which is the expected result (50) on π J X n . Equation (52) shows that u 2 (M n ) = β n (λ)u 2 (X n ) and makes the proof of the claim complete with the help of (55).

• As in the proof of the large and principally semisimple case (Theorem 3.5), π 1 X n = (n + τ 1 -1)v 1 , and the process splits into the sum

X n = nv 1 + r k=2 π J k X n + Y n + Z n
where Y n = J π J X n the sum being extended to all monogenic blocks of indices different from any J k that correspond to roots having real parts > 1/2 and Z n = {k, ℜλ k ≤1/2} π k X n . We study separately all terms of this decomposition. • Because of Theorem 3.4 part 1-, as in the end of the proof of the large and principally semisimple case, Z n ∈ o(n σ2 log ν n) almost surely and in L p for every p ≥ 1 (remember that

π k X n = u k (X n )v k ).
• Every J in the definition of Y n satisfies the assumption of the claim with a root's real part < σ 2 or a cardinality ≤ ν. Thus almost surely and in L p for every p ≥ 1,

Y n = o(n σ2 log ν n)
as n tends to infinity. • For every k ∈ {2, . . . , r}, J k satisfies the assumption of the claim and if one denotes

W k = lim n→∞ u min J k (X n ) n λ(J k ) , one obtains π J k X n = 1 ν! n λ(J k ) log ν nW k v max J k + o (n σ2 log ν n)
almost surely and in L p for every p ≥ 1, which completes the proof of (23). Note that u min J k is an eigenform of A and that γ τ1,n (λ(J k )) -1 u min J k (X n ) is an L ≥1convergent complex-valued martingale.

• Take any α 2 , . . . , α r ∈ Z ≥0 . Then α = 2≤k≤r α k δ min J k is a semisimple power of large projections, and

E   2≤k≤r W α k k   = lim n→∞ 1 n α,λ E u α (X n ) = Γ(τ 1 ) Γ(τ 1 + α, λ ) Q α (X 1 )
as can be deduced from Assertion 3-in Theorem 3.4. This completes the proof of Theorem 3.6.

Remarks and examples

7.1 Some remarks 1-Average case study of a Pólya process If (X n ) n is a large Pólya process, its asymptotic expectation can readily be deduced from Theorems 3.5 and 3.6. Without using the whole result, if (X n ) n is any Pólya process, one can simply argue as follows. Thanks to Relation [START_REF] Janson | Congruence properties of depths in some random trees[END_REF], EX n = 1≤k≤s Eu k (X n ).v k . If J is any monogenic block of indices, the subspace Span{u k , k ∈ J} is Φ-stable so that Proposition 5.1 (which is elementary) applies.

Hence Eu k (X n ) ∈ O(n ℜλ k log ν δ k n) when λ k = 1 and Eu k (X n ) = nu k (X 1 ) + O(1)
when λ k = 1 (in order to directly apply Proposition 5.1, remember that u k = Q δ k ). These facts imply the following result, already given in [START_REF] Athreya | Embedding of urn schemes into continuous time Markov branching processes and related limit theorems[END_REF] when 1 is simple root. Proposition 7.1 If Π 1 = {k, λ k =1} π k denotes the projection on the eigensubspace ker(A -1), then, as n goes off to infinity,

E(X n ) = nΠ 1 (X 1 ) + O(n τ )
where τ = max ({ℜ(λ), λ ∈ Sp(A), λ = 1} ∪ {0}). When 1 is a simple root of a Pólya process (X n ) n , the normalisation X n /n converges almost surely and in L ≥1 to the non random vector v 1 . This can be deduced from Theorem 3.4 and Decomposition (49), by arguments like in the end of Theorem 3.5's proof. This result is valid for small and large processes, without any irreducibility-type condition (compare with [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF]).

3-Small Pólya processes

As it has been told in Section 1, a small irreducible Pólya process has a Gaussian limit after normalisation (for a precise meaning of the present notion of irreducibility and complete results, see [START_REF] Athreya | Embedding of urn schemes into continuous time Markov branching processes and related limit theorems[END_REF] and [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF]). When the irreducibility assumption is released, this normality fails down. This fact can be explained by our treatment. We illustrate it in details in dimension 2.

Take the general two-dimensional Pólya process and choose coordinates such that the forms l k are the coordinates forms in R 2 . The matrix of the replacement endomorphism A have then the form 1a b a

1b where a and b are nonnegative reals (with restrictive conditions (3) if at least one of them is > 1). The process is small whenever a + b ≥ 1/2 because σ 2 = 1ab. Let's assume for our example that a + b > 1/2. If one makes the choice u 2 = axby, computation of the first reduced polynomials shows that

u 2 2 = Q (0,2) -(a -b)(1 -a -b)u 2 + ab(1 -a -b) 2 2(a + b) -1 u 1 . (56)
The term of Eu 2 2 (X n ) having the highest order of magnitude is Eu 1 (X n ) = nu 1 (X 1 ), but its coefficient is zero if a or b vanish or if a + b = 1. Such considerations justify the fact that the study of small triangular urns, that are not irreducible, has to be done separately in terms of asymptotics and limit laws (see [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF], [START_REF] Janson | Limit theorems for triangular urn schemes[END_REF], [START_REF] Puyhaubert | Modèles d'urnes et phénomènes de seuils en combinatoire analytique[END_REF]).

In arbitrary dimension s, one can refine the error term in Assertion 1-of Theorem 3.4, but this refinement requires more careful use of the replacement endomorphism. This fact comes from the expansion E u α (X n ) = EQ α (X n ) + β<α q α,β EQ β (X n ): if α is a power of small projections, the term in the equality's second member having the highest order of magnitude as n goes off to infinity is not necessarily EQ α (X n ), but EQ α (X n ) may nevertheless be the winner if suitable coefficients q α,β vanish.

4-Limit random variables W k

As it can be seen in the proof of Theorem 3.5, for any k ∈ {2, . . . , r}, the random variable W k is defined as the limit of the process u k (X n )/n λ k as n tends to infinity. This convergence is almost sure and in any L p , p ≥ 1 and is proved by martingale techniques.

N. Pouyanne: Pólya processes, April 2005; revised September 2006

To know whether W k is zero or not, it is sufficient to check the nullity of

EW 2 k = Γ(τ 1 )Q 2δ k (X 1 )/Γ(τ 1 + 2λ k ) when W k is real-valued (that is when λ k is real), or of E|W k | 2 = Γ(τ 1 )Q δ k +δ k ′ (X 1 )/Γ(τ 1 + 2ℜλ k ) when W k is not real-valued (i.e. when λ k ∈ C \ R),
where k ′ is such that u k = u k ′ (conditionally to the choice of a suitable Jordan basis).

Questions: what can be said about these variables? Are the laws of the W k always determined by their moments? Can they always be described in terms of known densities or other distributions?

All these remarks and questions can readily be adapted to limit variables W k of Theorem 3.6.

5-Conjugate replacement endomorphisms

In the asymptotic almost sure expansions ( 22) or (23), σ 2 , the complex numbers λ k and λ(J k ) and the integer ν depend only on the conjugacy class of the replacement endomorphism A. On the contrary, the distributions of the random variables W k depend on the increment vectors w k and on the linear forms l k (and on initial condition X 1 ), but not only on the conjugacy class of A = k l k ⊗ w k : two processes having conjugate replacement endomorphisms have the same asymptotic form ( 23), but have in general different limit laws W k . For example, the two standardized large urns having R = 1 0 9/20 11/20 and R ′ = 3/4 1/4 1/5 4/5 as (conjugate) replacement matrices have respective second reduced polynomials 56), evident notations). The algebraic relations satisfied by the moments of W and W ′ are not of the same kind.

Q (0,2) = u 2 (u 2 + 11/20) (see (58)) and Q ′ (0,2) = u ′ 2 2 -11 400 u ′ 2 + 121 800 u ′ 1 (see (
Another way to formulate this remark, as suggested by the referee, is the following. Two processes may have the same replacement endomorphism A (which is the restriction of Φ over linear forms) without having the same transition operator Φ: this will imply in general different Q α 's, even though the asymptotic form will be of the same nature. Note however that having the same replacement endomorphism A does not mean having the same linear forms l k and increment vectors w k .

A natural question arises: when two processes have conjugate (or equal) replacement endomorphisms, are their limit laws connected by some functional relation?

Examples

1-Pólya-Eggenberger urns

As stated in Section 1, any Pólya-Eggenberger urn is a Pólya process after standardization, i.e. after division by S in order to get balance equal to 1. For further developments of examples on the general two dimensional urn process, on some N. Pouyanne: Pólya processes, April 2005; revised September 2006 generic examples in dimension 5 and on the so-called s-dimensional cyclic urn whose (semisimple) replacement matrix is

       0 1 0 0 1 0 . . . 1 1 0       
, see [START_REF] Pouyanne | Classification of large Pólya-Eggenberger urns with regard to their asymptotics[END_REF] (the cyclic urn defines a small Pólya process if and only if s ≤ 6 because σ 2 = cos(2π/s)). In the present article, see (57) for some developments on the general triangular urn with two colours; other considerations are made on the same subject in [START_REF] Puyhaubert | Modèles d'urnes et phénomènes de seuils en combinatoire analytique[END_REF].

2-Triangular urns with two types of balls.

The general two-dimensional balanced triangular Pólya urn (generalized to real numbers) has the following R as replacement matrix:

R = 1 0 1 -ℓ ℓ , ( 57
)
where ℓ is any real number ≤ 1. In terms of Pólya process, this means that l 1 and l 2 are the coordinate forms, w 1 = t (1, 0) and w 2 = t (1ℓ, ℓ). If one chooses u 2 (x, y) = y as second form for a Jordan basis, a straightforward computation shows that for any integer p ≥ 0, one has

Q pδ2 = u 2 (u 2 + ℓ) . . . (u 2 + (p -1)ℓ)
and Φ(Q pδ2 ) = pℓQ pδ2 (the simple computation of the image by Φ of the product u 2 (u 2 + ℓ) . . . suffices to show that this product equals Q pδ2 ). Reversing this last formula leads, for any integer p ≥ 0, to

u p 2 = p k=1 (-ℓ) p-k p k Q kδ2 (58)
where p k denote Stirling numbers of the second kind (see for example [START_REF] Graham | Concrete Mathematics[END_REF] for this reversion formula).

In particular, if ℓ > 0, since the order of magnitude of EQ pδ2 (X n ) is n pℓ (Proposition 5.1), Eu 2 (X n /n ℓ ) p tends to ℓ p × Γ(x 1 + y 1 )/Γ(x 1 + y 1 + pℓ) × Γ(y 1 /ℓ + p)/Γ(y 1 /ℓ) as n tends to infinity, where X 1 = t (x 1 , y 1 ) is the initial composition of the urn. This shows the convergence in distribution of (X nnv 1 )/n ℓ = u 2 (X n /n ℓ )v 2 to the law having the written above expression as p-th moment (the asymptotics of the computed p-th moment as p tends to infinity shows by means of Stirling formula that the limit law is determined by its moments, proving the convergence in law; see for example [START_REF] Billingsley | Probability and measure[END_REF] for relations between convergence of moments N. Pouyanne: Pólya processes, April 2005; revised September 2006 and convergence in distribution). For descriptions of this limit laws in some very particular cases of parameters X 1 and ℓ in terms of stable laws or Mittag-Leffler distribution, one can refer to [START_REF] Puyhaubert | Modèles d'urnes et phénomènes de seuils en combinatoire analytique[END_REF] or [START_REF] Janson | Limit theorems for triangular urn schemes[END_REF]. When ℓ > 1/2, the process is large so that this convergence is almost sure and in any L p , p ≥ 1.

The case ℓ = 0 is degenerate: the process is deterministic. When ℓ < 0, as EQ pδ2 (X n ) ∈ O(n pℓ ) (in any case, even if τ 1 +pℓ is a nonpositive integer), Formula (58) implies that Eu 2 (X n ) p = O(n ℓ ) for any p. In this case, u 2 (X n ) tends almost surely to zero because balls of the second type can never be added (see for example [START_REF] Janson | Limit theorems for triangular urn schemes[END_REF], Section 2, Degenerate cases).

One can compare this to the results of [START_REF] Puyhaubert | Modèles d'urnes et phénomènes de seuils en combinatoire analytique[END_REF] and [START_REF] Janson | Limit theorems for triangular urn schemes[END_REF]. It can easily be generalized to some classes of triangular urns of higher dimension, principally semisimple or not (with enough zero entries, see [START_REF] Pouyanne | Classification of large Pólya-Eggenberger urns with regard to their asymptotics[END_REF] for examples).

3-Example of random replacement matrices

The following example of urn process comes from a private communication of Bernard Ycart. Take an urn containing first b black balls, w white balls and one red ball. As in the case of Pólya urn processes, one draws successively balls from the urn, with the following replacement rule. If a black (respectively white) ball is drawn, replace it in the urn together with another black (resp. white) one. If the red ball is drawn, replace it in the urn together with a black one with probability p ∈ [0, 1] or a white one with probability 1p.

As it is described, this urn process is not Pólya. But it is equivalent to the Pólya process defined in R 4 by: the l k are the coordinate forms, the replacement matrix (i.e. the matrix whose rows are the coordinates of the w k ) is

R =    
1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0     , and the initial vector is (b, w, p, 1p). It can be viewed as "non-integer" fourcolour Pólya-Eggenberger urn process, the colours being black, white, dark red and light red, the replacement matrix being R. Only the non-integer initial vector prevents our first problem from being a true Pólya-Eggenberger urn process. The matrix R admits 1 as double root, so that X n /n converges almost surely and its limit has Dirichlet distribution (see example 7-).

This example can easily be generalised to other replacement rules, provided that one never adds any red ball.

4-m-ary search trees

"m-ary search trees are fundamental data structures in computer science used in searching and sorting " (citation from [START_REF] Fill | The space requirements of m-ary search trees: distributional asymptotics for m ≥ 27[END_REF]). The space-requirements vector of an m-ary search tree under the random permutation model is an m -1-dimensional N. Pouyanne: Pólya processes, April 2005; revised September 2006 Pólya process as can be seen in [START_REF] Chauvin | Pouyanne m-ary search trees when m ≥ 27: a strong asymptotics for the space requirements[END_REF]. It only appears under the form of an urn process after some suitable change of coordinates. The associated endomorphism A is semisimple and the process is large if, and only if m ≥ 27. One can find further developments on this large process in [START_REF] Pouyanne | Classification of large Pólya-Eggenberger urns with regard to their asymptotics[END_REF]. See [START_REF] Chern | Phase changes in random m-ary search trees and generalized quicksort[END_REF], [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF] and [START_REF] Fill | The space requirements of m-ary search trees: distributional asymptotics for m ≥ 27[END_REF] for different treatments of the subject.

5-Random 2 -3-trees

This example comes from data structures in computer science too. The repartition of external nodes of a random 2 -3-tree having 1 or 2 sisters is the twodimensional Pólya-Eggenberger urn process with initial condition X 1 = t (2, 0) and replacement matrix -2 3 4 -3 . This process is small (σ 2 = -6) and principally semisimple. It follows from [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF] that its second order term has normal distribution. This example is the base example of [START_REF] Flajolet | Pekari Analytic urns[END_REF]. If one goes one step further, one can distinguish external nodes of a random 2 -3 tree with regard to the shape of the descendants-tree of their grand-mothers. This process is a 10-dimensional urn process with balance 1. Its replacement matrix

R =                 -4 2
               
contains negative off-diagonal entries. This does not prevent the urn to be tenable (for "physical" reasons, as first argument!). Indeed, the columns of R containing these negative entries are coupled in the following sense: if j = k and r j,k < 0, then the columns of r j,k and r k,j are proportional. These proportionalities imply deterministic relations between number of balls of concerned colours. For example, at any time, the number of (algebraically) added balls of colour 9 is thrice the number of added balls of colour 8 so that when a ball of colour 8 is drawn, if one can subtract 2 balls of colour 8, one can subtract 6 balls of colour 9 as well. The same kind of property holds for balls of colours 2 and 3, and for balls of colours 6 and 7. For such reasons, the same recurrence that shows that a Pólya process does not extinguish shows that our urn is tenable. Moreover, our treatment of Pólya processes readily applies to this urn process. It is small and principally semisimple, with σ 2 = 0 (the multiplicity of the eigenvalue 0 of R is 3). Its study shows for instance that, if n is the number of external N. Pouyanne: Pólya processes, April 2005; revised September 2006 nodes of the tree, the average number of their grand-mothers is ∼ 0.182n, that on average ∼ 21% (resp. ∼ 24%) of external nodes have grand-mothers having themselves 4 (resp. 5) grand-children etc.

Patient readers can go still one step further, looking at the fourth level of genealogical trees of external nodes. This leads to the study of a 76-dimensional urn process.

6-Congruence in binary search trees

The following example is mentioned in [START_REF] Chern | Phase changes in random point quadtrees[END_REF] as a private unpublished idea of S. Janson 7 . Take a binary search tree and an integer s ≥ 2. Consider the random vector of R s whose k-th coordinate is the number of leaves whose depth is ≡ k [mod s]. This defines an s-colour urn process with (semisimple) replacement matrix

       -1 2 -1 2 -1 . . . 2 2 -1       
; the balance is one and σ 2 = -1 + 2 cos(2π/s), so that the urn is small if and only if s ≤ 8. As it is readily irreducible, it can be deduced from [START_REF] Janson | Functional limit theorem for multitype branching processes and generalized Pólya urns[END_REF] that its second order term has normal distribution when s ≤ 8. When s ≥ 9, the process is large and its asymptotics is described by Theorem 3.5.

7-Processes having 1 as multiple root

Let (X n ) n be a Pólya process having 1 as multiple root; the way to use Theorem 3.5 to determine the almost sure limit law of X n /n suggests to abandon our convention u 1 = s k=1 l k . This does not change the validity of the whole result. Let r ≥ 2 be the multiplicity of 1 as eigenvalue of A. We choose a basis (u 1 , . . . , u r ) of A-fixed linear forms (i.e. a basis of ker( t A -1)), using the classical following construction. Consider the graph G whose vertices are the numbers {1, . . . , s} and where two vertices i and j are connected by an edge when l i (w j ) = 0 or l j (w i ) = 0. Let I 1 , . . . , I r be the connected components of G (the fact that there are r such components in a consequence of what follows). For any (j, k), it is readily shown that l j (w k ) = 0 if j / ∈ I k . We define

u k = j∈I k l j
for any k ∈ {1, . . . , r}, so that u k (w j ) = 0 if j / ∈ I k and u k (w j ) = 1≤i≤s l i (w j ) = 1 if j ∈ I k . A straightforward computation shows that any u k is an A-fixed linear form. Moreover, the restriction of t A to the stable subspace spanned by the l j , j ∈ I k is irreducible so that, because of Perron-Frobenius theory, u k spans the unique line of A-fixed forms of this subspace. This shows that (u 1 , . . . , u r ) is a basis of A-fixed linear forms. This basis is then completed into a Jordan basis (u 1 , . . . , u s ) under conditions 2-of Definition 2.3.

For such a basis, One recognizes here the moments of a Dirichlet distribution with parameters u 1 (X 1 ), . . . , u r (X 1 ) whose density on the simplex {x 1 ≥ 0, . . . , x r ≥ 0, (see [START_REF] Gouet | Strong Convergence of Proportions in a Multicolor Pòlya urn[END_REF]). This distribution is obviously characterized by its moments. In reference to the original paper of Pólya, processes under this assumption have been called essentially Pólya in [START_REF] Pouyanne | Classification of large Pólya-Eggenberger urns with regard to their asymptotics[END_REF].

  of reals, the inequality α ≥ 0 will mean that all the numbers α k are ≥ 0. N. Pouyanne: Pólya processes, April 2005; revised September 2006

Remark 4 . 5

 45 The differential operator can be written as Φ ∂ (f )(v) = Df v .Av for any differentiable function f , where Df v denotes the differential of f at point v. This can be readily seen from the formula Df v .w k = ∂f ∂w k (v).

Proposition 4 . 6 (

 46 Action of Φ ∂ on the u-monomials) For any choice of a Jordan basis (u k ) 1≤k≤s of linear forms of a Pólya process, 1-for every

Remark 4 . 7

 47 One can formally extend the result of 2-in Proposition 4.6 to any family of complex numbers α 1 , . . . , α s when ∀k, k = 0 =⇒ u k is eigenform of A. This gives other eigenfunctions of Φ ∂ , defined on suitable open subsets of V or V C (usual topology). N. Pouyanne: Pólya processes, April 2005; revised September 2006

Corollary 4 .

 4 14 (faces of Σ) The cone Σ has 2 s -2 faces of dimension s -1, Pólya processes, April 2005; revised September 2006

Figure 2 :

 2 Figure 2: trace of Σ (convex hull) and of {ηδ k , η ≥ 0, |η| ≥ 2, k ∈ {1, 2, 3}} (union of three triangles) on the hyperplane {x 1 + x 2 + x 3 = 1} of R 3

)

  Proof. If β, γ and k are like in the end of Proposition 4.18's proof, γ, λ = β, λ . This fact leads to the result. N. Pouyanne: Pólya processes, April 2005; revised September 2006 4.5 Action of Φ on polynomials (continued) Adopting notations of Section 4.4, we define, for any α ∈ (Z ≥0 ) s the subspace S ′ α of S α as

  It suffices to show that σ ′ ∈ Σ. Let I be a proper subset of {1, . . . , s}, that gives the equation of a face of Σ (see Corollary 4.14). If k ∈ I or k -1 / ∈ I, then δ * I (σ ′ ) ≥ 0 because δ * I (σ) ≥ 0. If k / ∈ I and k -1 ∈ I, then δ * I

N. Pouyanne :

 Pouyanne Pólya processes, April 2005; revised September 2006 This proves that (

  ) N. Pouyanne: Pólya processes, April 2005; revised September 2006

3 -Remark 5 . 3

 353 λ has the required asymptotics as it can be deduced from Proposition 5.1. Moreover, if α is a semisimple power of large projections, then ν α = 0 (consequence of Theorem 4.20 (2-), Proposition 4.18 (1-) and ν α 's definition (21)). We conclude with Proposition 5.1. N. Pouyanne: Pólya processes, April 2005; revised September 2006 In Theorem 3.4, Assertion 3-is a particular case of Assertion 2-, the constant named c appearing in 2-being

Assertion

  (b) follows from a similar argument.] These two properties suffice to show Assertions 1-and 2-in Theorem 3.4. Likewise, Theorem 4.20 2-and Theorem 3.4 3-can be obtained by the following refinement N. Pouyanne: Pólya processes, April 2005; revised September 2006 of the argument: Span{u

N. Pouyanne :

 Pouyanne Pólya processes, April 2005; revised September 2006

N. Pouyanne :

 Pouyanne Pólya processes, April 2005; revised September 2006 as n tends to infinity. Thus (53), (54) and (55) lead to

N. Pouyanne :

 Pouyanne Pólya processes, April 2005; revised September 2006

N. Pouyanne :

 Pouyanne Pólya processes, April 2005; revised September 2006 2-Drift when 1 is simple root

s k=1 l k = r k=1 u

  k . The properties of u k 's imply in particular that for any α = (α 1 , . . . , α r , 0, . . . ),Q α = r k=1 u k (u k + 1) . . . (u k + α k -1)and that Q α is eigenfunction for Φ, associated with the eigenvalue |α| = r k=1 α k . It follows then from Theorem 3.5 that X n /n converges almost surely and in any L p , p ≥ 1 to a random vector r k=1 W k v k , where the joint moments of the real random variables W 1 , . . . , W r are given byEW α = Γ(τ 1 ) Γ(τ 1 + |α|) r k=1 Γ(u k (X 1 ) + α k )Γ(u k (X 1 )) .

r

  k=1 x k = 1} of R r is given by (x 1 , . . . , x r ) → Γ k (X 1 ))

Note that such a process is generic in the sense that almost all (in the strong sense of algebraic geometry) replacement matrices of Pólya processes satisfy this assumption.

When the context is unambiguous, if z is a complex number, z will also denote zI where I is the identity endomorphism.

In short, if 1 is multiple root, λ 1 = • • • = λr = 1; otherwise, 1 2 < ℜλ 2 = • • • = ℜλr = σ 2 < 1.See[START_REF] Graham | Concrete Mathematics[END_REF], definition of σ 2 .

In other words, if J is any Jordan block of A in the u k 's basis, J is 1 or one of the J k 's, or the size of J is ≤ ν, or the root of J has a real part < σ 2 . See Definition 2.5 (principal blocks).

S. Janson has developed his example in[START_REF] Janson | Congruence properties of depths in some random trees[END_REF] during the revision of the present article. N. Pouyanne: Pólya processes, April 2005; revised September 2006

Acknowledgements

We claim that (Φα, λ )(Q α )α kα Q p(α) ∈ Span{Q β , β < p(α)} (proof just below). With Theorem 4.20, as α is a power of large projections, this implies that

Assertions ( 46) and (47) are then sufficient to show that max{q ≥ 0, (Φα, λ ) q (Q α ) = 0} = max{q ≥ 0, (Φ ∂α, λ ) q (u α ) = 0}, this number being equal to min{q ≥ 0, p [q] (α) is a semisimple power} (notation p [q] denotes the composition p • . . . p iterated q times and p

The only point of Σ having a nonpositive degree (|.|) is zero, so that Theorem 4.20 leads to

Taking the image by Φ ∂α, λ of this last relation leads, using (48) to

Because of Assertion ( 46),

The conclusion follows from Proposition 4.8 (Assertions 2-and 4-).

2-The total degree |α| being fixed, we proceed by induction on α. If α is semisimple, α = |α|δ m and ν α = 0; there is nothing to prove. If α is not semisimple, the computation of (Φ ∂α, λ )(u α ) shows that

All these αδ k + δ k-1 are < α and have total degree |α|; by induction, they all have the same ν, this number being -1 + 0≤k≤r kα m+k . The formula for ν α is proven.

6 Proofs of Theorems 3.5 and 3.6, asymptotics of large processes

Proof of Theorem 3.5. We adopt the notations of Section 2. Let's denote π = 2≤k≤r π k and π ′ = k≥r+1 π k ; the random vector X n splits into the sum Without loss of generality, we can assume for simplicity that J = {2, . . . , ν +2}. If one denotes N = π J (Aλ), then N commutes with A and satisfies N ν = 0 and N ν+1 = 0; furthermore, elementary considerations on A, the u k 's and the v k 's show that for any nonnegative integer q and for any k ∈ {2, . . . , ν + 2}, one has N q π k = u k v k+q if k + q ≤ ν + 2 and N q π k = 0 is k + q ≥ ν + 3. In particular, for any q, one can write N q = N q ( k∈J π k ) = q+2≤k≤ν+2 u k-q v k (with the convention N 0 = π J ). Hence, if β n = 1/γ τ1,n (as formal series or rational fraction; we omit the parameter τ 1 for simplicity of notation), Taylor formula leads to

Thus, for any k ∈ {2, . . . , ν + 2}, one has

The relation β n (λ) = (1 + λ/(n + τ 1 -1))β n+1 (λ) implies, with Leibnitz formula, that 1 -

Besides, definition of the process (X n ) n (Definition 1.1) ensures that X n+1 -X n ∈ {w 1 , . . . , w s } is almost surely O(1) and consequently that X n is almost surely O(n) as n goes off to infinity (elementary induction). Hence

almost surely, as n tends to infinity. With the same tools as for the derivatives of γ τ1,n (see ( 27)), for every nonnegative integer q, β (q) n (λ) = (-1) q log q n n λ Γ(τ