Walid Hachem
email: walid.hachem@telecom-paristech.fr

Philippe Loubaton
email: loubaton@univ-mlv.fr

Xavier Mestre
email: xavier.mestre@cttc.cat

Jamal Najim
email: jamal.najim@telecom-paristech.fr

Pascal Vallet
email: vallet@univ-mlv.fr

A Subspace Estimator for Fixed Rank Perturbations of Large Random Matrices

Keywords: Large Random Matrix Theory, MUSIC Algorithm, Extreme Eigenvalues, Finite Rank Perturbations

, relating the eigenspaces of extreme eigenvalues of the empirical covariance matrix with eigenspaces of the perturbation matrix. First and second order analyses of the new algorithm are performed.

Introduction

Parameter estimation algorithms based on the estimation of an eigenspace of the autocorrelation matrix of an observed multivariate time series are very popular in the areas of statistics and signal processing. Applications of such algorithms include the estimation of the angles of arrival of plane waves impinging on an array of antennas, the estimation of the frequencies of superimposed sine waves, or the resolution of multiple paths of a radio signal. Denoting by N the signal dimension (e.g., the number of antennas) and by n the length of the time observation window, the observed time series is represented by a N × n random matrix Σ n = X n + P n where X n and P n are respectively the so-called noise and signal matrices. In many applications, P n is represented as

P n = B(ϕ 1 , • • • ϕ r )S * n , (1)
where (ϕ 1 , . . . , ϕ r ) are the r ≤ min(N, n) deterministic parameters to be estimated, B is a N × r matrix of the form B(ϕ

1 , • • • ϕ r ) = b(ϕ 1 ) • • • b(ϕ r
) where b(ϕ) is a known C N -valued function of ϕ, and the S n is an unknown n × r matrix with rank r representing the signals transmitted by the r emitting sources. As usual (and unless stated otherwise), A * stands for the Hermitian adjoint of matrix A. It will be assumed in this work that this matrix is deterministic. Often, the noise matrix X n is a complex random matrix such that the real and imaginary parts of its elements are 2N n independent random variables with common probability law N (0, 1/(2n)). In this case, we shall say that √ nX n is a standard Gaussian matrix.

We shall consider here "direction of arrival" vector functions b(ϕ) that are typically met in the field of antenna processing. These functions are written b(ϕ) = N -1/2 exp(-ıDℓϕ)

N -1 ℓ=0
with domain ϕ ∈ [0, π/D] where D is a positive real constant and ı 2 = -1. Assuming that the angular parameters ϕ k are all different, the well-known MUSIC (MUltiple SIgnal Classification, [START_REF] Schmidt | Multiple emitter location and signal parameter estimation[END_REF][START_REF] Bienvenu | Adaptivity to background noise spatial coherence for high resolution passive methods[END_REF]) algorithm for estimating these parameters from Σ n relies on the following simple idea: Assume that √ nX n is standard Gaussian and let Π be the orthogonal projection matrix on the eigenspace of EΣ n Σ * n = BS * n S n B * +I N associated with the r largest eigenvalues, where I N is the N × N identity matrix. Obviously, Π is the orthogonal projector on the column space of B(ϕ 1 , . . . , ϕ r ). As a consequence, the angles ϕ k coincide with the zeros of the function b(ϕ) * (I -Π)b(ϕ) on [0, π/D]. Since b(ϕ) = 1, they equivalently coincide with the maximum values (at one) of the so-called localization function χ(ϕ) = b(ϕ) * Πb(ϕ).

In practice, Π is classically replaced with the orthogonal projection matrix Π on the eigenspace associated with the r largest eigenvalues of Σ n Σ * n . Assuming N is fixed and n → ∞, and assuming furthermore that S * n S n converges to some matrix O > 0 in this asymptotic regime, the ΣΣ * a.s.

--→ BOB * + I N by the Law of Large Numbers (a.s. stands for almost surely). Hence, the random variable χ classical (ϕ) = b(ϕ) * Πb(ϕ) a.s. converges to χ(ϕ), and it is standard to estimate the arrival angles as local maxima of χ classical (ϕ).

However, in many practical situations, the signal dimension N and the window length n are of the same order of magnitude in which case the spectral norm of Π -Π is not small, as we shall see below. In these situations, it is often more relevant to assume that both N and n converge to infinity at the same pace, while the number of parameters r is kept fixed. The subject of this paper is to develop a new estimator better suited to this asymptotic regime, and to study its first and second order behavior with the help of large random matrix theory.

In large random matrix theory, much has been said about the spectral behavior of X n X * n in this asymptotic regime, for a wide range of statistical models for X n . In particular, it is frequent that the spectral measure of this matrix converge to a compactly supported limiting probability measure π, and that the extreme eigenvalues of X n X * n a.s. converge to the edges of this support. Considering that Σ n is the sum of X n and a fixed-rank perturbation, it is well-known that Σ n Σ * n also has the limiting spectral measure π [2, Lemma 2.2]. However, the largest eigenvalues of Σ n Σ * n have a special behavior: Under some conditions, these eigenvalues leave the support of π, and in this case, their related eigenspaces give valuable information on the eigenspaces of P n . This paper shows how the angles ϕ k can be estimated from these eigenspaces.

The problem of the behavior of the extreme eigenvalues of large random matrices subjected to additive or multiplicative low rank perturbations (often called "spiked models") have received a great deal of interest in the recent years. In this regard, the authors of [START_REF] Baik | Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices[END_REF][START_REF] Baik | Eigenvalues of large sample covariance matrices of spiked population models[END_REF][START_REF] Paul | Asymptotics of sample eigenstructure for a large dimensional spiked covariance model[END_REF] study the behavior of the extreme eigenvalues of a sample covariance matrix when the population covariance matrix has all but finitely many eigenvalues equal to one, a prob-lem described in [START_REF] Johnstone | On the distribution of the largest eigenvalue in principal components analysis[END_REF]. Reference [START_REF] Capitaine | The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations[END_REF] is devoted to the extreme eigenvalues of a Wigner matrix that incurs a fixed-rank additive perturbation. Fluctuations of these eigenvalues are studied in [START_REF] Baik | Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices[END_REF][START_REF] Péché | The largest eigenvalue of small rank perturbations of Hermitian random matrices[END_REF][START_REF] Paul | Asymptotics of sample eigenstructure for a large dimensional spiked covariance model[END_REF][START_REF] Bai | Central limit theorems for eigenvalues in a spiked population model[END_REF][START_REF] Capitaine | The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations[END_REF][START_REF] Capitaine | Central limit theorems for eigenvalues of deformations of Wigner matrices[END_REF][START_REF] Benaych-Georges | Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices[END_REF].

Recently, Benaych-Georges and Nadakuditi proposed in [START_REF] Benaych-Georges | The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices[END_REF][START_REF] Benaych-Georges | The singular values and vectors of low rank perturbations of large rectangular random matrices[END_REF] a powerful technique for characterizing the behavior of extreme eigenvalues and their associated eigenspaces for three generic spiked models: The models X n + P n and (I n + P n )X n when both X n and P n are Hermitian and P n is low-rank, and the model that encompasses ours (X n + P n )(X n + P n ) * where X n and P n are rectangular. One feature of this approach is that it uncovers simple relations between the extreme eigenvalues and their associated eigenspaces on the one hand, and certain quadratic forms involving resolvents related with the non-perturbed matrix X n on the other. This makes the method particularly well-suited (but not limited to) the situation where X n is unitarily or bi-unitarily invariant, a situation that we shall consider in this paper. Indeed, in this situation, these quadratic forms exhibit a particularly simple behavior in the considered large dimensional asymptotic regime.

In this paper, we make use of the approach of [START_REF] Benaych-Georges | The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices[END_REF][START_REF] Benaych-Georges | The singular values and vectors of low rank perturbations of large rectangular random matrices[END_REF] to develop a new subspace estimator of the angles ϕ k based on the eigenspaces of the isolated eigenvalues of Σ n Σ * n . We perform the first and second order analyses of this estimator that we call the "Spike MUSIC" estimator. Our mathematical developments differ somehow from those of [START_REF] Benaych-Georges | The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices[END_REF][START_REF] Benaych-Georges | The singular values and vectors of low rank perturbations of large rectangular random matrices[END_REF] and could have their own interest. They are based on two simple ingredients: The first is an analogue of the Poincaré-Nash inequality for the Haar distributed unitary matrices which has been recently discovered by Pastur and Vasilchuk [START_REF] Pastur | On the law of addition of random matrices: covariance and the central limit theorem for traces of resolvent[END_REF], and the second is a contour integration method by means of which the first and second order analyses are done. The key step of the second order analysis of our estimator lies in the establishment of a Central Limit Theorem on the quadratic forms b(ϕ i ) * Π i b(ϕ i ) where the Π i are the orthogonal projection matrices on certain eigenspaces of Σ n Σ * n associated with the isolated eigenvalues. The employed technique can easily be used to study the fluctuations of projections of other types of vectors on these eigenspaces.

We now state our general assumptions and introduce some notations.

Assumptions and Notations

We now state the general assumptions of the paper. Consider the sequence of N × n matrices Σ n = X n + P n where:

Assumption A1. The dimensions N, n satisfy: N ≤ n, n → ∞ and N n → c ∈ (0, 1]
(notation for this asymptotic regime: n → ∞).

The following assumption on X n is widely used in the random matrix literature [START_REF] Hiai | The semicircle law, free random variables and entropy[END_REF][START_REF] Pastur | Eigenvalue distribution of large random matrices[END_REF]:

Assumption A2. Matrices X n are random N × n bi-unitarily invariant matrices, i.e., each X n admits the singular value decomposition X n = L n Γ n R * n where L n , the N × N matrix Γ n and R n are independent, L n is Haar distributed on the group U(N ) of unitary N × N matrices, and R n is a n × N submatrix of a Haar distributed matrix on U(n).

We recall that the Stieltjes transform of a probability measure π on the real line is the complex function

m(z) = 1 t -z π(dt) , analytic on C + = {z : ℑ(z) > 0}. Assumption A3. Let Q n (z) = (X n X * n -zI N ) -1 be the resolvent associated with X n X * n and let α n (z) = N -1 tr Q n (z).
For every z ∈ C + , α n (z) a.s. converges to a deterministic function m(z) which is the Stieltjes transform of a probability measure π supported by the compact interval [λ -, λ + ].

Assumption A4. The quantity X n X * n a.s. converges to λ + as n → ∞, where • denotes the spectral norm.

Let Q n (z) = (X * n X n -zI n ) -1 and αn (z) = n -1 tr Q n (z).
Equivalently to the convergence assumed by Assumption A3, one may assume that αn (z) a.s. converges on C + to a deterministic function m(z) which is the Stieltjes transform of a probability measure π. In that case, m(z) = cm(z) -(1c)/z and π = cπ + (1c)δ 0 .

Remark 1. In the areas of signal processing and communication theory, the noise matrix X n satisfying Assumptions A2-A4 is such that √ nX n is standard Gaussian -see for instance [START_REF] Marčenko | Distribution of eigenvalues in certain sets of random matrices[END_REF], [START_REF] Geman | A limit theorem for the norm of random matrices[END_REF].

We first make a general assumption on matrices P n ; it will be specified later, and adapted to the context of the MUSIC algorithm: Assumption A5. Matrices P n are deterministic with a fixed rank equal to r for all n large enough. Denoting by P n = U n Ω n V * n a singular value decomposition of P n , the matrix of singular values

Ω n = diag(ω 1,n , . . . , ω r,n ) with ω 1,n ≥ ω 2,n ≥ • • • ≥ ω r,n converges to O =    ω 1 I j1 . . . ω s I js    , (2)
where

ω 1 > • • • > ω s > 0 and j 1 + • • • + j s = r.

Notations.

As usual, if z ∈ C, we shall denote by ℜ(z) and ℑ(z) its real and imaginary parts. We shall denote by a.s.

--→ (resp. P -→, D -→) the almost sure convergence (resp. convergence in probability, in distribution). We denote by δ i,j the Kronecker delta (= 1 if i = j and 0 otherwise).

The eigenvalues of Σ n Σ * n are λ1,n ≥ λ2,n ≥ • • • ≥ λN,n . Associated eigenvectors will be denoted û1,n , û2,n , • • • , ûN,n . For k ∈ {1, . . . , r}, we shall denote by i(k) the index i ∈ {1, . . . , s} such that

