Line Le Goff

Philippe Soulier

Parameter estimation of a two-colored urn model class

Though widely used in applications, reinforced random walk on graphs have never been the subject of a valid statistical inference. We develop in this paper a statistical framework for a general two-colored urn model. The probability to draw a ball at each step depends on the number of balls of each color and on a multidimensional parameter θ through a function f , called a choice function. We introduce two estimators of θ: the maximum likelihood estimator and a weighted least squares estimator which is less efficient, but is closer to the calibration techniques used in the applied literature. In general, the model is an inhomogeneous Markov chain and this property makes the estimation of the parameter impossible on a single path, even if it were infinite. Therefore we assume that we observe i.i.d. experiments, each of a predetermined finite length. This is coherent with the usual experimental set-ups. We apply the statistical framework to a real life experiment: the selection of a path among pre-existing channels by an ant colony. We performed experiments, which consisted of letting ants pass through the branches of a fork. We consider the particular urn model proposed by J.-L. Deneubourg in 1990 to describe this phenomenon. We simulate this model for several parameter values in order to assess the accuracy of the MLE and the WLSE. Then we estimate the parameter from the experimental data and evaluate confident regions with Bootstrap algorithms. The findings of this paper do not contradict the biological literature, but give statistical significance to the values of the parameter found therein.

Introduction

