Sylvain Marchand

FOURIER-BASED METHODS FOR THE SPECTRAL ANALYSIS OF MUSICAL SOUNDS

Keywords: Sound analysis, sinusoidal modeling, Fourier transform, spectral reassignment

When dealing with musical sounds, the short-time Fourier transform prevails and sinusoids play a key role, according to both acoustics (vibrating modes) and psychoacoustics (pure tones). The values obtained when decomposing the signal on the time-frequency atoms are usually assigned to their geometrical center, leading to estimation errors for the sinusoidal parameters. To correct this, one can exploit the amplitude or phase information, use the derivatives of the analysis window, or those of the audio signal. This leads to three methods (phase vocoder, spectral reassignment, derivative algorithm) equally efficient: they are in fact different formulations of the best analysis method based on the Fourier spectrum.

INTRODUCTION

Additive synthesis can be considered as a spectrum modeling technique. It is originally rooted in Fourier's theorem, which states that any periodic function can be modeled as a sum of sinusoids at various amplitudes and harmonically related frequencies. Sinusoidal modeling consists in considering the trajectories in time of the amplitude and frequency parameters of each sinusoid present in the sound. This was proposed by McAulay and Quatieri [START_REF] Mcaulay | Speech Analysis/Synthesis Based on a Sinusoidal Representation[END_REF] for speech signals and by Smith and Serra [START_REF] Smith | PARSHL: An Analysis/Synthesis Program for Non-Harmonic Sounds based on a Sinusoidal Representation[END_REF] for musical sounds. Sinusoidal modeling leads to meaningful sound representations, suitable e.g. for audio effects (time stretching, pitch shifting, etc.), audio coding, source separation, or music transcription.

The sinusoidal model being parametric, an important problem is to be able to estimate the model parameters as accurately as possible, to get high quality sounds. In this paper, we focus on estimators based on the Fourier spectrum and well-suited for musical sounds, although other approaches exist (e.g. see [START_REF] Badeau | Performance of ESPRIT for Estimating Mixtures of Complex Exponentials Modulated by Polynomials[END_REF]) and other signals could also be considered.

After a presentation of sinusoidal modeling in Section 2, Section 3 describes three methods for the estimation of the sinusoidal parameters, and Section 4 shows that they are all efficient in practice and in fact equivalent in theory: they are different formulations of the best Fourier-based analysis method.

Together with Lagrange we studied in [START_REF] Marchand | On the Equivalence of Phase-Based Methods for the Estimation of Instantaneous Frequency[END_REF] the equivalence of these estimators in the stationary case and only for one This research was partly supported by the ANR agency, DReaM project (ANR-09-CORD-006).

sinusoidal parameter (the frequency). This paper can be regarded as an extension, where spectral reassignment plays a central role.

SPECTRAL SOUND MODELING

Sinusoidal Modeling

Let us consider here the sinusoidal model under its most general expression, which is a sum of complex sinusoids / exponentials (the partials) with slow time-varying amplitudes a p and non-harmonically related frequencies ω p (defined as the first derivative of the phases φ p ). The resulting signal s is thus

s(t) = P p=1 a p (t) exp(jφ p (t)) (1)
where P is the number of partials. Since this paper focuses on the statistical quality of the parameters' estimators rather than their frequency resolution, the signal model is reduced to only one partial (P = 1). The subscript notation for the partials is then useless. Let us also define Π 0 as being the value of a given parameter Π at time 0, corresponding to the center of the analysis frame. The signal s is then

s(t) = exp    (λ 0 + µ 0 t) λ(t)=log(a(t)) +j (φ 0 + ω 0 t) φ(t)    (2)
where µ (the amplitude modulation) is the derivative of λ (the log-amplitude), and ω (the frequency) is the derivative of φ (the phase). Thus, the log-amplitude and the phase are modeled by polynomials of degree 1, which can be viewed either as truncated Taylor expansions of more complicated amplitude and frequency modulations (e.g. tremolo / vibrato), or either as an extension of the stationary case where µ 0 = 0.

Spectral Analysis

The main problem we have to tackle now is the estimation of the model parameters. This can be achieved, as in the stationary case, by using the short-time Fourier transform (STFT):

S w (t, ω) = +∞ -∞ s(τ )w(τ -t) exp (-jω(τ -t)) dτ (3)
where S w is the short-time spectrum of the signal s. Fig. 1. Magnitude spectrum of a harmonic sound, resulting from a fast (discrete) Fourier transform (FFT). Each partial causes a peak (e.g. see •) and will be considered individually.

Note that, as in [START_REF] Marchand | Generalization of the Derivative Analysis Method to Non-Stationary Sinusoidal Modeling[END_REF], we use here a slightly modified definition of the STFT. Indeed we let the time reference slide with the window, which is also the case in practice when the STFT is implemented using a sliding fast Fourier transform (FFT).

For the sake of simplicity, all the mathematical derivations will be done in the continuous domain. However, in practice the signals are discrete (with some sampling frequency F s ). The Fourier transform (FT) will then be replaced by its discrete version (DFT) of size N , and the time will be expressed in samples (sample n being at time n/F s ) and the frequency in bins (bin m being at frequency mF s /N ).

Many instrumental sounds are harmonic, meaning that the frequencies of the partials are multiple of some fundamental frequency (related to our perception of pitch). The magnitude of the Fourier spectrum exhibits then a series of peaks (see Fig. 1). Each peak is a local maximum m in the magnitude spectrum and corresponds to some partial.

S w involves an analysis window w, usually symmetric and band-limited in such a way that for any frequency corresponding to one specific partial, the influence of the other partials can be neglected (in the general case when P > 1).

In the stationary case (µ 0 = 0), the spectrum of the analysis window gets simply centered on the frequency ω 0 and multiplied by the complex amplitude

s 0 = a 0 exp(jφ 0 ) = exp(λ 0 + jφ 0 ), (4)
as shown in Fig. 2, which can be regarded as a zoom on one of the peaks of the preceding figure. In the non-stationary case however, considering Equation (3) at estimation time 0, we see that s 0 gets multiplied by Γ w (ω 0 -ω, µ 0 ) where Fig. 2. Zoom on one peak: The analyzed sinusoid (dashed line) is observed from the spectrum of the analysis window through the discrete frequencies (solid lines) of the Fourier transform, leading to several bins with significant energy (•).

Γ w (ω, µ 0 ) = +∞ -∞ w(t) exp (µ 0 t + jωt) dt. (5)
In the special case of using a Gaussian window for w, an analytic formula can be derived. Else, it is always possible to compute Γ w directly from Equation [START_REF] Marchand | Generalization of the Derivative Analysis Method to Non-Stationary Sinusoidal Modeling[END_REF].

Once the estimated amplitude modulation μ0 and frequency ω0 are known, the amplitude and phase parameters can eventually be estimated since

ŝ0 = S w (0, ω m ) Γ w (ω 0 -ω m , μ0 ) , (6)
where ω m is the (discrete) frequency of the local maximum of the magnitude spectrum where the partial is detected.

SINUSOIDAL ESTIMATION

The problem is yet to estimate the amplitude modulation and frequency parameters. In this section, we present 3 methods providing estimation functions μ and ω for these parameters.

In practice, for each detected partial at time 0 (center of the analysis frame) and (discrete) frequency ω m , the estimates of its parameters are given by:

μ0 = μ(0, ω m ), (7
) ω0 = ω(0, ω m ).

(8)

Difference Method (Phase Vocoder)

The Fourier-based approach started together with computer music, about 50 years ago. The phase vocoder introduced by Flanagan and Golden [START_REF] Flanagan | Phase vocoder[END_REF] was already using the phase of the Fourier spectrum to estimate the frequency of the partials, and more precisely the phase difference of consecutive spectra [START_REF] Dolson | The Phase Vocoder: A Tutorial[END_REF]. This simple yet efficient difference approach was generalized recently to the non-stationary case [START_REF] Marchand | The Simplest Analysis Method for Non-Stationary Sinusoidal Modeling[END_REF].

Thus S w (t, ω) is the spectrum of the frame centered at the desired (discrete) estimation time, and let S ∓ w (ω) = S w (t∓1/F s , ω) be its left (previous, i.e. one sample before) and right (next, i.e. one sample after) neighboring spectra, respectively (F s denoting the sampling frequency).

Since the log-amplitude and phase differences correspond to the real and imaginary parts of the logarithm of spectral ratios, respectively, let us define:

∆ λ (S 1 , S 2 ) = log |S 1 | -log |S 2 | = ℜ (log (S 1 /S 2 )) , (9)
∆ φ (S 1 , S 2 ) = ∠S 1 -∠S 2 = ℑ (log (S 1 /S 2 )) (10)
(S 1 and S 2 denoting two arbitrary complex spectra).

Since we can measure the amplitude of the spectra, we can compute the left and right estimates of the amplitude modulation, and retain their mean as the final estimation:

µ -= ∆ λ (S w , S - w ) • F s , µ + = ∆ λ (S + w , S w ) • F s , μ = (µ -+ µ + )/2. ( 11
)
Similarly, with the measured phase of the spectra, we can compute an estimation of the instantaneous frequency:

ω -= ∆ φ (S w , S - w ) • F s , ω + = ∆ φ (S + w , S w ) • F s , ω = (ω -+ ω + )/2. (12)
In practice, we are looking for positive frequencies and since the phase is measured modulo 2π, after each call to the ∆ φ function we must apply the phase unwrapping procedure of the phase vocoder, i.e. adding 2π to the result if lower than 0.

Spectral Reassignment

Reassignment was first proposed by Kodera et al. [START_REF] Kodera | Analysis of Time-Varying Signals with Small BT Values[END_REF] and was generalized by Auger and Flandrin [START_REF] Auger | Improving the Readibility of Time-Frequency and Time-Scale Representations by the Reassignment Method[END_REF] to improve timefrequency representations. Usually, the values obtained when decomposing the signal on the time-frequency atoms are assigned to the geometrical of the cells (center of the analysis window and bins of the Fourier transform). The reassignment method assigns each value to the center of gravity of the cell's energy. The method uses the knowledge of the first derivative w ′ -obtained by analytic differentiation -of the analysis window w in order to adjust the frequency inside the Fourier transform bin. This approach was generalized for the amplitude modulation in the non-stationary case (see [START_REF] Marchand | Generalization of the Derivative Analysis Method to Non-Stationary Sinusoidal Modeling[END_REF]).

The complex short-time spectrum -resulting from the STFT -is, in the polar form:

S w (t, ω) = a(t, ω) exp (jφ(t, ω)) ( 13
)
where the instantaneous amplitude a and phase φ are realvalued functions of time t and frequency ω. By considering Equation (3), we can easily derive:

∂ ∂t log (S w (t, ω)) = jω - S w ′ (t, ω) S w (t, ω) (14)
where w ′ denotes the derivative of w. Then, since the amplitude modulation (resp. frequency) is the derivative of the amplitude (resp. phase), from Equations ( 13) and ( 14), we obtain the reassigned parameters:

μ(t, ω) = ∂ ∂t ℜ (log (S w (t, ω))) = -ℜ S w ′ (t, ω) S w (t, ω) , (15)
ω(t, ω) = ∂ ∂t ℑ (log (S w (t, ω))) = ω -ℑ S w ′ (t, ω) S w (t, ω) . ( 16
)

Derivative Method

Together with Desainte-Catherine in [START_REF] Desainte-Catherine | High Precision Fourier Analysis of Sounds Using Signal Derivatives[END_REF], we proposed to use the signal derivatives to estimate the sinusoidal parameters in the stationary case; and with Depalle in [START_REF] Marchand | Generalization of the Derivative Analysis Method to Non-Stationary Sinusoidal Modeling[END_REF], we generalized this derivative method to the non-stationary case. Indeed, considering Equation ( 2), since the derivative of an exponential is an exponential, we have:

s ′ (t) = (µ 0 + jω 0 ) • s(t) and thus ℜ s ′ s = µ 0 and ℑ s ′ s = ω 0 .
For this method to work in the case of a signal made of several partials, we have to switch to the spectral domain and define:

μ = ℜ S ′ w S w , ( 17
) ω = ℑ S ′ w S w , ( 18
)
where S ′ w is the short-time spectrum of the signal derivative s ′ . As shown in [START_REF] Marchand | Generalization of the Derivative Analysis Method to Non-Stationary Sinusoidal Modeling[END_REF], in practice this (discrete) derivative s ′ can be obtained by convolving the discrete signal s by the following differentiator filter:

h[n] = F s ( -1)
n n for n = 0, and h(0

) = 0 (19)
of infinite time support. Thus, in practice, we multiply h by a (finite-length) Hann window. This results in a high-pass filter, and can lead to estimation problems in the high frequencies (above approx. 3/4 of the Nyquist frequency), fortunately above the audible limit (16kHz). So, for each partial m detected in the (discrete) Fourier spectrum at time t and frequency ω m , together with Equations ( 7) and ( 8), we have now 3 ways to estimate the amplitude modulation and frequency parameters of the partial:

• the difference approach with Equations ( 11)-( 12),

• the reassignment approach with Equations (15)-( 16),

• the derivative approach with Equations (17)-(18). Once these parameters are known, the others (amplitude and phase) can be estimated in turn using Equation (6).

COMPARING THE ESTIMATORS

Now the question is: Which is the best approach?

Experimental Results

To quantitatively evaluate the precision of theses approaches for the estimation of all the model parameters, we ran the same experiments as in [START_REF] Marchand | Generalization of the Derivative Analysis Method to Non-Stationary Sinusoidal Modeling[END_REF][START_REF] Marchand | The Simplest Analysis Method for Non-Stationary Sinusoidal Modeling[END_REF].

We consider discrete-time signals s, with sampling rate F s , each consisting of 1 complex exponential generated according to Equation ( 2) with an initial amplitude a 0 = 1, and mixed with a Gaussian white noise. In our experiments, we set the sampling frequency F s = 44100Hz, the FFT size N = 511, and the signal-to-noise ratio (SNR) goes from -20dB to +100dB by steps of 5dB. For each SNR and for each analysis method, we test several parameter combinations: 99 frequencies (ω 0 ) linearly distributed in the (0, 3F s /8) interval, 9 phases (φ 0 ) linearly distributed in (-π, +π), and 5 amplitude modulations (µ 0 ) linearly distributed in [-100, +100]. For the analysis window w, we use the symmetric Hann window. We focus on the variance of the estimation error over this test set (the mean being zero for unbiased estimators). We then compare the difference method (D), the reassignment method (R), and two variants of the derivative method: The estimated derivative method (ED), where the derivative s ′ is estimated using the differentiator filter of Equation (19) of size 1023; and the theoretic derivative method (TD), where the exact derivative is used for s ′ -since it is analytically known for the test signals. The results of the TD method can be regarded as the best performance the ED method could achieve, at the expense of a longer differentiator filter though.

When looking at the results of these experiments (see Fig. 3), we see that all these methods are very efficient, close to the the Cramér-Rao bounds (CRB), which are the limit to the best possible performance achievable by an unbiased estimator given a data set (see [START_REF] Marchand | Generalization of the Derivative Analysis Method to Non-Stationary Sinusoidal Modeling[END_REF]).

In the high SNRs, the ED method is biased because of the approximation of the derivative by the finite-length differentiator filter. Applying the spectral reassignment on the discrete spectrum causes a bias, as noticed by Hainsworth [START_REF] Hainsworth | Techniques for the Automated Analysis of Musical Audio[END_REF], degrading the performances of the R method. Perhaps surprisingly, the simplest D method is the most efficient.

Theoretical Equivalences

Reassignment and Derivative

In [START_REF] Marchand | On the Equivalence of Phase-Based Methods for the Estimation of Instantaneous Frequency[END_REF], the reassignment (Section 3.2) and derivative (Section 3.3) methods were proven to be theoretically equivalent, at least as regards the estimation of the frequency in the stationary case. In [START_REF] Marchand | Generalization of the Derivative Analysis Method to Non-Stationary Sinusoidal Modeling[END_REF], we generalized the proof of the equivalence to the non-stationary case, and for the estimation of both the frequency and the amplitude modulation. More precisely, we introduce ρ = τ -t which gives another (equivalent) expression for the STFT (see Equation ( 3)):

S w (t, ω) = +∞ -∞ s(t + ρ)w(ρ) exp (-jωρ) dρ (20)
from which we can derive

∂ ∂t log (S w (t, ω)) = S ′ w (t, ω) S w (t, ω) . (21)
By considering Equation (21) instead of Equation ( 14) in Section 3.2 (reassignment approach), we would have obtained the equations of Section 3.3 (derivative approach). Thus the reassignment approach is equivalent to the derivative approach, at least in the continuous case. A different proof, based on integration by parts, can be found in [START_REF] Wen | Notes on Model-Based Non-Stationary Sinusoid Estimation Methods Using Derivatives[END_REF].

Reassignment and Difference

It turns out that the reassignment approach is also equivalent to the difference approach in the discrete case. Indeed, in the phase vocoder approach the parameters are estimated by first-order differences, approximating the differentiation of the spectrum of Equations ( 15)-( 16) in the discrete-time case.

CONCLUSIONS

Although the three approaches we presented in Section 3 are equivalent in theory, the small differences observed in practice in Section 4.1 are due to a bias of the reassignment method in the discrete case, and of the derivative method when using a finite-length differentiator filter. The most efficient approach turns out to be the simplest one, based on first-order differences, i.e. a rather crude approximation of differentiation. . . But further investigations are necessary, since in theory the reassignment method (resp. the derivative method) requires the analysis window (resp. time signal) to be differentiable, which are a priori different conditions.


Emmanuelle Anceaume

Bruno Sericola

NEW RESULTS ON A GENERALIZED COUPON COLLECTOR PROBLEM USING MARKOV CHAINS

Keywords: Coupon collector problem, Minimization, Markov chains

We study in this paper a generalized coupon collector problem, which consists in determining the distribution and the moments of the time needed to collect a given number of distinct coupons that are drawn from a set of coupons with an arbitrary probability distribution. We suppose that a special coupon called the null coupon can be drawn but never belongs to any collection. In this context, we obtain expressions of the distribution and the moments of this time. We also prove that the almost-uniform distribution, for which all the non-null coupons have the same drawing probability, is the distribution which minimizes the expected time to get a fixed subset of distinct coupons. This optimization result is extended to the complementary distribution of that time when the full collection is considered, proving by the way this well-known conjecture. Finally, we propose a new conjecture which expresses the fact that the almost-uniform distribution should minimize the complementary distribution of the time needed to get any fixed number of distinct coupons.

Introduction

The coupon collector problem is an old problem which consists in evaluating the time needed to get a collection of different objects drawn randomly using a given probability distribution. This problem has given rise to a lot of attention from researchers in various fields since it has applications in many scientific domains including computer science and optimization.

More formally, consider a set of n coupons which are drawn randomly one by one, with replacement, coupon i being drawn with probability p i . The classical coupon collector problem is to determine the expectation or the distribution of the number of coupons that need to be drawn from the set of n coupons to obtain the full collection of the n coupons. A large number of papers have been devoted to the analysis of asymptotics and limit distributions of this distribution when n tends to infinity, see [START_REF] Doumas | The Coupon Collector's Problem Revisited: Asymptotics of the Variance[END_REF] or [START_REF] Neal | The Generalised Coupon Collector Problem[END_REF] and the references therein. In [START_REF] Brown | Coupon Collecting[END_REF], the authors obtain some new formulas concerning this distribution and they also provide simulation techniques to compute it as well as analytic bounds of it.

We consider in this paper several generalizations of this problem. A first generalization is the analysis, for c ≤ n, of the number T c,n of coupons that need to be drawn, with replacement, to collect c different coupons from set {1, 2, . . . , n}. With this notation, the number of coupons that need to be drawn from this set to obtain the full collection is T n,n . If a coupon is drawn at each discrete time 1, 2, . . . then T c,n is the time needed to obtain c different coupons also called the waiting time to obtain c different coupons. This problem has been considered in [START_REF] Rubin | A waiting time distribution arising from the coupon collector's problem[END_REF] in the case where the drawing probability distribution is uniform.

In a second generalization, we assume that p = (p 1 , . . . , p n ) is not necessarily a probability distribution, i.e., we suppose that p 1 + • • • + p n ≤ 1 and we define p 0 = 1 -(p 1 + • • • + p n ). This means that there is a null coupon, denoted by 0, which is drawn with probability p 0 , but which does not belong to the collection. In this context, the problem is to determine the distribution of the number T c,n of coupons that need to be drawn from set {0, 1, 2, . . . , n}, with replacement, till one first obtains a collection composed of c different coupons, 1 ≤ c ≤ n, among {1, . . . , n}. These generalizations are motivated by the analysis of streaming algorithms in network monitoring applications as presented in Section 7.

The distribution of T c,n is obtained using Markov chains in Section 2, in which we moreover show that this distribution leads to new combinatorial identities. This result is used to get an expression of T c,n (v) when the drawing distribution is the almost-uniform distribution denoted by v and defined by

v = (v 1 , . . . , v n ) with v i = (1 -v 0 )/n, where v 0 = 1 -(v 1 + • • • + v n ).
Expressions of the moments of T c,n (p) are given in Section 3, where we show that the limit of (T c,n (p)) is equal to c when n tends to infinity. We show in Section 4 that the almost-uniform distribution v and the uniform distribution u minimize the expected value (T c,n (p)). We prove in Section 5 that the tail distribution of T n,n is minimized over all the p 1 , . . . , p n by the almost-uniform distribution and by the uniform distribution. This result was expressed as a conjecture in the case where p 0 = 0, i.e., when p 1 + • • • + p n = 1, in several papers like [START_REF] Boneh | The coupon-collector problem revisited -A survey of engineering problems and computational methods[END_REF] for instance, from which the idea of the proof comes from. We propose in Section 6 a new conjecture which consists in showing that the distributions v and u minimize the tail distribution of T c,n (p). This conjecture is motivated by the fact that it is true for c = 1 and c = n as shown in Section 5, and we show that it is also true for c = 2. It is moreover true for the expected value (T c,n (p)) as shown in Section 4.

Distribution of T c,n

Recall that T c,n is the number of coupons that need to be drawn from set {0, 1, 2, . . . , n}, with replacement, till one first obtains a collection with c different coupons, 1 ≤ c ≤ n, among {1, . . . , n}, where coupon i is drawn with probability p i , i = 0, 1, . . . , n.

To obtain the distribution of T c,n , we consider the discrete-time Markov chain X = {X m , m ≥ 0} that represents the collection obtained after having drawn m coupons. The state space of X is S n = {J ⊆ {1, . . . , n}} with transition probability matrix, denoted by Q, given, for every J, H ∈ S n , by

Q J,H =    p ℓ if H \ J = {ℓ} p 0 + P J if J = H 0 otherwise,
where, for every J ∈ S n , P J is given by ( 1)

P J = j∈J p j ,
with P ∅ = 0. It is easily checked that Markov chain X is acyclic, i.e., it has no cycle of length greater than 1, and that all the states are transient, except state {1, . . . , n} which is absorbing. We introduce the partition (S 0,n , S 1,n , . . . , S n,n ) of S n , where S i,n is defined, for i = 0, . . . , n, by

S i,n = {J ⊆ {1, . . . , n} | |J| = i} . (2)
Note that we have S 0,n = {∅},

|S n | = 2 n and |S i,n | = n i .
Assuming that X 0 = ∅ with probability 1, the random variable T c,n can then be defined, for every c = 1, . . . , n, by

T c,n = inf{m ≥ 0 | X m ∈ S c,n }.
The distribution of T c,n is obtained in Theorem 2 using the Markov property and the following lemma. For every n ≥ 1, ℓ = 1, . . . , n and i = 0, . . . , n, we define the set S i,n (ℓ) by

S i,n (ℓ) = {J ⊆ {1, . . . , n} \ {ℓ} | |J| = i} .
Lemma 1. For every n ≥ 1, for every k ≥ 0, for all positive real numbers y 1 , . . . , y n , for every i = 1, . . . , n and all real number a ≥ 0, we have

n ℓ=1 y ℓ J∈Si-1,n(ℓ) (a + y ℓ + Y J ) k = J∈Si,n Y J (a + Y J ) k ,
where Y J = j∈J y j and Y ∅ = 0.