j 1 + • • • + j i-1 < k ≤ j 1 + • • • + j i . For i = 1, . . . ,
s, We shall denote by Π i,n the orthogonal projection matrix on the eigenspace of Σ n Σ * n associated with the eigenvalues λk,n such that i(k) = i, i.e., Π i,n = k:i(k)=i ûk,n û * k,n when this eigenspace is defined. Columns of U n (see A5) will be denoted u 1,n , • • • , u r,n . Given i, the orthogonal projection matrix on the eigenspace of P n P * n associated with the eigenvalues ω 2 k,n such that i(k) = i will be Π i,n = k:i(k)=i u k,n u * k,n . Indexes n and N will often be dropped for readability.

Paper organization

The paper is organized as follows. Section 2 is devoted to the mathematical preliminaries. The general approach is described in Section 3. The Spike MUSIC algorithm is presented in Section 4 along with a first order study of this algorithm. Fluctuations of the estimates of the ϕ k are studied in Section 5 under the form of a Central Limit Theorem.

Preliminary mathematical results

We shall need the two following results. The first one is well-known [START_REF] Pastur | On the law of addition of random matrices: covariance and the central limit theorem for traces of resolvent[END_REF]. The second result, due to Pastur and Vasilchuk, is the unitary analogue of the well-known Poincaré-Nash inequality.

Lemma 1. Let W = [w ij ] be a random matrix Haar distributed on U(n). Then

E w ij w * i ′ j ′ = 1 n δ i,i ′ δ j,j ′ .
Lemma 2 ( [START_REF] Pastur | On the law of addition of random matrices: covariance and the central limit theorem for traces of resolvent[END_REF][START_REF] Pastur | Eigenvalue distribution of large random matrices[END_REF]). Let Φ : U(n) → C be a function that admits a C 1 continuation to an open neighborhood of U(n) in the whole algebra of n × n complex matrices. Then

var Φ(W n ) = E |Φ(W n )| 2 -|EΦ(W n )| 2 ≤ 1 n n j,k=1 E Φ ′ (W n ) • e j e T k W n 2
where E is the expectation with respect to the Haar measure on U(n), where Φ ′ is the differential of Φ as a function on R 2n 2 acting on the matrix e j e T k W n seen as an element of R 2n 2 , and where

e j = [0 • • • 0 1 0 • • • 0] * is the j th canonical vector of C n .
Given a small ε 1 > 0, let O n be the probability event

O n = { X n X * n ≤ λ + + ε 1 } . (3)
By Assumption A4, ½ On a.s.

--→ 1 as n → ∞.

Lemma 3. Let Assumption A2 holds true and let u, v be two unit norm deterministic N × 1 vectors such that u * v = 0. Then for any z with ℜ(z) > λ + + ε 1 ,

E |½ On × u * (Q(z) -α(z)I) u| p ≤ K p N p/2 d(z, λ + + ε 1 ) p , E |½ On × u * Q(z)v| p ≤ K p N p/2 d(z, λ + + ε 1 ) p ,
where the constant K p only depends on p, and where d(z, z ′ ) is the Euclidean distance between z and z ′ in C.

Proof. Recall that X = L Γ R * by Assumption A2; let D = (Γ 2 -zI) -1 ; write:

u * v * (Q -αI)   u v   = w * 1 w * 2 D - tr D N I   w 1 w 2   .
Thanks to A2, w 1 and w 2 are the first two columns of a N × N unitary Haar distributed matrix

W = [w ij ] independent of D. Let M = ½ On × D -N -1 (tr D)I and Φ i (W ) = w * 1 M w i for i = 1, 2. Then EΦ 1 (W ) = EΦ 2 (W ) = 0 by Lemma 1. Applying Lemma 2 to Φ i after noticing that Φ ′ i (W ) • A = e T 1 A * M w i + w * 1 M Ae i for any N × N matrix A, we obtain: E|Φ i | 2 = var(Φ i ) ≤ 1 N N j,k=1 E |w * k1 [M W ] ji + [W * M ] 1j w ki | 2 , ≤ 2 N E M w i 2 + M w 1 2 , ≤ 8 N d(z, λ + + ε 1 ) 2 .
We now proceed by induction; assume that the result is true until p ≥ 1. Applying Lemma 2 to Φ (p+1)/2 i , we obtain:

var Φ p+1 2 i ≤ 1 N N j,k=1 E p + 1 2 Φ p-1 2 i Φ ′ i (W ) • e j e T k W 2 , ≤ (p + 1) 2 2N E |Φ i | p-1 M w i 2 + M w 1 2 , ≤ 2(p + 1) 2 K p-1 d(z, λ + + ε 1 ) p+1 N (p+1)/2 .
Using again the induction hypothesis, we get:

E |Φ i | p+1 = var Φ p+1 2 i + EΦ p+1 2 i 2 ≤ 2(p + 1) 2 K p-1 + K 2 (p+1)/2 d(z, λ + + ε 1 ) p+1 N (p+1)/2 = K p+1 d(z, λ + + ε 1 ) p+1 N (p+1)/2 ,
which concludes the proof. Lemma 4. Let Assumption A2 hold true; let u, v be two unit norm deterministic vectors with respective dimensions N × 1 and n × 1. Then for any z such as

ℜ(z) > λ + + ε 1 , E ½ On × u * X Q(z)v p ≤ K p n p/2 d(z, λ + + ε 1 ) p . Proof. Let C = Γ(Γ 2 -zI) -1 . By Assumption A2, u * X Q(z)v = w * C w = Φ(w)
where w is a vector uniformly distributed on the unit sphere of C N , w is a vector uniformly distributed on the unit sphere of C n and truncated to its first N elements, and w, w and C are independent. The lemma is proved as above by applying Lemma 2 to Φ and by taking the expectation with respect to the law of w.

Lemma 5. Let Assumptions A1-A4 hold true. Let C be a closed path of C such that min z∈C ℜ(z) > λ + . Fix the integer r ≤ N and let U n and V n be two deterministic isometry matrices with dimensions N × r and n × r respectively. Then

sup z∈C U * n (Q n (z) -m(z)I N ) U n a.s. ----→ n→∞ 0 , sup z∈C V * n Q n (z) -m(z)I n V n a.s. ----→ n→∞ 0 , sup z∈C U * n X n Q n (z)V n a.s. ----→ n→∞ 0 .
Proof. Recall the definition (3) of the set O n and assume that ε

1 is chosen such that min z∈C ℜ(z) > λ + + ε 1 ; let h n (z) = ½ On × U * n (Q n (z) -α n (z)I N ) U n . For any ℓ, s ≤ r, [h n ] ℓ,s is a holomorphic function on C-[0, λ + +ε 1 ]. Consider a denumerable sequence of points (z k ) in C -[0, λ + + ε 1 ]
with an accumulation point in that set. By Lemma 3 with p = 3, Markov inequality and Borel-Cantelli's lemma, there exists a probability one set on which [h n (z k )] ℓ,s → 0 for every k. Moreover, the

|[h n (z k )] ℓ,s | are uniformly bounded on any compact set of C -[0, λ + + ε 1 ]
. By the normal family theorem, every n-sequence of [h n ] ℓ,s contains a further subsequence which converges uniformly on the compact set

C ⊂ C -[0, λ + + ε 1 ] to a holomorphic function that we denote h * . Since h * (z k ) = 0 for all k, h * (z) = 0 on C, hence |[h n (z)] ℓ,s
| converges uniformly to zero on C with probability one, and thanks to Assumption A4, U * (Q(z)α(z)I) U → 0 uniformly on C with probability one. The same argument, used in conjunction with Assumption A3, shows that with probability one, α(z)m(z) → 0 uniformly on C, and the first assertion is proven. The second and third assertions are proven similarly, the third being obtained with the help of Lemma 4.

Fixed Rank Perturbations: First Order Behavior

We first recall a result on matrix analysis that can be found in [START_REF] Horn | Matrix analysis[END_REF]Th. 7.3.7]:

Lemma 6. Given a N × n matrix A with N ≤ n, let A be the matrix: Along the ideas in [START_REF] Benaych-Georges | The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices[END_REF][START_REF] Benaych-Georges | The singular values and vectors of low rank perturbations of large rectangular random matrices[END_REF], we now characterize the behavior of the largest eigenvalues of ΣΣ * , and then focus on their eigenspaces.

A = 0 A A * 0 . Then σ 1 , • • • , σ N are the singular values of A if and only if σ 1 , • • • , σ N , -σ 1 , • • • , -σ N in addition to n -N

Asymptotic behavior of the largest eigenvalues of ΣΣ *

We start with an informal description of the approach. By Lemma 6, λ is an eigenvalue of ΣΣ * if and only if det(Σ -√ λI) = 0 where Σ = 0 Σ Σ * 0 . Writing:

Σ = 0 X X * 0 + U 0 0 V Ω 0 I r I r 0 U * 0 0 ΩV * △ = X + BJB * , (4)
and assuming that x > 0 is not a singular value of X, we have:

det(Σ -xI) = det(X -xI + BJB * ) = det(J) det(X -xI) det(J + B * (X -xI) -1 B) ,
after noticing that J = J -1 . Using the formula for the inversion of a partitioned matrix (see [START_REF] Horn | Matrix analysis[END_REF])

A 11 A 12 A * 12 A 22 -1 = (A 11 -A 12 A -1 22 A * 12 ) -1 -A -1 11 A 12 (A 22 -A * 12 A -1 11 A 12 ) -1 -(A 22 -A * 12 A -1 11 A 12 ) -1 A * 12 A -1 11 (A 22 -A * 12 A -1 11 A 12 ) -1
, we obtain:

Q(x) = (X -xI) -1 = -xI X X * -xI -1 = xQ(x 2 ) X Q(x 2 ) Q(x 2 )X * x Q(x 2 ) . (5) Therefore, det(Σ -xI) = det(J) det(X -xI) det H(x) ,
where

H n (x) = xU * Q(x 2 )U I r + U * X Q(x 2 )V Ω I r + ΩV * Q(x 2 )X * U xΩV * Q(x 2 )V Ω
whence for n large enough, the isolated eigenvalues of ΣΣ * above λ + will coincide with the zeros of det H( √ x) that lie above λ + . Under Assumptions A1-A5, Lemma 5 shows that H(x) a.s. converges to

H(x) = xm(x 2 )I r I r I r x m(x 2 )O 2 .
Consider the equation det

H( √ x) = det xm(x) m(x)O 2 -I r = 0 ,
and notice that the function

g(x) = xm(x) m(x) = x 1 t -x π(dt) c 1 t -x π(dt) - 1 -c x (6)
decreases from g(λ

+ + ) = lim x↓λ+ g(x) to zero on (λ + , ∞). Let ω 2 1 > • • • > ω 2 q be those among the diagonal elements of O 2 that satisfy ω 2 i > 1/g(λ + + ). Equation g(x) = ω -2 i
will have a unique solution x = ρ i > λ + for any i = 1, • • • , q, while it will have no solution larger than λ + for i > q. It is then expected that any eigenvalue λk,n of Σ n Σ * n for which i(k) ≤ q (remember the definition of i(k) provided in the paragraph "Assumptions and Notations" in Section 1), will converge to ρ i , while λj1+•••+jq+1,n → λ + almost surely.

These facts are formalized in the following theorem, shown in [START_REF] Benaych-Georges | The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices (v1)[END_REF][START_REF] Benaych-Georges | The singular values and vectors of low rank perturbations of large rectangular random matrices[END_REF]: Theorem 1. Let Assumptions A1-A5 hold true; let q be the maximum index such that

ω 2 q > 1/g(λ + + ). Let ρ i be the unique real number > λ + satisfying ω 2 i g(ρ i ) = 1 for i = 1, • • • , q. Then λj1+•••+ji-1+ℓ,n a.s. ----→ n→∞ ρ i for i = 1, • • • , q and ℓ = 1, • • • , j i while λj1+•••+jq+1,n a.s.
----→ n→∞ λ + .

In the case where √ nX is a standard Gaussian matrix, π is the Marčenko-Pastur distribution with support supp

(π) = [λ -, λ + ] = [(1 - √ c) 2 , (1 + √ c) 2 ],
and

m(x) = 1 2cx 1 -c -x + (1 -c -x) 2 -4cx (7)
for x ∈ (λ + , ∞). After a few derivations, we obtain:

Corollary 1. Assume √ nX is standard Gaussian. Let q be the maximum index such that ω 2 q > √ c. Then λj1+•••+ji-1+ℓ,n a.s. ----→ n→∞ (ω 2 i + 1)(ω 2 i + c) ω 2 i for i = 1, . . . , q , and λj1+•••+jq+1,n a.s. ----→ n→∞ (1 + √ c) 2 .
We now turn our attention to the eigenspaces of the isolated eigenvalues.

Asymptotic behavior of certain bilinear forms.

