Nelly Litvak

Philippe Robert
email: philippe.robert@inria.fr

A SCALING ANALYSIS OF A CAT AND MOUSE MARKOV CHAIN

Keywords: Cat and Mouse Markov Chains, Scaling of Null Recurrent Markov Chains, Pagerank Algorithms, Nelly

Motivated by an original on-line page-ranking algorithm, starting from an arbitrary Markov chain (Cn) on a discrete state space S, a Markov chain (Cn, Mn) on the product space S 2 , the cat and mouse Markov chain, is constructed. The first coordinate of this Markov chain behaves like the original Markov chain and the second component changes only when both coordinates are equal. The asymptotic properties of this Markov chain are investigated. A representation of its invariant measure is in particular obtained. When the state space is infinite it is shown that this Markov chain is in fact null recurrent if the initial Markov chain (Cn) is positive recurrent and reversible. In this context, the scaling properties of the location of the second component, the mouse, are investigated in various situations: simple random walks in Z and Z 2 , reflected simple random walk in N and also in a continuous time setting. For several of these processes, a time scaling with rapid growth gives an interesting asymptotic behavior related to limit results for occupation times and rare events of Markov processes. Contents 1. Introduction 1 2. The Cat and Mouse Markov Chain 4 3. Random Walks in Z and Z 2 9 4. The Reflected Random Walk 15 5. Continuous Time Markov Chains 24 References 27

Introduction

The PageRank algorithm of Google, as designed by Brin and Page [START_REF] Brin | The anatomy of a largescale hypertextual web search engine[END_REF] in 1998, describes the web as an oriented graph S whose nodes are the web pages and the html links between these web pages, the links of the graph. In this representation, the importance of a page is defined as its weight for the stationary distribution of the associated random walk on the graph. Several off-line algorithms can be used to estimate this equilibrium distribution on such a huge state space, the 'world largest Markov chain', they basically use numerical procedures (matrix-vector multiplications) and refreshing mechanisms to switch from a set of nodes to another set of nodes. See Berkhin [START_REF] Berkhin | A survey on pagerank computing[END_REF] for example.

Although the off-line linear-algebraic techniques are currently dominating in PageRank computations, several on-line algorithms that update the ranking scores while exploring the graph have been proposed to solve some of the shortcomings of the off-line algorithms. The starting point of this paper is an algorithm designed by Abiteboul et al. [START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF] to compute the stationary distribution of a finite recurrent Markov chain. This algorithm has the advantage that it uses less computing and memory resources, in particular it does not require storing the link matrix as the off-line algorithms. Furthermore, the accuracy of its estimates is increasing with time.

After the nth round of this algorithm, to each node x is associated a continuous variable W n (x), the "cash" at x. The initial state (W 0 (x), x ∈ S) for the cash is some probability distribution on S. At each step of the algorithm, the page with the largest cash variable is visited. When a page x is visited its cash is distributed among its neighbors in the following way: a neighbor y receives p(x, y)W n (x) if P = (p(u, v)) is the transition matrix of the Markov chain. In that manner, the total amount of cash is invariant, i.e. (W n (x)) is a probability distribution on S for any n ≥ 0. In the case of the web, p(x, y) = 1/ d x , if d x is the number of outgoing links from x. At the same time a variable h n (x) associated to x is increased by W n (x). The estimate of π(x), the stationary distribution at x, is given by [START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF] h n (x)

y∈S h n (y)
.

It is shown in Abiteboul et al. [START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF] that this quantity indeed converges to π(x) as n gets large.

A Markovian variant. Another possible strategy which chooses nodes at random to update the values of the cash variables is also considered in Abiteboul et al. [START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF]. Instead of considering the node with largest value of the cash, one considers a random walker who updates the values of the cash at the nodes of its random path in the graph. Note that both strategies have the advantage of simplifying the data structures necessary to manage the algorithm since there is no need of reordering the cash variables. It is shown in Litvak and Robert [START_REF] Litvak | Analysis of an on-line algorithm for solving large Markov chains[END_REF] that the corresponding quantity (1) also converges to the stationary distribution. The vector of cash at the nth visit is denoted by (V n (x), x ∈ S).

Since the total mass of cash is left invariant by these algorithms, it is assumed it is constant and equal to 1. The two sequences (V n (x), x ∈ S) and (W n (x), x ∈ S) are therefore Markov chains with values on probability distributions on the state space S. Outside the convergence of the quantity (1) to the stationary distribution, little is known on the asymptotic behavior of these Markov chain with continuous state space.

Cat and Mouse Markov chain. It is shown, Theorem 1, that the distribution of the vector (V n (x), x ∈ S) can be expressed in terms of the conditional distributions of a Markov chain (C n , M n ) on the discrete state space S 2 . The sequence (C n ), representing the location of the cat, is a Markov chain with transition matrix P = (p(x, y)). The second coordinate, for the location of the mouse, (M n ) has the following dynamic:

-If M n = C n , then M n+1 = M n ,
-If M n = C n , then, conditionally on M n , the random variable M n+1 has distribution (p(M n , y), y ∈ S) and is independent of C n+1 .

This can be summarized as follows: the cat moves according to the transition matrix P = (p(x, y)) and the mouse stays quiet unless the cat is at the same site in which case the mouse also moves independently according to P = (p(x, y)).

The asymptotic properties of this interesting Markov chain are the subject of this paper. Intuitively, it is very likely that the mouse will spend most of the time at nodes which are unlikely for the cat. It is shown that this is indeed the case when the state space is finite and if the Markov chain (C n ) is reversible but not in general.

When the state space is infinite and if the Markov chain (C n ) is reversible, the Markov chain (C n , M n ) is in fact null-recurrent. In this case, this implies that most of the time the mouse is "far away" from the favorite sites of (C n ). A precise description of the asymptotic behavior of the (non-Markovian) sequence (M n ) is done via a scaling in time and space for several classes of simple models. Interestingly, the scalings used are quite diverse as it will be seen. They are either related to asymptotics of rare events of ergodic Markov chains or to limiting results for occupation times of recurrent random walks.

Outline of the Paper. Section 2 analyzes the recurrence properties of the Markov chain (C n , M n ) when the Markov chain (C n ) is recurrent. It is shown that the distribution of the vector (V n (x), x ∈ S) is given by the distribution of the location of the mouse conditionally on the successive positions of the cat. A representation of the invariant measure of (C n , M n ) in terms of the reversed process of (C n ) is given. As a consequence, when the state space is infinite and (C n ) is ergodic and reversible, this measure has an infinite mass implying that (C n , M n ) is null-recurrent.

In Section 3, the cases of the symmetric simple random walks on Z d , with d = 1 and 2, are investigated (the other simple random walks in higher dimensions are transient). Jumps occur at random among the 2 d neighbors. In the one-dimensional case, on the linear time scale t → nt, as n gets large, the location of the mouse is of the order of 4 √ n and the limiting process is a Brownian motion taken at the local time at 0 of another independent Brownian motion. When d = 2, on the linear time scale t → nt, the location of the mouse is of the order of √ log n. In this case there is also a (weak) convergence of rescaled processes to a Brownian motion in R 2 on a time scale which is an independent discontinuous stochastic process with independent and non-homogeneous increments.

For both cases, the main problem is to get a functional renewal theorem associated to an i.i.d. sequence (T n ) of non-negative random variables such that E(T 1 ) = +∞. More precisely, if

N (t) = i≥1 ½ {T1+•••+Ti≤t} ,
one has to find φ(n) such that the sequence of processes (N (nt)/φ(n), t ≥ 0) converges as n goes to infinity. When the tail distribution of T 1 has a polynomial decay, several technical results are available. See Garsia and Lamperti [START_REF] Garsia | A discrete renewal theorem with infinite mean[END_REF] for example. This assumption is nevertheless not valid for the two-dimensional case. In any case, it turns out that the best way (especially for d = 2) to get such results is to formulate the problem in terms of occupation times of Markov processes for which several limit theorems are available. This is the key of the results of this section.

In Section 4 the case of the simple random walk in N with reflection at 0 is analyzed. A jump of size +1 [resp. -1] occurs with probability p [resp. (1 -p)] and the quantity ρ = p/(1 -p) is assumed to be strictly less than 1 so that the Markov chain is ergodic. It is shown that if the location of the mouse is far away from the origin, i.e. M 0 = n with n large, for the exponential time scale t → ρ -n t, the location of the mouse is of the order of n as long as t < W where W is a random variable related to an exponential functional of a Poisson process. See Bertoin and Yor [START_REF] Bertoin | Exponential functionals of Lévy processes[END_REF]. After time t = W it is shown that the rescaled process (M ⌊tρ -n ⌋ /n) oscillates between 0 and above 1/2 on every non-empty time interval.

Section 5 introduces the equivalent of the cat and mouse Markov chain in the context of continuous time Markov chains. As an example, the case of the M/M/∞ queue which can be seen as a discrete Ornstein-Uhlenbeck process is investigated. This stochastic process is known for its strong ergodic behavior: its invariant distribution is sharply concentrated around 0 (more than geometric decay) and also the fact that the time it takes to go to n from 0 is of the same order as the time it takes to go to n from n -1 (the last step is the most difficult). When M 0 = n, contrary to the case of the reflected random walk, there does not seem to exist a time scale for which a non-trivial functional theorem holds for the corresponding rescaled process until the hitting time of 0. Instead, it is possible to describe the asymptotic behavior of the location of the mouse after the pth visit of the cat has a multiplicative representation of the form

nF 1 F 2 • • • F p where (F p ) are i.i.d. random variables on [0, 1].
It should be noted that despite the examples analyzed are specific, they are quite representative of the different situations for the dynamic of the mouse. For null recurrent homogeneous random walks, asymptotic results for the occupation times of Markov processes give the correct time and space scalings for the location of the mouse. When the initial Markov chain is ergodic and the mouse is away from the origin, the time scaling is given by the exponential time scale of the occurrence of rare events. The fact that for all the examples considered, jumps occur on the nearest neighbors, does not change this qualitative behavior. Under more general conditions analogous results should hold. Additionally, this simple setting has the advantage of providing explicit expressions for the constants involved (except for the random walk in Z 2 in fact).

The Cat and Mouse Markov Chain

In this section some properties of the process (V n (x), x ∈ S) are investigated for a general transition matrix P = (p(x, y), x, y ∈ S) on a discrete state space S. Throughout the paper, it is assumed that P is aperiodic, irreducible without loops, i.e. p(x, x) = 0 for all x ∈ S and with an invariant measure π. Note that it is not assumed that π has a finite mass. The sequence (C n ) will denote a Markov chain with transition matrix P = (p(x, y)), it will represent the sequence of nodes which are sequentially updated by the random walker.