Urn models have been studied for nearly one century. In 1931, G. Pólya provided the first probabilistic result on the game consisting in drawing a ball from an urn initially containing one red ball and one black ball (see [START_REF] Pólya | Sur quelques points de la théorie des probabilités[END_REF]. At each time step, a ball is drawn and put back in the urn with an additional ball of the same color. The probability to draw a red ball is the proportion of red balls in the urn. G. Pólya proved that, as the number of draws tends to infinity, the proportion of red balls tends to a random variable following the uniform distribution on [0, 1].

The Pólya urn is easily generalizable to a large class of two-colored urn models characterized by a choice function f : Θ × N × N → [0, 1] which itself depends on a parameter θ ∈ Θ ⊂ R d , d ≤ 1. Let R n and B n be the numbers of red and black balls in the urn after n draws. Note that, by construction, R n + B n = n. The probability that the (n + 1)-th ball is red is given by

prob R n+1 = f (θ, R n , B n ) = f (θ, R n , n -R n ) . (1)
Consequently, the probability to draw a black ball at time n + 1 is 1 -prob R n+1 . The goal of this paper is to propose a valid statistical methodology to estimate the parameter θ. We suppose that we observe N independent paths, each consisting of a sequence of n colors drawn by the model defined in (1). The statistical theory is developed as n is fixed and N tends to infinity. We choose this framework since in some models, it is not possible to obtain consistent estimators of the parameter with only one path, even if its length n increases to infinity. Moreover data from real experiments comprises a set of finite paths. We define estimators for θ that we prove to be consistent and asymptotically normal under some usual regularity assumptions on the model (1). We study more precisely two particular cases: the maximum likelihood estimator (MLE) and the weighted least squares estimators (WLSE).

We have applied these statistical tools to the problem of path formation by an ant colony. One of the fundamental factors affecting an organism's survival is its ability to optimally and dynamically exploit its environment. For example, in order to take advantage of the best sites of resources, housing or reproduction, these areas must be discovered and exploited at the earliest opportunity. Many species of ants rise to this challenge by developing a network of paths, which connects different strategic sites such as nests and food sources. These paths consist of pheromones, attractive chemical substances. We focus on a specific aspect of this phenomenon: the selection of a path among pre-existing channels. When exploring their environment, ants often face bifurcations and must bypass obstacles. As shown by experimental studies, the laying of pheromones by ants passing successively through a bifurcation results in two possible outcomes: either one branch is eventually selected and the other abandoned, or both branches end up being uniformly chosen (see [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF]. The analysis of the spontaneous path formation by a colony of ants is made difficult by the absence of any means to measure precisely the quantity of, or even detect, the pheromones laid by the ants.

It is commonly assumed that when approaching a bifurcation, ants choose a branch and lay a certain constant amount of pheromone without ever turning back. Consequently, the quantity of pheromone laid on a branch is proportional to the number of ants which passed through it. Thus this phenomenon can be described by a urn model as proposed by J.-L. [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF] (see [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF]. More precisely they define a choice function with a two-dimension parameter (α, c) ∈ (0, 1) 2 such that the probability for an ant to choose the right branch after R n passages through the right branch and n passages in total is given by

P rob R n+1 = (c + R n ) α (c + R n ) α + (c + n -R n ) α .
(2)

The probability to choose the left branch is consequently 1 -P rob R n+1 . The parameter α makes this model non linear with respect to the proportion of passages through one branch. It models the sensitivity of the ant to the concentration of pheromone. The parameter c is the intrinsic attractiveness of each branch and can also be interpreted as the inverse of the attractiveness (or the strength) of the pheromone deposit laid by each ant.

Several probabilistic studies provide the asymptotic behavior of R n /n in terms of α and c (see [START_REF] Pólya | Sur quelques points de la théorie des probabilités[END_REF][START_REF] Tarrès | Localization of reinforced random walks[END_REF][START_REF] Davis | Reinforced random walk[END_REF]. The influence of the two parameters is on different time scales, but they can contribute to the same effect (selection of one branch or unifomization of the traffic on the two branches) or have antagonistic effects. The model is thus characterized by four phases, according to the values of α and c: slow or fast uniformization; slow or fast selection. The phase most commonly considered in the literature is slow selection. This corresponds in our model to α and c larger than 1: selection of one branch will eventually happen, though slowly because of weak pheromone deposits (see [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF][START_REF] Vittori | Path efficiency of ant foraging trails in an artificial network[END_REF][START_REF] Garnier | Path selection and foraging efficiency in argentine ant transport networks[END_REF]. However, the model may account for other possibilities, such as fast uniformization, which occurs when α < 1 and c > 1. One purpose of this paper is to investigate more thoroughly these possibilities which have been more or less overlooked in the previous literature.

Ethological studies have already provided values for the parameter (α, c), but the methods used mainly consisted of calibration without control of the statistical validity of these methods and results (see [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF][START_REF] Vittori | Path efficiency of ant foraging trails in an artificial network[END_REF][START_REF] Garnier | Path selection and foraging efficiency in argentine ant transport networks[END_REF][START_REF] Thienen | Pheromone communication in ants: a detailed analysis of concentration-dependent decisions in three species[END_REF] and in particular these methods do not produce confidence regions. However this type of information supplies interesting and important elements to the behavioral discussion. However this type of information supply interesting and important elements to the behavioral discussion. In this paper, we define the MLE and the WLSE for the ant behavior model (2). We assess the quality of these estimators in a simulation experiment. We then use them on experimental data provided by a real life experiment performed to this purpose with ants. We also compute confidence region by a Bootstrap algorithm.

The model ( 2) can be applied, mutatis mutandis, to many other fields. For instance we can consider a fork with two branches as a neuron having two axons. During each period of time, the length of one of the two axons increases. The longer an axon is, the higher the probability that it will further grow. Thus the dynamic of this biological system may also be modeled by (2) (see [START_REF] Khanin | A probabilistic model for the establishment of neuron polarity[END_REF]. Furthermore, using the notion of a choice function (see Section 2.3), the model (1) can be adapted and applied to many situations where a binary choice occurs, or to even more complex situations such as networks with several nodes (see [START_REF] Jeanson | Pheromone trail decay rates on different substrates in the pharaohs ant, monomorium pharaonis[END_REF][START_REF] Pemantle | A survey of random processes with reinforcement[END_REF], for instance network exploration by an ant colony (see [START_REF] Aron | Functional Selforganisation illustrated by Inter-nest Traffic in Ants : the Case of the Argentine Ant[END_REF][START_REF] Beckers | Modulation of trail laying in the ant lasius niger (hymenoptera: formicidae) and its role in the collective selection of a food source[END_REF][START_REF] Nicolis | Emerging patterns and food recruitment in ants: an analytical study[END_REF][START_REF] Dussutour | Amplification of individual preferences in a social context: the case of wall-following in ants[END_REF][START_REF] Nicolis | Self-organization, collective decision making and resource exploitation strategies in social insects[END_REF][START_REF] Thienen | Pheromone communication in ants: a detailed analysis of concentration-dependent decisions in three species[END_REF][START_REF] Arganda | Collective choice in ants: The role of protein and carbohydrates ratios[END_REF].

The paper is organized as follows. The model (1) and the statistical framework is rigorously defined in Section 2. Section 2.1 is focused on the MLE and Section 2.2 on the WLSE. Under some usual regularity conditions, we prove that both estimators are consistent and asymptotically normal. Moreover the MLE is asymptotically efficient. The numerical implementation of the MLE may be difficult and unstable (and lengthy), therefore, a WLSE is considered and theoretically studied. This estimator does not match the theoretical performances of the MLE, but is easier to compute and is popular among practitioners. Section 2.3 proposes an extension of the general urn model to a class of vertex reinforced random walk on graphs. Section 3 is an adaptation of the statistical framework to the ethological problem. In Section 3.1, we first introduce the assumptions on the ant behavior and then we define the model proposed by J.-L. Deneubourg. The four phases of the model are described more precisely and are interpreted from the point of view of ethology. Section 3.2 rewrites the MLE and the WLSE for this particular case. In Section 3.3, we show that it is not possible to consistently estimate the parameter of the model on a single experiment of length n, even if n tends to infinity. In order to assess the performance of the estimators, a short simulation experiment is reported in Section 3.4. Section 4 reports the study on the experimental data. The experimental protocol and the data produced are described in Sections 4.1 and 4.2. Section 4.3 supplies the estimation results (computation of the estimators and their confidence regions). We provide some concluding remarks in Section 5 and prove the theoretical statistical results of this paper in Section 6.

Parameter estimation

Let us first write precisely the model studied and statistical framework used. We assume that {X k , k ≥ 1} is a sequence of Bernoulli random variables (representing the colors of the balls drawn: 1 for red and 0 for black) and that there exists a function f 0 : N 2 → [0, 1] such that, for all integers k,

P(X k+1 = 1 | F k ) = f 0 (Z k , k -Z k ) .
where Z 0 = 0 and for k ≥ 1,

Z k = X 1 + • • • + X k and F k is the sigma-field generated by Z 0 , X 1 , . . . , X k . The random walk {Z k , k ≥ 0} is an inhomogeneous Markov chain.
For n ≥ 1 and a sequence (e 1 , . . . , e n ) ∈ {0, 1} n , applying the Markov property, we obtain

P(X 1 = e 1 , . . . , X n = e n ) = n-1 k=0 f 0 (z k , k -z k ) e k+1 {1 -f 0 (z k , k -z k )} 1-e k+1 , (3)
where z k = e 1 + • • • + e k with z 0 = 0, by convention.

We assume that we observe N experiments, each consisting in a path of length n of the model (3). In other words, we have a set of N sequences of n consecutive draws. For j = 1, . . . , N and k = 1, . . . , n, let X j k ∈ {0, 1} denote the color of the k-th ball drawn in the j-th experiment. Let Z j 0 = 0 and Z j k = k i=1 X j i , k ≥ 1 be the total number of red balls drawn at time k during the j-th experiment, so that X j k = Z j k -Z j k-1 . In all the paper, n will be fixed and our asymptotic results will be obtained with N (the number of experiments) tending to ∞.

Let Θ ⊂ R d and f : Θ × N 2 → (0, 1) be a function, called the choice function of the urn. We assume that there exists θ 0 ∈ Θ such that f 0 (•, •) = f (θ 0 , •, •), i.e. for k = 0, . . . , n -1 and i = 0, . . . , k,

P(X j k+1 = 1 | Z j k = i) = f (θ 0 , i, k -i) .
To proof the consistency and the asymptotic normality of the estimators introduced below, we need the following assumptions on the choice function f . For any function g defined on Θ, we denote ġ and g the gradient and Hessian matrix with respect to θ, ∂ s g the partial derivative with respect to the s-th component θ s of θ, 1 ≤ s ≤ d and A the transpose of the vector or matrix A.

Assumption 1.

(i) (Regularity) The set Θ is a compact with non empty interior. For 0 -1) .

≤ i ≤ k ≤ n -1, f 0 (i, k -i) > 0 and the function θ → f (θ, i, k -i) is twice continuously differentiable on Θ. (ii) (Identifiability) If f (θ 1 , i, k -i) = f (θ 2 , i, k -i) for all 0 ≤ i ≤ k ≤ n -1, then θ 1 = θ 2 , (iii) The n(n -1)-dimensional vectors {∂ s f (θ 0 , i, k -i), 0 ≤ i ≤ k ≤ n -1}, 1 ≤ s ≤ d, are linearly independent in R n(n
Assumption 1 ensures that θ 0 is the unique maximizer of L and that the Fisher information matrix

I n (θ 0 ) = -L(θ 0 ) = n-1 k=0 k i=0 P(Z k = i) f 0 (i, k -i) f0 (i, k -i) ḟ0 (i, k -i) ḟ0 (i, k -i)
is invertible, where we denote ḟ0 (i,

k -i) = ḟ (θ 0 , i, k -i) and f0 (i, k -i) = 1 -f 0 (i, k -i).
The explicit expression of the probabilities P(Z k = i), i, k ∈ N, is given in Section 6.1, Equation (13).

Maximum likelihood estimation (MLE)

The structure of the model (3) allows to have an explicit expression of likelihood V N (θ). The independence of the N experiments yields the following multiplicative form

V N (θ) = N j=1 n-1 k=0 f (θ, Z j k , k -Z j k ) X j k+1 {1 -f (θ, Z j k , k -Z j k )} 1-X j k+1 .
The log-likelihood function L N based on N paths, is thus given by

L N (θ) = N j=1 n-1 k=0 X j k+1 log f (θ, Z j k , k -Z j k ) + (1 -X j k+1 ) log{1 -f (θ, Z j k , k -Z j k )} . (4)
Let θN be the maximum likelihood estimator of θ 0 , that is θ)] (where the dependence in n is omitted). Then,

θN = arg max θ∈Θ L N (θ) . (5) Define L(θ) = N -1 E[L N (
L(θ) = n-1 k=0 E f 0 (Z k , k -Z k ) log f (θ, Z k , k -Z k ) + {1 -f 0 (Z k , k -Z k )} log{1 -f (θ, Z k , k -Z k )} . (6)
Let N (m, Σ) denote the Gaussian distribution with mean m and covariance Σ.

Theorem 2. If Assumptions 1-(i) and 1-(ii) hold then the maximum likelihood estimator θN is a strongly consistent estimator of θ 0 . If moreover Assumption 1-(iii) holds and θ 0 is an interior point of Θ, then, as N tends to ∞, √ N ( θN -θ 0 ) converges weakly towards N (0,

I -1 n (θ 0 )).
The proof is in Section 6.4. It is the consequence of a more general result stated and proved therein.

Weighted least squares estimation (WLSE)

Least squares estimators are very popular among practitioners. Moreover for some urn models, the MLE may be numerically unstable hence difficult (and lengthy) to compute so the WLSE constitutes a convenient alternative. In order to describe this estimator, we introduce some notation. For 0

≤ i ≤ k ≤ n -1, define a N (i, k -i) = 1 N N j=1 1 {Z j k =i} and p N (i, k -i) = 1 N N j=1 1 {Z j k =i} X j k+1 a N (i, k -i) , (7)
with the convention 0 0 = 0. The quantity a N (i, k -i) is the empirical probability that i red balls have been drawn at time k and p N (i, k -i) is the empirical conditional probability that a red ball is again chosen at time k + 1 given i red balls were drawn at time k.

We further define q N (i,

k-i) = 1-p N (i, k-i) and f (θ, i, k-i) = 1-f (θ, i, k-i). Let {w N (i, k -i), 0 ≤ i ≤
k} be a sequence of weights and define the contrast function

W N (θ) = n-1 k=0 k i=0 w N (i, k -i){p N (i, k -i) -f (θ, i, k -i)} 2 . ( 8
)
The weighted least squares estimator minimizes W N , that is

θW N = arg min θ∈Θ W N (θ) . (9)
Theorem 3. If Assumptions 1-(i) and 1-(ii) hold and if the weights w N converge almost surely to a sequence of positive weights w 0 , then the weighted least squares estimator θW N is a strongly consistent estimator of θ 0 . If moreover Assumption 1-(iii) holds and θ 0 is an interior point of Θ, then as N tends to ∞, √ N ( θW N -θ 0 ) converges weakly towards N (0, Σ n (θ 0 )), where Σ n (θ 0 ) is a definite positive covariance matrix.

If moreover w N (i,

k -i) = p N -1 q N -1 a N (i, k -i), for all 0 ≤ i ≤ k ≤ n -1, the estimator θW N is asymptotically efficient, i.e. Σ n (θ 0 ) = I n (θ 0 ).
The proof is in Section 6.4, where a explicit expression of Σ n (θ 0 ) -1 is supplied.

Generalization

It is possible to extend the statistical framework introduced in the previous sections to a large class of reinforced random walks on graphs. For instance, let G = (X , E) be a locally finite non oriented graph, with X the set of its vertices and E ⊂ {i, j} : i, j ∈ X , i = j the set of its non oriented edges. We denote by x ∼ y, if {x, y} ∈ E. Let N X be the set of integer vectors indexed on X . We define X = (X n ) n≥0 a random walk on G, i.e. a sequence of vertices, such that, for all n ≥ 0,

X n+1 ∼ X n . The vector Z n ∈ N X is such that, for all vertex x ∈ X , Z n (x)
is the number of times the walk X has visited x up to time n. Let Θ ⊂ R d , d ≥ 1, we suppose that the walk X is vertex-reinforced and that there exists a choice function f : Θ × X × N X → [0, 1] and a parameter θ ∈ Θ such that, for all n ≥ 0 and x ∈ X ,

P(X n+1 = x|X 0 , • • • , X n ) = f (θ, x, Z n )1 {x∼Xn} .
For instance, the choice function can be similar to the one proposed by J.-L. Deneubourg (see [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF], for n ≥ 0 and x ∈ X ,

P(X n+1 = x|X 0 , • • • , X n ) = c + Z n (x) α y∼Xn c + Z n (y) α 1 {x∼Xn} ,
where Θ = (0, +∞) 2 and θ = (α, c).

The statistical framework introduced for the general urn model is easily adaptable to this vertex reinforced random work. Under some adequate regular conditions, it would be not difficult to prove the consistency and the asymptotic normality of the MLE and the WLSE by establishing a theorem similar of the general result proved in Section 6.3.

Application to an ethological problem

In 1990, J.-L. Deneubourg et al. used a particular urn model to reproduce the sequences of consecutive choices made by ants at a fork (see [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF]. Let replace the urn filled with balls of two colors by a fork with two branches. Drawing a ball and adding a ball of the same color in the urn is equivalent to an ant choosing a branch and reinforcing it with pheromone by going throw it. Then the probability to draw a red ball depending on the previous draws is equal to the probability to choose the right branch depending on the previous passages.

We first introduce the model proposed by J.-L. Deneubourg et al. in the statistical framework described in the previous section. Futher, we provide a description of the model behavior depending on the parameter value. We also supply an ethological interpretation of the parameter. We then prove that it is impossible to estimate the parameter on a single path. Finally we report the study of the estimator accuracy that we perform on simulated data.

Formalization and results

Behavioral assumptions We first introduce the hypotheses assumed on the ant behavior.

1. Each ant regularly deposits a constant amount of pheromone as it walks.

2. The ants are strictly identical which means that every ant has the same reaction to the same amount of pheromone.

3. Pheromone trails do not evaporate during the experiment.

4. Each ant reaches the fork alone, chooses a branch and leaves the bifurcation by crossing only once into the chosen branch without passing through or reinforcing the non-chosen branch.

Under these assumptions, the quantity of pheromone laid on each branch is proportional to the number of passages through it. In path formation modeling, these assumptions are commonly made. However, because of the inter-individual variability in ant behavior, the first two assumptions are unrealistic. For instance, the pheromone perception noise implies that each ant could detect a different signal from the same quantity of pheromone. These assumptions are an approximation of the real ant behavior. The implicit hypothesis here is that the inter-individual variability is small enough to consider that all ants are identical. For the third assumption, we suppose that the persistence of the pheromone trails allows to ignore the evaporation of the pheromone. Experimental protocols are designed to make the four assumptions more acceptable by choosing the ant species adequately and by placing them in an appropriate situation (see Section 4).

The model The random variable X k , introduced previously, is the choice of the k-th ant going through the fork (1 for right and 0 for left). Consequently, for k ≥ 1, Z k is the number of passages through the right branch after k passages.

For θ = (α, c) ∈ (0, ∞) 2 and all integers 0 ≤ i ≤ k, we define choice function

f (θ, i, k -i) = (c + i) α (c + i) α + (c + k -i) α . ( 10
)
We assume that the probability that an ant chooses the right branch at time k + 1 given the first k choices is given by:

P(X k+1 = 1|F k ) = f (θ, Z k , k -Z k ) = (c + Z k ) α (c + Z k ) α + (c + k -Z k ) α , (11)
where c > 0 is the intrinsic attractiveness of each branch and α > 0 is the possible non-linearity of the choice. This process is an urn model which has been exhaustively investigated in the probabilistic literature. We recall here its main features.

Theorem 4.

(i) If α < 1, then lim n→∞ Z n n = 1 2 a.s.
(ii) If α = 1, then Z n /n converges almost surely to a random limit with a Beta(c, c) distribution with density x → Γ -2 (c)Γ(2c)x c-1 (1 -x) c-1 with respect to Lebesgue's measure on [0, 1], and Γ is the Gamma function. (iii) If α > 1, then eventually only one branch will be chosen, i.e.

∃x ∈ {0, 1} , ∃n 0 ∈ N , ∀n ≥ n 0 , X n = x .
The case α < 1 is due to [START_REF] Tarrès | Localization of reinforced random walks[END_REF]; the case α > 1 to [START_REF] Davis | Reinforced random walk[END_REF] and the case α = 1 to [START_REF] Pólya | Sur quelques points de la théorie des probabilités[END_REF] (see [START_REF] Freedman | Bernard friedman's urn[END_REF] for an online access).

Ethological interpretation of the parameters and properties of the model

The parameter α characterizes the ant's differential sensitivity to the pheromone. When α > 1, the ants can detect better and better increasing amounts of pheromones laid on each branch and thus are more likely to choose the branch with the most pheromones. Moreover, after a random but almost surely finite number of passages, one branch will eventually be selected, i.e. all ants will afterwards choose this branch (see Theorem 4-(iii)). In the opposite case, when α < 1, the ants are less able to perceive the differences between the amounts of pheromones laid on each branch as these amounts increase. This minimization effect is so strong that the proportion of passages on each branch converges to 1/2 (see Theorem 4-(i)). It is important to note that, when α = 1, the asymptotic behavior of the proportion of passages through each branch depends only on α and not on c. Furthermore the larger α is or the closer α is to zero, the faster these effects will happen.

The role of c is clearer when ( 11) is rewritten as follows:

P(X k+1 = 1|F k ) = (1 + Z k /c) α (1 + Z k c) α + (1 + (k -Z k )/c) α .
The parameter c is the inverse of the reinforcement incrementation and thus can be interpreted as the inverse of the attractiveness (or the strength) of the pheromones laid at each passage. Consequently when α is neither very close to zero nor very large, c has a strong short term influence. When c is small compared to 1, the first passage strongly reinforces the first chosen branch. Thus during the first few passages, a branch will be highly favored even if α < 1 (in which case the branches will eventually be uniformly crossed). When c is large, the first passages weakly reinforce the chosen branches. Then if α > 1 (in which case a branch will eventually be selected), a large number of passages must be observed before the clear emergence of a preference. Naturally, the larger c is or the closer c is to zero, the longer these effects will be seen.

When α = 1, the asymptotic behavior of the passage proportion is determined by c (see Theorem 4-(ii)). As c grows from zero to infinity, the limiting distribution of Z n /n (as n → ∞) evolves continuously from two Dirac point masses at 0 and 1 to a single Dirac mass at 1/2. To illustrate this point, we show in Figure 1 the density of the Beta distribution for c = 0.1 and c = 10. We make some further comments.

• If c < 1, a strong asymmetry in the choices of the branches appears. One branch is eventually chosen much more frequently than the other. Furthermore as c tends to 0, the Beta distribution tends to the distribution with two point masses at 0 and 1. This limit case corresponds to the situation in which a branch is selected, i.e. α > 1.

• If c = 1, the limiting distribution is uniform on [0, 1].

• If c > 1, Z n /n appears to be much more concentrated around 1/2. This is similar to what is observed in the case α < 1. To summarize, the model possesses four phases: fast and slow selections and fast and slow uniformizations. These phases are delimited by two phase transitions: a discontinuous one between α > 1 (branch selection) and α < 1 (branch uniformization) with a critical state α = 1 and a smooth one between c < 1 (strong pheromone deposits) and c > 1 (weak pheromone deposits). These properties are summarized in the phase diagram in Figure 2. When c is small, it is very likely that one branch will be favored during the first passages, thus the empirical distribution of the choices resembles the Beta distribution with a small c (the grey solid line in Figure 1). As the number of experiments increases, the shape of the empirical distribution will be closer and closer to its limit: a Dirac mass at 1/2 if α < 1 and two Dirac masses at 0 and 1 if α > 1. When c is large, the earlier passages do not show any preference between the branch. Again, when the number of experiments increases, the asymptotic behavior is progressively revealed.

To date, the most commonly used behavioral state in the model is the slow selection of a branch (see [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF][START_REF] Beckers | Trails and u-turns in the selection of a path by the ant lasius niger[END_REF]. But at least two other states are interesting. The fast uniformization can describe the case where none of the branches are preferred. The slow uniformization could reproduce the saturation phenomenon. There exists a threshold concentration of pheromone upon which ants can no longer detect the pheromone concentration variations (see [START_REF] Pasteels | Transmission and amplification of information in a changing environment: The case of insect societies[END_REF]. In experiments involving many ants, one can first observe the favorization of a branch. But when this branch is saturated (its attractiveness stops increasing), ants go more and more through the other branch, whose attractiveness still increases. Eventually, the two branches are uniformly chosen.

Remark 5. In the context of an estimation procedure, the similar effects of α and c (favorization/selection of a branch or not) induce an identifiability issue. Indeed, we observe a finite number of choices and consequently we only see the short term behavior. We have seen that the favorization of a branch in the first passages could be due to a pair of parameter values (α, c) with c small compared to 1 and α close to 1 or to a pair (α, c) with c close to 1 and α large compared to 1. On the other hand, if the first passages are nearly uniform on the two branches, it could be the result of c close to 1 and α small, or of c large and α close to 1. Thus, we can expect that the estimation of the parameters will be difficult when both parameters contribute to the same effect, e.g. α large and c small (fast selection of one branch) or α small and c large (no selection); and also when the parameters have competing effects: very small c and α < 1, or very large c and α > 1. The statistical procedure that we introduce in this paper partially circumvents this difficulty, since it focuses on the transition probabilities rather than on the general shape of a curve, which is what calibration methods do. This will be illustrated in Section 3.4.

Parameter estimation

We start with the maximum likelihood estimator, that is θN = (α N , ĉN ) defined by ( 5). The Fisher information matrix has the following expression.

I n (θ) = n-1 k=0 k i=0 P(Z k = i)f (α, c, i, k -i) f (α, c, i, k -i)J (α, c, i, k -i) , (12) with θ = (α, c) and for 0 ≤ i ≤ k ≤ n -1, J (α, c, i, k -i) = log 2 c+i c+k-i log c+i c+k-i α(k-2i) (c+i)(c+k-i) log c+i c+k-i α(k-2i) (c+i)(c+k-i) α 2 (k-2i) 2 (c+i) 2 (c+k-i) 2 .
It is important to note that the Fisher information matrix is not diagonal. Thus the estimation of each parameter has an effect on the estimation of the other. Corollary 6. Let Θ be a compact subset of (0, ∞) 2 which contains (α 0 , c 0 ). Then the maximum likelihood estimator θN is consistent and asymptotically normal and efficient, i.e.

√ N ( θN -θ 0 ) converges weakly to N (0, I -1 n (θ 0 )). As mentioned above, we also use weighted least squared estimators defined by ( 9) for several different weight sequences w N , such that w N (i, k -i) converges almost surely to w 0 (i, k -i) > 0, for all 0 ≤ k ≤ n -1 and 0 ≤ i ≤ k.

Corollary 7. Let Θ be a compact subset of (0, ∞) 2 which contains (α 0 , c 0 ) and assume that w N converges almost surely to positive weights w 0 . Then the weighted least squared estimator θW N is consistent and asymptotically normal, i.e.

√ N ( θW

N -θ 0 ) converges weakly to N (0, Σ n (θ 0 )), where Σ n (θ 0 ) is a positive definite covariance matrix. It is efficient, if w N (i, k -i) = p -1 N q -1 N a N (i, k -i), for all 0 ≤ k ≤ n -1 and 0 ≤ i ≤ k.
The proofs of these corollaries are in Section 6.5. They are an application of Theorems 2 and 3. Since Assumption 1-(i) obviously holds, it remains only to check (ii) and (iii) of Assumption 1.

Estimation on a single path

The main feature of the binary choice model for α 0 > 1 is that only one branch will be crossed eventually. It seems clear then that a statistical procedure based on only one path (one sequence of choices) cannot be consistent, since no new information will be obtained after one branch is eventually abandoned. This intuition is true and more surprisingly, it is also true in the case α 0 = 1. This is translated in statistical terms in the following theorem. Let n denote the loglikelihood based on a single path of length n and ˙ n its gradient. The model is regular, so the Fisher information is var θ ( ˙ n (θ)).

Theorem 8.

(i) If α 0 = 1 and c 0 > 0, then lim n→∞ I n (c 0 ) < ∞. (ii) If α 0 < 1, n -1 n (θ 0 ) → -log 2.
(iii) If α 0 > 1, then n (θ 0 ) converges almost surely to a random variable as n → ∞.

The proof is in Section 6.6. Statement (i) means that, when α 0 = 1, the Fisher information is bounded. This implies that the parameter c 0 cannot be estimated on a single path. This also implies that the length n of each path should be taken as large as possible (theoretically infinite) in order to minimize the asymptotic variance of the estimators. Statements (ii) and (iii) imply that the maximum likelihood estimator is inconsistent, since the likelihood does not tend to a constant.

Simulation experiment

In order to assess the quality of the estimators proposed, we have made a short simulation study. For several pairs (α, c), we have simulated 1000 experiments of N = 50 paths of length n = 100 (recall that n is the number of ants going through the bifurcation). These are reasonable values in view of the practical experiments with actual ants. We compare the performance of the maximum likelihood estimator θN (MLE) defined in (5) and of the weighted least squares estimator θW N (WLSE) defined in (9) with the weights w N (i, k -i) = a N (i, k -i) defined in (7). The asymptotically efficient WLSE with the weights w N (i, k -i) = a N (i, k -i)p N (i, k -i) -1 q N (i, k -i) -1 provides a severely biased estimation of α and always estimates a very small value of c with a very small dispersion. This is caused by the fact that the empirical p N and q N vanish frequently, so that the weights are infinite. We will not report the study for this estimator.

The theoretical standard deviation We first evaluate numerically some values of the theoretical standard deviations of both estimators for several values of α and c. We have chosen arbitrary values of α and c in the range 0.5, 2. We have also chosen values of α and c which correspond to those found in the literature cited and to those that we have estimated in the real life experiment described in Section 4. These results are reported in Table 1 and in Figure 3 and their features are summarized in the following points.

• As theoretically expected, the asymptotic variance of the MLE, which is the Fisher information bound, is smaller than the variance of the WLSE, but the ratio between the variances of the two estimators is never less than one fourth. Moreover, their overall behavior is similar.

• The variance of the estimators of α is smaller when both parameters do not contribute to the same effect. The worst variance is for α large and c small, that is when the values of both parameters imply fast selection of a branch. The variance tend to infinity when α tends to infinity.

• The variance of the estimators of c increases with c and tends to infinity when α tends to 0 and to ∞.

• These effects are explained by the fact that the coefficients of the Fisher information matrix tend to zero when α tends to zero, except the coefficient corresponding to α. See Formula ( 12). Performance of the estimators Recall that we have simulated 1000 experiments, each of N = 50 paths of length n = 100. Because of the length of the computations, each MLE was computed only 500 times. Table 1 reports root mean squared error (MSE) of both estimators based on the simulated data for the same values of the parameters and their features are summarized in the following points.

• For most values of the parameters, the MSE are close to the theoretical standard deviation.

• The MSE increase significantly when c is large or when both parameters contribute to the same effect.

• This increase is more noticeable for the WLSE than for the MLE.

• This increase is in part due to the skewness of these estimators. For some values of the parameters, both estimators tend to overestimate the parameters.

• For the MLE, the MSE is much larger in the case of non selection than in the case of selection where the empirical performance of the MLE nearly matches the theoretical value.

• These effects are always stronger for the estimation of c than for the estimation of α.

This degraded performance for some specific or extreme values of the parameters is in part due to numerical issues.

• In the case where selection of a branch is fast, many of the empirical weights used to compute the WLSE vanish, and the least squares method uses very few points to fit the curve. The MLE is not affected by this problem.

• In the case where both parameters concur to non selection, the probability of choosing one branch converges very fast to 1/2, and thus the experiment brings very little information. This affects both the MLE and the WLSE, and in addition, many of the empirical weights vanish so the WLSE is even less efficient.

The degraded performance may also be caused by the identifiability problem explained in Remark 5, i.e. the similar effects of the two parameters makes the estimation more difficult.

Bootstrap confidence intervals Since the asymptotic variance depends on the unknown parameters, we have computed the pivotal Bootstrap 95% confidence intervals for the parameters based on one simulation of N = 50 paths of length n = 100 and a Bootstrap sample size of 500 (see [START_REF] Wasserman | All of Statistics: A Concise Course in Statistical Inference[END_REF], Section 8.3, for details on this method). We have compared these Bootstrap intervals with the corresponding Monte-Carlo intervals, based on 500 simulations (see Table 2). The match is nearly perfect for the MLE for α, but as before, the performance is poorer for the estimation of c. The intervals for c are noticeably skewed to the right but always contain the true value. For further comparison, we only show here the results corresponding to the values of the parameters estimated in the real life experiment reported below and those corresponding to values found in the earlier literature.

Real life experiment with ants

In this section, we apply the previous estimators on data from a path selection experiment by a colony of ants.

Experiment description

This experiment was done in the Research Center on Animal Cognition (UMR 5169) of Paul Sabatier University Toulouse under the supervision of Guy Theraulaz, Hugues Chaté and the first author. A small laboratory colony (approximately 200 workers) of Argentine ants Linepithema humile was starved for two days before the experiment. During the experiment, the colony had access to a fork carved in a white PVC slab, partially covered by a Plexiglas plate (see Figure 4). The angle between the branches was 60 • . The fork galleries had a 0.5 cm square section. The entrance of the maze was controlled by a door. Food was never present during the experiment. The maze was initially free of any pheromone trail.

Figure 4: The experimental set-up: a fork carved in a white PVC slab, partially covered by a Plexiglass plate.

Each trial (N = 50) consisted in introducing separately each ant to the entrance of the fork (see Figure 4) one at a time. Once inside, an ant must choose between the left or the right branch of the fork. As soon as the ant had made a choice and stepped into one branch, it was removed from the set-up and another ant was introduced. All the choices were recorded and a trial ended when 100 ants had passed through the fork.

This experimental protocol was designed to strengthen the behavioral assumptions described in Section 3.1. Any return to the fork is forbidden so that we can consider that each ant passed only one time. There was never more than one ant in the set-up. This implies that each ant in the maze received no other cue about the previous passages than the pheromone that was been laid. The species Linepithema humile was in part chosen to justify the assumption of identical pheromone deposits. Indeed, these ant may deposit regularly the same type of pheromone on their trajectory (see [START_REF] Van Vorhis Key | Trail-following responses of the argentine ant, iridomyrmex humilis (mayr), to a synthetic trail pheromone component and analogs[END_REF][START_REF] Aron | Trail-laying behaviour during exploratory recruitment in the argentine ant, iridomyrmex humilis (mayr)[END_REF]. All ants were prepared the same way before the experiments to increase the credibility of the assumption stating that each ant behaved by the same way. The length of the experiments was limited to stay close to the half-life duration of the pheromone trails (see [START_REF] Jeanson | Pheromone trail decay rates on different substrates in the pharaohs ant, monomorium pharaonis[END_REF].

Data representation

Figures 5(a) shows the 50 paths of length n = 100, that is, 50 choice sequences of 100 ants that went through the bifurcation. The paths are represented as random walks with increment +1 when the right branch is chosen, and -1 when the left one is chosen. In less than ten experiments, a branch seemed to be selected, whereas in the others, selection of a branch was not obvious. Figure 5(b) shows the histogram of the distribution of Z 100 /100, that is the final proportion of the choices of the right branch. There is no clear visual evidence that α > 1 as it is claim in the literature (see [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF][START_REF] Vittori | Path efficiency of ant foraging trails in an artificial network[END_REF][START_REF] Garnier | Path selection and foraging efficiency in argentine ant transport networks[END_REF].

Parameter estimation

Several values of these parameters have been proposed in the applied literature. [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF] proposed α = 2, c = 20 and more recently [START_REF] Garnier | Path selection and foraging efficiency in argentine ant transport networks[END_REF] suggested α = 2.6 and c = 60. It must be noted however that these values are not obtained by a statistical method but by the calibration of a curve to a plot. Therefore, these methods do not lead to confidence intervals. Moreover, a calibration method has an inherent risk of over fitting, because of the identifiability problem explained in Remark 5. As illustrated in Figure 2, if for instance α and c are both small, then both branches will be asymptotically equally chosen, but paths of finite length n might be misleading and the calibration will suggest values of α and c corresponding to the selection of a branch. The statistical procedure is based on the dynamics of the process and is thus less prone to this type of error. Nevertheless, we will see that our results do not contradict those of [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF] and [START_REF] Garnier | Path selection and foraging efficiency in argentine ant transport networks[END_REF], but complement them.

Table 3 shows the results of the maximum likelihood estimation and the weighted least squares estimation. Both estimates of α are close to 1.1 and the estimates of c are between 3 and 7. The 95% confidence intervals are slightly larger than the simulated ones (see Table 2). This increased variability may be due to the extreme paths which seem to show a very fast selection of one branch (see Figures 5(a) and 5(b)). This may suggest that the ants did not have the same behavior and that the distribution of Z 100 /100 could be a mixture of two distributions.

For both methods, the 95% Bootstrap confidence intervals of α contain the value 1. More precisely, as shown in Figure 6, approximately 1/3 of the bootstrap parameters gives weak pheromone deposits (c > 1) and a weak differential sensitivity (α < 1), which means that branches are eventually uniformly crossed. In almost all the others cases, we conclude for weak pheromone deposits (c > 1) and a strong differential sensitivity (α > 1), which means that a branch will be eventually, though slowly, selected. In only a few cases do the estimators give strong pheromone deposits (c < 1), but a weak differential sensitivity (α < 1), which means that a branch is chosen more than the other at the beginning of the experiment, but branches are eventually uniformly crossed. Finally, there are no values which imply both strong pheromone deposits (c < 1) and a strong diffe-rential sensitivity (α > 1). Therefore, we can conclude that pheromone deposits are weak with a good confidence but we cannot confidently decide for α.

The values obtained by [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF] (α = 2, c = 20) and more recently by [START_REF] Garnier | Path selection and foraging efficiency in argentine ant transport networks[END_REF] (α = 2.6, c = 60) are both in the confidence intervals for the WLSE found in Table 3. But the values of α suggested by these authors are out of the 95% confidence interval for the MLE. Thus these parameters, which decide for a slow branch selection, are no more likely than a parameter set which would yield non selection of a path.

Figure 6 illustrates the fact that the two estimators are strongly positively correlated. There seems to be two cutoff values for c: if ĉ * > 8, then α * > 1, and if ĉ * < 1.5, then α * < 1. The above mentioned values reported by [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF] and [START_REF] Garnier | Path selection and foraging efficiency in argentine ant transport networks[END_REF] exhibit these features: they both have c > 8 and α > 1 and α increase with c.

If we fix the value of c and estimate only α, then the 95% Bootstrap confidence intervals for α are smaller. Figure 7 shows the estimated values of α and the confidence intervals as functions of the fixed value of c. We see that if c is greater than 6 for the MLE (or than 12 for the WLSE), then the confidence intervals of α lie entirely above 1. Furthermore if c is less than 0.8 for the MLE (or than 2 for the WLSE), then the confidence intervals of α lie entirely under 1. This shows that if the deposits are weak enough, i.e. c > 12, we can conclude that a slow selection of a branch will occur with probability 1. On the other hand, if the deposits are strong enough, i.e. c < 0.8, we can conclude that branches will eventually be uniformly crossed with probability 1.

Concluding remarks

In the literature no parameter estimation methods for reinforced random walks can be found. To partially fill this void, this article proposes a statistical framework to estimate the parameter of a general two-colored urn model. We define the maximum likelihood estimator (MLE) and the weighted least squares estimators (WLSE) for the parameter of this model and prove their consistency and their asymptotically normality under some usual regularity conditions. The proof lies on a general result for a large class of estimators called minimum contrast estimators. The MLE is asymptotically efficient, but can be difficult (lengthy) to compute, which can be an issue specially while using Bootstrap algorithms.

The WLSE is a suitable alternative. Moreover this estimator is popular among practitioners.

We apply this statistical tools to the problem of path selection by an ant colony. To this purpose, we performed experiments with actual ants to collect data. The experiment consisted of introducing one hundred ants into a Y shaped device, one at a time, and observing their successive choices. We also consider the particular urn model introduced by [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF] to describe this phenomenon. This urn has two parameters, α and c, which have distinct biological interpretations, but contribute to the same effect: either selection of a branch or uniformization of the choices. The parameter c influences the short term behavior, whereas α determines the asymptotic behavior. Consequently the model exhibits four phases which are illustrated by Figure 2. The case most commonly considered in the literature is the case of slow selection, which corresponds to α > 1 and c > 1: the ants will eventually always choose the same branch, but this selection will take a long time. For instance, [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF] provides the values α = 2 and c = 20. However other phases can be relevant to describe the ant behavior. For instance the fast uniformization, corresponding to α < 1 and c > 1, can model the less likely but not negligible case in which ants do not select a branch.

After assessing the accuracy of the MLE and the WLSE on simulated data, we estimate the value of α and c with the two estimators. We also evaluate confidence regions by Bootstrap proceeding. The estimated values of α and c ranged between 1.1 and 3 and between 3 and 7, respectively. This tends to imply that slow selection of a branch will occur. However, the Bootstrap sample gives a confidence level of 65% for the hypothesis of slow selection, while the hypothesis of fast uniformization has a confidence of 35%.

This low level of confidence for the commonly assumed slow selection phase might be explained by technical reasons. The number of experiments ( 50) is relatively small; increasing the number of replicas will reduce the confidence regions. Moreover the competition between the parameters for the same effect induces an identifiability issue. For instance the apparent preference of a branch may be due to α > 1 or c small with respect to 1. Therefore, the model, which is biologically relevant, is statistically difficult to estimate. Indeed, for an ethological study, discriminating the ant pheromone sensitivity from the pheromone deposit strength is meaningful. But for a statistical procedure, the similarity of effect of the two parameters scales down the estimation performance.

However, the uncertainty may not come from an inefficiency of the statistical procedure, but from shortcomings of the ethological hypotheses. Indeed, the estimated confidence intervals computed from the experimental data are larger than the ones computed from the simulated data (for similar parameter values). Moreover the assumption that the inter-individual variability is negligible is strong. For instance, it may be necessary to consider that the pheromone deposit varies at each passage, i.e. that c is random.

These ethological considerations will be further discussed in a forthcoming paper which will analyze more elaborated experimental designs. The ants will be observed while freely evolving in a network with several nodes. In addition of a data analysis, we will model the experiment with a reinforced random walk on a finite graph for which we have provided probabilistic results (see Le [START_REF] Goff | Vertex reinforced non-backtracking random walks: an example of path formation[END_REF]. The statistical methodology introduced in this paper will be extended to a larger class of reinforced random walks.

6 Proofs 6.1 Distribution of Z k , for k ∈ N

In order to compute the distribution of Z k , we introduce some notation. Let S k be the set of sequences of length k + 1 of integers i 0 , . . . , i k such that i 0 = 0 and i j -i j-1 ∈ {0, 1} for j = 1, . . . , k.

For i ≤ k let S k (i) = {(i 0 , . . . , i k ) ∈ S k | i k = i}.
Then we have

P(Z k = i) = (i 0 ,...,i k )∈S k (i) k-1 q=0
f 0 (i q , q -i q ) i q+1 -iq (1 -f 0 (i q , q -i q )) 1-i q+1 +iq . (13) 6.2 A central limit theorem for the empirical conditional probabilities

For 0 ≤ i ≤ k ≤ n -1, recall the definition of a N (i, k -i) and p N (i, k -i) in (7) and that f0 (i, k -i) = 1 -f 0 (i, k -i). Lemma 9. { √ N (p N (i, k -i) -f 0 (i, k -i)), 0 ≤ i ≤ k ≤ n -1}
converges weakly to a Gaussian vector with diagonal covariance matrix Γ 0 with diagonal elements

γ 0 (i, k -i) = f 0 (i, k -i) f0 (i, k -i) P(Z k = i) . ( 14
) Proof. Define b N (i, k -i) = N -1 N j=1 1 {Z j k =i} X j k+1 , the empirical estimate of b(i, k -i) = P(Z k = i, X k+1 = 1) and a(i, k -i) = E[a N (i, k -i)] = P(Z k = i). Write then p N (i, k -i) -f 0 (i, k -i) = b N (i, k -i) -b(i, k -i) a N (i, k -i) - b(i, k -i) a N (i, k -i)a(i, k -i) (a N (i, k -i) -a(i, k -i)) .
Since the paths (Z j 1 , . . . , Z j n ), 1 ≤ j ≤ N are i.i.d., the multivariate central limit holds for the sequence of 2n

(n -1) dimensional vectors {(b N (i, k -i) -b(i, k - i), a N (i, k -i) -a(i, k -i)), 0 ≤ i ≤ k ≤ n -1}.
The proof is concluded by tedious computations using the Markov property, which we omit.

Remark 10. We can prove that the covariance matrix Γ 0 is diagonal by a statistical argument. If we consider the tautological model {f (i, k -i), 0 ≤ i ≤ k ≤ n -1}, i.e. θ = f and f 0 is the true value. Then the likelihood is

L N (f ) = n-1 k=0 k i=0 a N (i, k -i){p N (i, k -i) log f (i, k -i) + q N (i, k -i) log f (i, k -i)} , where f (i, k-i) = 1-f (i, k-i). Thus we see that {p N (i, k -i), 0 ≤ i ≤ k ≤ n -1}
is the maximum likelihood estimator of f 0 . This model is a regular statistical model, thus √ N (p N -f 0 ) converges weakly to the Gaussian distribution with covariance matrix I -1 n (f 0 ), where I n (f ) is the Fisher information matrix of the model. It is easily seen that I n (f 0 ) is the n(n -1) dimensional diagonal matrix with diagonal elements given by ( 14).

A general result for minimum contrast estimators

Theorems 2 and 3 are a consequence of the general result we prove in this section. More precisely we demonstrate the consistency and the asymptotic normality of a general estimator of which the MLE and the WLSE are particular cases.

For 0

≤ i ≤ k ≤ n -1, recall the definition of a N (i, k -i), p N (i, k -i) in (7) and that f (θ, i, k -i) = 1 -f (θ, i, k -i). Let w N (i, k -i), 0 ≤ i ≤ k ≤ n -1
be a sequence of random weights and let G be function defined on [0, 1] × (0, 1). Define the empirical contrast function by

W N (θ) = n-1 k=0 k i=0 w N (i, k -i)G(p N (i, k -i), f (θ, i, k -i)) .
For instance, choosing G(p, q) = -p log q -(1 -p) log(1 -q) and w

N (i, k -i) = a N (i, k -i) yields W N (θ) = - n-1 k=0 k i=0 a N (i, k -i) p N (i, k -i) log f (θ, i, k -i) + q N (i, k -i) log f (θ, i, k -i) = -N -1 L N (θ) ,
so that minimizing W N is equivalent to maximizing the likelihood L N , defined in (4). Choosing G(p, q) = (p -q) 2 yields the weighted least squares contrast function W N , defined in (8). We now define the minimum contrast estimator of θ 0 by θW N = arg min θ∈Θ W N (θ) .

In order to prove the consistency and asymptotic normality of θW N , we make the following assumptions on G and on the weights w N (i, k -i). Let ∂ 2 G and ∂ 2 2 G denote the first and second derivatives of G with respect to its second argument.

Assumption 11. The function G is non negative, twice continuously differentiable on [0, 1]×(0, 1) with G(p, q)-G(p, p) > 0 if p = q, ∂ 2 G(p, p) = 0 and ∂ 2 2 G(p, p) > 0.

Assumption 12. For all 0

≤ i ≤ k ≤ n -1, w N (i, k -i) converge almost surely to w 0 (i, k -i) and w 0 (i, k -i) > 0.
Theorem 13. If Assumptions 1-(i), 1-(ii), 11 and 12 hold, then θW N is consistent. If moreover θ 0 is an interior point of Θ and Assumption 1-(iii) holds, then √ N ( θW N -θ 0 ) converges weakly to a Gaussian distribution with zero mean.

The exact expression of the variance is given in the proof.

Proof. Under Assumption 11, the strong law of large numbers shows that W N (θ) converges almost surely to

W(θ) = n-1 k=0 k i=0 w 0 (i, k -i)G(f 0 (i, k -i), f (θ, i, k -i)) .
Assumptions 1-(ii) and 11 ensure that θ 0 is the unique minimum of W. Indeed, G(p, q) > 0 if p = q and G(p, p) = 0. Thus, W is minimized by any value of θ such that f (θ, i, k -i) = f (θ 0 , i, k -i). By Assumption 1-(ii), this implies θ = θ 0 .

Moreover the convergence of W N to W is uniform, since Θ is compact and the function f is twice continuously differential with respect to θ, its first variable. This yields the consistency of θW N . For the sake of completeness, we give a brief proof. Since θ 0 minimizes W and θW N minimizes W N , we have

0 ≤ W( θW N ) -W(θ 0 ) = W( θW N ) -W N ( θW N ) + W N ( θW N ) -W N (θ 0 ) + W N (θ 0 ) -W(θ 0 ) ≤ W( θW N ) -W N ( θW N ) + W N (θ 0 ) -W(θ 0 ) ≤ 2 sup θ∈Θ |W N (θ) -W(θ)| .
Since θ 0 is the unique minimizer of W, for > 0, we can find δ such that if θ ∈ Θ and θ -θ 0 > , then W(θ) -W(θ 0 ) ≥ δ. Thus

P( θN -θ 0 > ) ≤ P(W( θN ) -W(θ 0 ) ≥ δ) ≤ P 2 sup θ∈Θ |W N (θ) -W(θ)| ≥ δ → 0 .
Proof of Theorem 3. Again, the proof consists in checking Assumption 11 and 12 to apply Theorem 13. The latter holds by virtue of Lemma 14 and Assumption 11 trivially holds for the function G(p, q) = (p -q) 2 . If w N (i, k -i) = p -1 N (i, k -i)q -1 N (i, k -i)a N (i, k -i), then

H(θ 0 ) = 2 Ẅ(θ 0 ) = 4I n (θ 0 ) = 4 n-1 k=0 k i=0 P(Z k = i) f 0 (i, k -i) f0 (i, k -i) ḟ0 (i, k -i)( ḟ0 (i, k -i)) . ( 16
)
So that Σ n (θ 0 ) = Ẅ-1 (θ 0 )H(θ 0 ) Ẅ-1 (θ 0 ) = I -1 n (θ 0 ). If the weights are chosen as w N (i, k) = a N (i, k), then w 0 (i, k -i) = P(Z k = i) and

H(θ 0 ) = 4 n-1 k=0 k i=0 P(Z k = i)f 0 (i, k -i) f0 (i, k -i) ḟ0 (i, k -i)( ḟ0 (i, k -i)) , (17) Ẅ (θ 0 ) = 2 n-1 k=0 k i=0 P(Z k = i) ḟ0 (i, k -i)( ḟ0 (i, k -i)) .
(18)

6.5 Proofs of Corollaries 6 and 7

Corollaries 6 and 7 are a consequence of Theorem 13. The assumptions on the weights w N and on the functions G have been already verified in the previous section. We have to prove the Assumption 1 on the choice function f defined in (10). Hypothesis 1-(i) is obvious. By elementary computations, we have, for 0

≤ i ≤ k ≤ n -1, f (α, c, i, k -i) = f (α 0 , c 0 , i, k -i) ⇔ c + i c + k -i α = c 0 + i c 0 + k -i α 0 ⇔ α α 0 = log(c 0 + i) -log(c 0 + k -i) log(c + i) -log(c + k -i) . (19)
Plugging the pairs (i, k) = (0, 1) and (i, k) = (0, 2) into (19) yields

It is easily checked that the function x → log(1 + x)/ log(1/2x) is strictly increasing on (0, ∞). Thus (20) implies that c = c 0 . Plugging this equality into (19) yields α = α 0 . This proves Assumption 1-(ii). We now prove that if n ≥ 2, the vectors {∂ α f (θ 0 , i, k -i), 0 ≤ i ≤ k ≤ n -1} and {∂ c f (θ 0 , i, k -i), 0 ≤ i ≤ k ≤ n -1} are linearly independent in R n(n-1) . For 0 ≤ i ≤ k ≤ n -1, we have,

∂ α f (α, c, i, k -i) = f (α, c, i, k -i)f (α, c, k -i, i) log c + i c + k -i , ∂ c f (α, c, i, k -i) = f (α, c, i, k -i)f (α, c, k -i, i) α(k -2i) (c + i)(c + k -i) .
Let (u, v) ∈ R 2 and assume that for all i, j ≤ n -1 such that i + j ≤ n -1, it holds that

u log c 0 + i c 0 + j + v α 0 (j -i) (c 0 + i)(c 0 + j) = 0 .
Replacing (i, j) for instance successively by (0, 1) and (0, 2) yields By strict convexity of the function x → x log x on (0, ∞), this is impossible. Thus u = v = 0 and Assumption 1-(iii) holds.

       u log c 0 c 0 + 1 + v α 0 c 0 (c 0 + 1) = 0 ,

Proof of Theorem 8

Proof of Theorem 8, case α 0 = 1. In this case the model is Pólya's urn, and we have

I n (c) = n-1 k=0 1 2c + k E 1 c + Z k + E 1 c + k -Z k - 4 2c + k . ( 21
)
The distribution of Z k is given by

P(Z k = i) = k i c(c + 1) • • • (c + i -1) × c(c + 1) • • • (c + k -i -1) 2c(2c + 1) • • • (2c + k -1) .
Thus,

E 1 c + Z k = k i=0 k i c(c + 1) • • • (c + i -1) × c(c + 1) • • • (c + k -i -1) 2c(2c + 1) • • • (2c + k -1) 1 c + i .
For any c > 0, there exists constants C 1 < C 2 such that, for all integers h ≥ 1,

C 1 h c ≤ h i=1 (1 + c/i) ≤ C 2 h c .
Therefore, there exists a constant C > 0 such that for all k ≥ 1,

E 1 c + Z k ≤ Ck -2 k-1 i=1 i k c-2 1 - i k c-1 =      O(k -1 ) if c > 1 , O(k -1 log k) if c = 1 , O(k -c ) if c < 1 .
In all three cases, we obtain that the first series in ( 21) is summable. By symmetry, the sum of the second expectations is also finite.

Proof of Theorem 8, case α 0 < 1. In this case, we know by Theorem 4 that Z n /n converges almost surely to 1/2. This implies that f (θ, Z n , n-Z n ) converges almost surely to 1/2 for all θ. By Cesaro's Lemma, this implies that n -1 n (θ) → -log 2 a.s.

Proof of Theorem 8, case α 0 > 1. Let Ω 1 be the event that color 1 is eventually selected, which happens with probability 1/2 by Theorem 4. Then, on Ω 1 , Z n /n → 1 and if k > T ∞ , then X k+1 = 1 and Z k = k -Q ∞ . Thus for large enough n, the log-likelihood on one path becomes

n (θ) = T∞ k=0 X k+1 log f (θ, Z k , k -Z k ) + (1 -X k+1 ) log{1 -f (θ, Z k , k -Z k )} + n k=T∞+1 log f (θ, k -Q ∞ , Q ∞ ) .
As k → ∞, for any α > 0,

log f (θ, k -Q ∞ , Q ∞ ) = -log 1 + (c + Q ∞ ) α (c + k -Q ∞ ) α ∼ - (c + Q ∞ ) α (c + k -Q ∞ ) α .
If α ≤ 1 the series is divergent and thus lim n→∞ n (θ) = -∞. If α > 1 then the series is convergent and thus, on Ω 1 ,

lim n→∞ n (θ) = ∞ k=0 X k+1 log f (θ, Z k , k -Z k ) + (1 -X k+1 ) log{1 -f (θ, Z k , k -Z k )} = T∞ k=0 X k+1 log f (θ, Z k , k -Z k ) + (1 -X k+1 ) log{1 -f (θ, Z k , k -Z k )} + ∞ T∞+1 log f (θ, k -Q ∞ , Q ∞ ) .
This implies that arg max θ∈Θ n (θ) = arg max θ∈Θ,α>1 n (θ) and that this argmax is a random variable which is a function of the whole path, and does not depend on the true value θ 0 .

Figure 1 :

 1 Figure 1: Graph of the Beta distribution for parameters (c, c) with c = 0.1, c = 1 and c = 10

Figure 2 :

 2 Figure 2: Phase diagram of the model. The graphs in the shaded boxes show the shape of the empirical distribution of Z n /n for small n (left) and its limiting distribution (as n → ∞, right).

Figure 3 :

 3 Figure 3: Theoretical standard deviation for N = 50 paths of length n = 100 of the MLE of α (a) and of c (b), for α in (0, 2] and fixed values of c. Theoretical standard deviation of the WLSE has the same shape, but with higher convergence speed as α tend to 0 or ∞.

  (a) The 50 paths of n = 100 ants choosing either left (+1) or right (-1) (b) Histogram of the final proportion of right passages (Z 100 /100)

Figure 5 :

 5 Figure 5: Data representation

Figure 6 :

 6 Figure 6: Log-log scatterplots of the estimates (α * , ĉ * ) for the 500 Bootstrap samples for the MLE (a) and the WLSE (b) for the 50 paths of real ants.

Figure 7 :

 7 Figure 7: Graph of the estimates α and their Bootstrap 95% confidence interval for the MLE (a) and the WLSE (b) for the 50 paths of real ants as a function of fixed value of c.

log(c 0 )

 0 -log(c 0 + 1) log(c) -log(c + 1) = log(c 0 ) -log(c 0 + 2) log(c) -log(c + 2) , or equivalently log(1 + 1/c 0 ) log(1 + 2/c 0 ) = log(1 + 1/c) log(1 + 2/c) .

Table 1 :

 1 Theoretical standard deviations (TSD) for N = 50 paths of length n = 100 and square root of the mean squared errors (MSE) for 500 (for the MLE) or 1000 (for the WLSE) simulated experiments of N = 50 paths of length n = 100. All figures of this table must be mutiply by 0.01.

	(α, c)		α		c M SE TSD √ M SE TSD	√	M SE
	(0.5, 0.5)	5.02	5.60	6.25	7.60	25.4	54.1	31.7	58.8
	(0.5, 1.0)	6.45	7.39	8.56	10.2	59.8	137	79.4		169
	(0.5, 2.0)	8.80	16.9	12.9	356	146	651	214	29500
	(1.0, 0.5)	3.81	3.90	4.97	6.25	11.8	12.4	15.9	21.0
	(1.0, 1.0)	4.34	4.98	5.91	7.34	25.2	31.3	34.9	47.3
	(1.0, 2.0)	5.83	5.80	8.72	9.38	59.3	64.9	89.1		111
	(1.5, 0.5)	7.83	7.85	12.8	19.4	12.3	13.0	18.7	24.6
	(1.5, 1.0)	6.69	6.59	10.8	15.1	21.0	21.4	33.1	40.3
	(1.5, 2.0)	6.88	7.24	11.5	13.9	41.7	45.9	68.8	78.4
	(2.0, 0.5)	19.4	26.1	41.8	2690	16.4	19.8	28.6	1410
	(2.0, 1.0)	13.5	14.2	28.7	985	23.9	26.0	44.3		988
	(2.0, 2.0)	11.2	11.7	23.1	35.4	40.7	43.4	77.2		101
	(2.0, 20.0) 35.5	58.8	129	124	794	1420	2880	3240
	(2.6, 60.0)	166	864	1230	3590	5780	32500	43200 142000
	(1.1, 3.0)	7.20	7.80	11.9	11.3	89.9	111	148		201
	(1.1, 7.0)	13.8	17.4	29.5	28.3	297	433	633		758
			All figures must be multiply by 0.01

Table 2 :

 2 Monte-Carlo 95% confidence intervals for 500 simulated experiment of N = 50 paths of length n = 100 and Bootstrap 95% confidence intervals for one simulated experiment of 50 paths of length 100

	(α, c)	IDC 95% for α Monte-Carlo Bootstrap Monte-Carlo Bootstrap IDC 95% for c
	MLE (2.0, 20) (1.50, 3.38) (1.90, 5.10) (9.90, 55.5) (19.1, 94.4)
	(2.6, 60) (1.23, 29.3) (1.12, 38.7) (15.9, 1053) (19.9, 1637)
	(1.1, 3.0) (0.98, 1.29) (1.01, 1.23) (1.81, 6.22) (1.34, 3.99)
	WLSE (2.0, 20) (1.26, 4.85) (1.06, 3.99) (5.92, 88.1) (2.76, 69.3)
	(2.6, 60) (0.74, 88.3) (0.24, 87.7) (3.86, 3754) (0.17, 4132)
	(1.1, 7.0) (0.75, 1.83) (0.55, 2.56) (1.68, 30.3) (1.48, 66.0)

Table 3 :

 3 The MLE and the WLSE for the 50 paths of real ants and their

	Boostrap 95% confidence intervals
	α	Bootstrap 95% CI	ĉ	Bootstrap 95% CI
	MLE 1.07	(0.80, 1.99)	3.26	(1.14, 23.0)
	WLSE 1.10	(0.62, 3.81)	6.91	(0.94, 85.

Acknowledgment We thanks Guy Theraulaz and Hugues Chaté for providing their material framework and their field expertise to allow the first author to collect the data of the Argentine ants experiments. These experiments are part of the project TRACES supported by the CNRS. They were done during two visits in April and July 2012 of the first author to the Centre de Recherches sur la Cognition Animale (CRCA, Centre de Recherches sur la Cognition Animale, UMR 5169, Paul Sabatier University, Toulouse), whose hospitality is gratefully acknowledged.

The central limit theorem is a consequence of the consistency and Lemma 9. A first order Taylor extension of ẆN (θ) at θ 0 yields 0 = ẆN ( θW N ) = ẆN (θ 0 ) + ẄN ( θN )( θW N -θ 0 ) , where θN ∈ [θ 0 , θW N ]. Setting ḟ0 (i, k -i) = ḟ (θ 0 , i, k -i), we have

Thus, by the delta-method (see Dacunha-Castelle and Duflo, 1986, Theorem 3.3.11) and since w N converges almost surely to w 0 , we obtain that √ N ẆN (θ 0 ) converges weakly towards

where Λ 0 (i, k) are independent Gaussian random variables with zero mean and variance γ 0 (i, k) defined in 14. Equivalently, √ N ẆN (θ 0 ) converges weakly to a Gaussian vector with zero mean and covariance matrix H(θ 0 ) defined by

By the law of large numbers, ẄN (θ) converges almost surely to Ẅ(θ) and this convergence is also locally uniform. Thus, ẄN ( θN ) converges almost surely to Ẅ(θ 0 ). Using again the fact that ∂ 2 G(p, p) = 0, we obtain

By assumption 12, g(i, k -i) > 0 for all 0 ≤ i ≤ k ≤ n -1, thus ( 15) is zero only if for all k = 0, . . . , n -1 and i = 0, . . . , k, we have d s=1 u s ∂ s f (θ 0 , i, k) = 0. By Assumption 1-(iii), this is possible only if u s = 0 for all s = 1, . . . , d. Thus Ẅ(θ 0 ) is positive definite.

We can now conclude that for large enough N , ẄN ( θN ) is invertible and we can write

The right hand side converges weakly to the Gaussian distribution with zero mean and covariance matrix Ẅ-1 (θ 0 )H(θ 0 ) Ẅ-1 (θ 0 ).

Proofs of theorems 2 and 3

Theorems 2 and 3 are a consequence of Theorem 13.

Lemma 14. Assumption 12 holds for the weights w N (i, 13), this in turn implies that P(Z k = i) > 0 for all 0 ≤ i ≤ k ≤ n -1.

Proof of Theorem 2. As mentioned above, the maximum likelihood estimator minimizes the contrast function W written with the function G(p, q) = -p log q -(1 -p)log(1 -q) and the weights a N (i, k -i). Thus the proof of Theorem 2 consists in checking Assumption 11 and 12 to apply Theorem 13. Lemma 14 implies that Assumption 12 holds.

The function G considered here satisfies Assumption 11. Indeed, for p, q ∈ (0, 1), define

Remark that K(p, q) is the Kullback-Leibler distance between the Bernoulli measures with respective success probabilities p and q. Then it is well known that K(p, q) > 0 except if p = q. Indeed, by Jensen's inequality, K(p, q) ≥ -log(pq/p + (1 -p)(1 -q)/(1 -p)) = log 1 = 0 , and by strict concavity of the log function, equality holds only if p = q. Moreover, ∂ 2 G(p, q) = -p/q+(1-p)/(1-q) so ∂ 2 G(p, p) = 0 and ∂ 2 2 G(p, p) = p -1 (1 -p) -1 > 0.