Recall the definition of s as provided in Assumption A5. Given i ≤ s, assume that ω 2 i > 1/g(λ + + ). Given two N × 1 deterministic sequences of vectors b 1,n and b 2,n with bounded norms, we shall find here a simple asymptotic relation between b * 1,n Π i,n b 2,n and b * 1,n Π i,n b 2,n , that will be at the basis of the Spike MUSIC algorithm. A close problem has been considered in [START_REF] Benaych-Georges | The singular values and vectors of low rank perturbations of large rectangular random matrices[END_REF]. We consider here a different technique, based on a contour integration and on the use of Lemmas 3 and 4. This method lends itself easily to the first and second order analyses of the Spike MUSIC algorithm that we shall develop in the following sections.

Writing b i = b i 0 with i = 1, 2, we have by virtue of Lemma 6:

b * 1 Π i b 2 = -1 ıπ Ci,n b * 1 (Σ -zI) -1 b 2 dz ,
where C i,n is a positively oriented circle that encloses the only singular values λk,n of Σ n for which i(k) = i. Recalling (4) and using Woodbury's identity ([19, §0.7.4]) together with the fact that J = J -1 , we obtain:

b * 1 Π i b 2 = -1 ıπ Ci b * 1 Q(z)b 2 dz + 1 ıπ Ci b * 1 Q(z)B (J + B * Q(z)B) -1 B * Q(z)b 2 dz .
Using [START_REF] Baik | Eigenvalues of large sample covariance matrices of spiked population models[END_REF], we obtain after a straightforward calculation:

b * 1,n Π i,n b 2,n = -1 ıπ Ci,n b * 1,n Q n (z)b 2,n dz + 1 ıπ Ci,n â * 1,n (z) H n (z) -1 â2,n (z) dz (8)
where

1 âℓ,n (z) = zU * n Q n (z 2 ) Ω n V * n Q n (z 2 )X * n b ℓ,n , â * ℓ,n (z) = b * ℓ,n zQ n (z 2 )U n X n Q n (z 2 )V n Ω n . (9)
Intuitively, the first integral is zero for n large enough and the second is close to

T i,n = 1 ıπ γi a * 1,n (z)H(z) -1 a 2,n (z) dz ,
where γ i is a small enough positively oriented circle which does not meet the image of supp(π) by x → √ x nor any of the √ ρ ℓ and such that only √ ρ i ∈ Int(γ i ), the interior of the disk defined by γ i (see Figure 1), a * ℓ,n (z) = b * ℓ,n zm(z 2 )U n 0 , and

a ℓ,n (z) = zm(z 2 )U * n 0 b ℓ,n .
The approximation b * 1 Π i b 2 ≃ T i will be justified rigorously below. For the moment, let us develop the expression of T i . Defining the r × r matrices:

I i =   0 I ji 0   ,
1 Notice that â * ℓ,n (z) as defined is not the Hermitian adjoint of âℓ,n (z). Despite this ambiguity, we introduce this notation which remains natural and widespread in Signal Processing.

.

λ + √ ρ i √ ρ 1 γ i
. where the integers j i are defined in Assumption A5, we have

H(z) -1 = s i=1 1 z 2 m(z 2 ) m(z 2 )ω 2 i -1 z m(z 2 )ω 2 i -1 -1 zm(z 2 ) ⊗ I i , (10)
which leads to

T i = 1 ıπ s ℓ=1 b * 1 Π ℓ b 2 γi z 3 m(z 2 ) 2 m(z 2 )ω 2 ℓ z 2 m(z 2 ) m(z 2 )ω 2 ℓ -1 dz = 1 2ıπ s ℓ=1 b * 1 Π ℓ b 2 γ ′ i wm(w) 2 m(w)ω 2 ℓ wm(w) m(w)ω 2 ℓ -1
dw by making the change of variable w = z 2 . Observe that the path γ ′ i now encloses ρ i only. Recall that wm(w) m(w)ω 2 ℓ -1 = 0 if and only if w = ρ ℓ for every ℓ such that ω 2 ℓ > 1/g(λ + + ), and since g(w) = wm(w) m(w) is decreasing on (λ + , ∞), these zeros are simple. As a result, the integrals above are equal to zero for ℓ = i, and the integrand has a simple pole at w = ρ i for ℓ = i. By the Residue Theorem, we have:

T i = 1 ıπ γi a * 1 (z)H(z) -1 a 2 (z) dz = ρ i m(ρ i ) 2 m(ρ i ) (ρ i m(ρ i ) m(ρ i )) ′ b * 1 Π i b 2 (11)
where the denominator at the right hand side is the derivative of the function λ → λm(λ) m(λ) at λ = ρ i . We now make this argument more rigorous:

Theorem 2. Let Assumptions A1-A5 hold true. For a given i ≤ s, assume that ω 2 i > 1/g(λ + + ). Let (b 1,n ) and (b 2,n ) be two sequences of deterministic vectors with bounded norms. Then

b * 1,n Π i,n b 2,n - ρ i m(ρ i ) 2 m(ρ i ) (ρ i m(ρ i ) m(ρ i )) ′ b * 1,n Π i,n b 2,n a.s.
----→ n→∞ 0 .

Proof. Write

T i = 1 ıπ γi â * 1 (z) H(z) -1 â2 (z) dz .
Then, with probability one, b * 1 Π i b 2 = T i for n large enough. Indeed, on the set O n (as defined in (3)), the singular values of Σ greater than λ + + ε 1 coincide with the poles of H(z) which are greater than λ + + ε 1 by the argument preceding Theorem 1. On this set, the first integral on the right hand side (r.h.s.) of ( 8) is zero, and by Theorem 1, the second integral can be replaced with γi with probability one for n large enough. By Lemma 5, the differences H(z) -H(z), â1 (z)a 1 (z), and â2 (z)a 2 (z) a.s. converge to zero, uniformly on γ i . Hence T i -T i a.s.

--→ 0.

The Spike MUSIC Estimation Algorithm

Algorithm description

We now consider the application context described in the introduction, and assume that The assumption over the speed of convergence of S * S will be needed only for the purpose of the second order analysis. It is satisfied by most practical systems met in the field of signal processing. We moreover observe that it is possible to relax the assumption that O is diagonal at the expense of a more complicated second order analysis.

P n = B n (ϕ 1 , . . . , ϕ r )S * n where B n (ϕ 1 , . . . , ϕ r ) = b n (ϕ 1 ) • • • b n (ϕ k ) ,
P n = B n (ϕ 1 , • • • ϕ r )S * n where r is a fixed integer, B n (ϕ 1 , • • • ϕ r ) = b n (ϕ 1 ) • • • b n (ϕ r ) is a N × r matrix, b n (ϕ) = N -1/2 exp(-ıDℓϕ) N -1 ℓ=0 on ϕ ∈ [0, π/D],
In order for the algorithm to be able to estimate the r angles, it is necessary that the perturbation P gives rise to r isolated eigenvalues, a fact that is stated in the following assumption:

Assumption A7. Recall the definition (6) of function g, let λ + as defined in A3 and let g(λ + + ) = lim x↓λ+ g(x). Let the ω i 's as defined in A5, then:

ω 2 r > 1 g(λ + + )
.

The Spike MUSIC algorithm goes like this. The localization function χ(ϕ) defined in the introduction is also written as χ(ϕ) =

χn (ϕ) = r k=1 |b n (ϕ) * ûk,n | 2 ζ( λk,n ) , (12)
where

ζ(λ) = (λm(λ) m(λ)) ′ λm(λ) 2 m(λ) (13)
is a consistent estimator of χ n (ϕ) in the asymptotic regime described by A1. By searching for the maxima of χ(ϕ), we infer that we obtain consistent estimates of the angles or arrival.

Observe that this algorithm requires the knowledge of the Stieltjes Transform of the limit spectral measure of XX * (available if the statistical description of the noise is known) and the number r of emitting sources. Notice that when this number is unknown, it can be estimated along the ideas described in e.g. [START_REF] Bianchi | Performance of statistical tests for single-source detection using random matrix theory[END_REF][START_REF] Nadler | On the distribution of the ratio of the largest eigenvalue to the trace of a Wishart matrix[END_REF]. We now perform the first order analysis of this algorithm.

First order analysis of the Spike MUSIC algorithm

We now formalize the argument of the previous paragraph and we push it further to show the consistency "up to the order n" of the Spike MUSIC estimator. We shall need this speed to perform the second order analysis (Lemma 9 below). ----→ n→∞ 0.

The proof of this theorem is performed in two steps. With an approach similar to the one used in Section 3, we first prove that χ(ϕ)χ(ϕ) a.s.

--→ 0, and the convergence is uniform on ϕ ∈ [0, π/D] (Proposition 1 below). Next, following the technique of [START_REF] Hannan | Non-linear time series regression[END_REF][START_REF] Hannan | The estimation of frequency[END_REF], we prove that this uniform a.s. convergence leads to Theorem 3.

In the sequel, we write:

â(z, ϕ) = zU * Q(z 2 ) ΩV * Q(z 2 )X * b(ϕ) and a(z, ϕ) = zm(z 2 )U * 0 b(ϕ) , (14) â
* (z, ϕ) = b * (ϕ)[zQ(z 2 )U X Q(z 2 )V Ω] , a * (z, ϕ) = b(ϕ)[zm(z 2 )U 0] .
Beware that â * and a * are not the Hermitian adjoints of â and a (see the footnote associated to Eq. ( 9)). ----→ n→∞ 0 .

Proof. Write

χ(ϕ) -χ(ϕ) = r k=1 (ζ( λk ) -ζ(ρ i(k) ))|b(ϕ) * ûk | 2 + s i=1 ζ(ρ i )b(ϕ) * Π i b(ϕ) -b(ϕ) * Π i b(ϕ) .
By Theorem 1 and the continuity of ζ on (λ + , +∞), the first term at the r.h.s. goes to zero a.s. and uniformly in ϕ. Consider the second term. Let γ i be a small enough positively oriented circle which does not meet supp(π)

∪ { √ ρ 1 , • • • , √ ρ s } and such that only √ ρ i ∈ Int(γ i ). Since λk a.s. --→ ρ i(k) , max i max ϕ b(ϕ) * Π i b(ϕ) -T i (ϕ) = 0
a.s. for n large enough, where

T i (ϕ) = 1 ıπ γi â * (z, ϕ) H(z) -1 â(z, ϕ) dz
Recalling Eq. ( 11), it will therefore be enough to prove that max

1≤i≤s max ϕ∈[0,π/D] |Z i (ϕ)| a.s. ----→ n→∞ 0 , where Z i (ϕ) = 1 ıπ γi â * (z, ϕ) H(z) -1 â(z, ϕ) -a * (z, ϕ)H(z) -1 a(z, ϕ) dz . We have max ϕ |Z i (ϕ)| ≤ 2R 1 0 max ϕ e( √ ρ i + Re 2ıπθ , ϕ) dθ
where R is the radius of γ i and where e(z, ϕ) = â * (z, ϕ) H(z) -1 â(z, ϕ)a * (z, ϕ)H(z) -1 a(z, ϕ) .

≤ (â * -a * )H -1 â + aH -1 (â -a) + â * ( H -1 -H -1 )â .
Since H -1 , max ϕ a and max ϕ â are bounded on γ i , e(z, ϕ) satisfies on this path

e(z, ϕ) ≤ K â(z, ϕ) -a(z, ϕ) + H(z) -1 -H(z) -1 .
By Lemma 5 and the fact that H -1 is bounded on γ i , the term H -1 -H -1 = H -1 (H -H)H -1 converges to zero uniformly on γ i with probability one. To obtain the result, we prove that âa a.s.

--→ 0 and that this convergence is uniform on (z, ϕ)

∈ γ i × [0, π/D]. Let us focus on the first term zu * 1 (Q(z 2 ) -m(z 2 )I)b(ϕ) of â -a, where we recall that u 1 is the first column of U . Since b(ϕ) = u 1 = 1, |zu * 1 (Q(z 2 ) -m(z 2 )I)b(ϕ)| ≤ |zu * 1 (Q(z 2 ) -α(z 2 )I)b(ϕ)| + |z(α(z 2 ) -m(z 2 ))| .
With probability one, the second term converges to zero on γ i , and the convergence is uniform (along the principle of the proof of Lemma 5). Since

sup n max ϕ n -1 b ′ (ϕ) = sup n max ϕ n -1 N -1/2 ℓD exp(-ıℓDϕ) N -1 ℓ=0 < ∞ , the term ξ(z, ϕ) = ½ On × zu * 1 (Q(z 2 ) -α(z 2 )I)b(ϕ) satisfies |ξ(z 1 , ϕ 1 ) -ξ(z 2 , ϕ 2 )| ≤ K(n|ϕ 1 -ϕ 2 | + |z 1 -z 2 |)
for every (z 1 , ϕ 1 ), (z 2 , ϕ 2 ) in γ i × [0, π/D]. Therefore, it will be enough to prove that max (z,ϕ)∈An×Bn ξ(z, ϕ) a.s.