The transition matrix of the reversed Markov chain (C * n ) is denoted by

p * (x, y) = π(y) π(x) p(y, x)
and, for y ∈ S, one defines

H * y = inf{n > 0 : C * n = y} and H y = inf{n > 0 : C n = y}.
A Representation of (V n (x), x ∈ S). The set of probability distributions on S is denoted by P S . If V 0 ∈ P S , the total amount of cash initially is 1, then from the description of the algorithm it follows that for x ∈ S and t ≥ 0, the relation

(2) V n+1 (x) = y =x p(y, x)V n (y)½ {Cn=y} + V n (x)½ {Cn =x}
holds. Indeed, if a node y = x is visited then node x receives p(y, x)V n (y) of the cash from the node y. If the node x is visited then it distributes all its cash, and in this case, V n+1 (x) is zero. The process (V n (x), x ∈ S) is a Markov chain with values in P S the set of probability distributions on S. In the following it is shown that this continuous state space Markov chain can be expressed in term of a discrete state space Markov chain. For this purpose, a Markov chain (C n , M n ) on S × S referred to as the "cat and mouse Markov chain" is introduced. Its transition matrix Q = (q(•, •)) is defined as follows, for x, y, z ∈ S, [START_REF] Berkhin | A survey on pagerank computing[END_REF] q[(x, y), (z, y)] = p(x, z), if x = y; q[(y, y), (z, w)] = p(y, z)p(y, w).

The process (C n ) [resp. (M n )] will be defined as the position of the cat [resp. the mouse]. Note that the position (C n ) of the cat is indeed a Markov chain with transition matrix P = (p(•, •)). The position of the mouse (M n ) changes only when the cat is at the same position. In this case, starting from x ∈ S they both move independently according to the stochastic vector (p(x, •)).

Cat and mouse problems are quite standard in game theory, the cat playing the role of the "adversary". See Coppersmith et al. [START_REF] Coppersmith | Random walks on weighted graphs and applications to on-line algorithms[END_REF] and references therein. Here, of course, there is no question on the strategy of the mouse but only to analyze a Markovian description of the way the mouse may avoid, as much as possible, meetings with the cat. The evolution of the mouse (M n ) is analyzed in various settings in the rest of the paper.

Let (F n ) denote the history of the motion of the cat, for n ≥ 0, F n is the σ-field generated by the variables C 0 , C 1 , . . . , C n . The cash process can then be described as follows.

Theorem 1. If the Markov chain (C n , M n ) with transition matrix defined by Relation (3) is such that P(M 0 = x|C 0 ) = V 0 (x) for x ∈ S then, for n ≥ 0, the identity

(4) (V n (x), x ∈ S) dist. = (P[M n = x | F n-1 ], x ∈ S)
holds in distribution. In particular, for x ∈ S,

E(V n (x)) = P(M n = x).
Proof. For t ≥ 0 and x ∈ S,

P(M n+1 = x | F n ) = y =x P(M n+1 = x, M n = y | F n ) + P(M n+1 = x, M n = x | F n ).
For y = x, the Markov property of the sequence (C n , M n ) gives the relation

P(M n+1 = x, M n = y | F n ) = P(M n+1 = x | M n = y, F n ) × P(M n = y | F n ) = P(M n+1 = x | M n = y, C n ) × P(M n = y | F n-1 ) = p(y, x) × P(M n = y | F n-1 )½ {Cn=y} .
In the case where the mouse does not move,

P(M n+1 = x, M n = x | F n ) = P(M n = x | F n-1 )½ {Cn =x} ,
by regrouping these terms, one gets the relation

P(M n+1 = x | F n ) = y =x P(M n = y | F n-1 )½ {Cn=y} p(y, x) + P(M n = x | F n-1 )½ {Cn =x} .
This shows that that the sequence (

P[M n = x | F n-1 ], x ∈ S) satisfies Relation (2).
The theorem is proved.

Recurrence Properties of the Cat and Mouse Markov Chain. Since the transition matrix of (C n ) is assumed to be irreducible and aperiodic, it is not difficult to check that the Markov chain (C n , M n ) is aperiodic and visits with probability 1 all the elements of the diagonal of S × S. In particular there is only one irreducible component. Note that (C n , M n ) itself is not necessarily irreducible on S × S as the following example shows: Take S = {0, 1, 2, 3} and the transition matrix p(0, 1) = p(2, 3) = p(3, 1) = 1 and p(1, 2) = 1/2 = p(1, 0), in this case the element (0, 3) cannot be reached starting from [START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF][START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF].

Theorem 2 (Recurrence). The Markov chain (C n , M n ) on S×S with transition matrix Q defined by relation (3) is recurrent: the measure ν defined as

(5) ν(x, y) = π(x) E x   H * y n=1 p(C * n , y)   , x, y ∈ S
is invariant. Its marginal on the second coordinate is given by, for y ∈ S ν 2 (y)

def. = x∈S ν(x, y) = E π (p(C 0 , y)H y ),
and it is equal to π on the diagonal, ν(x, x) = π(x) for x ∈ S.

In particular, with probability 1, the elements of S×S for which ν is non zero are visited infinitely often and ν is, up to a multiplicative coefficient, the unique invariant measure. The recurrence property is not surprising: the positive recurrence property of the Markov chain (C n ) shows that cat and mouse meet infinitely often with probability one. The common location at these instants is a Markov chain with transition matrix P and therefore recurrent. Note that the total mass of ν,

ν(S 2 ) = y∈S E π (p(C 0 , y)H y ),
can be infinite when S is countable. See Kemeny et al. [START_REF] Kemeny | Denumerable Markov chains[END_REF] for an introduction on recurrence properties of discrete countable Markov chains. The measure ν 2 on S is related to the location of the mouse under the invariant measure ν. By Theorem 1 this quantity is closely related to the evolution of the cash process.

Proof. From the ergodicity of (C n ) it is clear that ν(x, y) is finite for x, y ∈ S. One has first to check that ν satisfies the equations of invariant measure for the Markov chain (C n , M n ), ( 6)

ν(x, y) = z =y ν(z, y)p(z, x) + z ν(z, z)p(z, x)p(z, y), x, y ∈ S.
For x, y ∈ S,

z =y ν(z, y)p(z, x) = z =y π(x)p * (x, z)E z   H * y n=1 p(C * n , y)   = π(x)E x   H * y n=2 p(C * n , y)   ,
and

z∈S ν(z, z)p(z, x)p(z, y) = z∈S π(x)p * (x, z)p(z, y)E z   H * z -1 n=0 p(C * n , z)   .
The cycle formula for the invariant distribution of (C * n ) gives that

E z   H * z -1 n=0 p(C * n , z)   = E z (H * z )E π (p(C * 0 , z)) = π(z) π(z) = 1
and, at the same time, the identity ν(x, x) = π(x) for x ∈ S. Hence,

z∈S ν(z, z)p(z, x)p(z, y) = z∈S π(x)p * (x, z)p(z, y) = π(x)E x (p(C * 1 , y)) .
The two last identities for ν show that ν is indeed an invariant distribution.

The second marginal is given by, for y ∈ S,

x∈S ν(x, y) = t≥1 x∈S π(x)E x p(C * t , y)½ {H * y ≥t} = t≥1 E π p(C * t , y)½ {H * y ≥t} = t≥1 E π p(C 0 , y)½ {Hy ≥t} = E π (p(C 0 , y)H y ) ,
the theorem is proved.

The representation (5) of the invariant measure can be obtained (formally) through an iteration of the equilibrium equations [START_REF] Bingham | Limit theorems for occupation times of Markov processes, Z. Wahrscheinlichkeitstheorie und Verw[END_REF]. Since the first coordinate of (C n , M n ) is a Markov chain with transition matrix P and ν is invariant measure for (C n , M n ), the first marginal of ν is thus equal to απ for some α > 0, i.e.

y ν(x, y) = απ(x), x ∈ S.
The constant α is in fact the total mass of ν. In particular, from Equation ( 5), one gets that the quantity

h(x) def. = y∈S E x   H * y n=1 p(C * n , y)   , x ∈ S,
is independent of x ∈ S and equal to α. This can be proved more directly in the following way. One easily checks that x → h(x) is harmonic with respect to (C * n ), i.e. that the relation

h(x) = y∈S p * (x, y)h(y).
holds for all x ∈ S. One uses the classical result that since (C * n ) is a positive recurrent Markov chain, all harmonic functions are constant. See Neveu [START_REF] Neveu | Martingales à temps discret[END_REF]. In particular, one has

α = x∈S π(x)h(x) = y∈S E π   H * y n=1 p(C * n , y)   = y∈S E π (p(C 0 , y)H y ),
with the same calculation as in the proof of the above theorem. Note that the parameter α can be infinite.

Proposition 1 (Location of the mouse in the reversible case). If (C n ) is a reversible Markov chain, with the definitions of the above theorem, for y ∈ S, the relation

ν 2 (y) = 1 -π(y), holds. If the state space S is countable, the Markov chain (C n , M n ) is then null- recurrent.
Proof. For y ∈ S, by reversibility,

ν 2 (y) = E π (p(C 0 , y) H y ) = x π(x)p(x, y)E x (H y ) = x π(y)p(y, x)E x (H y ) = π(y)E y (H y -1) = 1 -π(y).
The proposition is proved.

Corollary 1 (Finite State Space). If the state space S is finite with cardinality N , then (C n , M n ) converges in distribution to (C ∞ , M ∞ ) such that (7) P(C ∞ = x, M ∞ = y) = cπ(x)E x   H * y n=1 p(C * n , y)   , x, y ∈ S, with c = 1 y∈S E π (p(C 0 , y)H y ) , in particular P(C ∞ = M ∞ = x) = cπ(x). If the Markov chain (C n ) is reversible, then P(M ∞ = y) = 1 -π(y) N -1 .
Tetali [START_REF] Tetali | Design of on-line algorithms using hitting times[END_REF] showed, via linear algebra, that if (C n ) is a general recurrent Markov chain, then ( 8)

z∈S E π (p(C 0 , z) H z ) ≤ N -1.
See also Aldous and Fill [START_REF] Aldous | Reversible Markov chains and random walks on graphs[END_REF]. It follows that the value c = 1/(N -1) obtained for reversible chains, is the minimal possible value of c. The constant c is the probability that cat and mouse are at the same location.