Proof. For n = 1, since S 0,1 (1) = ∅, the left hand side is equal to y 1 (a + y 1 ) k and since S 1,1 = {1}, the right hand side is also equal to y 1 (a + y 1 ) k . Suppose that the result is true for integer n -1, with n ≥ 2, i.e., suppose that for every k ≥ 0, for all positive real numbers y 1 , . . . , y n-1 , for every i = 1, . . . , n -1 and for all real number a ≥ 0, we have

n-1 ℓ=1 y ℓ J∈Si-1,n-1(ℓ) (a + y ℓ + Y J ) k = J∈Si,n-1 Y J (a + Y J ) k .
We then have

n ℓ=1 y ℓ J∈Si-1,n(ℓ) (a + y ℓ + Y J ) k = n-1 ℓ=1 y ℓ J∈Si-1,n(ℓ) (a + y ℓ + Y J ) k + y n J∈Si-1,n(n) (a + y n + Y J ) k . Since S i-1,n (n) = S i-1,n-1 , we get n ℓ=1 y ℓ J∈Si-1,n(ℓ) (a + y ℓ + Y J ) k = n-1 ℓ=1 y ℓ J∈Si-1,n(ℓ) (a + y ℓ + Y J ) k + y n J∈Si-1,n-1 (a + y n + Y J ) k .
For ℓ = 1, . . . , n -1, the set S i-1,n (ℓ) can be partitioned into two subsets S ′ i-1,n (ℓ) and S ′′ i-1,n (ℓ) defined by

S ′ i-1,n (ℓ) = {J ⊆ {1, . . . , n} \ {ℓ} | |J| = i -1 and n ∈ J} and
S ′′ i-1,n (ℓ) = {J ⊆ {1, . . . , n} \ {ℓ} | |J| = i -1 and n / ∈ J} .
Since S ′′ i-1,n (ℓ) = S i-1,n-1 (ℓ), the previous relation becomes

n ℓ=1 y ℓ J∈Si-1,n(ℓ) (a + y ℓ + Y J ) k = n-1 ℓ=1 y ℓ   J∈Si-1,n-1(ℓ) (a + y ℓ + Y J ) k + J∈S ′ i-1,n (ℓ) (a + y ℓ + Y J ) k   + y n J∈Si-1,n-1 (a + y n + Y J ) k = n-1 ℓ=1 y ℓ J∈Si-1,n-1(ℓ) (a + y ℓ + Y J ) k + n-1 ℓ=1 y ℓ J∈Si-2,n-1(ℓ) (a + y n + y ℓ + Y J ) k + y n J∈Si-1,n-1 (a + y n + Y J ) k .
The recurrence hypothesis can be applied for both the first and the second terms. For the second term, the constant a is replaced by the constant a + y n . We thus obtain

n ℓ=1 y ℓ J∈Si-1,n(ℓ) (a + y ℓ + Y J ) k = J∈Si,n-1 Y J (a + Y J ) k + J∈Si-1,n-1 Y J (a + y n + Y J ) k + y n J∈Si-1,n-1 (a + y n + Y J ) k = J∈Si,n-1 Y J (a + Y J ) k + J∈Si-1,n-1 (y n + Y J )(a + y n + Y J ) k = J∈Si,n-1 Y J (a + Y J ) k + J∈S ′ i,n Y J (a + Y J ) k ,
where