----→ n→∞ 0 where A n contains n regularly spaced points in γ i and B n contains n 2 regularly spaced points in [0, π/D]. This can be obtained from Lemma 3 with p = 9, Markov inequality and Borel Cantelli's lemma. The other terms of âa can be handled similarly.

We now prove Theorem 3 by following the ideas of [START_REF] Hannan | Non-linear time series regression[END_REF][START_REF] Hannan | The estimation of frequency[END_REF]. To that end, we need the following lemma, proven in [START_REF] Ciblat | Asymptotic analysis of blind cyclic correlation-based symbol-rate estimators[END_REF]: Lemma 7. Let (c N ) be a sequence of real numbers belonging to a compact of [-1/2, 1/2] and converging to c. Let

q N (c N ) = 1 N N -1 k=0 exp(-2ıπkc N ) .
Then the following hold true:

q N (c N ) ----→ N →∞ 0 if c = 0 , q N (c N ) ----→ N →∞ 0 if c = 0 and N |c N -c| → ∞ , q N (c N ) ----→ N →∞ exp(-ıπd) sinc(d) if c = 0 and N |c N -c| → d ,
where sinc stands as usual for sine cardinal.

Proof of Theorem 3. We start by observing that χ(ϕ) = d(ϕ) * (B * B) -1 d(ϕ) where B is the matrix defined in A6 and where

d(ϕ) = b(ϕ k ) * b(ϕ) r k=1 . By Lemma 7, B * B → I r , hence χ(ϕ) -d(ϕ) 2 → 0.
In the remainder of the proof, we shall stay in the probability one set where the uniform convergence in the statement of Proposition 1 holds true. Taking k = 1 without loss of generality, we shall show that any sequence φ1,n for which χ( φ1,n ) attains its maximum in the closure of a small neighborhood of ϕ 1 satisfies N ( φ1,nϕ 1 ) → 0. Given a sequence of such φ1,n , assume we can extract a subsequence φ1,n * such that N | φ1,n *ϕ 1 | → ∞. In this case, Lemma 7 and the observations made above on the structure of χ(ϕ) show that χ( φ1,n * ) → 0. Since max ϕ | χ(ϕ)χ(ϕ)| → 0, χ( φ1,n * ) → 0. But χ(ϕ 1 ) → χ(ϕ 1 ) = 1, which contradicts the fact that φ1,n * maximizes χ. Hence the sequence N ( φ1,n *ϕ 1 ) belongs to a compact. Assume N ( φ1,n *ϕ 1 ) → 0. If we take a further subsequence of the latter that converges to a constant d = 0, then by Lemma 7, χ converges to sinc(d) 2 < 1 along this subsequence, which also raises a contradiction. This proves the theorem.

Second Order Analysis of the Spike MUSIC Estimator

In order to perform the second order analysis, we also assume:

Assumption A8. Let λ -, λ + , α and m be as in A3. Then for any z ∈ C -[λ -, λ + ], √ n (α(z) -m(z)) converges in probability to zero. Remark 2. If √ nX is standard Gaussian and if c n = N/n satisfies √ n(c n -c) → 0, then
Assumption A8 is satisfied. Indeed, call m n (z) the Stieltjes Transform of the Marčenko-Pastur distribution, i.e., the analytic continuation of (7), when c is replaced with c n , and let π n be the associated probability measure. For

z ∈ C -[λ -, λ + ], function f (x) = (x -z) -1
is analytic outside the support of π n for n large, and [3, Th.1.1] can be applied to show that √ n(α n (z)m n (z))

P -→ 0. When √ n(c n -c) → 0, it is furthermore clear that √ n(m n (z) - m(z)) → 0.
The main result of this section is the following: Theorem 4. Let Assumptions A1-A8 hold true. Then the estimates φk,n satisfy

n 3/2    φ1,n -ϕ 1 . . . φr,n -ϕ r    D ----→ n→∞ N   0,    σ 2 1 I j1 . . . σ 2 s I js       ( 15
)
where

σ 2 i = 6 c 2 D 2 m ′ (ρ i ) -m(ρ i ) 2 cm(ρ i ) 2 + ω 2 i (m(ρ i ) + ρ i m ′ (ρ i )) , 1 ≤ i ≤ s .
When √ nX is standard Gaussian, plugging the r.h.s. of ( 7) into this expression leads after some derivations to:

Corollary 2. If √ nX is standard Gaussian and if √ n(c n -c) → 0, the convergence (15) holds true with σ 2 i = 6 c 2 D 2 ω 2 i + 1 ω 4 i -c
.

This corollary calls for some comments: Remark 3 (Efficiency at high SNR). Recalling that ω 2 i > √ c is the condition for the existence of a corresponding isolated eigenvalue (Corollary 1), we observe that the estimator variance for ϕ k goes to infinity as the corresponding ω 2 i decreases to √ c. At the other extreme, this variance behaves like 6c

-2 D -2 ω -2 i as ω 2 i → ∞.
It is useful to notice that this asymptotic variance coincides with the Cramér-Rao bound for estimating ϕ k [START_REF] Stoica | MUSIC, maximum likelihood, and Cramer-Rao bound[END_REF]. In other words, the Spike MUSIC estimator is efficient at high SNR when the noise matrix is standard Gaussian.

A numerical illustration

In order to illustrate the convergence and the fluctuations of the Spike MUSIC algorithm, we simulate a radio signal transmission satisfying Assumptions A1-A8. We consider r = 2 emitting sources located at the angles 0.5 and 1 radian, and a number of receiving antennas ranging from N = 5 to N = 50. The observation window length is set to n = 2N (hence c = 0.5). The noise matrix X n is such that √ nX n is standard Gaussian. The source powers are assumed equal, so that the matrix O given by Equation ( 2) is written O = ωI 2 , and the Signal to Noise Ratio for any source is SNR = 10 log 10 ω 2 decibels. In Figure 2, the SNR is set to 10 dB, and the empirical variance of φ1,nϕ 1 (red curve) is computed over 2000 runs. The variance provided by Corollary 2 is also plotted versus N . We observe a good fit between the variance predicted by Corollary 2 and the empirical variance after N = 15 antennas. In Figure 3, the variance is plotted as a function of the SNR, the number of antennas being fixed to N = 20. The empirical variance is computed over 5000 runs. The Cramér-Rao Bound is also plotted. The empirical variance fits the theoretical one from SNR ≈ 6 dB upwards.

Proof of Theorem 4.

We start with some additional notations and definitions. Matrix B = b(ϕ 1 ), . . . , b(ϕ r ) will be often written as B = [b 1 , . . . , b r ] or in block form as B = B 1 , . . . , B s where B i has j i columns. We shall also write B ′ = b ′ (ϕ 1 ), . . . , b ′ (ϕ r ) and B ′′ = b ′′ (ϕ 1 ), . . . , b ′′ (ϕ r ) where b ′ (ϕ) and b ′′ (ϕ) are respectively the first and second derivatives of b(ϕ). We shall also use the short hand notations

B ′ = [b ′ 1 , . . . , b ′ r ] and B ′′ = [b ′′ 1 , . . . , b ′′ r ]. Matrix B ⊥ = [b ⊥ 1 , . . . , b ⊥ r ]
will be defined by the equation

1 n B ′ = - ıcD 2 B + cD 2 √ 3 B ⊥ . (16)
Finally, if x n , y n are random sequences, we denote by x n ≍ y n the convergence x ny n P -→ 0.

We now state some preliminary results. In the following, we say that the complex random vector η is governed by the law CN (0, R) where R is a nonnegative Hermitian matrix if the real vector

ℜ(η) ℑ(η) has the law N 0, 1 2 ℜ(R) -ℑ(R) ℑ(R) ℜ(R)
. The following proposition, whose proof is postponed to Appendix A, is crucial:

Proposition 2.
Let Assumptions A1-A4 hold true. Let t ≤ N be a fixed integer, let W = w 1 , • • • , w t and W = w1 , • • • , wt be deterministic isometry matrices with dimensions N × t and n × t respectively. Let ρ be a real number such that ρ > λ + . Then

ξ n = √ n W * Q(ρ) -α(ρ)I N W, W * Q(ρ) -α(ρ)I n W , W * X Q(ρ) W is tight.
Assume t is even. Given real numbers ρ 1 , . . . , ρ t/2 all strictly greater than λ + , the t × 1 random vector

η n = √ N w * k Q(ρ k )w t/2+k 1≤k≤t/2 , √ n w * k X Q(ρ k ) wk 1≤k≤t/2 T converges in distribution towards CN (0, R) with R = diag m ′ (ρ k ) -m(ρ k ) 2 t/2 k=1 0 0 diag (m(ρ k ) + ρ k m ′ (ρ k )) t/2 k=1
.

Writing Q -mI = (Q -αI) + (αm)I, and similarly for Q, we obtain:

Corollary 3. Assume in addition that Assumption A8 is satisfied. Then

ξ n = √ n W * Q(ρ) -m(ρ)I N W, W * Q(ρ) -m(ρ)I n W , W * X Q(ρ) W is tight.
Intuitively, tightness of ξ n leads to the tightness of the √ n( λk,n -ρ i(k) ). This is formalized by the following proposition, proven in Appendix B: Proposition 3. Assume the setting of Theorem 4. Then the sequences

√ n( λk,n -ρ i(k) ) are tight for 1 ≤ k ≤ r.
The following lemma is proven in Appendix C. Lemma 8. Let Assumptions A5 and A6 hold true. Then the following convergences hold true:

B * B ----→ n→∞ I r , 1 n 2 B * B ′′ ----→ n→∞ - c 2 D 2 3 I r , (B ⊥ ) * B ⊥ ----→ n→∞ I r , (B ⊥ ) * B ----→ n→∞ 0 , Π i -Π Bi ----→ n→∞ 0 for all i = 1, . . . , s
where Π Bi is the orthogonal projection matrix on the column space of B i .

We now enter the proof of Theorem 4.

Recall the definitions ( 12) and ( 13) of χ and ζ. In most of the proof, we shall focus on √ n( φ1,nϕ 1 ). Recalling that χ′ ( φ1 ) = 0 and performing a Taylor-Lagrange expansion of χ′ around ϕ 1 , we obtain 0 = χ′ ( φ1 ) = χ′ (ϕ 1 ) + ( φ1ϕ 1 ) χ′′ (ϕ 1 ) + ( φ1ϕ 1 ) 2 2 χ(3) ( φ1 ) , where χ(3) is the third derivative of χ and where φ1 ∈ [ϕ 1 ∧ φ1 , ϕ 1 ∨ φ1 ]. Hence

n 3/2 ( φ1 -ϕ 1 ) = - n -1/2 χ′ (ϕ 1 ) n -2 χ′′ (ϕ 1 ) + 0.5n -2 ( φ1 -ϕ 1 ) χ(3) ( φ1 )
.

We start by characterizing the asymptotic behavior of the denominator of this equation:

Lemma 9. Assume that the setting of Theorem 4 holds true. Then,

χ′′ (ϕ 1 ) n 2 + ( φ1 -ϕ 1 ) χ(3) ( φ1 ) 2n 2
a.s.

----→ n→∞ -c 2 D 2 6 .

Proof. We have χ′′ (ϕ 1 )

n 2 = 2 n 2 r k=1 ζ( λk )|(b ′ 1 ) * u k | 2 + 2 n 2 r k=1 ℜ ζ( λk )b * 1 u k u * k b ′′ 1 , χ ′′ (ϕ 1 ) n 2 = 2 n 2 (b ′ 1 ) * U U * b ′ 1 + 2 n 2 ℜ (b * 1 U U * b ′′ 1 ) . (17)
Theorem 1 along with the continuity of ζ on (λ + , ∞), and Theorem 2 show that

1 n 2 χ′′ (ϕ 1 ) - 1 n 2 χ ′′ (ϕ 1 )
a.s.

----→ n→∞ 0 .

Writing 1 n 2 χ ′′ (ϕ 1 ) = 2 n 2 s i=1 ((b ′ 1 ) * Π i b ′ 1 + ℜ(b * 1 Π i b ′′ 1 )) ,
we have

1 n 2 (b ′ 1 ) * Π i b ′ 1 = - ıcD 2 b 1 + cD 2 √ 3 b ⊥ 1 * Π i - ıcD 2 b 1 + cD 2 √ 3 b ⊥ 1 , ----→ n→∞ c 2 D 2 4 δ i,0
by the first, fourth and fifth assertions of Lemma 8. By the same lemma,