In the reversible case, one gets the intuitive fact that the less likely a site is for the cat, the most likely it is for the mouse. This is however false in general. Consider a Markov chain whose state space S consists of r cycles with respective sizes m 1 , . . . , m r with one common node 0

S = {0} ∪ r k=1 {(k, i) : 1 ≤ i ≤ m k },
and with the following transitions:

for 1 ≤ k ≤ r and 2 ≤ i ≤ m k , p((k, i), (k, i -1)) = 1, p((k, 1), 0) = 1 and p(0, (k, m k )) = 1 r . Define m = m 1 + m 2 + • • • + m r . It is easy to see that π(0) = r m + r and π(y) = 1 m + r , y ∈ S -{0}.
One gets that for the location of the mouse, for y ∈ S,

ν 2 (y) = E π (p(C 0 , y)H y ) = π(y)(m -m k + r), if y = (k, m k ), 1 ≤ k ≤ r π(y), otherwise.
Observe that for any y distinct from 0 and (k, m k ), we have π(0) > π(y) and ν 2 (0) > ν 2 (y), the probability to find a mouse in 0 is larger than in y. Note that in this example one easily obtains c = 1/r.

Random Walks in Z and Z 2

In this section, the asymptotic behavior of the mouse when the cat follows a recurrent random walk in Z and Z 2 is analyzed. The jumps of the cat are uniformly distributed on the neighbors of the current location.

3.1. One-Dimensional Random Walk. The transition matrix P of this random walk is given by

p(x, x + 1) = 1 2 = p(x, x -1), x ∈ Z
To get the main limiting result of the one-dimensional random walk, Theorem 3, two technical lemmas are first established.

Lemma 1. For any x, ε > 0 and K > 0,

lim n→+∞ P   inf 0≤k≤⌊x √ n⌋ 1 √ n k+⌊ε √ n⌋ i=k (1 + T 1,i ) ≤ K   = 0,
where (T 1,i ) are i.i.d. random variables with the same distribution as the first hitting time of 0 of (C n ),

T 1 = inf{n > 0 : C n = 0} with C 0 = 1.
Proof. If E is an exponential random variable with parameter 1 independent of the sequence (T 1,i ), by using the fact that, for u ∈ (0, 1), E(u

T1 ) = (1 - √ 1 -u 2 )/u, then for n ≥ 2, log P   1 √ n ⌊ε √ n⌋ k=0 (1 + T 1,k ) ≤ E   = ⌊ε √ n⌋ log 1 -1 -e -2/ √ n ≤ -ε 4 √ n.
Denote by m n the infimum of the assertion, the above relation gives directly

P (m n ≤ E) ≤ ⌊x √ n⌋e -ε 4 √ n , hence +∞ n=2 P (m n ≤ E) < +∞,
consequently, with probability 1 there exists N 0 such that, for any n ≥ N 0 , we have m n > E. Since P(E ≥ K) > 0, the lemma is proved.

Lemma 2. Let, for n ≥ 1, (T 2,i ) i.i.d. random variables with the same distribution as

T 2 = inf{k > 0 : C k = 0} with C 0 = 2 and u n = +∞ ℓ=1 ½ { P ℓ k=1 (2+T 2,k )<n} , then the process u ⌊tn⌋ / √ n converges in distribution to (L B (t)/2)
, where L B (t) is the local time process at time t ≥ 0 of a standard Brownian motion.

Proof. The variable T 2 can be written as a sum T 1 + T ′ 1 of independent random variables T 1 and T ′ 1 having the same distribution as T 1 defined in the above lemma. For k ≥ 1, the variable T 2,k can written as T 1,2k + T 1,2k+1 . Clearly

1 2 +∞ ℓ=1 ½ { P ℓ k=1 (1+T 1,k )<n} - 1 2 ≤ u n ≤ 1 2 +∞ ℓ=1 ½ { P ℓ k=1 (1+T 1,k )<n} . Furthermore +∞ ℓ=1 ½ { P ℓ k=1 (1+T 1,k )<n} , n ≥ 1 dist. = (r n ) def. = n-1 ℓ=1 ½ {C ℓ =0} , n ≥ 1 ,
where (C n ) is the symmetric simple random walk. A classical result by Knight [START_REF] Knight | Random walks and a sojourn density process of Brownian motion[END_REF], see also Borodin [START_REF] Borodin | The asymptotic behavior of local times of recurrent random walks with finite variance[END_REF] and Perkins [START_REF] Perkins | Weak invariance principles for local time[END_REF], gives that the process (r ⌊nt⌋ / √ n) converges in distribution to (L B (t)) as n gets large. The lemma is proved.

The main result of this section can now be stated.

Theorem 3 (Scaling of the Location of the Mouse

). If (C 0 , M 0 ) ∈ N 2 , the con- vergence in distribution lim n→+∞ 1 4 √ n M ⌊nt⌋ , t ≥ 0 dist. = B 1 (L B2 (t)), t ≥ 0
holds, where (B 1 (t)) and (B 2 (t)) are independent standard Brownian motions on R and (L B2 (t)) is the local time process of (B 2 (t)) at 0.

The location of the mouse at time T is therefore of the order of 4 √ T as T gets large. The limiting process can be expressed as a Brownian motion slowed down by the process of the local time at 0 of an independent Brownian motion. The quantity L B2 (T ) can be interpreted, as the scaled duration of time the cat and the mouse spend together.

Proof. A coupling argument is used. Take -i.i.d. geometric random variables (G i ) such that P(G 1 ≥p)=1/2 p-1 for p ≥ 1; -(C a k ) and (C b j,k ), j ≥ 1, i.i.d. independent symmetric random walks starting from 0;

and assume that all these random variables are independent. One denotes, for m = 1, 2 and i ≥ 1,

T b m,i = inf{k ≥ 0 : C b i,k = m}. A cycle of the Markov chain (C i , M i ) is constructed as follows. Define (C k , M k ) = (C a k , C a k ), 0 ≤ k < G 1 , (C a G1 -2I 1 + C b 1,k-G1 , C a G1 ), G 1 ≤ k ≤ τ 1 , with I 1 = C a G1 -C a G1-1 , τ 1 = G 1 + T b 2,1 . It is not difficult to check that [(C k , M k ), 0 ≤ k ≤ τ 1 ]
has the same distribution as the cat and mouse Markov chain on a cycle between two meeting times during which an excursion of the cat away from the mouse occurs.

With the convention t 0 = 0, by induction, denote by

t j = τ 1 + • • • + τ j , (C k , M k ) = (C a k-ti +si , C a k-ti+si ), t i ≤ k < t i + G i+1 , (C a si+1 -2I i+1 + C b i+1,k-ti -Gi+1 , C a si+1 ), t i + G i+1 ≤ k ≤ t i+1 , with I i+1 = C a si+1 -C a si+1-1 and τ i+1 = G i+1 + T b 2,i+1
. In this way, the sequence (C n , M n ) has the same distribution as the Markov chain with transition matrix Q defined by Relation [START_REF] Berkhin | A survey on pagerank computing[END_REF].

With this representation, the location M n of the mouse at time n is given by C a κn , where

κ n = +∞ i=1 i ℓ=1 G ℓ + (n -t i ) ½ {ti-1≤n≤ti-1+Gi} + +∞ i=1 i ℓ=1 G ℓ ½ {ti-1+Gi<n<ti} , in particular (9) νn ℓ=1 G ℓ ≤ κ n ≤ νn+1 ℓ=1 G ℓ with ν n = inf{ℓ : t ℓ+1 > n} = inf ℓ : ℓ+1 k=1 G k + T b 2,k > n .
Define

ν n = inf ℓ : ℓ+1 k=1 2 + T b 2,k > n ,
then, for δ > 0, on the event

{ν n > ν n + δ √ n}, n ≥ νn+δ √ n k=1 2 + T b 2,k ≥ νn+1 k=1 T b 2,k + G k + νn+δ √ n k=νn+2 2 + T b 2,k - νn+1 k=1 (G k -2) ≥ n + νn+δ √ n k=νn+2 2 + T b 2,k - νn+1 k=1 (G k -2)
and, since

T b 1,k ≤ 2 + T b 2,k , the relation (10) ν n -ν n > δ √ n ⊂    inf 1≤ℓ≤νn ℓ+⌊δ √ n⌋ k=ℓ T b 1,k ≤ νn+1 k=1 (G k -2)    holds. For t > 0, define (∆ n (s), 0 ≤ s ≤ t) def. = 1 √ n (ν ⌊ns⌋ -ν ⌊ns⌋ ), 0 ≤ s ≤ t
for ε > 0, by Lemma 2 and the law of large numbers, there exist some x 0 > 0 and n 0 such that if n ≥ n 0 then

P ν ⌊nt⌋ ≥ x 0 √ n ≤ ε and P   x0 √ n+1 k=1 (G k -2) ≥ x 0 √ n   ≤ ε.
hence, by Relation (10) one gets that, for n ≥ n 0 and δ > 0,

P sup 0≤s≤t ∆ n (s) > δ ≤ 2ε + P   inf 1≤k≤x0 √ n 1 √ n k+⌊δ √ n⌋ k T b 1,k ≤ x 0   .
By Lemma 1, the left hand side is thus arbitrarily small if n is sufficiently large. In a similar way the same results holds for the variable sup(-∆ n (s) : 0 ≤ s ≤ t).

The variable sup(|∆ n (s)| : 0 ≤ s ≤ t) converges therefore in distribution to 0. Consequently, by using Relation [START_REF] Brin | The anatomy of a largescale hypertextual web search engine[END_REF] and the law of large numbers, the same property holds for

sup 0≤s≤t 1 √ n κ ⌊ns⌋ -2ν ⌊ns⌋ .
Donsker's Theorem gives that the sequence of processes (C a ⌊ √ ns⌋ / 4 √ n, 0 ≤ s ≤ t) converges in distribution to (B 1 (s), 0 ≤ s ≤ t), in particular, for ε and δ > 0, there exists some n 0 such that if n ≥ n 0 , then

P sup 0≤u,v≤t,|u-v|≤δ 1 4 √ n C a ⌊ √ nu⌋ -C a ⌊ √ nv⌋ ≥ δ ≤ ε,
see Billingsley [START_REF] Billingsley | Convergence of probability measures[END_REF] for example. Since M n = C a κn for any n ≥ 1, the processes 1

4 √ n M ⌊ns⌋ , 0 ≤ s ≤ t and 1 4 √ n C a 2ν ⌊ns⌋ , 0 ≤ s ≤ t
have therefore the same asymptotic behavior for the convergence in distribution. Since, by construction (C a k ) and (ν n ) are independent, with Skorohod's representation Theorem, on can assume that, on an appropriate probability space with two independent Brownian motions (B 1 (s)) and (B 2 (s)), the convergences