S ′ i,n = {J ⊆ {1, . . . ,
(a + y ℓ + Y J ) k = J∈Si,n-1 Y J (a + Y J ) k + J∈S ′ i,n Y J (a + Y J ) k = J∈S ′′ i,n Y J (a + Y J ) k + J∈S ′ i,n Y J (a + Y J ) k = J∈Si,n Y J (a + Y J ) k ,
which completes the proof.

In the following we will use the fact that the distribution of T c,n depends on the vector p = (p 1 , . . . , p n ), so we will use the notation T c,n (p) instead of T c,n , meaning by the way that vector p is of dimension n. We will also use the notation

p 0 = 1 - n i=1 p i .
Finally, for ℓ = 1, . . . , n, the notation p (ℓ) will denote the vector p in which the entry p ℓ has been removed, that is p (ℓ) = (p i ) 1≤i≤n,i =ℓ . The dimension of p (ℓ) , which is n -1 here, is not specified but will be clear by the context of its use. We are now able to prove the following result.

Theorem 2. For every n ≥ 1 and c = 1, . . . , n, we have, for every k ≥ 0,

(3) È{T c,n (p) > k} = c-1 i=0 (-1) c-1-i n -i -1 n -c J∈Si,n (p 0 + P J ) k ,
where P J is given by (1).

Proof. Relation (3) is true for c = 1 since in this case we have È{T 1,n (p) > k} = p k 0 . So we suppose now that n ≥ 2 and c = 2, . . . , n.

Since X 0 = ∅, conditioning on X 1 and using the Markov property, see for instance [START_REF] Sericola | Markov Chains: Theory, Algorithms and Applications[END_REF], we get for k ≥ 1,

È{T c,n (p) > k} = p 0 È{T c,n (p) > k -1} + n ℓ=1 p ℓ È{T c-1,n-1 (p (ℓ) ) > k -1}. (4)
We now proceed by recurrence over index k. Relation ( 3) is true for k = 0 since it is well-known that

(5) c-1 i=0 (-1) c-1-i n -i -1 n -c n i = 1.
Relation (3) is also true for k = 1 since on the one hand È{T c,n (p) > 1} = 1 and on the other hand, using Relation (4), we have

È{T c,n (p) > 1} = p 0 È{T c,n (p) > 0} + n ℓ=1 p ℓ È{T c-1,n-1 (p (ℓ) ) > 0} = p 0 + n ℓ=1 p ℓ = 1.
Suppose now that Relation (3) is true for integer k -1, that is, suppose that we have

È{T c,n (p) > k -1} = c-1 i=0 (-1) c-1-i n -i -1 n -c J∈Si,n (p 0 + P J ) k-1 .
Using (4) and the recurrence relation, we have

È{T c,n (p) > k} = p 0 c-1 i=0 (-1) c-1-i n -i -1 n -c J∈Si,n (p 0 + P J ) k-1 + n ℓ=1 p ℓ c-2 i=0 (-1) c-2-i n -i -2 n -c J∈Si,n(ℓ) (p 0 + p ℓ + P J ) k-1 .
Using the change of variable i := i -1 in the second sum, we obtain

È{T c,n (p) > k} = c-1 i=0 (-1) c-1-i n -i -1 n -c p 0 J∈Si,n (p 0 + P J ) k-1 + c-1 i=1 (-1) c-1-i n -i -1 n -c n ℓ=1 p ℓ J∈Si-1,n(ℓ) (p 0 + p ℓ + P J ) k-1 = c-1 i=1 (-1) c-1-i n -i -1 n -c p 0 J∈Si,n (p 0 + P J ) k-1 + n ℓ=1 p ℓ J∈Si-1,n(ℓ) (p 0 + p ℓ + P J ) k-1 + (-1) c-1 n -1 n -c p k 0 .
From Lemma 1, we have

n ℓ=1 p ℓ J∈Si-1,n(ℓ) (p 0 + p ℓ + P J ) k-1 = J∈Si,n P J (p 0 + P J ) k-1 , that is È{T c,n (p) > k} = (-1) c-1 n -1 n -c p k 0 + c-1 i=1 (-1) c-1-i n -i -1 n -c J∈Si,n (p 0 + P J ) k = c-1 i=0 (-1) c-1-i n -i -1 n -c J∈Si,n (p 0 + P J ) k ,
which completes the proof.

This theorem also shows, as expected, that the function È{T c,n (p) > k}, as a function of p, is symmetric, which means that it has the same value for any permutation of the entries of p. As a corollary, we obtain the following combinatorial identities.

Corollary 3. For every c ≥ 1, for every n ≥ c and for all p 1 , . . . , p n ∈ (0, 1)

such that p 1 + • • • + p n = 1, we have c-1 i=0 (-1) c-1-i n -i -1 n -c J∈Si,n (p 0 + P J ) k-1 = 1, for k = 0, 1, . . . , c -1.
Proof. The random variable T c,n takes its values on the set {c, c + 1, . . .}, so we have

È{T c,n > k} = 1, for k = 0, 1, . . . , c -1,
which completes the proof thanks to Theorem 2.

For every n ≥ 1 and for every v 0 ∈ [0, 1], we define the vector v = (v 1 , . . . , v n ) by v i = (1v 0 )/n. We will refer it to as the almost-uniform distribution. We then have, from (3),

È{T c,n (v) > k} = c-1 i=0 (-1) c-1-i n -i -1 n -c n i v 0 1 - i n + i n k .
We denote by u = (u 1 , . . . , u n ) the uniform distribution defined by u i = 1/n. It is equal to v when v 0 = 0. The dimensions of u and v are specified by the context.

Moments of T c,n

For r ≥ 1, the rth moment of T c,n (p) is defined by

(T r c,n (p)) = ∞ k=1 k r È{T c,n (p) = k}.
It can be obtained in function of the tail distribution of T c,n (p) by writing

(T r c,n (p)) = ∞ k=1 k r È{T c,n (p) = k} = ∞ k=1 k r È{T c,n (p) > k -1} - ∞ k=1 k r È{T c,n (p) > k} = ∞ k=0 ((k + 1) r -k r ) È{T c,n (p) > k} = r-1 ℓ=0 r ℓ ∞ k=0 k ℓ È{T c,n (p) > k}.
We easily get the first and second moments of T c,n (p), by taking r = 1 and r = 2 respectively, that is

(6) (T c,n (p)) = ∞ k=0 È{T c,n (p) > k} = c-1 i=0 (-1) c-1-i n -i -1 n -c J∈Si,n 1 1 -(p 0 + P J ) and (T 2 c,n (p)) = (T c,n (p)) + 2 ∞ k=1 kÈ{T c,n (p) > k} = c-1 i=0 (-1) c-1-i n -i -1 n -c J∈Si,n 1 + 2(p 0 + P J ) [1 -(p 0 + P J )] 2 .
The expected value given by ( 6) has been obtained in [START_REF] Flajolet | Birthday paradox, coupon collectors, caching algorithms and self-organizing search[END_REF] in the particular case where p 0 = 0. When the drawing probabilities are given by the almost-uniform distribution v, we get

(T c,n (v)) = 1 1 -v 0 c-1 i=0 (-1) c-1-i n -i -1 n -c n i n n -i = 1 1 -v 0 (T c,n (u)).
Using the following two relations

n i = n -1 i + n -1 i -1 1 {i≥1} and n -1 i n n -i = n i ,
where 1 A is the indicator function of set A, we get

(T c,n (u)) = c-1 i=0 (-1) c-1-i n -i -1 n -c n i n n -i = c-1 i=0 (-1) c-1-i n -i -1 n -c n i + c-1 i=1 (-1) c-1-i n -i -1 n -c n -1 i -1 n n -i .
From Relation (5), the first sum is equal to 1. Using the change of variable i := i + 1 in the second sum, we obtain

(T c,n (u)) = 1 + c-2 i=0 (-1) c-2-i n -i -2 n -c n -1 i n n -i + 1 = 1 + n n -1 (T c-1,n-1 (u)). ( 7
)
Note that the dimension of the uniform distribution in the left hand side is equal to n and the one in the right hand side is equal to n -1. Since (T 1,n (u)) = 1, we obtain

(8) (T c,n (u)) = n(H n -H n-c ) and (T c,n (v)) = n(H n -H n-c ) 1 -v 0 ,
where H ℓ is the ℓth harmonic number defined by H 0 = 0 and, for ℓ ≥ 1,

H ℓ = ℓ i=1 1/i.
We deduce easily from ( 7) that, for every c ≥ 1, we have lim

n-→∞ (T c,n (u)) = c and lim n-→∞ (T c,n (v)) = c 1 -v 0 .
In the next section we show that, when p 0 is fixed, the minimum value of (T c,n (p)) is reached when p = v, with v 0 = p 0 .

Distribution minimizing (T c,n (p))

The following lemma will be used to prove the next theorem. Lemma 4. For every n ≥ 1 and r 1 , . . . , r n ∈ (0, 1) with

r 1 + • • • + r n = 1, we have n ℓ=1 1 r ℓ ≥ n 2 .
Proof. We proceed by recurrence. The result is clearly true for n = 1. Suppose that the result is true for integer n -1, n ≥ 2. We then have

n ℓ=1 1 r ℓ = 1 r n + n-1 ℓ=1 1 r ℓ = 1 r n + 1 1 -r n n-1 ℓ=1 1 h ℓ ,
where h ℓ is given, for ℓ = 1, . . . n -1, by

h ℓ = r ℓ 1 -r n . Since h 1 + • • • + h n-1 = 1
, we get, using the recurrence hypothesis,

n ℓ=1 1 r ℓ ≥ 1 r n + (n -1) 2 1 -r n = (nr n -1) 2 r n (1 -r n ) + n 2 ≥ n 2 ,
which completes the proof.

Theorem 5. For every n ≥ 1, for every c = 1, . . . , n and p = (p 1 , . . . , p n ) ∈ (0, 1)

n with p 1 + • • • + p n ≤ 1, we have (T c,n (p)) ≥ (T c,n (v)) ≥ (T c,n (u))
,

where v = (v 1 , . . . , v n ) with v i = (1 -p 0 )/n and p 0 = 1 -(p 1 + • • • + p n )
and where u = (1/n, . . . , 1/n).

Proof. The second inequality comes from [START_REF] Sericola | Markov Chains: Theory, Algorithms and Applications[END_REF].

Defining v 0 = 1 -(v 1 + • • • + v n ),
we have v 0 = p 0 . For c = 1, the result is trivial since we have from Relation (6)

(T 1,n (p)) = 1 1 -p 0 = 1 1 -v 0 = (T 1,n (v)).
For c ≥ 2, which implies that n ≥ 2, summing Relation (4) for k ≥ 1, we get

(T c,n (p)) -1 = p 0 (T c,n (p)) + n ℓ=1 p ℓ (T c-1,n-1 (p (ℓ) )).
We then obtain

(9) (T c,n (p)) = 1 1 -p 0 1 + n ℓ=1 p ℓ (T c-1,n-1 (p (ℓ) )) .
We now proceed by recurrence. Suppose that the inequality is true for integer c -1, with c ≥ 2, i.e., suppose that, for every n ≥ c, for every q = (q 1 , . . . , q n-1 ) ∈ (0, 1) n-1 with q

1 + • • • + q n-1 ≤ 1, we have (T c-1,n-1 (q)) ≥ (T c-1,n-1 (v)), with v 0 = q 0 = 1 - n-1 i=1 q i .
Using Relation [START_REF] Sericola | Markov Chains: Theory, Algorithms and Applications[END_REF], this implies that

(T c-1,n-1 (p (ℓ) )) ≥ (n -1)(H n-1 -H n-c ) 1 -(p 0 + p ℓ ) .
From Relation (9), we obtain

(10) (T c,n (p)) ≥ 1 1 -p 0 1 + (n -1)(H n-1 -H n-c ) n ℓ=1 p ℓ 1 -(p 0 + p ℓ )
.

Observe now that for ℓ = 1, . . . , n we have

p ℓ 1 -(p 0 + p ℓ ) = -1 + 1 (n -1)r ℓ ,
where the r ℓ are given by

r ℓ = 1 -(p 0 + p ℓ ) (n -1)(1 -p 0 )
and satisfy r 1 , . . . , r n ∈ (0, 1) with

r 1 + • • • + r n = 1. From Lemma 4, we obtain n ℓ=1 p ℓ 1 -(p 0 + p ℓ ) = -n + 1 n -1 n ℓ=1 1 r ℓ ≥ -n + n 2 n -1 = n n -1 .
Replacing this value in (10), we obtain, using ( 8),

(T c,n (p)) ≥ 1 1 -p 0 (1 + n(H n-1 -H n-c )) = n(H n -H n-c ) 1 -p 0 = (T c,n (v)),
which completes the proof.

Distribution minimizing the distribution of T n,n (p)

For every n ≥ 1, i = 0, 1, . . . , n and k ≥ 0, we denote by N (k) i the number of coupons of type i collected at instants 1, . . . , k. It is well-known that the joint distribution of the N (k) i is a multinomial distribution. More precisely, for every k ≥ 0 and k 0 , k 1 , . . . , k n ≥ 0 such that

k 0 + k 1 + • • • + k n = k, we have (11) È{N (k) 0 = k 0 , N (k) 1 = k 1 , . . . , N (k) n = k n } = k! k 0 !k 1 ! • • • k n ! p k0 0 p k1 1 • • • p kn n .
Recall that the coupons of type 0 do not belong to the collection. For every ℓ = 1, . . . , n, we easily deduce that, for every k ≥ 0 and k 1 , . . . , k ℓ ≥ 0 such that

k 1 + • • • + k ℓ ≤ k, È{N (k) 1 = k 1 , . . . , N (k) ℓ = k ℓ } = k! k 1 ! • • • k ℓ ! (k -(k 1 + • • • + k ℓ ))! p k1 1 • • • p k ℓ ℓ (1 -(p 1 + • • • + p ℓ )) k-(k1+•••+k ℓ ) .
To prove the next theorem, we recall some basic results on convex functions. A function f is said to be convex on an interval I if for every x, y ∈ I and λ ∈ [0, 1], we have

f (λx + (1 -λ)y) ≤ λf (x) + (1 -λ)f (y).
Let f be a function defined on an interval I. For every α ∈ I, we introduce the function g α , defined for every x ∈ I \ {α}, by

g α (x) = f (x) -f (α) x -α .
It is well-known that f is a convex function on interval I if and only if for every α ∈ I, the function g α is increasing on I \ {α}. The next result is also known but less popular, so we give its proof.

Lemma 6. Let f be a convex function on an interval I. For every x, y, z, t ∈ I with x < y, z < t, we have

(t -y)f (z) + (z -x)f (y) ≤ (t -y)f (x) + (z -x)f (t).
If, moreover, we have t + x = y + z, we get

f (z) + f (y) ≤ f (x) + f (t).
Proof. It suffices to apply twice the property that function g α is increasing on I \ {α}, for every α ∈ I. Since z < t, we have g x (z) ≤ g x (t) and since x < y, we have g t (x) ≤ g t (y). But as g x (t) = g t (x) and g t (y) = g y (t), we obtain g x (z) ≤ g x (t) = g t (x) ≤ g t (y) = g y (t), which means in particular that

f (z) -f (x) z -x ≤ f (t) -f (y) t -y , that is (t -y)f (z) + (z -x)f (y) ≤ (t -y)f (x) + (z -x)f (t).
The rest of the proof is trivial since t + x = y + z implies that ty = zx > 0.

Theorem 7. For every n ≥ 1 and p = (p 1 , . . . , p n ) ∈ (0, 1)

n with p 1 + • • • + p n ≤ 1, we have, for every k ≥ 0, È{T n,n (p ′ ) ≤ k} ≤ È{T n,n (p) ≤ k}, where p ′ = (p 1 , . . . , p n-2 , p ′ n-1 , p ′ n ) with p ′ n-1 = λp n-1 + (1 -λ)p n and p ′ n = (1 -λ)p n-1 + λp n , for every λ ∈ [0, 1].
Proof. If λ = 1 then we have p ′ = p so the result is trivial. If λ = 0 then we have p ′ n-1 = p n and p ′ n = p n-1

and the result is also trivial since the function È{T n,n (p) ≤ k} is a symmetric function of p. We thus suppose now that λ ∈ (0, 1). For every n ≥ 1 and k ≥ 0, we have

{T n,n (p) ≤ k} = {N (k) 1 > 0, . . . , N (k) n > 0}.
We thus get, for

k 1 > 0, . . . , k n-2 > 0 such that k 1 + • • • + k n-2 ≤ k, setting s = k -(k 1 + • • • + k n-2 ), È{T n,n (p) ≤ k, N (k) 1 = k 1 , . . . , N (k) n-2 = k n-2 } = È{N (k) 1 = k 1 , . . . , N (k) n-2 = k n-2 , N (k) n-1 > 0, N (k) n > 0} = u≥0,v>0,w>0, u+v+w=s È{N (k) 0 = u, N (k) 1 = k 1 , . . . , N (k) n-2 = k n-2 , N (k) n-1 = v, N (k) n = w}.
Using Relation (11) and introducing the notation

q 0 = p 0 p 0 + p n-1 + p n , q n-1 = p n-1 p 0 + p n-1 + p n and q n = p n p 0 + p n-1 + p n , we obtain È{T n,n (p) ≤ k, N (k) 1 = k 1 , . . . , N (k)
n-2 = k n-2 } = u≥0,v>0,w>0, u+v+w=s k!p u 0 p k1 1 • • • p kn-2 n-2 p v n-1 p w n u!k 1 ! • • • k n-2 !v!w! = k!p k1 1 • • • p kn-2 n-2 k 1 ! • • • k n-2 ! u≥0,v>0,w>0, u+v+w=s p u 0 p v n-1 p w n u!v!w! = k!p k1 1 • • • p kn-2 n-2 (1 -(p 1 + • • • + p n-2 )) s k 1 ! • • • k n-2 !s! u≥0,v>0,w>0, u+v+w=s s! u!v!w! q u 0 q v n-1 q w n = k!p k1 1 • • • p kn-2 n-2 (1 -(p 1 + • • • + p n-2 )) s k 1 ! • • • k n-2 !s! (1 -(q 0 + q n-1 ) s -(q 0 + q n ) s + q s 0 ) .
Note that this relation is not true if at least one of the k ℓ is zero. Indeed, if k ℓ = 0 for some ℓ = 1, . . . , n -2, we have

È{T n,n (p) ≤ k, N (k) 1 = k 1 , . . . , N (k)
n-2 = k n-2 } = 0. Summing over all the k 1 , . . . , k n-2 such that k 1 + • • • + k n-2 ≤ k, we get (12) È{T n,n (p) ≤ k} = (k1,...,kn-2)∈En-2 k!p k1 1 • • • p kn-2 n-2 (1 -(p 1 + • • • + p n-2 )) s k 1 ! • • • k n-2 !s! (1 -(q 0 + q n-1 ) s -(q 0 + q n ) s + q s 0 ) ,
where the set E n-2 is defined by

E n-2 = {(k 1 , . . . , k n-2 ) ∈ (AE * ) n-2 | k 1 + • • • + k n-2 ≤ k}
and AE * is the set of positive integers. Note that for n = 2, since

p 0 + p 1 + p 2 = 1, we have È{T 2,2 (p) ≤ k} = 1 -(p 0 + p 1 ) k -(p 0 + p 2 ) k + p k 0 . Recall that p 0 = 1 -(p 1 + • • • + p n ). By definition of p ′
n-1 and p ′ n , we have, for every λ ∈ (0, 1),

p ′ n-1 + p ′ n = p n-1 + p n . It follows that, by definition of p ′ , p ′ 0 = 1 -(p 1 + • • • + p n-2 + p ′ n-1 + p ′ n ) = 1 -(p 1 + • • • + p n-2 + p n-1 + p n ) = p 0 .
Suppose that we have p n-1 < p n . This implies, by definition of p ′ n-1 and p ′ n , that p n-1 < p ′ n-1 , p ′ n < p n , that is q n-1 < q ′ n-1 , q ′ n < q n , where

q ′ n-1 = p ′ n-1 p ′ 0 + p ′ n-1 + p ′ n = p ′ n-1 p 0 + p n-1 + p n and q ′ n = p ′ n p ′ 0 + p ′ n-1 + p ′ n = p ′ n p 0 + p n-1 + p n .
In the same way, we have

q ′ 0 = p ′ 0 p ′ 0 + p ′ n-1 + p ′ n = p 0 p 0 + p n-1 + p n = q 0 .
We thus have q 0 + q n-1 < q ′ 0 + q ′ n-1 , q ′ 0 + q ′ n < q 0 + q n . The function f defined by f (x) = x s is convex on interval [0, 1] so, from Lemma 6, since 2q 0 + q n-1 + q n = 2q ′ 0 + q ′ n-1 + q ′ n , we have (13)

q ′ 0 + q ′ n-1 s + (q ′ 0 + q ′ n ) s ≤ (q 0 + q n-1 ) s + (q 0 + q n ) s .
Similarly, if p n < p n-1 , we have, by definition, p n < p ′ n , p ′ n-1 < p n-1 , that is q n < q ′ n , q ′ n-1 < q n-1 and thus we also have Relation (13) in this case. Using Relation (13) in Relation (12), we get, since q ′ 0 = q 0 , È{T n,n (p) ≤ k} ≤ (k1,...,kn-2)∈En-2

k!p k1 1 • • • p kn-2 n-2 (1 -(p 1 + • • • + p n-2 )) s k 1 ! • • • k n-2 !s! 1 -q ′ 0 + q ′ n-1 s -(q ′ 0 + q ′ n ) s + q ′ 0 s = È{T n,n (p ′ ) ≤ k},
which completes the proof.

The function È{T n,n (p) ≤ k}, as a function of p, being symmetric, this theorem can easily be extended to the case where the two entries p n-1 and p n of p, which are different from the entries p ′ n-1 and p ′ n of p ′ , are any p i , p j ∈ {p 1 , . . . , p n }, with i = j.

In fact, we have shown in this theorem that for fixed n and k, the function of p, È{T n,n (p) ≤ k}, is a Schur-convex function, that is, a function that preserves the order of majorization. See [START_REF] Marshall | Inequalities via majorization -An introduction[END_REF] for more details on this subject. Proof. To prove the first inequality, we apply successively and at most n -1 times Theorem 7 as follows. We first choose two different entries of p, say p i and p j such that p i < (1p 0 )/n < p j and next to define p ′ i and p ′ j by

p ′ i = 1 -p 0 n and p ′ j = p i + p j - 1 -p 0 n .
With respect to Theorem 7, this leads to write p ′ i = λp i + (1λ)p j and p ′ j = (1λ)p i + λp j , with

λ = p j - 1 -p 0 n p j -p i .
From Theorem 7, the vector p ′ that we obtain by taking the other entries equal to those of p, i.e., by taking p ′ ℓ = p ℓ , for ℓ = i, j, is such that

È{T n,n (p) > k} ≥ È{T n,n (p ′ ) > k}.
Note that at this point vector p ′ has at least one entry equal to (1p 0 )/n), so repeating at most n -1 this procedure, we get vector v.

To prove the second inequality, we use Relation (11). Introducing, for every n ≥ 1, the set F n defined by

F n (ℓ) = {(k 1 , . . . , k n ) ∈ (AE * ) n | k 1 + • • • + k n = ℓ}.
For k < n, both terms are zero, so we suppose that k ≥ n. We have

È{T n,n (v) ≤ k} = È{N (k) 1 > 0, . . . , N (k) n > 0} = k-n k0=0 È{N (k) 0 = k 0 , N (k) 1 > 0, . . . , N (k) n > 0} = k-n k0=0 (k1,...,kn)∈Fn(k-k0) k! k 0 !k 1 ! • • • k n ! p k0 0 1 -p 0 n k-k0 = k-n k0=0 k k 0 p k0 0 (1 -p 0 ) k-k0 1 n k-k0 (k1,...,kn)∈Fn(k-k0) (k -k 0 )! k 1 ! • • • k n ! .
Setting p 0 = 0, we get

È{T n,n (u) ≤ k} = 1 n k (k1,...,kn)∈Fn(k) k! k 1 ! • • • k n ! . This leads to È{T n,n (v) ≤ k} = k-n k0=0 k k 0 p k0 0 (1 -p 0 ) k-k0 È{T n,n (u) ≤ k -k 0 } ≤ È{T n,n (u) ≤ k} k-n k0=0 k k 0 p k0 0 (1 -p 0 ) k-k0 ≤ È{T n,n (u) ≤ k},
which completes the proof.

To illustrate the steps used in the proof of this theorem, we take the following example. Suppose that n = 5 and p = (1/16, 1/6, 1/4, 1/8, 7/24). This implies that p 0 = 5/48 and (1p 0 )/n = 43/240. In a first step, taking i = 4 and j = 5, we get p (1) = (1/16, 1/6, 1/4, 43/240, 19/80). In a second, taking i = 2 and j = 5, we get p (2) = (1/16, 43/240, 1/4, 43/240, 9/40).

In a third step, taking i = 1 and j = 3, we get p (3) = (43/240, 43/240, 2/15, 43/240, 9/40).

For the fourth and last step, taking i = 5 and j = 3, we get p (4) = (43/240, 43/240, 43/240, 43/240, 43/240) = 43 48 (1/5, 1/5, 1/5, 1/5, 1/5).

A new conjecture

In this section, we propose a new conjecture stating that the complementary distribution function of T c,n is minimal when the distribution p is equal to the uniform distribution u.

Conjecture. For every n ≥ 1, c = 1, . . . , n and p = (p 1 , . . . , p n ) ∈ (0, 1) n with p

1 + • • • + p n ≤ 1, we have, for every k ≥ 0, È{T c,n (p) > k} ≥ È{T c,n (v) > k} ≥ È{T c,n (u) > k}, where v = (v 1 , . . . , v n ) with v i = (1 -p 0 )/n and p 0 = 1 -(p 1 + • • • + p n ) and where u = (1/n, . . . , 1/n).
This new conjecture is motivated by the following facts:

• the result is true for the expectations, see Theorem 5.

• the result is true for c = n, see Theorem 8.

• the result is trivially true for c = 1 since

È{T 1,n (p) > k} = È{T 1,n (v) > k} = p k 0 ≥ 1 {k=0} = È{T 1,n (u) > k}.
• the result is true for c = 2, see Theorem 9 below.

Theorem 9. For every n ≥ 2 and p = (p 1 , . . . , p n ) ∈ (0, 1)

n with p 1 + • • • + p n ≤ 1, we have, for every k ≥ 0, È{T 2,n (p) > k} ≥ È{T 2,n (v) > k} ≥ È{T 2,n (u) > k}, where v = (v 1 , . . . , v n ) with v i = (1 -p 0 )/n and p 0 = 1 -(p 1 + • • • + p n )
and where u = (1/n, . . . , 1/n).

Proof. From Relation (2), we have

È{T 2,n (p) > k} = -(n -1)p k 0 + n ℓ=1 (p 0 + p ℓ ) k and È{T 2,n (v) > k} = -(n -1)p k 0 + n p 0 + 1 -p 0 n k .
For every constant a ≥ 0, the function f (x) = (a + x) k is a convex on [0, ∞[, so we have, taking a = p 0 , by the Jensen inequality

p 0 + 1 -p 0 n k = 1 n n ℓ=1 (p 0 + p ℓ ) k ≤ 1 n n ℓ=1 (p 0 + p ℓ ) k .
This implies that È{T 2,n (p) > k} ≥ È{T 2,n (v) > k}.

To prove the second inequality, we define the function F n,k on interval [0, 1] by

F n,k (x) = -(n -1)x k + n x + 1 -x n k .
We then have F n,k (p 0 ) = È{T 2,n (v) > k} and F n,k (0) = È{T 2,n (u) > k}. The derivative of function F n,k is

F ′ n,k (x) = k(n -1) x + 1 -x n k-1 -x k-1 ≥ 0.
Function F n,k is thus an increasing function, which means that È{T 2,n (v) > k} ≥ È{T 2,n (u) > k}.

Application to the detection of distributed deny of service attacks

A Deny of Service (DoS) attack tries to progressively take down an Internet resource by flooding this resource with more requests than it is capable to handle. A Distributed Deny of Service (DDoS) attack is a DoS attack triggered by thousands of machines that have been infected by a malicious software, with as immediate consequence the total shut down of targeted web resources (e.g., e-commerce websites). A solution to detect and to mitigate DDoS attacks it to monitor network traffic at routers and to look for highly frequent signatures that might suggest ongoing attacks. A recent strategy followed by the attackers is to hide their massive flow of requests over a multitude of routes, so that locally, these flows do not appear as frequent, while globally they represent a significant portion of the network traffic. The term "iceberg" has been recently introduced to describe such an attack as only a very small part of the iceberg can be observed from each single router. The approach adopted to defend against such new attacks is to rely on multiple routers that locally monitor their network traffic, and upon detection of potential icebergs, inform a monitoring server that aggregates all the monitored information to accurately detect icebergs. Now to prevent the server from being overloaded by all the monitored information, routers continuously keep track of the c (among n) most recent high flows (modelled as items) prior to sending them to the server, and throw away all the items that appear with a small probability p i , and such that the sum of these small probabilities is modelled by probability p 0 . Parameter c is dimensioned so that the frequency at which all the routers send their c last frequent items is low enough to enable the server to aggregate all of them and to trigger a DDoS

Theorem 8 .

 8 For every n ≥ 1 and p = (p 1 , . . . , p n ) ∈ (0, 1) n with p 1 + • • • + p n ≤ 1, we have, for every k ≥ 0, È{T n,n (p) > k} ≥ È{T n,n (v) > k} ≥ È{T n,n (u) > k}, where v = (v 1 , . . . , v n ) with v i = (1p 0 )/n and p 0 = 1 -(p 1 + • • • + p n ) and where u = (1/n, . . . , 1/n).

  The sets S ′ i,n and S ′′ i,n form a partition of S i,n and since S ′′ i,n = S i,n-1 , we get

	n
	y ℓ
	ℓ=1	J∈Si-1,n(ℓ)

n} | |J| = i and n ∈ J}. Consider the set S ′′ i,n = {J ⊆ {1, . . . , n} | |J| = i and n / ∈ J}.

alarm when needed. This amounts to compute the time needed to collect c distinct items among n frequent ones. Moreover, Theorem 5 shows that the expectation of this time is minimal when the distribution of the frequent items is uniform.


Troquer le changement social contre des bonnes pratiques de gestion : l'animation face aux transformations du secteur associatif.

VACHEE Cécile et DANSAC Christophe

Laboratoire de Recherche Pluridisciplinaire du Nord est de Midi-Pyrénées (LRPMip) / IUT Toulouse 2 Figeac. Contact : cecile.vachee@univ-tlse2.fr ou christophe.dansac@univ-tlse2.fr Une partie des recherches évoquées dans ce papier a fait l'objet d'un partenariat avec la CPCA Midi-Pyrénées et d'un financement par la Région Midi-Pyrénées dans le cadre du programme de soutien aux recherches en SHS.

Historiquement, l'animation socioculturelle se développe en marge des marchés liés à la globalisation, au sein d'un système principalement fondé sur le secteur de l'économie sociale et solidaire et plus particulièrement sur le secteur associatif [START_REF] Lafortune | Vers un système d'animation socioculturelle : défis actuels et synergies internationales[END_REF]. Les associations sont perçues comme des organisations encore épargnées par la course aux profits économiques. Elles seraient des « refuges » portés par des formes de dénégation du profit où les valeurs humanistes et la solidarité primeraient sur la spéculation financière et la recherche de bénéfices. De récents sondages1 montrent que 87% des français interrogés ont une bonne opinion des associations et pensent qu'elles sont les acteurs les plus efficaces pour agir face aux difficultés provoquées par la crise. Pourtant, les analyses portant sur l'évolution du secteur associatif et de son environnement socio-économique montrent que les frontières entre le tiers secteur et le secteur marchand sont désormais ténues [START_REF] Hély | Les métamorphoses du monde associatif[END_REF].

Les antagonismes fondateurs (liberté d'adhésion, gestion démocratique et participative versus primauté du profit économique…) et revendiqués par le secteur associatif tendent à être remis en cause par les transformations des modèles de gouvernance des associations. Le contexte socio-économique et politique dans lequel elles évoluent les fragilise. Les craintes des dirigeants associatifs, concernant les moyens financiers ou humains de leur action sont grandissantes. La mise en concurrence, à toutes les échelles territoriales, par des politiques volontaires et/ou la raréfaction des ressources financières, les amène à s'inscrire dans des logiques parfois contradictoires avec leurs principes initiaux.

Dans ces conditions, les animateurs qui oeuvrent dans le secteur associatif voient évoluer les conditions de construction de leurs missions, voire la nature même de ces missions. Si l'animation socioculturelle peut se définir comme « un processus de diffusion de la capacité d'expérience sensible, d'expression, de sens critique, d'initiative et de créativité des populations » [START_REF] Lafortune | Vers un système d'animation socioculturelle : défis actuels et synergies internationales[END_REF] 2), les transformations récentes du secteur associatif tendent à redéfinir les contours de cette approche. Certains animateurs s'avouent par exemple contraints à une « pêche aux projets » dans laquelle ils ont le sentiment de s'éloigner de leur vocation émancipatrice initiale. À ces pressions qui s'exercent sur les financements s'ajoutent la culture de la responsabilité des politiques publiques et les évaluations qui l'accompagnent.

Elles obligent les acteurs associatifs à rationaliser leur activité afin de pouvoir en rendre compte. Cette culture de l'« accountability », dont certains sociologues ont déjà dénoncé les effets pervers dans le travail social [START_REF] Eliasoph | Top-Down Civic Projects Are Not Grassroots Associations: How The Differences Matter in Everyday Life[END_REF], impose à l'animateur un rôle de gestionnaire au détriment de ses missions originelles. Ce travail a donc pour but d'interroger, dans le contexte associatif français, la perspective d'une homologie structurelle entre les organisations du tiers secteur et les entreprises marchandes, et la façon dont le néolibéralisme, par son empreinte dans tous les secteurs, peut obérer les capacités d'intelligence stratégique de l'animateur. Il s'agit de comprendre comment les logiques de rationalisation et de croissance influencent la praxis de l'animateur professionnel dans un contexte où les associations doivent sécuriser leurs financements, et pour ceci, la plupart du temps, développer ou diversifier leurs activités.

Ainsi notre propos se centrera sur les animateurs qui travaillent pour des structures associatives, et laissera de côté ceux qui de plus en plus nombreux [START_REF] Gillet | L'animation en questions[END_REF] travaillent dans la fonction publique. Ceux-ci ne sont sans doute pas soumis aux mêmes contraintes, même si une part des phénomènes que nous aborderons doit sans doute les toucher également, et mériterait de recevoir plus d'attention de la part des chercheurs [START_REF] Bacou | Les effets de la territorialisation des emplois sur les parcours professionnels des animateurs/animatrices en accueils de loisirs[END_REF].

Les principales difficultés du secteur associatif

Les associations oeuvrant dans le domaine de l'éducation populaire et de l'animation socioculturelle connaissent, comme toutes les autres, de forts bouleversements : réforme des collectivités territoriales, baisse des financements publics, complexification de la gestion, modifications des formes de mobilisation des bénévoles, professionnalisation et spécialisation des salariés. La plupart des enquêtes 2 portant sur les difficultés des associations montrent que les principaux points de blocage et d'inquiétude sont liés aux aspects financiers. La recherche de financements est généralement évoquée au premier rang des difficultés exprimées, et ni les ressources d'activités, ni les subventions des collectivités locales ne semblent suffire. Les associations ont des difficultés à collecter des fonds qu'ils soient publics ou privés (mécénat par exemple) et ce en raison de la complexité et de la diversité de l'accès aux ressources, comme le notent Tchernonog et Vercamer (2006) 3 : entre 1999 et 2006, les financements des associations par l'État et les organismes sociaux (représentant près d'un quart, 23.6%, du budget global du secteur) ont baissé respectivement de 5 et 9%, soit une chute de 0.8 milliard d'euros. L'effort des collectivités (Communes : + 6% ; Départements : + 20% ; Régions : +40%) a certes augmenté, avec 2.1 milliards d'euros supplémentaires, mais cette augmentation est loin de compenser la perte subie si on la corrige par l'inflation et si on tient compte de l'augmentation globale de l'activité.

L'action associative semble donc mise en danger, et en tout cas ceux qui la conduisent en ont le sentiment : la plupart de ses responsables associatifs se plaignent des baisses des financements publics, de la complexification des procédures et du changement des modes d'investissement des bénévoles. Le changement des ressources apparaît aussi comme une préoccupation dans les enquêtes annuelles sur l'opinion des responsables associatifs4 . Ainsi parmi les associations employeuses, seuls 33% des dirigeants considèrent leur association en bonne santé sur le plan économique.

Pour faire face, les associations s'interrogent sur les solutions à mettre en place. Parmi elles, la communication est souvent présentée comme un remède aux difficultés rencontrées (Vachée & Dansac, 2011). Communiquer est vu comme un enjeu stratégique majeur qui permet de penser à la fois la politique de recrutement de bénévoles, la valorisation des actions et la recherche ou consolidation de partenariats et de financements ; la communication embrasse par conséquent un grand nombre de besoins et de préoccupations. Lorsqu'il est salarié d'une association, l'animateur, en sa qualité de chargé de projets, est appelé à développer cette forme de communication externe qui, s'adressant à un public de bénéficiaires des actions, n'est souvent qu'un leurre pour résoudre les difficultés des associations. En effet, dans un monde idéal où toutes les associations maîtriseraient les stratégies optimales de communication ainsi que les ressources afférentes nécessaires, les destinataires de cette dite communication seraient noyés sous un flot de propositions. Chacune de celles-ci n'aurait alors plus aucune valeur informationnelle comme le démontre la théorie de l'information de [START_REF] Shannon | A mathematical theory of communication[END_REF]. La même inefficacité peut être redoutée quant au rôle espéré de la communication dans la promotion du projet associatif auprès de bénévoles potentiels et des publics cible de l'animateur. Cette croyance en l'efficacité de la communication externe tend à reléguer l'effort d'inventivité que l'animateur doit fournir concernant des formes de communication interne et engageante envers les publics dans un but de co-construction des actions et projets. Cette croyance conduit à beaucoup investir dans la communication, on le voit dans les formations proposés aux bénévoles et aux futurs animateurs. Pour exemple, l'offre de formation du CARIF-OREF pour les animateurs fait apparaître cette prédominance de manière quantitative : Les 14 formations proposées5 sont dédiées à la communication en direction du public, majoritairement à travers les réseaux sociaux, et dans une moindre mesure en interne dans des espaces collaboratifs. Le programme du DUT Carrières Sociales (option animation socioculturelle) accorde lui aussi de nombreuses heures à la communication et à ses outils, incluant même un module « Marketing des associations ».

La croissance des activités comme solution au besoin de survie

D'autres solutions sont proposées par les acteurs associatifs pour survivre face aux difficultés rencontrées : la recherche d'efficacité dans le développement et la diversification des activités. Notre équipe a modélisé le cycle de développement du projet associatif des associations [START_REF] Dansac | De l'instrumentalisation des agences de moyens au service du lien social à la « dé-professionnalisation » de l'animation ? Animation, culture et citoyenneté : Modèles de politiques socio-éducatives et socioculturelles dans des contextes de changement[END_REF]. Dans ce cycle (cf. schéma 1), l'employeur associatif qui a réussi, grâce à l'investissement de ses bénévoles, à générer une activité suffisante pour professionnaliser son association, doit protéger ses emplois. Il est alors engagé dans une logique de croissance qui nécessite une gestion toujours plus complexe. Les acteurs associatifs se donnent des objectifs qui vont les obliger à adopter des techniques de management augmentant la bureaucratie. Ces évolutions vont impacter les manières d'envisager le projet associatif et bouleverser la hiérarchie des priorités dans les façons d'envisager les actions. Le développement des activités entraîne une cascade de conséquences sur le fonctionnement global de l'association et sur les modalités d'engagement de ses membres et salariés. En effet, l'augmentation des besoins matériels, financiers, humains et la recherche d'efficacité entraînent les acteurs dans une rationalisation de leurs actions et dans des logiques comptables. Dans les pays anglo-saxons, beaucoup d'associations introduisent des instruments du management car l'idée que les pratiques managériales améliorent l'efficience, bien que non validée est largement diffusée [START_REF] Kreutzer | Volunteering Versus Managerialism: Conflict Over Organizational Identity in Voluntary Associations[END_REF]. Le recrutement de professionnels nécessite la rédaction de fiches de postes, cette définition des statuts et des rôles apparait comme un fait nouveau dans l'organisation et participe du renforcement de la rationalisation. L'animateur peut alors se trouver aspiré par une dynamique managériale et gestionnaire qui peut l'écarter du sens et des valeurs qu'il confère à ses projets [START_REF] Peyre | Animation socioculturelle et employeurs associatifs : Livre noir : Du grand écart entre discours et pratiques ! (sous la direction de Marion Peyre[END_REF].

Ces évolutions sont rendues possibles par un contexte socio-économique bien particulier, favorable au développement des techniques de management dans les associations. Le transfert du modèle de gestion des entreprises vers les associations est facilité voire cristallisé par un ensemble de transformations du contexte juridico-administratif dans lequel évoluent les acteurs associatifs.

Schéma 1 : Cycle de vie du projet associatif [START_REF] Dansac | De l'instrumentalisation des agences de moyens au service du lien social à la « dé-professionnalisation » de l'animation ? Animation, culture et citoyenneté : Modèles de politiques socio-éducatives et socioculturelles dans des contextes de changement[END_REF].

Un contexte favorisant le modèle de l'animateur gestionnaire

Depuis le milieu des années 2000, on assiste à des transformations (Loi Organique relative aux Lois de Finances : LOLF ; Révision Générale des Politiques Publiques) dans les politiques publiques et leur évaluation, visant à augmenter leur efficacité et leur efficience par, entre autres, l'augmentation du contrôle de l'utilisation des deniers publics. Présentés comme un saut qualitatif dans la réponse publique aux besoins de la société, ces changements durcissent les relations entre financeurs et bénéficiaires en exacerbant la rationalisation des activités sociales. La diffusion d'une culture de la responsabilité comptable et d'une culture du résultat est un élément qui permet d'analyser l'impact de ces réformes sur le fonctionnement des associations. L'imposition de normes et de critères comptables réduit les activités à des indicateurs mesurables ce qui peut avoir pour conséquence la transformation du sens des actions. Les lignes financières spécifiques qui permettent de prendre en charge des besoins particuliers disparaissent au profit de financements d'actions ou de lignes de financement plus globales. Avec la LOLF, l'Etat organise ses dépenses par objectif et non plus par ligne budgétaire, les appels d'offre et les appels à projets se multiplient, obligeant les associations à se positionner dans un univers concurrentiel pour obtenir des financements.

Dans ces conditions, l'animateur en charge des projets doit transformer ses pratiques. Des animateurs salariés d'associations affirment lors d'entretiens devoir désormais aller « à la pêche aux projets » sous peine de « passer à côté » de financements. Le montage des dossiers dépend alors de la commande institutionnelle, des desiderata des financeurs qui se juxtaposent, tout comme les dispositifs, obligeant l'animateur à agir selon les opportunités de financement plutôt qu'en fonction de son analyse des besoins des bénéficiaires de l'action [START_REF] Hbila | Jeunes de quartiers populaires et politiques de jeunesse : l'expérience du Grand Ouest[END_REF]. Les animateurs sont en tension dans leurs pratiques professionnelles par le fait que l'action est de plus en plus dépendante de « commandes institutionnelles correspondant à une politique de services, où les projets sont des programmes préétablis et contraignants qui externalisent une politique publique » [START_REF] Richelle | Quelle évolution pour l'animation face à la tentative de marchandisation des associations d'éducation populaire ? 5e Colloque International de l'Animation Socioculturelle[END_REF].

La croissance des activités d'une association la met dans une spirale qui l'oblige à sécuriser ses financements : calculabilité, prévisibilité et sécurisation priment sur le contenu des projets.

Ces influences sont catalysées par le terreau socio-économique que nous venons de décrire.

Tout se passe alors comme si cette « course en avant » [START_REF] Bordes | Quelle évolution pour l'animation face à la tentative de marchandisation des associations d'éducation populaire ? 5e Colloque International de l'Animation Socioculturelle[END_REF] était dans l'ordre « naturel » des choses. A partir de là, elle n'est pas remise en question et peut s'imposer comme étant la norme et « ce modèle vise -idéalement -l'assujettissement radical de la décision à la production de chiffres » (Ogien, 2007, p. 140). On assiste donc à une véritable « emprise de l'esprit gestionnaire » et la généralisation de l'utilisation du terme de « gouvernance » dans les réflexions sur le fonctionnement du secteur non-marchand est un symptôme du renforcement de l'intégration des principes d'efficacité au détriment du débat démocratique et de l'échange d'idées [START_REF] Ogien | La gouvernance, ou le mépris du politique[END_REF].

b. L'externalisation des ressources

Le besoin croissant de bénévoles [START_REF] Tchernonog | Le paysage associatif français, 2007 : mesures et évolutions : profil, activités, budget, financement, dirigeants, gouvernance, emploi salarié, travail bénévole[END_REF] associé aux changements de leurs modes d'engagement [START_REF] Ion | L'engagement au pluriel[END_REF] [START_REF] Simonet | Give back to the community » : le monde du bénévolat américain et l'éthique de la responsabilité communautaire[END_REF].

En France, ce renouveau de « l'appel aux bonnes volontés qui risque de porter de nouvelles atteintes à la professionnalité de l'animateur » [START_REF] Ion | Brève chronique des rapports entre travail social et bénévolat[END_REF] Le recours aux agences de bénévoles ainsi que la promotion du volontariat sont des éléments qui encouragent l'approche par compétences dans la gestion des ressources humaines. Le métier d'animateur risque alors la réduction de ses fonctions à des techniques d'encadrement, dont il devra apprendre à rendre compte en termes d'efficacité. S'il a recours au volontariat, l'animateur devra évaluer l'action de ces volontaires à l'aide de critères qu'il n'a pas luimême mis en place mais qui sont prédéfinis par les institutions en charge de la promotion du dispositif. La ressource humaine n'est donc pas engagée en fonction des besoins et de l'essence du projet associatif mais en fonction de critères d'évaluation externes. Les missions de l'animation se transforment donc sous l'effet de l'apport immédiat et facilité des « plugg-in volunteers » [START_REF] Eliasoph | Top-Down Civic Projects Are Not Grassroots Associations: How The Differences Matter in Everyday Life[END_REF]. L'animateur n'est plus engagé dans des projets innovants ayant pour objectif de mobiliser des publics qu'il aurait repérés en amont, mobilisation qui pour lui ne correspondrait pas à une simple « levée de main d'oeuvre », mais participerait d'un processus de création du lien social dans la co-action. Dans un scénario pessimiste, les animateurs ne seraient plus nécessaires, déjà remplacés par des gestionnaires dont les fonctions essentielles seraient celles qui incombent à la Gestion des Ressources Humaines des entreprises privées. Ils perdraient le contact avec le terrain et les valeurs qui ont sous-tendu au départ l'action associative. Une telle dérive menant à la perte du sens de l'action et des valeurs est déjà signalée par certains y compris dans des mouvements historiques d'éducation populaire [START_REF] Peyre | Animation socioculturelle et employeurs associatifs : Livre noir : Du grand écart entre discours et pratiques ! (sous la direction de Marion Peyre[END_REF]. Ainsi on voit déjà certains Centre Sociaux ou des associations à 7 www.uniscité.fr, consulté le 3/09/2011 vocation sociale confier des tâches aux bénévoles recrutés, pour 4 heures en échange d'une place de concert, par la Fondation Orange RockCorps.

c. Le danger de la valorisation du bénévolat

La baisse du nombre de bénévoles engagés dans les associations [START_REF] Tchernonog | Le paysage associatif français, 2007 : mesures et évolutions : profil, activités, budget, financement, dirigeants, gouvernance, emploi salarié, travail bénévole[END_REF] a progressivement amené les acteurs associatifs à envisager des outils pour susciter de nouvelles vocations ou fidéliser voire renforcer celles existantes. Parmi ces outils on retrouve de manière régulière l'évocation de contreparties matérielles : par exemple la proposition de loi8 n°3561 vise à valoriser à hauteur d'un trimestre de cotisation pour la retraite la responsabilité associative pendant 5 ans d'affilée.

Une autre solution envisagée est déjà mise en oeuvre : la valorisation des compétences acquises. On peut prendre l'exemple du Passeport Bénévole mis en place par France Bénévolat. Il est conçu comme un véritable outil de traçage des expériences du bénévole qui permettrait à celui-ci, à terme, de récapituler les compétences qu'il a acquises et de les faire valoir dans un cadre de Validations des Acquis de l'Expérience. Des tels outils commencent à se diffuser dans les mouvements d'éducation populaire, on les retrouve chez les Scouts et Eclaireurs de France, ou encore chez les FRANCAS, et également dans le monde sportif. La légitimité de cette démarche est appuyée par la complexité croissante de l'environnement dans lequel évolue le bénévole et la nécessité de formation que celle-ci entraîne.

Si une des fonctions de l'animation est de mobiliser les bénévoles autour d'un projet dans une dynamique engageante, le risque de ces contreparties est de modifier la nature des motivations qui conduisent au bénévolat. On peut ainsi craindre que les vocations carriéristes soient favorisées au détriment d'un engagement par et pour des valeurs. Les premières sont en forte attente de résultats concrets et à court terme alors que seules les secondes permettent d'envisager un horizon de transformation sociale à long terme [START_REF] Ion | La fin des militants[END_REF]. Le monde associatif essaie d'attirer les bénévoles comme le secteur marchand essaie d'attirer des clients, avec tout ce que cela entraîne comme risque de consumérisme. Dans une logique comptable, l'animateur peut être amené à développer ces dispositifs de valorisation des bénévoles pour des motifs opportunistes et quantitatifs.

d. Les injonctions à la mise en réseau et à la mutualisation

Si la logique de réseau et de partenariats, avec tout ce qu'elle sous-entend en termes de facilités de communication, est compatible avec la promotion du projet associatif et sa pérennité (chères aux acteurs associatifs), il n'en est pas de même concernant la mutualisation. Des craintes sont exprimées quant à la perte d'autonomie et à la dissolution des valeurs originelles, véritables menaces pour l'identité de l'association9 . Le rapport de force lié à la taille des associations, la mise en concurrence dans les choix d'attribution des financements, et la vulnérabilité aux options politiques territoriales suscitent des inquiétudes quant à la pérennité des ressources matérielles.

La mutualisation, le partenariat, et la mise en réseau, en augmentant la quantité d'acteurs en jeu, tendent à déposséder chacun du contrôle sur l'action et sur les moyens de celle-ci, ainsi que sur la valorisation qui viendrait des résultats de l'action. Il s'agit donc d'un facteur de risque pour la mobilisation. Il y a là un nouveau danger pour l'animateur qui, s'il doit impulser la dynamique de partenariat et de mise en réseau, risque d'augmenter la rationalisation et la comptabilisation des moyens.

e. Le développement du mécénat

Associé à la problématique de la diminution des moyens, se trouve aussi une pression à l'hybridation des ressources, dont le principe semble désormais totalement intégré (cf. numéro spécial Associations du Monde du 27/10/2011, Guide du Routard des Associations et des Fondations), comme il l'est déjà dans le monde anglo-saxon, où les financements des entreprises ou de leurs fondations sont devenus incontournables pour le montage de projets.

Les Dispositifs Locaux d'Accompagnement (DLA), qui visent à favoriser la survie des associations, encouragent cette hybridation et accompagnent l'externalisation : des entreprises sont sollicitées dans le cadre de mécénat ou de bénévolat de compétences pour la communication externe (fabrication de sites web, mailing, campagne publicitaire).

Les associations sont ainsi parfois obligées de consolider des partenariats avec des organisations à but lucratif dans le cadre de mécénat [START_REF] Hély | Les métamorphoses du monde associatif[END_REF]. Cela les amène parfois à adhérer à des logiques antagonistes (logique économique orientée vers le profit vs valeurs de désintéressement prônées par le mouvement associatif). L'action de ces entreprises peut parfois s'associer avec celle des agences de moyens, comme c'est le cas dans le programme « Passeurs de mémoires », partenariat entre groupe Malakof-Médéric et l'association Unis-Cité. Celui-ci permet à des jeunes volontaires de celle-ci d'être en contact avec des pensionnaires des établissements gérés par celui-là. Ce genre de partenariat peut parfois amener à une externalisation totale de la fonction d'animation, risquant à terme de provoquer la disparition de l'animateur, ou son utilisation à seule fin de gérer des programmes de ce type.

L'animateur en coeur d'un champ de forces complexe

Les changements décrits ci-dessus traduisent un ensemble de pressions, de tensions et de forces sur l'animateur et sur sa professionnalité en tant que « nature plus ou moins élevée et rationalisée des savoirs et des capacités utilisés dans l'exercice professionnel » [START_REF] Bourdoncle | La fascination des professions[END_REF]. A partir de la conceptualisation de l'animation professionnelle proposée par [START_REF] Gillet | Animation et animateurs : le sens de l'action[END_REF], déjà inspirée de la dynamique des groupes, nous nous proposons d'utiliser la théorie des champs de force [START_REF] Lewin | Field Theory And Experiment In Social Psychology: Concepts And Methods[END_REF] On pourrait imaginer des associations fonctionnant en totale autonomie, sans partenaires ni financeurs, ayant ainsi un champ de la gouvernance réduit à l'interaction entre salariés et dirigeants bénévoles.

Le Champ psychologique de l'Animateur

Parmi les forces qui interagissent dans le Champ psychologique de l'Animateur, on identifie celles qui l'orientent vers des valeurs (fonction militante), vers des publics (fonction médiatrice), vers des pratiques (fonction technicienne). Comme le propose [START_REF] Gillet | Animation et animateurs : le sens de l'action[END_REF], l'équilibre de ces forces permet le développement de compétences spécifiques et stratégiques propres au champ de l'animation. La variation de chacune des forces (remise en question des valeurs, préjugés sur les publics, défaut de compétences ou de connaissances techniques) peut réduire les capacités stratégiques de l'animateur, indépendamment de son environnement.

Ainsi, comme le symbolise le triangle figurant au centre de ce champ, l'animateur peut être amené à accorder plus d'importance à une fonction, éventuellement aux dépends des autres.

Nous faisons l'hypothèse que les phénomènes évoqués précédemment créent, dans et hors l'association, des forces qui peuvent également influencer les pratiques de l'animateur. Ce sont ces influences sur ses pratiques qui sont symbolisées par les triangles qui figurent dans le schéma 2 dans les autres champs.

Schéma 2 : Les forces qui influencent les fonctions professionnelles de l'animateur Le Champ de l'Association L'animateur n'évolue pas en apesanteur. Il est inséré dans une organisation qui produit des contraintes : le Champ de l'Association. Ce dernier est d'une part particulièrement influencé par le besoin de survie lié à la présence de professionnels à rémunérer. D'autre part, il est structuré par des rapports et enjeux de pouvoir liés aux situations d'interdépendances stratégiques entre les acteurs [START_REF] Friedberg | Le pouvoir et la règle : dynamiques de l'action organisée[END_REF]. Ces interactions s'inscrivent dans un contexte où des acteurs extérieurs interviennent et influencent les modes d'administration de l'association dans des liens fonctionnels qui construisent le Champ de la Gouvernance.

Le Champ des Publics

Les associations du secteur de l'animation socioculturelle ne peuvent être abordées en dehors des publics pour et avec lesquels elles évoluent. Ces publics peuvent être des adhérents, des bénéficiaires/usagers, des bénévoles.

Les bénéficiaires/usagers, selon leur rapport à l'activité de l'association, déploieront des attitudes consommatrices, engagées, ou résistantes. L'engagement du public, parce qu'il adhère au projet et aux valeurs de l'association, stimulera les fonctions militante et médiatrice de l'animateur. En revanche, une attitude consommatrice obligera l'animateur à mettre de côté ses convictions pour répondre aux demandes et évaluer son action de façon quantitative. Parfois, les animateurs sont en position de responsabilité de direction ou de coordination, et sont alors associés aux réflexions des administrateurs de l'association, et donc inclus dans ce champ de la gouvernance. Dans ce cas, la nature de la fonction de médiation (médiaction pour Gillet) est changée, et cette fonction est plus orientée vers la mise en lien de partenaires, la mise en réseau, que vers la rencontre des publics (Monceau, 2012).

Le Champ des Partenaires et celui des Financeurs

Les incitations aux partenariats vont, de fait, renforcer ces effets. La mise à disposition (de matériels, de personnels, etc.) -présentée comme une solution aux problèmes rencontrésimpose des pratiques de gestion en termes de planification, de partage de la ressource, d'approche par compétences, etc. Si l'association n'est pas autonome d'un point de vue financier, elle est prise dans une dynamique de recherches de fonds qui renforce les pratiques de rationalisation, poussant l'animateur vers le rôle de gestionnaire.

Les Opportunités ou Menaces

Dans l'inventaire des phénomènes qui impactent les stratégies de l'animateur, nous avons également identifié l'existence de certaines opportunités, outils hautement accessibles, faciles et/ou peu coûteux. Ces opportunités happent les pratiques des animateurs, parfois les attirant vers l'animation concrète aux dépens de l'animation abstraite (au sens de Gillet, 2006, p. 182).

Le mécénat de compétence est souvent mis en avant par les acteurs comme moyen de compléter les ressources humaines internes. Ainsi des associations confient certaines tâches, notamment de communication (élaboration de document, diffusion, création de sites web) à des salariés d'entreprises privées (soutenu et aidé dans cette démarche par des DLA, Dispositifs Locaux d'Accompagnement). L'externalisation de la communication peut obliger les animateurs à l'élucidation, les amenant à questionner les valeurs qui sous-tendent leur action, et leurs spécificités par rapport à d'autres acteurs. Elle les allège de la dimension technique associée à l'ensemble des démarches à mettre en oeuvre pour la communication externe. La résultante globale de ces forces serait plutôt au service du changement social. La disponibilité d'équipements et de matériels, dans lesquels les collectivités ou même les associations auraient investi préalablement relève également de ces phénomènes, créant parfois une véritable pression à l'utilisation, susceptible de ramener l'animateur à ses fonctions techniques sans qu'il ait le choix de questionner la pertinence de l'utilisation de ces outils par rapport aux valeurs qui le guident dans sa pratique. La possibilité déjà évoquée de faire appel à des agences de moyens se situe dans ce cadre, l'externalisation du bénévolat apparaît alors comme une contrainte pour l'association, obligeant l'animateur à définir les tâches que ces extérieurs devront assumer, créer des emplois du temps, bref gérer techniquement des ressources humaines.

Enfin une forte pression temporelle pèse parfois sur l'animateur (ex. délai réduit pour répondre à des appels d'offre, actions financées sur des périodes courtes), surtout quand celuici est amené à exercer une multitude de rôles au sein de l'association. Il est alors empêché de laisser mûrir les projets, voit diminuer sa capacité à mobiliser des publics sur le long terme dans des démarches véritablement génératrices de lien, et est orienté vers des techniques permettant d'optimiser ses actions.