1 n 2 b * 1 Π i b ′′ 1 - δ i,0 n 2 b * 1 b ′′ 1 → 0 and 1 n 2 b * 1 b ′′ 1 → - c 2 D 2 3 .
Hence n -2 χ′′ (ϕ 1 ) → -c 2 D 2 /6.

Furthermore, it is easily seen that n -3 χ(3) ( φ1 ) is bounded. Since n( φ1ϕ 1 )

a.s.

--→ 0 by Theorem 3, n -2 ( φ1ϕ 1 ) χ(3) ( φ1 ) a.s.

--→ 0, which establishes the result.

We now turn to the numerator n -1/2 χ′ (ϕ

1 ) = 2n -1/2 r k=1 ζ( λk )ℜ (b * 1 ûk û * k b ′ 1 )
, and start with the following lemma: Lemma 10. Assume that the setting of Theorem 4 holds true. Then

1 √ n χ′ (ϕ 1 ) -2ℜ(ξ) P -→ 0 , where ξ = s i=1 ζ(ρ i ) ıπ √ n γi â * (z, ϕ 1 ) H(z) -1 â′ ϕ (z, ϕ 1 ) -a * (z, ϕ 1 )H(z) -1 a ′ ϕ (z, ϕ 1 ) dz, (18)
and where the deterministic circle γ i encloses ρ 1/2 i only and:

â′ ϕ (z, ϕ) = ∂â(z, ϕ) ∂ϕ = zU * Q(z 2 ) ΩV * Q(z 2 )X * b ′ (ϕ) , a ′ ϕ (z, ϕ) = ∂a(z, ϕ) ∂ϕ = zm(z 2 )U * 0 b ′ (ϕ) .
Proof. Recall the definition of χ as given in [START_REF] Capitaine | Central limit theorems for eigenvalues of deformations of Wigner matrices[END_REF]. A direct computation yields:

χ′ (ϕ) = 2 r k=1 ζ( λk,n )ℜ (b * 1 (ϕ)û k û * k b ′ 1 (ϕ)) , = 2 s i=1 k:i(k)=i ζ( λk,n )ℜ (b * 1 (ϕ)û k û * k b ′ 1 (ϕ)) .
Recall that r and s are fixed and independent from n by A5. We start by showing that

1 √ n χ′ (ϕ 1 ) - 2 √ n s i=1 ζ(ρ i )ℜ b * 1 Π i b ′ 1 P ----→ n→∞ 0. ( 19
) Since √ n(ζ( λk,n )-ζ(ρ i(k) )
) is tight as a corollary of Proposition 3, it will be enough to prove

that n -1 ℜ (b * 1 ûk û * k b ′ 1 )
→ 0 in probability for every k. By the definition ( 16) of B ⊥ , we have

1 n ℜ (b * 1 ûk û * k b ′ 1 ) = cD 2 √ 3 ℜ b * 1 ûk û * k b ⊥ 1 . By Cauchy-Schwarz inequality, b * 1 ûk û * k b ⊥ 1 2 ≤ b * 1 Π i(k) b 1 (b ⊥ 1 ) * Π i(k) b ⊥ 1 . By Theorem 2, b * 1 Π i(k) b 1 (b ⊥ 1 ) * Π i(k) b ⊥ 1 -ζ(ρ i(k) ) -2 b * 1 Π i(k) b 1 (b ⊥ 1 ) * Π i(k) b ⊥ 1 a.s.
--→ 0, and by Lemma 8, b *

1 Π i(k) b 1 (b ⊥ 1 ) * Π i(k) b ⊥ 1
→ 0 (consider alternatively the cases i(k) = 1 and i(k) > 1) which proves [START_REF] Horn | Matrix analysis[END_REF]. Now, applying ( 8) and ( 14), and taking up an argument used in the proof of Theorem 2, we have

2 s i=1 ζ(ρ i ) √ n ℜ b * 1 Π i b ′ 1 = 2 s i=1 ℜ -ζ(ρ i ) ıπ √ n Ci b * 1 0 Q(z) b ′ 1 0 dz + 2 s i=1 ℜ ζ(ρ i ) ıπ √ n Ci â * (z, ϕ 1 ) H(z) -1 â′ ϕ (z, ϕ 1 ) dz = 2 s i=1 ℜ ζ(ρ i ) ıπ √ n γi â * (z, ϕ 1 ) H(z) -1 â′ ϕ (z, ϕ 1 ) dz
with probability one for n large. On the other hand, recalling [START_REF] Bienvenu | Adaptivity to background noise spatial coherence for high resolution passive methods[END_REF], we have

0 = χ ′ (ϕ 1 ) = 2 s i=1 ℜ ζ(ρ i ) ıπ γi a * (z, ϕ 1 )H(z) -1 a ′ ϕ (z, ϕ 1 ) dz ,
which proves the result.

Write H(z) = H(z) + E(z) and â(z, ϕ) = a(z, ϕ) + e(z, ϕ). To be more specific,

E(z) = zU * (Q(z 2 ) -m(z 2 )I N )U U * X Q(z 2 )V Ω ΩV * Q(z 2 )X * U zΩV * ( Q(z 2 ) -m(z 2 )I n )V Ω (20)
and

e(z, ϕ) = zU * Q(z 2 ) -m(z 2 )I ΩV * Q(z 2 )X * b(ϕ). Write e ′ ϕ (z, ϕ) = ∂e(z, ϕ)/∂ϕ. For a given z ∈ γ i , H -1 = H -1 -H -1 EH -1 + O( E 2
). This suggests the following development

ξ = s i=1 ζ(ρ i ) ıπ √ n γi a * (z, ϕ 1 )H(z) -1 e ′ ϕ (z, ϕ 1 ) dz + ζ(ρ i ) ıπ √ n γi e * (z, ϕ 1 )H(z) -1 a ′ ϕ (z, ϕ 1 ) dz - ζ(ρ i ) ıπ √ n γi a * (z, ϕ 1 )H(z) -1 E(z)H(z) -1 a ′ ϕ (z, ϕ 1 ) dz + q i = s i=1 (X 1,i + X 2,i + X 3,i + q i ) .
where the terms q i are "higher order terms" that appear when we expand the r.h.s. of [START_REF] Hiai | The semicircle law, free random variables and entropy[END_REF]. We first handle the terms X k,i 's, then q i .

The terms X 1,i

Writing

U n = U 1,n • • • U s,n and V n = V 1,n • • • V s,n
where both U i,n and V i,n have j i columns, and recalling (10), we have

X 1,i = ζ(ρ i ) ıπ √ n s ℓ=1 γi zm(z 2 )b * 1 U ℓ 0 × z m(z 2 )ω 2 ℓ -1 -1 zm(z 2 ) ⊗ I j ℓ z 2 m(z 2 ) m(z 2 )ω 2 ℓ -1 × zU * ℓ Q(z 2 ) -m(z 2 )I b ′ 1 ω ℓ V * ℓ Q(z 2 )X * b ′ 1 dz = ζ(ρ i ) ıπ √ n s ℓ=1 γi z 3 ω 2 ℓ m(z 2 ) m(z 2 )b * 1 Π ℓ Q(z 2 ) -m(z 2 )I b ′ 1 z 2 m(z 2 ) m(z 2 )ω 2 ℓ -1 dz - ζ(ρ i ) ıπ √ n s ℓ=1 γi ω ℓ zm(z 2 )b * 1 U ℓ V * ℓ Q(z 2 )X * b ′ 1 z 2 m(z 2 ) m(z 2 )ω 2 ℓ -1 dz = ζ(ρ i ) 2ıπ √ n s ℓ=1 γ ′ i wω 2 ℓ m(w) m(w)b * 1 Π ℓ (Q(w) -m(w)I) b ′ 1 wm(w) m(w)ω 2 ℓ -1 dw - ζ(ρ i ) 2ıπ √ n s ℓ=1 γ ′ i ω ℓ m(w)b * 1 U ℓ V * ℓ Q(w)X * b ′ 1 wm(w) m(w)ω 2 ℓ -1 dw
where γ ′ i encloses ρ i only. These integrals are zero for ℓ = i. For large n and with probability one, none of the numerators has a pole within γ ′ i , hence by the Residue Theorem

X 1,i = b * 1 Π i (Q(ρ i ) -m(ρ i )I) b ′ 1 √ nm(ρ i ) - ω i b * 1 U i V * i Q(ρ i )X * b ′ 1 √ n
a.s. for n large enough.

Due to the bounded character of n -1 b ′ and to Corollary 3, X 1,i is tight for every i. By Lemma 8,

X 1,i ≍ δ i-1,0 b * 1 (Q(ρ 1 ) -m(ρ 1 )I) b ′ 1 √ nm(ρ 1 ) - ω 1 b * 1 U 1 V * 1 Q(ρ 1 )X * b ′ 1 √ n .

The terms X 2,i

We have here

X 2,i = ζ(ρ i ) ıπ √ n s ℓ=1 γi zb * 1 Q(z 2 ) -m(z 2 )I U ℓ ω ℓ b * 1 X Q(z 2 )V ℓ × z m(z 2 )ω 2 ℓ -1 -1 zm(z 2 ) ⊗ I j ℓ z 2 m(z 2 ) m(z 2 )ω 2 ℓ -1 × zm(z 2 )U * ℓ b ′ 1 0 dz = ζ(ρ i ) 2ıπ √ n s ℓ=1 γ ′ i wm(w) m(w)ω 2 ℓ b * 1 (Q(w) -m(w)I) Π ℓ b ′ 1 wm(w) m(w)ω 2 ℓ -1 dw - ζ(ρ i ) 2ıπ √ n s ℓ=1 γ ′ i ω ℓ m(w)b * X Q(w)V ℓ U * ℓ b ′ 1 wm(w) m(w)ω 2 ℓ -1 dw = b * 1 (Q(ρ i ) -m(ρ i )I) Π i b ′ 1 √ nm(ρ i ) - ω i b * 1 X Q(ρ i )V i U * i b ′ 1 √ n w.p. 1 for large n ≍ δ i-1,0 b * 1 (Q(ρ i ) -m(ρ i )I) Π 1 b ′ 1 √ nm(ρ i ) - ω i b * 1 X Q(ρ i )V 1 U * 1 b ′ 1 √ n
by Corollary 3 and Lemma 8.

The terms X 3,i

From ( 10) and ( 20), we have

X 3,i = - ζ(ρ i ) ıπ √ n γi s p,ℓ=1 zm(z 2 )b * 1 U 0 × z m(z 2 )ω 2 p -1 -1 zm(z 2 ) ⊗ I p E(z) z m(z 2 )ω 2 ℓ -1 -1 zm(z 2 ) ⊗ I ℓ (z 2 m(z 2 ) m(z 2 )ω 2 p -1)(z 2 m(z 2 ) m(z 2 )ω 2 ℓ -1) × zm(z 2 )U * b ′ 1 0 dz = - ζ(ρ i ) ıπ √ n γi s p,ℓ=1 ω 2 p z 2 m(z 2 ) m(z 2 ) -zm(z 2 ) × zb * 1 Π p (Q(z 2 ) -m(z 2 )I)Π ℓ b ′ 1 ω ℓ b * 1 Π p X Q(z 2 )V ℓ U * ℓ b ′ 1 ω p b * 1 U p V * p Q(z 2 )X * Π ℓ b ′ 1 zω p ω ℓ b * 1 U p V * p ( Q(z 2 ) -m(z 2 ))V ℓ U * ℓ b ′ 1 (z 2 m(z 2 ) m(z 2 )ω 2 p -1)(z 2 m(z 2 ) m(z 2 )ω 2 ℓ -1) × ω 2 ℓ z 2 m(z 2 ) m(z 2 ) -zm(z 2 ) dz = - ζ(ρ i ) 2ıπ γ ′ i s p,ℓ=1 G p,ℓ (w) (wm(w) m(w)ω 2 p -1)(wm(w) m(w)ω 2 ℓ -1) dw where G pℓ (w) = n -1/2 ω 2 p ω 2 ℓ w 2 m(w) 2 m(w) 2 b * 1 Π p (Q(w) -m(w)I)Π ℓ b ′ 1 -ω p ω 2 ℓ wm(w) 2 m(w) b * 1 U p V * p Q(w)X * Π ℓ b ′ 1 -ω 2 p ω ℓ wm(w) 2 m(w) b * 1 Π p X Q(w)V ℓ U * ℓ b ′ 1 +ω p ω ℓ wm(w) 2 b * 1 U p V * p ( Q(w) -m(w)I)V ℓ U * ℓ b ′ 1 .
For large n and with probability one, the G pℓ (w) are holomorphic functions in a domain enclosing γ ′ i , and G pℓ (w) does not cancel any of the terms of the denominator. The integrals of all terms in the sum such that p = i and ℓ = i are zero. Each of the integrands of the terms p = i, ℓ = i or p = i, ℓ = i has a pole with degree one, and the corresponding integrals are of the form K iℓ G iℓ (ρ i ) or K pi G pi (ρ i ) where the K iℓ and K pi are real constants. By inspecting the expression of G pℓ and by using Corollary 3 and Lemma 8, it can be seen that these terms converge to zero in probability. It remains to study the term p = ℓ = i, which has a degree 2 pole. Recalling that the residue of a meromorphic function f (z) that has a pole with degree 2 at z 0 is lim z→z0 d (zz 0 ) 2 f (z) /dz and letting g ℓ (z) = zm(z) m(z)ω 2 ℓ -1, the integral of this term is The terms q i These are the higher order terms that appear when we expand the right hand side of [START_REF] Hiai | The semicircle law, free random variables and entropy[END_REF]. We shall work here on one of these terms, namely ε = ζ(ρ i ) ıπ √ n γi a * (z, ϕ 1 ) H(z) -1 -H(z) -1 + H(z) -1 E(z)H(z) -1 a ′ ϕ (z, ϕ 1 ) dz and show that ε P -→ 0. The other higher order terms can be handled similarly. Writing z = √ ρ i + R exp(2ıπθ) on the circle γ i , we have