lim n→+∞ (C a ⌊ √ ns⌋ / 4 √ n, 0 ≤ s ≤ t) = (B 1 (s), 0 ≤ s ≤ t), lim n→+∞ (ν ⌊ns⌋ / √ n) = (L B2 (s)/2, 0 ≤ s ≤ t).
hold almost surely for the norm of the supremum. This concludes the proof of the theorem. A transition matrix Q R on E 2 is defined as follows, for e, f , g ∈ E.

( The transition matrix Q R has some similarity with a cat and mouse Markov chain associated to R = (r ef , e, f ∈ E) defined by Equation [START_REF] Garsia | A discrete renewal theorem with infinite mean[END_REF]: as long as the two coordinates are not equal, the first one moves according to R. But when they are equal, only the second one moves to one of the three other elements with uniform probability.

)      Q R ((e, g), (f, g)) = r ef , e = g, Q R ((e, 12
A characterization of the matrix R. Let

τ + = inf(n > 0 : C n ∈ E) and τ = inf(n ≥ 0 : C n ∈ E), then clearly r ef = P(C τ + = f | C 0 = e). For x ∈ Z 2 , define φ(x) = P(C τ = e 1 | C 0 = x),
by symmetry, it is easily seen that the coefficients of R can be determined by φ. For

x ∈ E, by looking at the state of the Markov chain at time 1, one gets the relation

∆φ(x) def. = φ(x+e 1 ) + φ(x+e -1 ) + φ(x+e 2 ) + φ(x+e -2 ) -4φ(x) = 0
and φ(e i ) = 0 if i ∈ {-1, 2, -2} and φ(e 1 ) = 1. In other words, φ is the solution of a discrete Dirichlet problem: it is an harmonic function (for the discrete Laplacian) on Z 2 with fixed values on E. Classically, there is a unique solution to the Dirichlet problem, see Norris [START_REF] Norris | Markov chains[END_REF] for example. An explicit expression of φ is, apparently, not available.

Theorem 4. If (C 0 , M 0 ) ∈ N 2 , the convergence in distribution of finite marginals

lim n→+∞ 1 √ n M ⌊e nt ⌋ , t ≥ 0 dist. = (W (Z(t))),
holds, with

(Z(t)) = 16µ R (D E ) 3π L B (T t ) ,
where µ R is the probability distribution on E 2 introduced in Definition 1, the process

(W (t)) = (W 1 (t), W 2 (t)
) is a two dimensional Brownian motion and -(L B (t)) the local time at 0 of a standard Brownian motion (B(t)) on R independent of (W (t)). -For t ≥ 0, T t = inf{s ≥ 0 : B(s) = t}.

Proof. The proof follows the same lines as before: a convenient construction of the process to decouple the time scale of the visits of the cat and the motion of the mouse. The arguments which are similar to the ones used in the proof of the one-dimensional case are not repeated.

When the cat and the mouse at the same site, they stay together a geometric number of steps whose mean is 4/3. When they are just separated, up to a translation, a symmetry or a rotation, if the mouse is at e 1 , the cat will be at e 2 , e -2 or -e 1 with probability 1/3. The next time the cat will meet the mouse corresponds to one of the instants of visit to E by the sequence (C n ). If one considers only these visits and, up to a translation, it is not difficult to see that the position of the cat and of the mouse is a Markov chain with transition matrix Q R . Let (R n , S n ) be the associated Markov chain, for N visits to the set E, the proportion of time the cat and the mouse will have met is given by

1 N N ℓ=1 ½ {R ℓ =S ℓ } ,
this quantity converges almost surely to µ R (D E ). Now one has to estimate the number of visits of the cat to the set E. Kasahara [START_REF]A limit theorem for sums of random number of i.i.d. random variables and its application to occupation times of Markov chains[END_REF], see also Bingham [6] and Kasahara [START_REF] Kasahara | A limit theorem for slowly increasing occupation times[END_REF], gives that, for the convergence in distribution of the finite marginals, the following convergence holds

lim n→+∞   1 n ⌊e nt ⌋ i=0 ½ {Ci∈E}   dist. = 4 π L B (T t ) .
The rest of the proof follows the same lines as in the proof of Theorem 3.

Remark.

Tanaka's Formula, see Rogers and Williams [START_REF] Rogers | Diffusions, Markov processes, and martingales[END_REF], gives the relation

L(T t ) = t - Tt 0 sgn(B(s)) dB(s),
where sgn(x) = -1 if x < 0 and +1 otherwise. Since the process (T t ) has independent increments and that the T t 's are stopping times, one gets that (L(T t )) has also independent increments. The function t → T t being discontinuous, the limiting process (W (Z(t))) is also discontinuous. This is related to the fact that the convergence of processes in the theorem is minimal: it is only for the convergence in distribution of finite marginals. For t ≥ 0, the distribution of L(T t ) is an exponential distribution with mean 2t, see Borodin and Salminen [START_REF] Borodin | Handbook of Brownian motion-facts and formulae, Probability and its Applications[END_REF] for example. The characteristic function of

W 1 16µ R (D E )L(T t ) 3π
at ξ ∈ C such that Re(ξ) = 0 can be easily obtained as

E e iξW1[Z(t)] = α 2 0 α 2 0 + ξ 2 t , with α 0 = √ 3π 4 µ R (D E ) .
With a simple inversion, one gets that the density of this random variable is a bilateral exponential distribution given by

α 0 2 √ t exp - α 0 √ t |y| , y ∈ R.
The characteristic function can be also represented as

E e iξW1[Z(t)] = α 2 0 α 2 0 + ξt = exp +∞ -∞ e iξu -1 Π(t, u) du , with Π(t, u) = e -α0|u|/ √ t |u| , u ∈ R, Π(t, u)
du is in fact the associated Lévy measure of the non-homogeneous process with independent increments (W 1 (Z(t))). See Chapter 5 of Gikhman and Skorokhod [START_REF] Gikhman | Introduction to the theory of random processes[END_REF].

The Reflected Random Walk

In this section, the cat follows a simple ergodic random walk on the integers with a reflection at 0, an asymptotic analysis of the evolution of the sample paths of the mouse is carried out. Despite it is a quite simple example, it exhibits an interesting scaling behavior.

Let P denote the transition matrix of the simple reflected random walk on N,

     p(x, x + 1) = p, x ≥ 0, p(x, x -1) = 1 -p, x = 0, p(0, 0) = 1 -p. (13)
It is assumed that p ∈ (0, 1/2) so that the corresponding Markov chain is positive recurrent and reversible and its invariant probability distribution is a geometric random variable with parameter ρ def.

= p/(1 -p). In this case, it is easily checked that the measure ν on N 2 defined in Theorem 2 is given by

               ν(x, y) = ρ x (1 -ρ), 0 ≤ x < y -1, ν(y -1, y) = ρ y-1 (1 -ρ)(1 -p), ν(y, y) = ρ y (1 -ρ), ν(y + 1, y) = ρ y+1 (1 -ρ)p, ν(x, y) = ρ x (1 -ρ), x > y + 1.
Proposition 2. If, for n ≥ 1, T n = inf{k>0 : C k =n} then, as n goes to infinity, the random variable T n /E 0 (T n ) converges in distribution to an exponentially distributed random variable with parameter 1 and

lim n→+∞ E 0 (T n )ρ n = 1 + ρ (1 -ρ) 2 , with ρ = p/(1 -p).
If C 0 = n, then T 0 /n converges almost surely to (1 -ρ)/(1 + ρ).

Proof. The convergence result is standard, see Keilson [START_REF] Keilson | Markov chains models-rarity and exponentiality[END_REF] for closely related results. The asymptotic behavior of the sequence (E 0 (T n )) follows simply by getting the average hitting time of x starting from x -1 (recurrence relation) and by summing up x from 1 to x.

Free Process. Let (C ′ n , M ′ n ) be the cat and mouse Markov chain associated to the simple random walk on Z without reflection (the free process):

p ′ (x, x + 1) = p = 1 -p ′ (x, x -1), ∀x ∈ Z. Proposition 3. If (C ′ 0 , M ′ 0 ) = (0, 0)
, then the asymptotic location of the mouse for the free process

M ′ ∞ = lim n→∞ M ′ n is such that, for u ∈ C such that |u| = 1, ( 14
) E u M ′ ∞ = ρ(1 -ρ)u 2 -ρ 2 u 2 + (1 + ρ)u -1 , in particular E(M ′ ∞ ) = - 1 ρ and E 1 ρ M ′ ∞ = 1, furthermore the relation (15) E sup n≥0 1 √ ρ M ′ n < +∞ holds. If (S k )
is the random walk associated to the sequence (A i ) of i.i.d. random variables with the same distribution as M ′ ∞ and (E i ) are i.i.d. exponential random variables with parameter (1 + ρ)/(1 -ρ) 2 , then the random variable W defined by

(16) W = +∞ k=0 ρ -S k E k ,
is almost surely finite with infinite expectation.

Proof. Let τ = inf{n ≥ 1 : C n < M n }, for u ∈ C such that |u| = 1 then, by looking at the different cases, one has

E u M ′ τ = (1 -p) 1 u + p 2 u E u M ′ τ + p(1 -p)u Since, M ′ τ -C ′ τ = 2
, after time τ , the cat and the mouse meet again with probability (p/(1 -p)) 2 , consequently,

M ′ ∞ dist. = 1+G i=1 M ′ τ,i
where (M ′ τ,i ) are i.i.d. random variables with the same distribution as M ′ τ and G is an independent geometrically distributed random variable with parameter ρ 2 . This identity gives directly the expression for the characteristic function of M ′ ∞ and also the relation

E(M ′ ∞ ) = -1/ρ. The upper bound sup n≥0 M ′ n ≤ U def = 1 + sup n≥0 C ′ n
and the fact that U -1 has the same distribution as the invariant distribution of the reflected random walk (C n ), i.e. a geometric distribution with parameter ρ, give directly Inequality [START_REF] Kasahara | A limit theorem for slowly increasing occupation times[END_REF]. Let N = (N t ) be a Poisson process with rate (1 -ρ) 2 /(1 + ρ), it is easy to check the following identity for the distributions ( 17)

W dist. = +∞ 0 ρ -SN t dt,
by the law of large numbers, (S Nt /t) converges almost surely to

-(1+ρ)/[(1-ρ) 2 ρ],
one gets therefore that W is almost surely From Equation ( 14), one gets

E(u M ′ ∞
) is well defined for u = 1/ρ and its value is

E(ρ -M ′ ∞ ) = 1. This gives directly that E(W ) = +∞.
Note that, as a consequence of this result, the exponential moment

E u M ′ ∞ of the random variable M ′ ∞ is finite for u in the interval [1, 1/ρ].
Exponential Functionals. The representation [START_REF] Keilson | Markov chains models-rarity and exponentiality[END_REF] shows that the variable W is an exponential functional of a compound Poisson process. See Yor [START_REF] Yor | Exponential functionals of Brownian motion and related processes[END_REF]. It can be seen as the invariant distribution of the auto-regressive process (X n ) defined as

X n+1 def. = ρ -An X n + E n , n ≥ 0.
The distributions of these random variables are investigated in Guillemin et al. [START_REF] Guillemin | AIMD algorithms and exponential functionals[END_REF] when (A n ) are non-negative. See also Bertoin and Yor [START_REF] Bertoin | Exponential functionals of Lévy processes[END_REF]. The above proposition shows that W has a heavy tailed distribution, as it will be seen in the scaling result below, this has a qualitative impact on the asymptotic behavior of the location of the mouse. See Goldie [START_REF] Goldie | Implicit renewal theory and tails of solutions of random equations[END_REF] for an analysis of the asymptotic behavior of tail distributions of these random variables.

A Scaling for the location of the Mouse. The rest of the section is devoted to the analysis of the location of the mouse when it is initially far away from the location of the cat. Define

s 1 = inf{ℓ ≥ 0 : C ℓ = M ℓ } and t 1 = inf{ℓ ≥ s 1 : C ℓ = 0}
and, for k ≥ 1,

s k+1 = inf{ℓ ≥ t k : C ℓ = M ℓ } and t k+1 = inf{ℓ ≥ s k+1 : C ℓ = 0} (18)
Proposition 2 suggests an exponential time scale for a convenient scaling of the location of the mouse. When the mouse is initially at n and the cat at the origin, it takes the duration s 1 of the order of ρ -n so that the cat reaches this level. Just after that time, the two processes behave like the free process on Z analyzed above, hence when the cat returns to the origin (at time t 1 ), the mouse is at position n+M ′ ∞ . The following proposition presents a precise formulation of this description, in particular a proof of the corresponding scaling results. For the sake of simplicity, and because of the topological intricacies of convergence in distribution, in a first step the convergence result is restricted on the time interval [0, s 2 ], i.e. on the two first "cycles". Theorem 5 below gives the full statement of the scaling result. Proposition 4. If M 0 = n ≥ 1 and C 0 = 0 then, as n goes to infinity, the random variable (M t1 -n, ρ n t 1 ) converges in distribution to (A 1 , E 1 ) and the process

M ⌊tρ -n ⌋ n ½ {0≤t<ρ n s2}
converges in distribution for the Skorohod topology to the process

½ {t<E1+ρ -A 1 E2} ,
where A 1 is a random variable with the same distribution as M ′ ∞ defined in Proposition 3, it is independent of E 1 and E 2 , two independent exponential random variables with parameter

(1 + ρ)/(1 -ρ) 2 .
Proof. For T > 0, D([0, T ], R) denotes the space of cadlag functions, i.e. of right continuous functions with left limits and d 0 is the metric on this space defined by, for x, y ∈ D([0, T ], R),

d 0 (x, y) = inf ϕ∈H sup 0≤s<t<T log ϕ(t) -ϕ(s) t -s + sup 0≤s<T |x(ϕ(s)) -y(s)| ,
where H is the set of non-decreasing functions ϕ such that φ(0) = 0 and φ(T ) = T ). See Billingsley [START_REF] Billingsley | Convergence of probability measures[END_REF].

An upper index n is added on the variables s 1 , s 2 , t 1 to stress the dependence on n. Take three independent Markov chains (C a k ), (C b k ) and (C c k ) with transition matrix P such that C a 0 = C c 0 = 0, C b 0 = n and, for i = a, b, c, T i p denotes the hitting time of p ≥ 0 for

(C i k ). Since ((C k , M k ), s n 1 ≤ k ≤ t n 1 ) has the same distribution as ((n + C ′ k , M ′ k ), 0 ≤ k < T b 0 , by the strong Markov property, the sequence (M k , k ≤ s n 2 ) has the same distribution as (N k , 0 ≤ k ≤ T a n + T b 0 + T c n ) where N k =        n, k ≤ T a n n + M ′ k-T a n , T a n ≤ k ≤ T a n + T b 0 n + M ′ T b 0 , T a n + T b 0 ≤ k ≤ T a n + T b 0 + T c n+M ′ T b 0 where ((C b k , M ′ k ), 0 ≤ k ≤ T b 0
) is a sequence with the same distribution as the free process killed at the hitting time of 0 of the first coordinate. Additionally, it is independent of the Markov chains (C a k ) and (C c k ). In particular, the random variable M t1 -n has the same distribution as M ′ T b 0 , and since T b 0 converges almost surely to infinity, it is converging in distribution M ′ ∞ . Proposition 2 and the independence of (C a k ) and (C c k ) show that the sequences (ρ n T a n ) and (ρ n T c n ) converge in distribution to two independent exponential random variables E 1 and E 2 with parameter (1 + ρ)/(1 -ρ) 2 . By using Skorohod's Representation Theorem, see Billingsley [START_REF] Billingsley | Convergence of probability measures[END_REF], up to a change of probability space, it can be assumed that these convergences hold for the almost sure convergence.

The rescaled process (M ⌊tρ -n ⌋ /n½ {0≤t<ρ n s2} , t ≤ T ) has the same distribution as

x n (t) def. =                  1, t < ρ n ⌈T a n ⌉, 1 + 1 n M ′ ⌊ρ -n t-T a n ⌋ , ρ n ⌈T a n ⌉ ≤ t < ρ n ⌈T a n + T b 0 ⌉, 1 + 1 n M ′ T b 0 , ρ n ⌈T a n + T b 0 ⌉ ≤ t < ρ n ⌈T a n + T b 0 + T c n+M ′ T b 0 ⌉, 0, t ≥ ρ n ⌈T a n + T b 0 + T c n+M ′ T b 0 ⌉, for t ≤ T . Proposition 2 shows that T b 0 /n converges almost surely to (1 -ρ)/(1 + ρ) so that (ρ n ⌈T a n + T b 0 ⌉) converges to E 1 and, for n ≥ 1, ρ n T c n+M ′ T b 0 = ρ -M ′ T b 0 ρ n+M ′ T b 0 T c n+M ′ T b 0 -→ ρ -M ′ ∞ E 2 ,
almost surely as n goes to infinity. Additionally, one has also

lim n→+∞ 1 n sup k≥0 |M ′ k | = 0, almost surely. Define x ∞ = ½ {t<T ∧(E1+ρ -M ′ ∞ E2)} , where a ∧ b = min(a, b) for a, b ∈ R. Time change. For n ≥ 1 and t > 0, define u n [resp. v n ] as the minimum [resp. maximum] of t ∧ ρ n ⌈T a n + T b 0 + T c n+M ′ T b 0 ⌉ and t ∧ (E 1 + ρ -M ′ ∞ E 2 )
, and

ϕ n (s) =      v n u n s, 0 ≤ s ≤ u n , v n + (s -u n ) T -v n T -u n , u n < s ≤ T.
Note that ϕ n ∈ H, by using this function in the definition of the distance d 0 on D([0, T ], R) to have an upper bound of (d(x n , x ∞ )) and with the above convergence results, one gets that, almost surely, the sequence (d(x n , x ∞ )) converges to 0. The proposition is proved.

Theorem 5 (Scaling for the Location of the Mouse).

If M 0 = n, C 0 = 0, then the process M ⌊tρ -n ⌋ n ½ {t<ρ n tn}
converges in distribution for the Skorohod topology to the process (½ {t<W } ), where W is the random variable defined by Equation [START_REF]A limit theorem for sums of random number of i.i.d. random variables and its application to occupation times of Markov chains[END_REF].

If H 0 is the hitting time of 0 by (M n ), H 0 = inf{s ≥ 0 : M s = 0},
then, as n goes to infinity, ρ n H 0 converges in distribution to W .

Proof. In the same way as in the proof of Proposition 4, it can be proved that for p ≥ 1, the random vector [(M t k -n, ρ n t k ), 1 ≤ k ≤ p] converges in distribution to the vector

S k , k-1 i=0 ρ -Si E i .
and, for k ≥ 0, the convergence in distribution ( 19)

lim n→+∞ M ⌊tρ -n ⌋ n ½ {0≤t<ρ n t k } = ½ {t<E1+ρ -S 1 E2+•••+ρ -S k-1 E k }
holds for the Skorohod topology. Let φ : [0, 1] → R + be defined by φ(s) = E(ρ -sA1 ), then φ(0) = φ(1) = 1 and φ ′ (0) < 0, since φ is strictly convex then for all s < 1, φ(s) < 1.

By using Proposition 3 one gets that there exist N 0 , K 0 ≥ 0 and 0

< δ < 1 such that if n ≥ N 0 E (n,n) (M t1 ) def. = E(M t1 | M 0 = C 0 = n) ≤ n + 1 2 E(M ′ ∞ ) = n - 1 2ρ , (20)
and, by Proposition 2,

ρ n/2 E (0,n) ( √ t 1 ) ≤ K 0 , (21)
and finally, with the identity E(1/ρ M ′ ∞ ) = 1, Inequality ( 15) and Lebesgue's Theorem, one gets that

(22) E ρ -(Mt 1 -n)/2 ≤ δ.
Let ν = inf{k ≥ 1 : M t k ≤ N 0 } and, for k ≥ 1, G k the σ-field generated by the random variables (C j , M j ) for j ≤ t k . Because of Inequality [START_REF] Knight | Random walks and a sojourn density process of Brownian motion[END_REF], it is easily checked that the sequence

M t k∧ν + 1 2ρ (k ∧ ν), k ≥ 0
is a supermartingale with respect to the filtration (G k ) hence,

E (M t k∧ν ) + 1 2ρ E(k ∧ ν) ≤ E(M 0 ) = n,
since the location of the mouse is non-negative, by letting k go to infinity, one gets that E(ν) ≤ 2ρn. In particular ν is almost surely a finite random variable.

It is claimed that the sequence (ρ n t ν ) converges in distribution to W . For p ≥ 1 and on the event {ν ≥ p},

(23) (ρ n (t ν -t p )) 1/2 =   ν-1 k=p ρ n (t k+1 -t k )   1/2 ≤ ν-1 k=p ρ n (t k+1 -t k ).
For k ≥ p, Inequality [START_REF] Litvak | Analysis of an on-line algorithm for solving large Markov chains[END_REF] and the strong Markov property give the relation

ρ Mt k /2 E t k+1 -t k | G k = ρ Mt k /2 E (0,Mt k ) √ t 1 ≤ K 0 holds on the event {ν > k} ⊂ {M t k > N 0 }. One gets therefore that E ρ n (t k+1 -t k )½ {k<ν} = E ρ (n-Mt k )/2 ½ {k<ν} ρ Mt k /2 E t k+1 -t k | G k ≤ K 0 E ρ (n-Mt k )/2 ½ {k<ν}
holds and, with Inequality [START_REF] Neveu | Martingales à temps discret[END_REF] and again the strong Markov property,

E ρ (n-Mt k )/2 ½ {k<ν} = E ρ -P k-1 j=0 (Mt j+1 -Mt j )/2 ½ {k<ν} ≤ δE ρ - P k-2 j=0 (Mt j+1 -Mt j )/2 ½ {k-1<ν} ≤ δ k .
Relation [START_REF] Norris | Markov chains[END_REF] gives therefore that

E ρ n (t ν -t p ) ≤ K 0 δ p 1 -δ .
For ξ ≥ 0, E e -ξρ n tν -E e -ξρ n tp ≤ E 1 -e -ξρ n (tν -tp) + + P(ν < p)

= +∞ 0 ξe -ξy P(ρ n (t ν -t p ) ≥ u) du + P(ν < p) ≤ K 0 δ p 1 -δ +∞ 0 ξ √ u e -ξu du + P(ν < p), (24)
by using Markov's Inequality. Since ρ n t p converges in distribution to E 0 +ρ -S1 E 1 + • • • + ρ -Sp E p , one can prove that, for ε > 0, by choosing a fixed p sufficiently large and that if n is large enough then the Laplace transforms at ξ ≥ 0 of the random variables ρ n t ν and W are at a distance less than ε.

At time t ν the location M tν of the mouse is x ≤ N 0 and the cat is at 0. Since the sites visited by M n is a Markov chain with transition matrix (p(x, y)), with probability 1, the number R of jumps for the mouse to reach 0 is finite. By recurrence of (C n ), almost surely, the cat will meet the mouse R times in a finite time. Consequently, by the strong Markov property, the difference H 0 -t ν is almost surely a finite random variable, the convergence in distribution of (ρ n H 0 ) to W is therefore proved.

Non-convergence of scaled process after W. Theorem 5 could suggest that the convergence holds for a whole time axis, i.e.,

lim n→+∞ M ⌊tρ -n ⌋ n , t ≥ 0 = ½ {t<W } , t ≥ 0 ,
for the Skorohod topology. That is, after time W the rescaled process stays at 0 like for fluid limits of stable stochastic systems. The next proposition shows that this convergence does not hold at all. Proposition 5. If M 0 =C 0 =0 then for any s, t > 0 with s < t, the relation

(25) lim n→+∞ P sup s≤u≤t M ⌊uρ -n ⌋ n ≥ 1 2 = 1
holds.

It should be kept in mind that, since (C n , M n ) is recurrent, the process (M n ) returns infinitely often to 0 so that Relation [START_REF] Robert | Stochastic networks and queues[END_REF] implies that the scaled process exhibit oscillations for the norm of the supremum on compact intervals.

Proof. First it is assumed that s = 0. If C 0 = 0 and T 0 = inf{k > 0 : C k = 0}, then in particular E(T 0 ) = 1/(1 -ρ). The set C = {C 0 , . . . , C T0-1 } is a cycle of the Markov chain, denote by B its maximal value. The Markov chain can be decomposed into independent cycles (C n , n ≥ 1) with the corresponding values (T n 0 ) and (B n ) for T 0 and B. Kingman's result, see Theorem 3.7 of Robert [START_REF] Robert | Stochastic networks and queues[END_REF] for example, shows that there exists some constant K 0 such that P(B ≥ n) ∼ K 0 ρ n . Take 0 < δ < 1/2, for α > 0,

U n def. = ρ (1-δ)n ⌊αρ -n ⌋ k=1 ½ {B k ≥δn} -P(B ≥ δn) ,
then, by Chebishov's Inequality, for ε > 0,

P(|U n | ≥ ε) ≤ 1 ε 2 ρ (1-2δ)n P(B ≥ δn) ≤ K 0 ε 2 ρ (1-δ)n
, for some constant K. By using Borel-Cantelli's Lemma, one gets that the sequence (U n ) converges almost surely to 0, hence almost surely [START_REF] Rogers | Diffusions, Markov processes, and martingales[END_REF] lim

n→+∞ ρ (1-δ)n ⌊αρ -n ⌋ k=1 ½ {B k ≥δn} = αK 0 .
For x ∈ N, let ν x be the number of cycles up to time x, the strong law of large numbers gives that, almost surely,

lim x→+∞ ν x x = lim x→+∞ 1 x x i=1 ½ {C k =0} = 1 -ρ.
Denote by x n def = ⌊ρ -n t⌋, for α 0 > 0, the probability that the location of the mouse is never above level δn on the time interval (0,

x n ] is (27) P sup 1≤k≤⌊ρ -n t⌋ M k ≤ δn ≤ P sup 1≤k≤⌊ρ -n t⌋ M k ≤ δn, ρ (1-δ)n νx n -1 i=0 ½ {Bi≥δn} ≥ α 0 K 0 2 + P ρ (1-δ)n νx n -1 i=0 ½ {Bi≥δn} < α 0 K 0 2 .
If α 0 is taken to be (1 -ρ)t and if α 1 = α 0 K 0 /2, by Equation ( 26), one gets that the last expression converges to 0 as n gets large. Since the sequence of successive sites visited by the mouse is a also a simple reflected random walk,

P sup 1≤k≤⌊ρ -n t⌋ M k ≤ δn, ρ (1-δ)n νx n -1 i=0 ½ {Bi≥δn} ≥ α 1 ≤ P   sup 1≤k≤⌊ρ -n t⌋ M k ≤ δn, ρ (1-δ)n ⌊ρ -n t⌋ i=0 ½ {Ci=Mi} ≥ α 1   ≤ P sup 1≤k≤⌊α1ρ -(1-δ)n ⌋ C k ≤ δn = P T ⌊δn⌋+1 ≥ ⌊α 1 ρ -(1-δ)n ⌋
with the notations of Proposition 2, but this proposition shows that the random variable ρ ⌊δn⌋ T ⌊δn⌋+1 converges in distribution as n gets large. Consequently, since δ < 1/2, the expression

P T ⌊δn⌋+1 ≥ ⌊α 1 ρ -(1-δ)n ⌋ = P ρ ⌊δn⌋ T ⌊δn⌋+1 ≥ α 1 ρ -(1-2δ)n
converges to 0. The relation

lim n→+∞ P sup 0≤u≤t M ⌊uρ -n ⌋ n ≥ 1 2 = 1
has been proved. The proof of the same result on the interval [s, t] uses a coupling argument. Define the cat and Mouse Markov chain ( C k , M k ) as follows:

( C k , k ≥ 0) = (C ⌊sρ -n ⌋+k , k ≥ 0)
and the respective jumps of the sequences (M ⌊sρ -n ⌋+k ) and ( M k ) are independent except when M ⌊sρ -n ⌋+k = M k in which case they are the same. In this way, one checks that ( C k , M k ) is a cat and mouse Markov chain with the initial condition

( C 0 , M 0 ) = (C ⌊sρ -n ⌋ , 0).
By induction on k, one gets that M ⌊sρ -n ⌋+k ≥ M k for all k ≥ 0. Because of the ergodicity of (C k ), the variable C ⌊sρ -n ⌋ converges in distribution as n get large, in the same way as before, one gets that

lim n→+∞ P sup 0≤u≤t-s M ⌊uρ -n ⌋ n ≥ 1 2 = 1, therefore lim inf n→+∞ P sup s≤u≤t M ⌊uρ -n ⌋ n ≥ 1 2 ≥ lim inf n→+∞ P sup 0≤u≤t-s M ⌊uρ -n ⌋ n ≥ 1 2 = 1.
This completes the proof of Relation [START_REF] Robert | Stochastic networks and queues[END_REF].

It is very likely that the relation

lim n→+∞ P sup s≤u≤t M ⌊uρ -n ⌋ n = 1 2 = 1
holds in fact for the following intuitive (and non-rigorous) reason. Each time the cat meets the mouse at x large, the location of the mouse is at x + M ′ ∞ when the cat returns to 0, where M ′ ∞ is the random variable defined in Proposition 3. In this way, after the nth visit of the cat, the mouse is at the nth position of a random walk associated to M ′ ∞ starting at x. Since E(1/ρ M ′ ∞ ) = 1, Kingman's result, see Kingman [START_REF] Kingman | Inequalities in the theory of queues[END_REF], implies that the hitting time of δn by this random walk is of the order of ρ -δn . For each of the steps of the random walk, the cat needs also of the order of ρ -δn units of time. Hence to reach level δn, ρ -2δn units of time are required, this happens on the time scale t → ρ -n t only if δ ≤ 1/2. The difficulty is that the mouse is not at x + M ′ ∞ when the cat returns at 0 at time τ x but at x + M ′ τx , so that the associated random walk is not space-homogeneous but only asymptotically close to the one described above. Since an exponentially large number of steps of the random walks are considered, controlling the accuracy of the approximation turns out to be a problem.

Continuous Time Markov Chains

Let Q = (q(x, y), x, y ∈ S) be the Q-matrix of a continuous time Markov chain on S such that, for any x ∈ S, q x def. = y:y =x q(x, y) is finite and that the Markov chain is positive recurrent and π is its invariant probability distribution. The transition matrix of the underlying discrete time Markov chain is denoted as p(x, y) = q(x, y)/q x , for x = y, note that p(•, •) vanishes on the diagonal. For an introduction on Markov chains see Norris [START_REF] Norris | Markov chains[END_REF] and Rogers and Williams [START_REF] Diffusions | Markov processes, and martingales[END_REF] for a more advanced presentation.

The analogue of the Markov chain (C n , M n ) in this setting is the Markov chain (C(t), M (t)) on S 2 whose infinitesimal generator Ω is defined by, for x, y ∈ S,

(28) Ω(f )(x, y) = z∈S q(x, z)[f (z, y) -f (x, y)]½ {x =y} + z,z ′ ∈S q x p(x, z)p(x, z ′ )[f (z, z ′ ) -f (x, x)]½ {x=y}
for any function f on S 2 vanishing outside a finite set. The first coordinate is indeed a Markov chain with Q-matrix Q and when the cat and the mouse are at the same site x, after an exponential random time with parameter q x they jump independently according to the transition matrix P . Note that if one looks at the sequence of sites visited by (C(t), M (t)) then it has the same distribution as the cat and mouse Markov chain associated to the matrix P . For this reason, the results obtained in Section 2 can be proved easily in this setting. In particular (C(t), M (t)) is null recurrent when (C(t)) is reversible. Proposition 6. If, for t ≥ 0,

U (t) = t 0 ½ {M(s)=C(s)} ds
and S(t) = inf{s > 0 : U (s) ≥ t} then the process (M (S(t))) has the same distribution as (C(t)), i.e. it is a Markov process with Q-matrix Q.

This proposition simply states that, up to a time change, the mouse moves like the cat. In discrete time this is fairly obvious, the proof is in this case a little more technical.

Proof. If f is a function S, then by characterization of Markov processes, one has that the process (H(t)) def.

= f (M (t)) -f (M (0)) -t 0 Q( f )(C(s), M (s)) ds is a local martingale with respect to the natural filtration (F t ) of (C(t), M (t)), where f : S 2 → R such that f (x, y) = f (y) for x, y ∈ S. The fact that, for t ≥ 0, S(t) is a stopping time, that s → S(s) is non-decreasing and Doob's optional stopping theorem imply that (H(S(t))) is a local martingale with respect to the filtration (F S(t) ). Since is a local martingale for any function f on S. This implies that (M (S(t))) is a Markov process with Q-matrix Q, i.e. that (M (S(t))) has the same distribution as (C(t)). See Rogers and Williams [START_REF] Rogers | Diffusions, Markov processes, and martingales[END_REF].

The example of the M/M/∞ process. The example of the M/M/∞ queue is investigated in the rest of this section. The associated Markov process can be seen as an example of a discrete Ornstein-Uhlenbeck process. As it will be shown, there is a significant qualitative difference with the example of Section 4 which is a discrete time version of the M/M/1 queue. The Q-matrix is given by [START_REF] Yor | Exponential functionals of Brownian motion and related processes[END_REF] q(x, x + 1) = ρ, q(x, x -1) = x

The corresponding Markov chain is positive recurrent and reversible and its invariant probability distribution is Poisson with parameter ρ. If C(0) = n, then T 0 / log n converges in distribution to 1.

See Chapter 6 of Robert [START_REF] Robert | Stochastic networks and queues[END_REF]. It should be remarked that the duration of time it takes to reach n starting from 0 is essentially the time it takes to go to n starting from n -1. where (E i ) are i.i.d. exponential random variables with parameter 1. For 1 ≤ i ≤ n, E i is the service time of the ith initial customer. At time τ , the process of the mouse will have run only for U (τ ), so the ith customer is still there if E i > U (τ ). Consequently, by conditioning on the value of U (τ ), by the law of large numbers one obtains that the sequence (M (τ )/n) converges in distribution to the random variable F def.

= exp(-U (τ )). The dynamic of the cat and mouse gives that: -On the event τ ≥ T 0 , necessarily M (τ -) = C(τ -) = 0, thus the quantity P(τ ≥ T 0 ) ≤ P(M (τ ) = 1) converges to 0. -Just before time τ , the mouse and the cat are at the same location and

P(C(τ ) = M (τ -) -1) = E M (τ -) ρ + M (τ -)
converges to 1 as n gets large. If ε > 0, then

E P M(τ )-1 (T 0 ≥ T M(τ ) ) ≤ P M (τ ) n ≤ ε + sup k≥⌊εn⌋ P k (T 0 ≥ T k+1 ),
hence, by Proposition 7, for ε [resp. n] sufficiently small [resp. large], the above quantity is arbitrarily small. This result implies that the probability of the event {M (τ ) = M (T 0 )} converges to 1. The Proposition is proved.

A Multiplicative Phenomenon. If C(0) = 0 and M (0) = n, the next time the cat returns to 0, Proposition 8 shows that the mouse will be at a location of the order of nF 1 , where F 1 = exp(-E 1 /ρ) and E 1 is an exponential random variable with parameter 1. After the pth round, the location of the mouse is of the order of (30) n p k=1

F k = n exp - 1 ρ p k=1 E k ,
where (E k ) are i.i.d. with the same distribution as E 1 . A precise statement of this non-rigorous statement can be formulated easily. From Equation (30), one gets that after a Poisson number of rounds with parameter ρ log n, the location of the mouse is within a finite interval. The corresponding result for the reflected random walk exhibits an additive behavior. Theorem 5 gives that the location of the mouse is of the order of (31) n + p i=1 A i after p rounds, where the common distribution of the (A k ) is given by the generating function of Relation [START_REF] Guillemin | AIMD algorithms and exponential functionals[END_REF]. In this case the number of rounds after which the location of the mouse is located within a finite interval is of the order of n. As Theorem 5 shows, for the reflected random walk, t → ρ -n t is a convenient time scaling to describe the location of the mouse until it reaches a finite interval.

3. 2 . 4 . 1 .

 241 Random Walk in the Plane. The transition matrix P of this random walk is given by, forx ∈ Z 2 , p(x, x+(1, 0)) = p(x, x-(1, 0)) = p(x, x+(0, 1)) = p(x, x-(0, 1)) = 1Definition Let e 1 =(1, 0), e -1 =-e 1 , e 2 =(0, 1), e -2 =-e 2 and the set of unit vectors of Z 2 is denoted by E = {e 1 , e -1 , e 2 , e -2 }. If (C n ) is a random walk in the plane, (R n ) denotes the sequence in E such that (R n ) is the sequence of unit vectors visited by (C n ) and (11) r ef def.= P(R 1 = f | R 0 = e), e, f ∈ E.

  e), (e, -e)) = 1/3, Q R ((e, e), (e, e)) = Q R ((e, e), (e, -e)) = 1/3, with the convention that e, -e are the unit vectors orthogonal to e, µ R denotes the invariant probability distribution associated to Q R and D E is the diagonal of E 2 .