Une éthique de responsabilité éloignant de la praxis ?

L'animateur professionnel est un acteur doté de compétences pour apprécier les situations sociales dans lesquelles il est plongé [START_REF] Weber | Economie et société (édition en 2 tomes[END_REF]. Avec Weber et plus tard les pragmatistes français, on doit donc considérer que son action (rationnelle) peut être guidée soit par des valeurs et des convictions, soit par une finalité, un objectif. Lorsqu'il agit selon ses valeurs et ses convictions, l'animateur active le pôle « militant » décrit par [START_REF] Gillet | Animation et animateurs : le sens de l'action[END_REF] et agit sans mesurer ce qu'il peut lui en coûter. Ainsi lorsqu'il construit des projets, c'est le sens qui prime sur les autres dimensions, et en particulier sur la dimension technique.

La situation de changement que nous décrivons dans cet article a des conséquences sur la nature des actions rationnelles. Avec la montée de l'esprit gestionnaire et ses corollaires, l'animateur tend à agir en fonction de finalités comptables, en subordonnant la défense de ses convictions. En effet, l'action rationnelle en finalité cultive le lien avec les instruments qui permettent de mesurer et de comptabiliser les activités sociales, les calculs, les évaluations, les statistiques. La rationalisation, qui s'est accélérée ces dernières années, devient la norme et écarte les autres types d'agissement. Les comportements sont taxés d'immobilistes pour ceux qui relèvent de l'action traditionnelle (habitudes), d'irréalistes pour ceux qui se réfèrent à l'action affectuelle, et d'incantatoires manquant de réalisme pour ceux qui relèvent de la conviction [START_REF] Lemieux | La sociologie sur le vif[END_REF]. L'animateur se trouve donc en tension entre les deux éthiques, celle de la conviction et celle de la responsabilité, mais c'est cette dernière qui a le plus de chance de s'imposer au regard du contexte actuel. Or, chez Weber, c'est l'équilibre entre les deux éthiques qui devrait guider nos choix car, l'éthique de la responsabilité peut conduire à l'opportunisme alors que l'éthique de conviction lorsqu'aucune considération pratique et concrète ne la modère, peut dégénérer en fanatisme et intolérance. Soumis à ces tensions, on peut se demander si l'animateur est encore capable de produire une réflexion sur ses pratiques, et quelle est son rapport à la praxis en tant que système où l'action est concertée, précédée et accompagnée de décision et d'évaluation [START_REF] Gillet | Animation et animateurs : le sens de l'action[END_REF].

  Il paraît difficile pour l'animateur d'échapper à cette emprise, d'autant plus difficile qu'une série de dispositifs incitatifs fleurissent actuellement pour contrecarrer la « baisse de l'engagement » ou « crise du bénévolat ». Notre objectif est ici de montrer comment cet ensemble de mesures vient renforcer la dimension gestionnaire et opportuniste dans les fonctions d'animation.4. Des incitations qui renforcent l'opportunisme et le pragmatisme a. La promotion du bénévolatLa recommandation de la valorisation comptable du bénévolat dans l'Union Européenne, suivant les préconisations du Bureau International du Travail et de l'Organisation des Nations Unies[START_REF] Archambault | Mesurer le bénévolat pour en améliorer la connaissance et satisfaire à une recommandation internationale[END_REF] se traduit en particulier par l'injonction à « mesurer » la participation bénévole et à l'intégrer dans les budgets des associations. A cette volonté de déterminer la valeur du bénévolat s'associe une volonté de le promouvoir. Par l'ONU d'abord, en 2001, même si l'année mondiale du bénévolat a été éclipsée en France par le centenaire des associations, ensuite par la Communauté Européenne qui l'a remis à l'ordre du jour à travers l'Année Européenne du Bénévolat, en 2011, déployant un dispositif de communication important 6 . Par l'Etat enfin, qui pour soutenir ces bonnes pratiques, et favoriser le civisme qu'elles mettent en exergue, mais aussi pour répondre à la problématique de l'insertion professionnelle des jeunes, a promulgué la loi sur l'égalité des chances qui instaure le Service Civil Volontaire en l'accompagnant de la création de l'agence du service civique.

  , a favorisé l'apparition d'une nouvelle forme d'associations qui visent à organiser, avec des méthodes proches de celles des agences d'intérim, l'engagement bénévole ou le volontariat au service d'actions impactant le champ social, socioculturel ou environnemental. Ce type d'agences existe depuis plus longtemps en Amérique du Nord. Par exemple aux USA, Impact Online Inc. (créée en 1994 par quatre diplômés de Master of Business) opère le site internet VolunteerMatch qui permet de trouver facilement des missions bénévoles ; City-Year organise, avec le soutien de programmes fédéraux, des services civiques

  est institutionnalisé par les associations comme Uni-Cités ou France Bénévolat. Ces nouvelles entreprises associatives sont considérées comme aptes à combattre les problèmes sociaux et à orienter les jeunes vers une vie de solidarité et d'entraide. En nécessitant des postes d'encadrement hiérarchique et d'organisation des tâches, ce mouvement engendre la création de postes de Gestion des Ressources Humaines pour les bénévoles, ce qui impacte une fonction centrale des animateurs : la dynamisation et la coordination des bénévoles. De fait, quand on regarde la composition des équipes de France Bénévolat ou d'Unis-Cité, on s'aperçoit qu'il n'y a pas d'animateur professionnel, l'essentiel des missions étant assuré par des personnes ayant des formations en communication, en business, et en gestion. Parmi les offres d'emploi de l'association 7 , aucune ne requiert un diplôme d'animation.

  pour schématiser les changements repérés. Il s'agit de décrire et d'évaluer le poids des forces positives favorables au développement du projet initial de l'animation -le changement social -et celui des forces défavorables, qui éloignent l'animateur de ses missions originelles et de ce qui fonde le « coeur de métier » en accentuant les pratiques gestionnaires. Loin d'épuiser toutes les forces qui peuvent être impliquées dans la détermination des pratiques, ou les phénomènes qui traversent le monde associatif, cette analyse systémique (tirée d'éléments empiriques) vise à donner les prémisses d'un nouveau cadre d'analyse de l'animation professionnelle. Nous avons identifié 6 champs inhérents aux fonctions et à l'environnement professionnel de l'animateur : le Champ psychologique de l'Animateur, le Champ de l'Association, puis ceux des Publics, des Financeurs, de la Gouvernance, et des Partenaires. Ces champs sont représentés dans le schéma 2 par des zones qui se recouvrent plus ou moins selon les réalités fonctionnelles des associations. Ainsi certaines associations n'ont comme bénéficiaires que leurs adhérents, ramenant alors le Champ du Public à l'intérieur du Champ de l'Association.

  Enfin, la résistance des publics entraîne une réflexion globale sur le sens et le besoin de leur captation. Cette prise de recul permet à l'animateur de questionner les bénéfices de ses actions et il active ainsi son rôle de « militant ». Mais cette attitude des publics renforce dans le même temps la tentation d'attirer les publics pour de « mauvaises raisons », à savoir pour augmenter les effectifs. Dans ce sens, l'animateur sera tenté par la communication externe, ce qui renforce le pôle technicien et gestionnaire.Le besoin de survie de l'association rend cruciale la pérennité voire l'augmentation de la ressource bénévole, favorisant le recours à de formes d'externalisation de la ressource humaine. La gestion de cette ressource, et les incitations à la valorisation du bénévolat obligent l'animateur à déployer des techniques de management, particulièrement dans un contexte de motivations carriéristes. Il s'éloigne ainsi d'une de ses fonctions premières qui consiste à impliquer les bénévoles dans la co-construction des projets, ce qui renforce les forces qui l'attirent vers le pôle gestionnaire et technicien.Enfin, il existe dans certaines associations des dirigeants qui peuvent, par leur désir de pouvoir et leur besoin de contrôle, produire des demandes qui écartent les animateurs de leurs fonctions d'origine parce que ces derniers n'ont plus aucun rôle dans la définition des objectifs des projets et sont relégués à des fonctions techniques. Ce genre de situation peut aussi produire une réaction inverse de résistance chez l'animateur désireux de réaffirmer sa place et ses missions.Les dirigeants et les bénévoles, par leurs actions et positions dans l'association, participent à la dynamique du champ de la gouvernance.Le Champ de la GouvernanceLe besoin de survie et le contexte dans lequel baignent les associations poussent les acteurs à s'inscrire dans une culture managériale qui renforce sans équivoque le pôle technicien des fonctions d'animateurs par la gestion des ressources humaines, la logique comptable, etc. La nécessité de s'inscrire dans des projets communs multiplie le nombre de partenaires et donc le nombre de voix dans les prises de décisions. Contraints de négocier, les animateurs peuvent être amenés à faire le deuil d'un certain nombre de leurs valeurs pour ne pas entraver la réalisation d'un projet et pour que le consensus se fasse.L'hypothèse de ce Champ de la Gouvernance est d'autant plus importante que l'animation est de plus en plus territorialisée, et que dans ce domaine, comme dans d'autres (cf. le lobbying associatif pour la création du service civique,[START_REF] Simonet | Le travail bénévole : engagement citoyen ou travail gratuit? Paris: La Dispute[END_REF], les associations contribuent souvent à l'élaboration de ses politiques dans un cadre de gouvernance territoriale (par exemple dans l'élaboration des Contrats Educatifs Locaux).

Sondage Le Parisien-Aujourd'hui en France / Fonda /CEVIPOF, L'image des associations en France, CSA -Janvier

2007. Sondage CSA/Chorum/MAIF/Crédit coopératif, Les français, les associations et la crise, Octobre 2009.

Accompagnement : les associations actrices de leur développement. Bulletin de la CPCA n°15, juin 2011. Tchernonog V., Vercamer J-P., Trajectoires associatives -Les facteurs de fragilité des associations,Deloitte, 2006.

Tchernonog, V., & Vercamer, J.-P. (2006). Trajectoires associatives -Enquête sur les facteurs de fragilité des associations. CNRS.

Bazin, C., & Malet, J. (2011). L'opinion des responsables associatifs employeurs. Recherches et Solidarités.

Consultation du site du CARIF-OREF au 19 janvier 2012

Signalons que cette préoccupation européenne de mobiliser des forces de travail gratuites ou à faible coût se traduit aussi par la déclaration de l'année 2012 comme étant celles des Séniors actifs.

enregistrée à la Présidence de l'Assemblée Nationale le 22 juin 2011

Vachée, C. et Soldano, C. (2011). Vie associative et territoires. Une enquête réalisée auprès des associations du Parc Naturel Régional des Causses du Quercy et du SICOVAL, Rapport CPCA/PNRCQ.