ζ(ρ i ) G ii (ρ i )g ′′ i (ρ i ) g ′ i (ρ i ) 3 - G ′ ii (ρ i ) g ′ i (ρ i
|ε| ≤ K √ n 1 0 H(z) -1 -H(z) -1 + H(z) -1 E(z)H(z) -1 dθ
where K is a constant whose value can change from line to line, but which remains independent from n. Let φ be a function from [0, 1] to a normed vector space. If φ is twice differentiable on (0, 1), then it is known that φ(1)φ(0)φ ′ (0) ≤ sup t∈(0,1) 0.5 φ ′′ (t) .

Setting φ(t) = (H + tE) -1 and recalling that Ĥ = H + E, we have φ(1) = Ĥ, φ(0) = H and φ ′′ (t) = (H + tE) -1 E(H + tE) -1 E(H + tE) -1 , hence H(z) -1 -H(z) -1 + H(z) -1 E(z)H(z) -1 ≤ K E(z) 2 for z ∈ γ i . Write Q -mI = (Q -αI) + (αm)I and Q -mI = ( Q -αI) + (αm)I, and decompose E as defined in [START_REF] Johnstone | On the distribution of the largest eigenvalue in principal components analysis[END_REF] as E = E 1 + E 2 where Observe that covariance matrix of ηn conditional to Γ n converges almost surely to R. Moreover, thanks to A4, it is easy to see that the Lyapunov condition ----→ n→∞ 0 is satisfied for any a > 0, hence ηn L -→ CN (0, R) which completes the proof of Proposition 2.

E 1 (z) = zU * (Q(z 2 ) -α(z 2 )I N )U U * X Q(z 2 )V Ω ΩV * Q(z 2 )X * U zΩV * ( Q(z 2 ) -α(z 2 )I n )V Ω ,

Figure 1 :

 1 Figure 1: The contour γ i w.r.t. the support of the limit singular value distribution of Xn and the other √ ρ ℓ .

  and b n (ϕ) = N -1/2 exp(-ıDℓϕ) N -1 ℓ=0 with domain ϕ ∈ [0, π/D]. When the ϕ k are different, one can check that B * n B n → I r as n → ∞. In most practical cases of interest, S * n S n → O 2 where O is given by Equation (2). In these conditions, due to B * n B n → I r , the diagonal elements of O are the limits of the singular values of P n and Assumption A5 holds true. In the area of signal processing, the positive real numbers ω 2 i are called the Signal to Noise Ratios (SNR) associated with the r sources. Assumption A5 becomes: Assumption A6. Matrices P n of dimension N × n are deterministic and are written:

  and the ϕ k are all different. Matrix S n of dimensions n × r satisfies: √ n(S * n S n -O 2 ) = O(1) as n → ∞, where O is defined in Assumption A5, and O is the classical Landau notation.

s

  i=1 b(ϕ) * Π i b(ϕ). Given ϕ, the results of the previous section (Theorems 1 and 2 with b 1 = b 2 = b(ϕ)) show us that:

Theorem 3 .

 3 Let Assumptions A1-A6 hold true. Then for all k = 1, • • • , r, there exists a local maximum φk,n of χn (ϕ) such that n( φk,nϕ k ) a.s.

Proposition 1 .

 1 In the setting of Theorem 3, max ϕ∈[0,π/D] | χn (ϕ)χ n (ϕ)| a.s.

Figure 2 :

 2 Figure 2: Spike MUSIC algorithm, Variance vs N .

Figure 3 :

 3 Figure 3: Spike MUSIC algorithm, Variance vs the SNR.

) 2 .

 2 Thanks to Corollary 3 and Lemma 8, ℜ(G ii (ρ i )) P -→ 0. The same can be said about G ′ ii (ρ i ) after a simple modification of Proposition 2 and Corollary 3. In conclusion, ∀i = 1, . . . , s, ℜ(X 3,i ) P -→ 0.