S(t) 0 QS(t) 0 ½ 0 Q

 000 ( f )(C(s), M (s)) ds = y∈S S(t) 0 q(M (s), y)½ {C(s)=M(s)} (f (y) -f (M (s))) ds = {C(s)=M(s)} Q(f )(M (s)) ds = t (f )(M (S(s))) ds, one gets therefore that f (M (S(t))) -f (M (0)) -t 0 Q(f )(M (S(s))) ds

Proposition 7 .

 7 If C(0) = x ≤ n -1 andT n = inf{s > 0 : C(s) = n},then, as n tends to infinity, the variable T n /E x (T n ) converges in distribution to an exponentially distributed random variable with parameter 1 andlim n→+∞ E x (T n )ρ n /(n -1)! = e -ρ .

Proposition 8 .½

 8 If C(0) = M (0) = n, andT 0 = inf{s > 0 : C(s) = 0},then, as n goes to infinity, the random variable M (T 0 )/n converges in distribution to a random variable F on [0, 1] such that P(F ≤ x) = x ρ .Proof. Let τ = inf{s > 0 : M (s) = M (s-) + 1} be the instant of the first upward jump of (M (s)). Since (M (S(s))) has the same distribution as (C(s)) one gets that U (τ ) is an exponential random variable with parameter ρ and, since there is no arrival up to time τ , then M (τ ) {Ei>U(τ )} ,

This is not the case for the M/M/∞ queue, since the duration of the first round of the cat, of the order of (n -1)!/ρ n by Proposition 7, dominates by far the duration of the subsequent rounds, i.e. when the location of the mouse is at xn with x < 1.

Litvak gratefully acknowledges the support of The Netherlands Organisation for Scientific Research (NWO) under Meervoud grant no. 632.002.401.


domain: phys spi

text:
Des Palais

VERSAILLES France Congres

Joris Gorée
email: joris.goree@onera.fr

Sophie Derelle

Edouard Huard De Verneuil

Julien Jaeck

Olivier Gravrand
email: olivier.gravrand@cea.fr

Olivier Boulade
email: olivier.boulade@cea.fr

Jérome Primot

DEVELOPMENT OF A CRYOGENIC SPOT SCAN BENCH FOR THE STUDY OF MID-INFRARED DETECTORS

Keywords: Pixel spatial response, Spot scan, Infrared, Cryogenics

In this article, we present a cryogenic spot scan bench dedicated to the 3-5.5 µm spectral band currently under development in the MIRCOS platform at ONERA. Initial tests have been carried out on a 30 µm pitch HgCdTe focal plane array, and improvements are underway to characterize the spatial response of detectors with smaller pixel pitches.

INTRODUCTION