E 2 2 T 2 ,Z 2 T

 2222 (z) = zU * (α(z 2 )m(z 2 ))I N )U 0 0 zΩV * ( α(z 2 )m(z 2 ))I n V Ω . Let Z = [z i,k] N,t i,k=1 and Z = [z i,k ] n,t i,k=1 be N × t and n× t standard Gaussian random matrices chosen such that Z, Z and the N × N matrix Γ of singular values of X are independent. For k = 1, . . . , t/2, letD k = diag(d i,k ) N i=1 = (Γ 2ρ k ) -1 and C k = diag(c i,k ) N i=1 = Γ(Γ 2ρ k ) Z) -1/2 Z * D k -tr D k N Z(Z * Z) -1/2 k,k+t/2 k=1,...,t/2 , √ n (Z * Z) -1/2 Z * C k Z[1; N ]( Z * Z) -1/2 k,k k=1,...,t/where Z[1; N ] is Z truncated to its first N rows. By the Law of Large Numbers, N -1 Z * Z → I t and n -1 Z * Z → I t almost surely. Hence, if we show that the multidimensional random variablesA k,n = N -1/2 Z * (D k -N -1 tr D k )Z and B k,n = N -1/2 Z * C k Z[1; N ] are tight for k = 1, . . . , t/2, and ηn = 1 √ N   Z * D k -tr D k N Z k,k+t/2 k=1,...,t/* C k Z[1; N ] k,k k=1,...,t/converges in law towards CN (0, R), the second result of Proposition 2 is proven. From A3 and A4,ρ k )m(ρ k ) 2 , ρ k ) + ρ k N tr Q(ρ k ) 2 a.s. ----→ n→∞ m(ρ k ) + ρ k m ′ (ρ k ) for all k = 1, . . . ,t/2. Recalling that Z and Z are standard Gaussian, it results that lim sup n E A k,n 2 Γ n and lim sup n E B k,n 2 Γ n are bounded w.p. 1 by a constant. Tightness of the A k,n and B k,n follows. Now we have ηn ,k -N -1 tr D k )z * i,k z i,k+t/2 k=1,...,t/2 , c i,k z * i,k zi,k k=1,...,

Consider any element of E 1 , for instance zu * 1 (Q(z 2 )α(z 2 )I)u 1 . By Lemma 3, √ nE

We now prove that √ n 1 0 E 2 2 dθ P -→ 0. In the space of probability measures on R endowed with the weak convergence metric, in order to prove that a sequence converges weakly to µ, it is enough to prove that from any sequence, we can extract a subsequence along which the weak convergence to µ holds true. We shall show along this principle that √ n

with an accumulation point in that set. By A8, from every sequence, there is subsequence n ℓ such that √ n ℓ (α n ℓ (z 1 )m(z 1 )) → 0 almost surely (recall that the convergence in probability implies the a.s. convergence along a subsequence). By Cantor's diagonal argument, we can extract a subsequence (call it again n ℓ ) such that √ n ℓ (α n ℓ (z k )m(z k )) → 0 almost surely for every k. By the normal family theorem, there is a subsequence along which the function

--→ 0, hence weakly. Necessarily,

dθ converges weakly to zero. Now since the weak convergence to a constant is equivalent to the convergence in probability to the same constant, we obtain the desired result. We have finally shown that:

Final derivations

Write χ′ = χ′ (ϕ 1 ), . . . , χ′ (ϕ r ) . Generalizing the previous argument to all the ϕ k and gathering the results, we obtain

By Lemma 8, matrix

Hence, Proposition 2 can be applied to the r.h.s. of this expression, and n -1/2 χ′ converges in law to

It remains to recall Lemmas 9 and 10 to terminate the proof of Theorem 4.

Appendix A. Proof of Proposition 2

The tightness of ξ n follows from Lemmas 3 and 4 with p = 2 and from the application of Chebyshev's inequality.

Appendix B. Sketch of the proof of Proposition 3.

For k = 1, . . . , r, let ρk,n be the solutions of the equation ω 2 k,n g(ρ) = 1, where we recall that the ω 2 k,n are the diagonal elements of matrix Ω n . Then, by a simple extension to the case r ≥ 1 of the proof of [START_REF] Benaych-Georges | The singular values and vectors of low rank perturbations of large rectangular random matrices[END_REF]Th. 2.15], one can show that the sequences √ n( λk,nρk,n ) are tight. To obtain the result, we show that

. Since the non zero eigenvalues of P P * coincide with those of B * B S * S, it will be enough to prove that

, and the proposition is shown.

Observing that

and using the fact that

and replacing in the above convergences, the stated properties of B ⊥ become straightforward. We now show the last convergence. Assume without generality loss that i = 1 and recall that S * S → O 2 . Consider the isometry matrices W = B(B * B) -1/2 and Z = S(S * S) -1/2 , and let A = (B * B) 1/2 (S * S) 1/2 , resulting in P = W AZ * . Notice that the singular values of A coincide with those of P apart from the zeros. Let π 1 be the orthogonal projection matrix on the eigenspace of AA * associated with the eigenvalues ω 2 1,n , . . . , ω 2 j1,n . With these notations, Π 1 = W π 1 W * and Π B1 = B 1 (B * 1 B 1 ) -1 B * 1 . We have A → O, hence π 1 → I j1 0 0 0 . Since B * B → I, for any vector x such that x = 1, we have x * Π 1 xx * B 1 B * 1 x → 0, and x * Π B1 xx * B 1 B * 1 x → 0. Therefore, x * (Π 1 -Π B1 )x → 0, which proves the last result.


Jean-Louis Dessalles
email: dessalles@enst.fr

Coincidences and the Encounter Problem: A Formal Account

Keywords: coincidence, complexity, probability, unexpectedness, surprise

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Coincidences

Suicides are banal events: About thirty people commit suicide every day in a country like France. Yet, a French national newspaper, Le Figaro, reported two anonymous suicides in its March 20, 2004 edition, insisting on their similarity: Two late middle aged women who did not know each other walked in elegant dress into the sea and drowned, almost simultaneously early in the morning, just a few kilometers away from one another. The coincidence was so strange that the news was subsequently analyzed on a national radio.

The famous parallel between Abraham Lincoln and John F. Kennedy"s fates leaves no one indifferent, even if one knows that the coincidence should not be regarded as unlikely (Kern & Brow, 2001). Their election to Congress and then as president of the United States, the births of their successors, the births of their assassins occurred on the same years, one century apart. Both successors were named Johnson. Both assassins were themselves assassinated before being tried.

Two Parisian colleagues running into each other in a small village close to Coban, Guatemala, perceive the coincidence as incredible and urge to tell the event to their friends.

Studying why and how human beings are fascinated by coincidences constitutes an important chapter of cognitive science. Coincidence avoidance has definite implications for decision making, especially in science and in court of law. Moreover, people can accurately assess the strength of coincidences [START_REF] Griffiths | Randomness and coincidences: Reconciling intuition and probability theory[END_REF][START_REF] Griffiths | Probability, algorithmic complexity, and subjective randomness[END_REF], which means that they are able to capture complex relations between events.

The human sensitivity to coincidences is an embarrassment for most current models of cognition. Some authors consider it as mere marginal malfunction of an otherwise functional general ability to assess the likelihood of events. The malfunction would be due to representativeness bias [START_REF] Kahneman | Subjective probability: A judgement of representativeness[END_REF], to erroneous prior knowledge [START_REF] Bar-Hillel | The base-rate fallacy in probability judgments[END_REF] or to failure to consider proper alternatives [START_REF] Diaconis | Methods for studying coincidences[END_REF][START_REF] Falk | Judgment of coincidences: Mine versus yours[END_REF]Tversky & Kohler, 1994). Other authors see in the perception of coincidences a fundamental device for concept learning and theory formation [START_REF] Griffiths | Probability, algorithmic complexity, and subjective randomness[END_REF]. The aim of the present paper is not to settle the issue, although our model clearly depicts the sensitivity to coincidences as a genuine competence rather than as the result of a malfunction. Our contribution, which builds on recent studies on cognitive complexity, is limited to showing that the perception of coincidences obeys definite, formal laws. This mere fact, if correct, may have some implications for our understanding of human cognition, especially by shedding new light on the notion of subjective probability.

Though coincidences are systematically experienced as improbable by subjects, their relation to probability is notoriously unclear: Among events of same probability, some may appear coincidental and others not [START_REF] Griffiths | Probability, algorithmic complexity, and subjective randomness[END_REF]. For instance, children"s attention is grabbed when the family car reaches 66666 km on the clock, but they do not care when they read 67426 km. People are stunned when unexpectedly meeting a friend in a remote place, although they are fully unable to quantify the probability of the event.

Recent accounts of the human ability to assess coincidences split into two opposite directions. Some authors would consider that the basic ingredient of coincidences is the probability of the event [START_REF] Falk | Judgment of coincidences: Mine versus yours[END_REF] or of its putative causes [START_REF] Griffiths | Probability, algorithmic complexity, and subjective randomness[END_REF], even if they acknowledge the role that descriptive complexity may play [START_REF] Griffiths | Probability, algorithmic complexity, and subjective randomness[END_REF]. Some other studies have signaled the crucial role of descriptive complexity in cognitive processes [START_REF] Chater | The search for simplicity: A fundamental cognitive principle?[END_REF][START_REF] Chater | Simplicity: a unifying principle in cognitive science?[END_REF] and more particularly in the perception of coincidences [START_REF] Feldman | How surprising is a simple pattern? Quantifying 'Eureka![END_REF]. The former group view "probability as primary, and the relationship between randomness and complexity as a secondary consequence of a statistical inference" [START_REF] Griffiths | Probability, algorithmic complexity, and subjective randomness[END_REF]. The present account, in line with the second group of studies, puts descriptive complexity at the core of the cognitive competence underlying the perception of coincidences.

In what follows, we first give a list of problems that cognitive models of coincidences must address. We then define the notion of unexpectedness as complexity drop, before showing that this notion nicely accounts for each of the listed problems, including the "encounter problem". We finally consider the compatibility of the model with traditional probabilistic accounts.

Proceedings of the 30th

What Is To Be Explained

There are required specifications that a cognitive model of coincidence must meet. Let us phrase them using three examples, the double suicide by drowning, the Lincoln-Kennedy parallel and the fortuitous encounter.

-Analogy: Each common feature between Lincoln and Kennedy"s lives adds to the coincidence. In the case of the two drowned women, interest would have been even higher if they had had the same first name. If they had been of different ages, interest would have been lower. The repeated 100-year interval in the two-president coincidence is an analogy within the analogy.

-Association: Non-analogue features, such as the fact that Kennedy was shot in a car named Lincoln, still add to the coincidence value.

-Prominence: Kennedy and Lincoln are among the foremost US presidents. The coincidence would be less interesting if it involved obscure US presidents, or prominent Uruguayan presidents (for non-Uruguayan citizens).

-Round numbers: The Lincoln-Kennedy coincidence would be slightly less interesting if it involved an 87-year interval.

-Closeness: The short distance between the two suicides is a crucial aspect of the coincidence. In the report, proximity in time (early in the same morning), in space (a few kilometers apart) and in social hierarchy (two upperclass women) was highlighted. Conversely, interest in the coincidence would drop if the distance in any of these dimensions was increased.

-Remoteness: The remoteness of the place is a crucial ingredient of fortuitous encounters. While there is no coincidence in encountering a colleague two blocks away from workplace, running into a colleague in an obscure village 9000 km away from home is thrilling.

-Egocentricity: People are much more sensitive to coincidences (e.g. having same birth dates) when they are involved [START_REF] Falk | Judgment of coincidences: Mine versus yours[END_REF]. The double suicide is much more intriguing for people who live close to the place where the event took place.

-Causality: Surprise vanishes when the coincidental events find a common easy causal explanation, for instance if the two suicidal women knew each other and had made a common decision. Conversely, interest is preserved when the available explanatory hypotheses are highly unlikely [START_REF] Griffiths | Probability, algorithmic complexity, and subjective randomness[END_REF] as the fact, mentioned on the radio, that the two drowned women may have influenced each other through telepathy.

All these parameters have systematic effects on the perception of coincidences. This is an indication that some genuine cognitive competence is at work and that the surprise generated by coincidences is not the mere sideeffect of a general sensitivity to the presence of statistical exceptions. Probabilistic or statistical accounts would fail to account for most of the above properties, though they may suggest local laws in the case of closeness and egocentricity (using Poisson distributions), of remoteness (using a diffusion model) and of explanation (using Bayesian networks: [START_REF] Griffiths | Probability, algorithmic complexity, and subjective randomness[END_REF]. A unified account is proposed now.

Unexpectedness and Descriptive Complexity

The core property of coincidences is that they are unexpected. Unexpectedness has been given various definitions. An obvious one corresponds to Shannon"s definition of information U = log 2 1/p i , where p i is the a priori probability of the event [START_REF] Shannon | A mathematical theory of communication[END_REF]. Another is [START_REF] Weaver | Probability, rarity, interest, and surprise[END_REF]; it accounts for the fact that improbable events are only interesting if they are a contrast to probable alternatives. Various authors have noticed the close relation between description complexity, also known as Kolmogorov complexity, and probability [START_REF] Solomonoff | Complexity-based induction systems: Comparisons and convergence theorems[END_REF][START_REF] Solomonoff | The discovery of algorithmic probability[END_REF][START_REF] Chater | The search for simplicity: A fundamental cognitive principle?[END_REF][START_REF] Feldman | How surprising is a simple pattern? Quantifying 'Eureka![END_REF]. The problem with Solomonoff"s definition of probability as p = 2 -C , where C is the complexity of the event, is that simpler situations are assigned higher probability, as they are more likely to be generated. In coincidences, the reverse happens: Events are perceived as unlikely when they are "too" simple, for instance simpler than what the "null hypothesis" predicts [START_REF] Feldman | How surprising is a simple pattern? Quantifying 'Eureka![END_REF]. We propose a similar idea, captured in the following definition of unexpectedness.

U =  p j 2 /p i
U(D) = C w (D) -C(D) (1)
As observed by [START_REF] Tversky | Support theory: A nonextensional representation of subjective probability[END_REF], "probability judgments are attached not to events but to descriptions of events". The unexpectedness of an event described through D is the difference between its W-complexity, or complexity "in the world" (as it is understood by the subject) and its observational complexity or O-complexity. Both C w and C are cognitive: They correspond to minimal cognitive descriptions available to the individual [START_REF] Chater | The search for simplicity: A fundamental cognitive principle?[END_REF]. They express the length of minimal "programs" given to two different "machines" that may be dubbed W-machine and Omachine. The W-machine functions according to what the subject sees as the normal behavior of the world (the Wmachine, therefore, depends on the subject"s knowledge). The O-machine is unconstrained and may use any observational ability available to the subject. C w and C are the minimal amounts of instructions, in bits, that must be given as input to these machines to generate the event described by D. These definitions are consistent with the original definition of Kolmogorov complexity, except that the ideal Turing machine is replaced by two versions of the human cognitive analysis capabilities.

Consider the coincidence of seeing 66666 on the clock when driving. The W-machine generates this pattern by copying an uninstantiated digit and then by performing five independent instantiations. The W-complexity thus amounts to C w = C copy + 5log 2 10 (as the complexity of designating one number chosen among n is log 2 n). The O-machine generates the same pattern by copying an instantiated digit: C = log 2 10 + C copy . We thus get: U = 4log 2 10 = 13.3 bit.

According to definition (1), merely mentioning "John F. Kennedy" creates a negative unexpectedness. The world (as the subject knows it) is supposed to be available to the Wmachine; therefore, the W-complexity of "John F. Kennedy" is zero, as he is believed to have existed. The O-machine requires a non-zero input to determine "John F. Kennedy". A minimal cognitive description may use a list of famous characters ranked by celebrity. The O-complexity would be the logarithm of Kennedy"s rank in that list. Alternatively (especially for people outside the US), a minimal description may go through the mention of the notion of US presidency, and then through the determination of John Kennedy among US presidents. O-complexity here is related to cognitive availability [START_REF] Tversky | Availability: A heuristic for judging frequency and probability[END_REF] and may be independently assessed by various means including reaction times.

The mere mention of a feature like Kennedy"s age by the time he was killed requires no work from the W-machine, as everyone has an age; but its instantiation to a definite value such as 46 involves some complexity. In the worst case, the W-machine generates that age by copying it from its input. However, the W-machine may determine the age by choosing among likely age values for a US president, which leads to a lower complexity.

Unexpectedness and Coincidences

Let us show now how the notion of unexpectedness can account for the eight specifications previously listed. We need the notion of computation sequence, noted with operator *. The sequence D 1 *D 2 means that the W-machine needs to generate D 1 before generating D 2 :

C w (D 1 *D 2 ) = C w (D 1 ) + C w (D 2 |D 1 ) (2)
In a coincidence like the double suicide, the two events e 1 and e 2 are independent for the W-machine: C w (e 2 |e 1 ) = C w (e 2 ). We get:

U(e 1 *e 2 ) > C w (e 1 ) + C w (e 2 ) -C(e 1 ) -C(e 2 |e 1 )

(3)

The inequality comes from the fact that the computation sequence may be suboptimal for the O-machine. We can now review the eight specifications.

Analogy: This formula correctly predicts the importance of a close analogy between the two events, as best analogies make C(e 1 ) + C(e 2 |e 1 ) minimum [START_REF] Cornuéjols | Analogie, principe d'économie et complexité algorithmique[END_REF]. Each new common element, such as the birth date of the assassins in the Lincoln-Kennedy parallel, is needed twice for the Wmachine, but only once for the O-machine, as its contribution to C(e 2 |e 1 ) is zero. Common elements thus add to the unexpectedness of the situation. An additional prediction is that more complex common elements will be more surprising. Interest would indeed grow if the two drowned women wore a tattoo, but even more so if both had a red fivecentimeter long tattoo on the right shoulder.

Association: Inequation (3) predicts that any element of e 1 that the O-machine can reuse to generate e 2 will add to the surprise. Hence the mention that Kennedy was killed in car named Lincoln. The W-machine must generate the make of the car and requires several bits which add to C w (e 2 ) to distinguish it from other makes; this generation is easier for the O-machine when e 1 is given as input, as the name "Lincoln" is available for free.

Prominence: Why is it important that Abraham Lincoln and John F. Kennedy be famous? Formula ( 3) provides an answer. These two persons exist and are unique in the subject"s world; the W-machine has thus no work to do to generate them. For the O-machine, however, their minimal description may go through determining their social role, US president, and then find them in a ranked list of USpresidents. Hence the importance for the coincidence to involve two prominent figures, as their complexity, which amounts to the logarithm of their rank in a list ordered by celebrity, adds to C(e 1 ) and to C(e 2 |e 1 ). Similarly, a social role such as president of Uruguay, if more complex for the subject, makes the coincidence less surprising, as it adds significantly to C(e 1 ).

Round numbers:

The presence of the negative term --C(e 2 |e 1 ) in (3) explains why the Lincoln-Kennedy story is more interesting as it is than if the repeated time interval had been of 87 years instead of 100. The point is that the cognitive complexity of the program that transforms 1846 into 1946 or 1860 into 1960 is simpler than the program that would transform 1846 into 1933 and 1860 into 1947 (the first program affects only one digit). Alternatively, one can observe that 100, as a number, is simpler than 87. The complexity of an integer n is smaller than log 2 n. In the case of round numbers, it is significantly smaller. One million may be concisely defined as 10 6 , or as 1 followed by six copies of 0.

Closeness: The role of closeness in time and space, as in the example of the double suicide, can only be understood if the notion of complexity is extended to continuous quantities. Though Kolmogorov complexity is defined only for discrete structures, the complexity of a place is naturally defined as the most concise set of directions that allows finding it. Locating a surface a 2 on a two-dimensional area S requires no more than log 2 (S/a 2 ) bits. When trying to locate such an area B from a place A, one may use a relative code, in which locations are ranked according to their distance from A. In such a system, the complexity of B amounts to C(B|A) = log 2 (d 2 /a 2 ), where d is the distance from A to B. This complexity varies as 2log 2 d. In expression (3), the W-machine must compute the location of each event independently. The O-machine computes the location of one event, and then may use a relative coding. Hence the crucial importance of the two events being close to each other, as C(e 2 |e 1 ) involves a term 2log 2 d. The same prediction holds for the time dimension: Surprisingness decreases as log 2 t where t is the time interval between the two events. Proximity effects do not require the presence of two events. On July 22, 2003, a minor blaze on the upper floor of the Eiffel Tower was reported in French national news media. This phenomenon is explained by formula (1). The W-machine must generate the location of the blaze. If fires occur with a spatial density D, then localizing one of them demands log 2 1/(a 2 D) bits, as 1/D represents the area of occurrence of one such event on average. The O-machine has first to specify the location of the Eiffel Tower, but this requires minimum complexity as the place is prominent (it is the top most popular monument in France). Then the Omachine gets the location of the blaze for free. The coincidence effect is predicted to decrease as the logarithm of the spatial density of the event and proportionally to the complexity of the monument. No wonder that events happening on prominent places are preferentially reported in the news [START_REF] Warren | Modern news reporting[END_REF].

Remoteness: Fortuitous encounters seem to be an exception to the rule of closeness, as the interest of the coincidence grows this time with the remoteness of the place! A proper application of (3), however, restores the prediction.

First, let us observe that the encounter problem is spectacular, as it provides the best evidence that the human mind is sensitive to description complexity. In this kind of coincidence, interest grows with the complexity of the place and with the simplicity of the encountered person. The complexity of the place l is the relevant factor, not the distance: a big distant airport may be less complex than the backyard of an obscure building of a lost suburb a few kilometers away. The simplicity of the encountered person P is the relevant factor, not her closeness. Running into a celebrity may be as unexpected as running into a close colleague. These phenomenon is correctly predicted by the fact that unexpectedness varies as C(l) -C(P), as we show now.

Let us compute 1 the unexpectedness of the sequence ego*P*l(ego)*l(P). Here, l(ego) and l(P) designate the presence of self and of P at location l. For the W-machine, C w (P) = 0 as P is supposed to exist. In the "world", P"s and ego's presence at l are independent: C w (l(P)|l(ego)) = C w (l(P)). If ego and P play symmetrical roles, the Wmachine requires C w (ego*P*l(ego)*l(P)) = 2 C w (l(ego)) to generate the encounter situation. The term C w (l(ego)) corresponds to the minimum size of a set of directions to reach l and amounts to C(l) in most cases (except if l is materially difficult to reach). On the other hand, for the Omachine, C(l(P)|l(ego)) is zero. The O-machine demands C(P) to determine P and C(l(ego)) to bring ego to l. Again, we suppose that C(l(ego)) = C(l). We get, as announced:

U(ego*P*l(ego)*l(P)) > C(l) -C(P) (4) 1 A recursive application of formula (2) gives C w (D 1 *D 2 *D 3 ) = C w (D 1 ) + C w (D 2 |D 1 ) + C w (D 3 |D 1 &D 2 ).
Irrelevant elements in conditional complexity expressions are omitted for the sake of clarity.

An alternative computation goes over the sequence ego*l(ego)*l(P)*P. This time, P is first determined by her position l(P) = l(ego). Now C w (l(P)|l(ego)) is zero, but not C w (P|l(P)). To instantiate P, the W-machine has to distinguish among all individuals that may happen to be in l. One procedure to do so consists in checking local people first, by delimiting an area of radius R around l and considering all people living within it. Then R is increased until the actual P is reached. In this computation, l and P"s home play symmetrical roles, so that C w (P|l(P)) = C(l) + c (again, l is supposed to be as complex for P as for ego). The constant c depends on the spatial density of people. The resulting unexpectedness C(l) + c -C(P) is similar to what we obtained in (4). Note that this second computation still holds when the encounter occurs in the vicinity of ego"s home. In this case, C w (l(ego)) and C(l(ego)) are negligible, but C w (l(P)) is close to C(h(P)) (the complexity of P"s home) and the unexpectedness amounts to C(h(P)) + c -C(P). It is indeed quite a coincidence to meet a celebrity in front of one"s home.

Egocentricity: In the case of fortuitous encounters as for happening to have the same birthday, the coincidence is less impressive if it involves another person Q instead of ego [START_REF] Falk | Judgment of coincidences: Mine versus yours[END_REF]. This effect is well predicted by formula (1): The burden of determining Q adds to the O-complexity (but not to the W-complexity) and unexpectedness is diminished by the amount C(Q). This accounts for the fact that firsthand stories are always preferred [START_REF] Coates | Men talk[END_REF], since they are systematically more unexpected. To show this, we can derive the following inequation from (2):

U(D 1 *D 2 ) > U(D 1 ) + U(D 2 |D 1 ) (5)
A recursive application of (5) gives: U(Q*e 1 *e 2 ) = -C(Q) + U(e 1 |Q) + U(e 2 |Q&e 1 ). We may consider that U(e 2 |Q&e 1 ) = U(e 2 |e 1 ), as the most concise description of e 2 for the O-machine only uses e 1 , whereas the W-machine uses neither e 1 nor Q.

U(Q*e 1 *e 2 ) > -C(Q) + U(e 1 |Q) + U(e 2 |e 1 ) (6)
If Q is replaced by ego, we get:

U(ego*e 1 *e 2 ) > U(e 1 |ego) + U(e 2 |e 1 ) (7)
This explains why coincidences involving ego are more intriguing, as unexpectedness is larger in (7) than in (6). Importantly, this "egocentric touch" [START_REF] Falk | Judgment of coincidences: Mine versus yours[END_REF]) is obtained without any extensional reasoning. The present account considers neither alternatives nor "the size of the set to which one implicitly relates" [START_REF] Falk | Judgment of coincidences: Mine versus yours[END_REF]. Equation ( 7) also explains why a coincidence like the double suicide is more surprising to local people. The value of U(e 1 |ego) may be significant, as it would be for a single suicide happening in the vicinity, whereas it may be negative for people living farther away.

Causality: Griffith and Tennenbaum (2007) developed a probabilistic (Bayesian) account of the reason why coinci-dences are all the more surprising as they reveal the possibility of an alternative hidden causal structure that is itself highly unlikely. If the less unlikely causal explanation for the double suicide is that the two women influenced each other through telepathy, the feeling of coincidence remains high. If, however, one can believe that they met and decided to commit suicide simultaneously, the coincidence fades away. Our model accounts for the phenomenon, without relying on the notion of probability. Suppose that some causal explanation H accounts for both e 1 and e 2 . This means that C w (e 1 |H) and C w (e 2 |H) are negligible. If e 1 and e 2 are explained by H, then:

C w (e 1 *e 2 ) < C w (H*e 1 *e 2 )  C w (H) (8)
The W-complexity C w (H) of a causal explanation H is the amount of information required for the "world" W to generate H. It measures the credibility of the theory [START_REF] Chaitin | On the intelligibility of the universe and the notions of simplicity, complexity and irreducibility[END_REF]. If H is easy to believe, U(e 1 *e 2 ) does not take significant values and there is no reason to be surprised. Conversely, if H is hard to accept, as for the telepathy hypothesis, 2 then C w (H) takes high, prohibitive, values. The sequence H*e 1 *e 2 no longer provides the lowest value for C w (e 1 *e 2 ) and the hypothesis should be rejected.

Discussion: What the model predicts

The perception of coincidences is a definite ability, like the ability to decide whether a sentence in one"s mother language is grammatical or not. Individuals know when a state of affairs makes a good coincidence, and they know if some variation of a given parameter makes a difference. This cognitive ability has to be accounted for, and this is what is attempted here.

The model proposed in this paper meets all the specifications concerning the perception of coincidences that have been listed above, by explaining the systematic role of analogy, of association, of prominence, of round numbers, of closeness, of remoteness, of egocentricity and of causality. Probabilistic models at best predict certain of these features, while the others remain mysterious. The model derived from formula (1) succeeds in predicting them all. Moreover, it does it in a quantitative way. For instance, the effect of spatial closeness is expected to obey a logarithmic law 2log 2 d, and time will affect coincidence logarithmically as well. In the case of fortuitous encounters, the complexity (= shortest description) of the place is predicted to be the determining factor, not distance. These various dependencies are all testable and thus make the model falsifiable.

A classical critique addressed to complexity-based approaches is that Kolmogorov complexity is proven to be uncomputable [START_REF] Li | An introduction to Kolmogorov complexity and its applications[END_REF]. Models based on Kolmogorov complexity are thus sometimes believed to 2 One way to estimate the W-complexity of the telepathy hypothesis is to imagine the complexity of the conditions that led to an effect in this situation and to the absence of effect in other situations. lack any real predictive power. This led authors [START_REF] Simon | Complexity and the representation of patterned sequences of symbols[END_REF][START_REF] Feldman | How surprising is a simple pattern? Quantifying 'Eureka![END_REF] to consider alternative measures of complexity, such as Boolean complexity or algebraic complexity, that are computable. Indubitably, human minds are not ideal computing device that would be free to run any kind of program. Minds are bound to process signals and representations in certain particular ways. However, they are sensitive to the complexity of their own processes, as shown for instance by the existence of strong perceptive biases toward simplicity [START_REF] Chater | The search for simplicity: A fundamental cognitive principle?[END_REF][START_REF] Chater | Simplicity: a unifying principle in cognitive science?[END_REF]. The law encapsulated in formula (1) suggests that this preference for simplicity operates at higher levels of abstraction as well, and across various modalities. Unexpectedness conflates all available sources of complexity (perceptual, structural, spatio-temporal, conceptual) into one single measure that constitutes the judgment of coincidence. This is why the analogy with Kolmogorov complexity is justified, as the only absolute criterion is the size of the shortest available description.

One can legitimately worry about the existence of two types of models that address the issue of coincidence perception. If the complexity-based model proposed here is correct, why would probabilistic or Bayesian accounts have partial predictive power? And why are coincidences systematically accompanied by a subjective feeling of low probability [START_REF] Griffiths | Probability, algorithmic complexity, and subjective randomness[END_REF]? The relation between descriptive complexity and probability has always been noticed [START_REF] Solomonoff | The discovery of algorithmic probability[END_REF], but its usual formulation as p = 2 -C(D) is unsatisfactory for our purpose. It would mean that the probability of structures is a decreasing function of their complexity, but coincidences are often striking just because they are simple. To account for the subjective perception of probability in case of lottery results, we introduced an alternative way of deriving probability from complexity [START_REF] Dessalles | A structural model of intuitive probability[END_REF], by defining cognitive probability as:

p = 2 -U (9)
Cognitive probability is defined only for unexpected situations, which means that U > 0. This definition reverses Shannon"s definition, where unexpectedness plays the role of information. It suggests that unexpectedness, as defined by (1), is a more fundamental cognitive notion from which cognitive probability is derived. Formula (9) offers a nonextensional definition of cognitive probability. 3 It explains why individuals do not find that all actual states of the world have zero probability, despite the fact that each is unique. It also explains why certain features are regarded as relevant while others (like the horizontal orientation of dice) are spontaneously discarded. In the case of coincidences, the sensation of low probability appears to result, not from the evaluation of a set of alternatives, but from the perception of www.simplicitytheory.org a complexity drop. We do not wonder what the alternatives are when we hear that two sixty-year old women chose to walk with their most beautiful dress into the sea early in the same morning (should they have worn pants, or chosen late afternoon?).

Conclusion

The research initiated in the recent years on the cognitive role of descriptive complexity has already produced valuable results. The model presented in this paper is meant as a contribution to this enterprise. It should be extended in two directions. First, it is important to get a deeper understanding of the processes through which human subjects assess descriptive complexity and to see how they are compatible with the definitions adopted in the present model. Second, it will be interesting to confront the various predictions of the model with actual reactions of subjects to whom various versions of coincidences are presented, as we did for probability estimates [START_REF] Dessalles | A structural model of intuitive probability[END_REF]). Parameters can be manipulated according to the model to affect surprise. Such studies may prove delicate, however, as surprise cannot be easily elicited successively in the same subjects.

One important conclusion strongly suggested by the model is that the human mind is able to perform non-trivial formal computations. The sensitivity to complexity drop seems to be a general law, which applies across modalities and at all levels of abstraction. This means that our mind is able, in some way, to assess the complexity of its own information processing. Such a possibility opens many new perspectives.

  Annual Conference of the Cognitive Science Society (Cogsci 2008), 2134-2139

Checking whether the probabilities of all elementary alternatives sum to 1 would be quite artificial in most cases, as situations are rarely perceived as exclusive. 66666 km or 67426 km on the clock are respectively read as "one repeated digit" and "any amount" and are assigned probability 10 -4 and 1.