Astrophysical requirements in terms of spatial and spectral resolution imply the development of larger format focal plane arrays (FPA), especially for quantum cooled infrared detectors. That generally leads to a reduction in pixel pitch. During the last twenty years, the pixel pitch has been reduced from 30µm to 15µm [START_REF] Castelein | Detectors and Associated Signal Processing[END_REF], 12µm [START_REF] Strong | Performance of 12µm to 15µm Pitch MWIR and LWIR HgCdTe FPAs at Elevated Temperatures[END_REF], 10µm [START_REF] Gravrand | Issues in HgCdTe Research and Expected Progress in Infrared Detector Fabrication[END_REF] and even 5µm [START_REF] Shkedy | HOT MWIR detector with 5µm pitch[END_REF][START_REF] Huang | Small pixel MWIR sensors for low SWaP applications[END_REF]. Precise knowledge of the spatial response of the pixel through modulation transfer function (MTF) and/or point spread function (PSF) is required but harder to determine as the pixel pitch decreases. These figures of merit reflect the ability of the detector to spatially reproduce the contrast of fine details in the scenery. Measurement of PSF/MTF is critical, on the one hand, for manufacturers in order to optimize pixel design, and on the other hand, for the astrophysics community in the context of the development and operation of scientific instruments. This work is supported by the LabEx FOCUS (FOCal plane array for Universe Sensing) gathering nine major French laboratories that bring their expertise in the detection field to contribute to the development of better detectors for astronomy and Earth observation.

PSF measurements on cooled infrared FPAs strongly depend on the packaging that usually limits access to the detector and thus the fineness of the projected patterns. These patterns are generally limited by diffraction which depends on the aperture number N of the cold shield. The diameter of the first black ring of the Airy pattern, equal to 2.44𝜆𝑁, is for instance around 24.4µm for 𝜆 = 5µ𝑚 and 𝑁 = 2 which is a classical aperture number for cooled infrared FPAs.

To address this issue, ONERA developed in 2018 a versatile cryogenic test platform called MIRCOS (Moyen Infrarouge Refroidi pour la Caractérisation d'Optiques et de Systèmes), which can host different cooled projection system located in the same cold shield as the detector. Such a bench makes it possible to project very fine patterns while considerably reducing the ambient thermal background and then improving the signal-to-noise ratio. This bench has been previously used in [START_REF] Huard | Development of a Cryogenic Test Bench for Spectral MTF Measurement on Midwave Infrared Focal Plane Arrays[END_REF] to evaluate the MTF of a specific HgCdTe MWIR FPA using a 2D interferometric method developed at ONERA. This paper describes the spot scan method currently in development.

DESCRIPTION OF THE SPOT SCAN BENCH

MIRCOS cryogenic chamber

An illustration and a picture of the bench are presented in Fig. 1 and Fig. 2. The light beam comes from a blackbody heated at 1473 K, which illuminates a hole placed at the focal point of the collimator. Then, the collimated beam goes through a 60mm diameter ZnSe window of the vacuum chamber (10 -6 bar) and enters into the cryogenic chamber cooled at 80K. A narrow bandpass filter can be added in front of the window in order to limit the blackbody spectral band.

Cooling is achieved by pouring liquid nitrogen into the cold table and the final temperature is generally reached in approximatively 5 hours. The temperature is maintained at 80K by using an electrovalve (placed on a self-pressurised liquid nitrogen dewar) monitored by two temperature Additional probes provide real-time monitoring of the temperature on different components (projection systems, cold shield…) inside the cryogenic chamber.

The advantage of MIRCOS is that different systems can be integrated into the same cold shield as the detector, which will allow a large optical aperture. For this purpose, the cryogenic chamber is 56cm long, 39cm large and 40cm high while the cold shield is 42cm long, 17cm large and 20cm high.

Cryogenic objective

The projection system used to measure the PSF of the detector is an objective designed and manufactured by Winlight System, as it is shown in Fig. 2. It operates in the MWIR (Mid-Wave Infrared, 3-5.5 µm) band and has a focal length of 25 mm. The aperture number N is equal to 1.2. It has been designed to operate in a finite-to-finite configuration at a working temperature of 80K. This configuration is achieved by placing a 15µm diameter pinhole object at a distance of 215mm from the principal object plane of the objective so that the magnification equals 1/3. A condenser focuses the collimated incoming light on the pinhole increasing the signal-to-noise ratio. The pinhole and the condenser are mechanically bound to the objective. This overall setup has two advantages: it allows a precise centring of the pinhole with the objective. The theoretical size of the geometric image is smaller than the first black ring of the objective Airy spot (which is about 12µm at 4µm of wavelength). The geometric image is also equivalent to the FWHM (Full Width at Half Maximum) of the objective Airy spot (which is about 4.9µm at 4µm of wavelength).

In order to perform deconvolution on the measured PSF, a fine optical characterization of the objective will be carried out.

Cryogenic linear stages

In order to scan the spot on the detector along three translation axes, cryogenic linear stages are installed inside the cold shield. Those stages have a maximum course of 20 mm, which allow covering the whole surface of the detector enough. However, the vertical stage tolerates a maximum weight of 200g, which roughly corresponds to the weight of the spot scan objective. Therefore, we chose to use a counterweight to lighten the load on the vertical stage and thus allow the system to move properly. The counterweight can be seen in Fig. 1.

RESULTS OF BENCH VALIDATION

Measurements presented in this section have been performed with a 30µm pixel pitch HgCdTe MWIR FPA whose MTF has been previously measured with an interferometric approach [START_REF] Huard | Development of a Cryogenic Test Bench for Spectral MTF Measurement on Midwave Infrared Focal Plane Arrays[END_REF]. As a first step, those measurements were performed without any filter.

Simulation of optical PSF

Fig. 3 shows the theoretical monochromatic PSF of the objective simulated from the computeraided design (CAD) provided by Winlight under ZEMAX©. In the ideal case, if the objective is diffraction limited, the FWHM will change from 3.3µm at a wavelength of 2.9µm to 6.4µm at a wavelength of 5.5µm, corresponding to a broadening of 3µm. Therefore, we planned to characterize the objective using several narrow filters in order to be able to retrieve the spectral dependency

First spot image

Firstly, it is necessary to check the conformity of a measurement of an image focused on the detector. Fig. 4 shows the focused spot with its energy distribution. New measurements will soon be carried out with narrow spectral filters and will be compared to simulated results.

Validation of the positioning of the spot

Secondly, the position of the light spot onto the detector must be in the same place for the same set point, so that the measurement is precise and repeatable.

Precise restitution of the spot position on the FPA can be obtained by defocusing the image in order to apply the barycentre method as is shown in Fig. 5.

From this defocused spot, first 2D scans were carried out in order to check the proper functioning of the linear stages (Fig. 6).

These first measurements allowed us to roughly validate the displacement of the spot on a 90x90µm area, which corresponds to 3x3 pixels. An analysis of the results showed that the precision of the displacements is presently limited by the accuracy of several elements of the measurement, including the reading position of linear stages. The resulting error is between 2 and 3 µm. This is not sufficient to perform accurate measurements on FPA with pixel pitch lower than 15µm. An interferometric system is currently being installed in the cryogenic bench to improve our knowledge of the position of the spot. The expected precision is lower than 200nm.

Optical alignment study

Finally, it is necessary to check that the optical bench is correctly aligned. It is important to know that 3 coordinate systems are involved into measurements: (𝑋, 𝑌, 𝑍) are the orthonormal coordinate reference system where 𝑍 ⃗ is the optical axis, (𝑋 𝐷 , 𝑌 𝐷 , 𝑍 𝐷 ) are the coordinate system linked to the detector, and (𝑋 𝑀 , 𝑌 𝑀 , 𝑍 𝑀 ) are the coordinate system linked to the linear stages. The latter is not necessarily an orthogonal system because each axis is linked to one different linear stage and each linear stage may not be perfectly mounted.

Nevertheless, those results do not prevent us from starting to study the optical alignment of the bench. Indeed, the 𝑍 𝑀 -scan along the mechanical axis allows estimating residual tilts between the mechanical axis, the optical axis and the axis perpendicular to the FPA. Fig. 7 shows the evolution of the position of the spot along the horizontal detector axis (𝑋 𝐷 -axis) while scanning along the mechanical axis (𝑍 𝑀 -axis). It is important to note that the barycentre estimation can no longer be used when the spot is focused onto one or very few pixels. (Typically, when |Δ𝑍 𝑀 | < 50µ𝑚).

The apparent slope indicates the presence of a residual tilt. However, this measurement combines two tilts (in the X-Z plane) between three different axes (optical axis, mechanical axis and axis perpendicular to the detector). A drawing showing the combination of the different residual tilts is shown in Fig. 8. 𝛼 is the tilt between the optical axis and the mechanical axis, and 𝛽 is the tilt between Assessment of β can be easier considering Eq. 3:

Eq.3 Δ𝑋 𝐷,2 = 𝑁 × 𝑝 𝑝𝑖𝑥𝑒𝑙 Δ𝑋 𝐷,2 corresponds to the displacement along the detector. 𝑁 is the number of pixels that separates Position 1 to Position 2. 𝑝 𝑝𝑖𝑥𝑒𝑙 is the pixel pitch.

FIRST ESTIMATION OF A PIXEL PSF

An initial extraction of the spatial response of the pixel during a serpentine scan (Fig. 6) allows comparison with measurements made using an interferometric technique on the same detector, as Fig. 10 shows.

The interferometric method consists in using a special gratingnamed CSIG for continuously selfimaging gratingto project 2D high-resolution patterns [START_REF] Huard | Development of a Cryogenic Test Bench for Spectral MTF Measurement on Midwave Infrared Focal Plane Arrays[END_REF] that can be predicted by wave physics simulations. A specific treatment in the Fourier space of the detected pattern allows then the restitution of the 2D pixel MTF. A reverse Fourier transform is eventually computed to retrieve the 2D pixel PSF. This method was used in a global way since all pixels contributed to the pattern. Thus, the measured MTF and PSF are the ones of an equivalent average pixel.

These preliminary measurements show a good agreement between results from two different approaches. This comparison is interesting because the illumination of the detector is very different: on the one hand, the interferometric method requires an illumination over the entire FPA and, on the other hand, the spot scan method requires an illumination on a single or very few pixels of the FPA.

CONCLUSION AND PERSPECTIVES

The MIRCOS bench has the advantage of being a versatile cryogenic setup. It currently hosts a new cryogenic spot scan objective that will enable us to directly measure the pixel PSF with an excellent signal-to-noise ratio. A preliminary validation has been made and the first results are encouraging. A methodology has been developed in order to reach the initial goals, that is to say being able to characterize FPA with pixel pitches lower than 10um.

Interferometric sensors are currently being installed in order to manage more precisely displacements of linear stages (expected precision

Figure 1 :

 1 Figure 1: Drawing of the PSF measurement bench

Figure 2 :

 2 Figure 2: Picture of the PSF measurement bench. Inside view of the cold shield.

Figure 2 :

 2 Figure 2: Spectral PSF simulation under ZEMAX© of the spot scan objective.

Figure 3 :Figure 4 :Figure 6 :Figure 7 :

 3467 Figure 3: Picture of a focused spot and its energy distribution

Figure 9 :

 9 Figure 9: Measured spatial response of a pixel obtained with two different approaches

Figure 10 :

 10 Figure 10: Second tilt measurement

lower than 200 nm). Moreover, a spectral characterization of the objective is currently underway with a wavefront analyser to determine the optical PSF. This measurement will be essential for the deconvolution step in the case of pixel pitches lower than 15µm.

Once the bench is fully developed and validated, spot scan measurements will be performed on different FPA of interest for LabEx FOCUS (for instance HgCdTe FPA with smaller pitches, type-II superlattice FPA).

ACKNOWLEDGEMENT

This project was partially funded by the DGA (Direction Générale de l'Armement), the ANR (Agence Nationale de Recherche) via the LabEx FOCUS (ANR-11-LBX-0013) and the Conseil Général de l'Essonne (A.S.T.R.E. program).

CONFLICT OF INTEREST

The authors declare that they have no conflict of interest.