---
abstract: 'This article examines large time behaviour and the second eigenvalue problem for Markovian mean-field interacting particle systems with jumps. Our first main result is on the time required for convergence of the empirical measure process of the particle system to its invariant measure; we show that, there is a constant $\Lambda \geq 0$ such that, when there are $N$ particles in the system and when time is of the order $\exp\{N(\Lambda+O(1))\}$, the process has mixed well and is very close to its invariant measure. We then obtain large-$N$ asymptotics of the second eigenvalue of the generator associated with the empirical measure process when it is reversible with respect to its invariant measure. We show that its absolute value scales like $\exp\{-N\Lambda\}$. The main tools used in establishing our results are the large deviation properties of the empirical measure process from its large-$N$ limit. As an application of the study of large time behaviour, we also show convergence of the empirical measure of the system of particles to a global minimum of a certain entropy function when particles are added over time in a controlled fashion. The controlled addition of particles is analogous to the cooling schedule associated with the search for a global minimum of a function using the simulated annealing algorithm.'
address:
- |
    Department of Electrical Communication Engineering\
    Indian Institute of Science\
    Bangalore 560012, India\
- |
    Department of Electrical Communication Engineering\
    and Robert Bosch Centre for Cyber Physical Systems\
    Indian Institute of Science\
    Bangalore 560012, India\
author:
- 
- 
bibliography:
- 'ims-template.bib'
title: 'Large Time Behaviour and the Second Eigenvalue Problem for Finite State Mean-Field Interacting Particle Systems'
---

Introduction {#section:introduction}
============

In this paper, we study large time behaviour and the second eigenvalue problem for Markovian mean-field interacting particle systems with jumps. Our motivation is to provide an understanding of metastable phenomena in engineered systems such as load balancing networks [@aghajani-etal-17; @aghajani-ramanan-19; @mukhopadhyay-etal-16; @mitzhenmaker-00; @graham-00], wireless local area networks [@bhattacharya-kumar-17; @benaim-leboudec-08; @bordenave-etal-12; @kumar-etal-06; @ramaiyan-etal-08; @bianchi-98], and in natural systems involving grammar acquisition, sexual evolution [@panageas-vishnoi-16; @panageas-etal-16], epidemic spread [@leonard-90; @djehiche-kaj-95], etc. These systems are briefly described in Section \[section:examples\].

Before we describe our main contributions, let us describe the setting of our mean-field interacting particle system.

The setting
-----------

Let there be $N$ particles. Each particle has a state associated with it which comes from a finite set $\mathcal{Z}$; the state of the $n$th particle at time $t$ is denoted by $X_n^N(t) \in \mathcal{Z}$, where the superscript $N$ indicates that there are $N$ particles in the system. The empirical measure of the system of particles at time $t$ is defined by $$\begin{aligned}
\mu_N(t) \coloneqq \frac{1}{N} \sum_{n=1}^N \delta_{X_n^N(t)} \in M_1(\mathcal{Z}),\end{aligned}$$ where $\delta_{\cdot}$ denotes the Dirac measure. Here, $M_1(\mathcal{Z})$ denotes the space of probability measures on $\mathcal{Z}$ equipped with the topology of weak convergence. Note that $\mu_N(t)$ is a random measure, i.e., an $M_1(\mathcal{Z})$-valued random variable. Each particle has a set of allowed transitions; to define this, let $(\mathcal{Z}, \mathcal{E})$ be a directed graph with the interpretation that whenever $(z,z^\prime) \in \mathcal{E}$, a particle in state $z$ is allowed to move from $z$ to $z^\prime$. To specify the interaction among particles and evolution of the states of the particles over time, for each $(z,z^\prime) \in \mathcal{E}$, we are given a function $\lambda_{z,z^\prime}: M_1(\mathcal{Z}) \to [0, \infty)$. We consider the generator $\Psi^N$ acting on functions $f$ on $\mathcal{Z}^N$ by

$$\begin{aligned}
\Psi^N f(\mathbf{z}^N) = \sum_{n=1}^N \sum_{z_n^\prime: (z_n, z_n^\prime) \in \mathcal{E}} \lambda_{z_n, z_n^\prime}(\overline{\mathbf{z}^N}) (f(\mathbf{z}^N_{n,z_n,z_n^\prime}) - f(\mathbf{z}^N));\end{aligned}$$

here $\overline{\mathbf{z}^N} = \frac{1}{N}\sum_{n=1}^N \delta_{z_n} \in M_1(\mathcal{Z})$ denotes the empirical measure associated with the configuration $\mathbf{z}^N \in \mathcal{Z}^N$, and $\mathbf{z}^N_{n,z_n,z_n^\prime}$ denotes the resultant configuration of the particles when the $n$th particle changes it state from $z_n$ to $z_n^\prime$.

We make the following assumptions on the model:

1.  The graph $(\mathcal{Z}, \mathcal{E})$ is irreducible. \[assm:a1\]

2.  The functions $\lambda_{z,z^\prime}(\cdot)$, $(z,z^\prime) \in \mathcal{E}$, are Lipschitz on $M_1(\mathcal{Z} )$ and there exist positive constants $c, C $ such that $c \leq \lambda_{z,z^\prime}(\xi) \leq C$ for all $(z,z^\prime) \in \mathcal{E}$ and all $\xi \in M_1(\mathcal{Z})$. \[assm:a2\]

Let $D([0, \infty), \mathcal{Z}^N)$ denote the space of $\mathcal{Z}^N$-valued functions on $[0, \infty)$ that are right continuous with left limits (càdlàg), equipped with the Skorohod-$J_1$ topology (see [[@ethier-kurtz Chapter 3]]{}). Note that, under the Lipschitz assumption \[assm:a2\] on the transition rates, the $D([0, \infty), \mathcal{Z}^N)$-valued martingale problem for $\Psi^N$ is well posed (see [[@ethier-kurtz Exercise 15, Section 4.1]]{}); therefore, given an initial configuration of particles $(X_n^N(0), 1 \leq n \leq N) \in \mathcal{Z}^N$, we have a Markov process $\left( (X_n^N(t), 1 \leq n \leq N),  t \geq 0\right) $ on the space $D([0,\infty),\mathcal{Z}^N)$. To describe the process in words, a particle in state $z$ at time $t$ moves to state $z^\prime$ at rate $\lambda_{z,z^\prime}(\mu_N(t))$, independent of everything else; i.e., the evolution of the state of a particle depends on the states of the other particles via the empirical measure of states of all the particles, hence the name mean-field interaction.

We now describe another Markov process associated with the particle system. Consider the mapping $$\begin{aligned}
\left( (X_n^N(t), 1 \leq n \leq N),  t \geq 0\right) \mapsto \left( \frac{1}{N} \sum_{n=1}^N \delta_{X^N_n(t)}, t \geq 0\right) = (\mu_N(t), t \geq 0)\end{aligned}$$ that maps the evolution of the states of all the particles to the empirical measure process $(\mu_N(t), t \geq 0)$. This process is also Markovian with state space $M_1^N(\mathcal{Z})$ – the elements of $M_1(\mathcal{Z})$ that can arise as empirical measures of $N$-particle configurations. Its generator $L^N$ acting on functions $f$ on $M_1^N(\mathcal{Z})$ is given by $$\begin{aligned}
L^N f(\xi) = N \sum_{(z,z^\prime) \in \mathcal{E}} \xi(z) \lambda_{z,z^\prime}(\xi) \left[f\left( \xi + \frac{\delta_{z^\prime}}{N} - \frac{\delta_z}{N}\right) - f(\xi)  \right].\end{aligned}$$

The mean-field limit
--------------------

It often turns out that we can study various properties of our particle system by examining its macroscopic behaviour encoded in the process $\mu_N$. Towards this, we often approximate the process $\mu_N$, for large $N$, using a deterministic dynamical system. This approximation is often referred to as the mean-field limit.

Under assumptions \[assm:a1\] and \[assm:a2\], one can show the following law of large numbers [@mckean-67; @gartner-88; @sznitman-91; @benaim-leboudec-08]. Suppose that the initial conditions $\{\mu_N(0)\}_{N \geq 1}$ converge weakly to a deterministic measure $\nu \in M_1(\mathcal{Z})$. Then for any fixed $T > 0$, the empirical measure process $(\mu_N(t), 0 \leq t \leq T)$ converges in $D([0,T],M_1(\mathcal{Z}))$ to the solution to the ODE $$\begin{aligned}
\dot{\mu}(t) = \Lambda_{\mu(t)}^* \mu(t), \, 0 \leq t \leq T, \, \mu(0) = \nu,
\label{eqn:MVE}\end{aligned}$$ where, for any $\xi \in M_1(\mathcal{Z})$, $\Lambda_{\xi}$ denotes the $|\mathcal{Z}|\times |\mathcal{Z}|$ rate matrix when the empirical measure is $\xi$ (i.e. $\Lambda_\xi(z,z^\prime)= \lambda_{z,z^\prime}(\xi)$ for $(z,z^\prime) \in \mathcal{E}$, $\Lambda_{\xi}(z,z^\prime) = 0$ when $(z,z^\prime) \notin \mathcal{E}$, and $\Lambda_{\xi}(z,z) = -\sum_{z^\prime \neq z} \lambda_{z,z^\prime}(\xi)$ for $z \in \mathcal{Z}$), $\Lambda^*_\xi$ denotes its transpose, and $D([0,T],M_1(\mathcal{Z}))$ denotes the space of $M_1(\mathcal{Z})$-valued càdlàg functions on $[0,T]$ equipped with the Skorohod-$J_1$ topology (we assume that all paths are left continuous at $T$). The above ODE is referred to as the McKean-Vlasov equation. The assumption \[assm:a2\] on the Lipschitz continuity of the transition functions $\lambda_{z,z^\prime}$ implies that the above ODE is well-posed. Therefore, for large values of $N$, the above mean-field convergence result suggests that one can approximate the trajectory of the empirical measure process $\mu_N$ using the McKean-Vlasov equation, and hence, one can study properties of the process $\mu_N$ from that of the ODE (\[eqn:MVE\]).

One can also show convergence in the stationary regime. Take for instance the situation when the McKean-Vlasov equation has a unique globally asymptotically stable equilibrium. Since $\mu_N$ is a Markov process on a finite set and is irreducible (by assumption \[assm:a1\]), there exists a unique invariant probability measure for the process $\mu_N$ which we denote by $\wp_N$. (Note that this is a probability measure on $M_1(\mathcal{Z})$.) Let $\xi^* \in M_1(\mathcal{Z})$ denote the unique globally asymptotically stable equilibrium of the McKean-Vlasov equation (\[eqn:MVE\]). One can then show that $\wp_N$ converges weakly to $\delta_{\xi^*}$ as $N \to \infty$, the point mass at $\xi^*$ (see [@benaim-leboudec-08; @bordenave-etal-12]). This also suggests that we can understand the stationary behaviour of the $N$-particle system by examining the limiting behaviour of the deterministic McKean-Vlasov equation, i.e. we can effectively “interchange" the limits $N \to \infty$ and $t \to \infty$ of $\mu_N(t)$ to understand its stationary behaviour, when the McKean-Vlasov equation has a unique globally asymptotically stable equilibrium. Settings when this is not the case are what we study in this paper.

Motivation, contributions, and outline of the paper
---------------------------------------------------

We now describe the questions that we address in this paper and highlight our main results.

Suppose that the limiting McKean-Vlasov equation (\[eqn:MVE\]) has multiple $\omega$-limit sets (multiple stable equilibria and/or limit cycles). If we focus on a fixed time interval $[0,T]$, let the number of particles $N \to \infty$ and let the initial conditions $\mu_N(0)$ converge weakly to a deterministic limit $\nu$, then the mean-field convergence suggests that the empirical measure process tracks the solution to the McKean-Vlasov equation (\[eqn:MVE\]) over $[0,T]$ starting at $\nu$. If we then let $t \to \infty$, the solution to the McKean-Vlasov equation goes to an $\omega$-limit set of (\[eqn:MVE\]) depending on the initial condition $\nu$. On the other hand, for a large but fixed $N$, the process would track the McKean-Vlasov equation with very high probability, and as time becomes large, would thus enter a neighbourhood of the $\omega$-limit set corresponding to the initial condition $\nu$; however, since $N$ is finite, the process can exit the basin of attraction of this $\omega$-limit set. It is then likely to remain in a neighbourhood of another $\omega$-limit set for a large amount of time before transiting to the next one, and so on. These are examples of *metastable phenomena,* and it turns out that the sojourn times in the basin of attraction of an $\omega$-limit set are of the order $\exp\{O(N)\}$, as we shall soon see. One of the aims of our paper is to quantify such metastable phenomena, namely

1.  the mean time spent by the process near an $\omega$-limit set,

2.  the probability of reaching a given $\omega$-limit set before reaching another one,

3.  the probability of traversing a given set of $\omega$-limit sets in a particular order,

and so on. These quantifications help predict the performance of engineering systems, some of which we will describe in Section \[section:examples\]. We study the aforementioned metastability questions in Section \[section:large\_time\_behaviour\]. Such large time phenomena for diffusion processes with a small noise parameter have been studied in the past by Freidlin and Wentzell [@freidlin-wentzell] under the “general position condition" (see [[@freidlin-wentzell Sections 6.4-6.6]]{}). Hwang and Sheu [@hwang-sheu-90] studied large time behaviour for diffusion processes under a more general setup. The key in both these works is the large deviation properties of the small noise diffusion processes over finite time durations, which have been established in [[@freidlin-wentzell Chapter 5]]{}. In this paper, we extend the analysis to Markov mean-field jump processes, specifically $(\mu_N(\cdot))_{N \geq 1}$. The tools that we use in our paper are similar to those used by Hwang and Sheu, along with the large deviation properties of our process $\mu_N$ over finite time durations, which have been established by L[é]{}onard [@leonard-95] and Borkar and Sundaresan [@borkar-sundaresan-12].

Our study of the large time behaviour of the process $\mu_N$ (i.e., (i)-(iii) above) enables us to show our first main result: there exists a constant $\Lambda \geq 0$ such that, if time is of the order $\exp\{N(\Lambda+O(1))\}$, then the process $\mu_N$ is very close to its invariant measure (see Theorem \[thm:conv\]). Conversely, when $\Lambda > 0$ and when time is of the order $\exp\{N(\Lambda - \delta) \}$ with $\delta > 0$ arbitrarily small, the process may not have reached a neighbourhood of the “most stable" equilibria, with nontrivial probability in the exponential scale (see Theorem \[thm:mixing\]). A similar result for the mean-field discrete-time setting but without the specification of the constant $\Lambda$ was established by Panageas and Vishnoi [@panageas-vishnoi-16]. Let us reemphasise that our setting is a continuous time setting. Further, our desire to identify the constant $\Lambda$ demands that we must study the large deviation asymptotics in some detail in the continuous time setting. The proof of our theorem is similar to that of [[@hwang-sheu-90 Theorem 2.1, Part I]]{}, where similar results are established for convergence to the invariant measure for small noise diffusions.

The next question that we want to understand is the asymptotics of the second eigenvalue of the generator $L^N$ of the Markov process $\mu_N=(\mu_N(t), t \geq 0)$ when it is reversible with respect to its invariant measure. This study is motivated by the fact that, for a fixed $N$, the convergence speed of the process $\mu_N$ to its invariant measure (over time) can be understood by studying the modulus of the second eigenvalue of the generator of $\mu_N$. We show that, for the same constant $\Lambda$ above, the modulus of the second eigenvalue scales like $\exp\{-N\Lambda\}$ (see Theorem \[thm:eval\_problem\]). It turns out that $\Lambda$ can be positive only when there are metastable states in the limiting dynamics. In such situations, one expects slower convergence to the invariant measure for large values of $N$. On the other hand, $\Lambda$ can be $0$, for example, when the limiting dynamics (\[eqn:MVE\]) has a unique globally asymptotically stable equilibrium; in this special case, convergence of $\mu_N$ to its invariant measure does not suffer from the slowing down phenomenon associated with positive $\Lambda$. In fact, Panageas and Vishnoi [@panageas-vishnoi-16] and Panageas et al. [@panageas-etal-16] show that the mixing time is $O(\log N)$ in the discrete-time setting. Kifer [@kifer-90] considers a more restrictive discrete-time model, which does not cover the mean-field model, and identifies the constant analogous to $\Lambda$ [@kifer-90 Theorem 4.3]. The restriction is that the state space of $\mu_N$ is the same for each $N$ and that a certain uniform finite duration large deviation principle should hold with the rate function satisfying a continuity property. One can view our result as an extension of Kifer’s [@kifer-90 Theorem 4.3] to the continuous time *mean-field* setting, where the state space of the Markov process $\mu_N$ changes with $N$. Hwang and Sheu [@hwang-sheu-90] establish a result similar to ours on the scaling of the second eigenvalue of a reversible small noise diffusion process, and our method of proof is inspired by their approach.

As an application of the large time behaviour of $\mu_N$, we also study convergence of the empirical measure process to a global minimum of a natural ‘entropy’ function when particles are injected over time at a specific rate reminiscent of the simulated annealing algorithm’s cooling schedule, $N(t) = \lfloor \frac{\log (2+t)}{c^* + \delta}\rfloor$ for a suitable $c^*$ and any $\delta > 0$. The convergence to a global minimum holds for all starting points (see Theorem \[thm:conv-globalmin\]). Such approaches may be of use in situations where a population growth schedule is applied in order to engineer the mean-field system’s move to a desired equilibrium point as time $t \to \infty$. One can also use this approach to study numerically the most likely region in which the process $\mu_N$ spends time for large values of $N$, under stationarity. Again, our proof is inspired by the analysis of the simulated annealing algorithm in [[@hwang-sheu-90 Part III]]{}.

The rest of the paper is organised as follows. In Section \[section:ldp\_finite\], we discuss a known large deviation principle for the empirical measure process $\mu_N$ over a finite time horizon. This result plays an important role in the study of large time behaviour of $\mu_N$ and the large deviation principle for the invariant measure $\{\wp_N\}_{N\geq 1}$. We then study the large time behaviour of the process $\mu_N$ in Section \[section:large\_time\_behaviour\], and prove our first main result on the proximity of the law of $\mu_N$ to its invariant measure. In Section \[section:eval\_problem\], we study the asymptotics of the second eigenvalue of the generator of the process $\mu_N$ in the reversible case. Finally, in Section \[section:conv\_global\_minimum\], we study the convergence of the empirical measure process to a global minimum of the aforementioned ‘entropy’ function when particles are injected into the system at a suitable rate.

Examples {#section:examples}
--------

The mean-field interacting particle system that we have described can be used to model many interesting phenomena that arise in various domains such as physics, engineering, biology, etc. In this section, we shall describe some applications that are relevant to communication networks and shall point to the related literature that study these applications via mean-field models. We remark that, as far as the applicability of the mean-field model is concerned, the examples and the related literature that we have mentioned below are by no means exhaustive.

The first example is load balancing in networks. We describe the simplest model, the power of two choices, studied by Mitzenmacker [@mitzhenmaker-00]. Here, each particle is a single server $M/M/1$ queue, and the state represents the number of customers waiting in the queue. In load balancing, one is interested in routing the incoming customers to an appropriate queue so as to minimise the average delay experienced by a customer. The obvious way to do this is to route the customer to a queue with the least number of waiting customers. But, since there are a large number of queues, polling all of them and finding the ones with the least number of customers is expensive. So a simple alternative is to pick a queue at random and route the incoming customer to that queue, which is studied in [@graham-00]. It turns out that, if we pick two queues at random and route the customer to the least loaded queue between the two (with ties broken uniformly at random), the delay decreases dramatically. This algorithm demonstrates the power of two choices, and the evolution of the state of each queue under this algorithm can be described using the mean-field model which has been used to analyse the delay performance [@mitzhenmaker-00]. For related problems on load balancing in networks, see Mukhopadhyay et al. [@mukhopadhyay-etal-16] who study heterogenous servers, Aghajani et al. [@aghajani-etal-17; @aghajani-ramanan-19] who study non-Markovian queues, etc., and the references therein. Note that one important difference with our setting is that the state space of a queue is countably infinite in this class of problems. The finite state space model arises in the above settings when the buffers are finite and packets arriving at a fully buffered queue are lost.

Another example arises in the modelling of a wireless local area network (WLAN). Here, each particle is a wireless node trying to access a common medium, and the state of a particle represents the aggressiveness with which a packet transmission is attempted. The nodes interact with each other via the medium access control (MAC) protocol implemented in the system. Whenever a wireless node encounters a collision due to a transmission from another node, it changes its state to a less aggressive one, and whenever it succeeds, it changes its state to a more aggressive one. Therefore, the evolution of the state of a node depends on the empirical measure of the states of all the nodes, as in our mean-field model. This model was first proposed by Bianchi [@bianchi-98] and has proved to be very successful in analysing the performance of the MAC protocol; other works that focus on the WLAN application include: Bordenave et al. [@bordenave-etal-12] who studied a two time scale mean-field interacting particle system with a fast varying background process to model partial interference among nodes, Kumar et al. [@kumar-etal-06] who used the mean-field model to study the performance of WLANs using a fixed-point analysis, Ramaiyan et al. [@ramaiyan-etal-08] and Bhattacharya and Kumar [@bhattacharya-kumar-17] who looked at the problem of short term unfairness using the aforementioned fixed-point analysis, etc. Note that our model is a continuous-time modification of the discrete-time models in the above papers. Yet the continuous time model provides accurate predictions on the discrete-time model; see [[@borkar-sundaresan-12 page 4]]{}. For a continuous-time model, see Boorstyn et al. [@boorstyn-etal-87].

Other applications that use the mean-field model include analysis and control of spread of epidemics in networks [@benaim-leboudec-08; @akhil-etal-19; @leonard-90; @djehiche-kaj-95], dynamic routing in circuit-switched networks [@anantharam-91], scheduling in cellular systems [@manjerkar-etal-14], game-theoretic modelling and analysis of behaviour of agents in societal networks [@reiffers-sundaresan; @li-etal-15], etc.

Large deviations over finite time durations {#section:ldp_finite}
===========================================

In this section, we present a large deviation principle for the process $\mu_N$ over finite time durations. This result will be used later to study the large-time behaviour of $\mu_N$ and the rate of convergence of $\mu_N$ to its invariant measure.

Fix $T>0$. We introduce some notations. Let $p_{\nu_N}^{(N)}$ denote the solution to the $D([0,T], M_1(\mathcal{Z}))$-valued martingale problem for $L^N$, i.e., the law of the empirical measure process $(\mu_N(t), 0 \leq t \leq T)$, and let $p_{\nu_N,T}^{(N)}$ denote the law of the terminal-time empirical measure $\mu_N(T) \in M_1(\mathcal{Z})$, with initial condition $ \mu_N(0) = \nu_N $. Let $\mathcal{AC}[0,T]$ denote the space of absolutely continuous $M_1(\mathcal{Z})$-valued paths on $[0,T]$ (in particular they are differentiable for almost all $t \in [0,T]$; see [[@leonard-95 Definition 3.1]]{}). Define $$\begin{aligned}
\tau^*(u) \coloneqq \left\{
\begin{array}{lll}
\infty & \text{ if } u < -1 \\
1 & \text{ if } u = -1 \\
(u+1) \log (u+1) - u& \text{ if } u > -1,
\end{array}
\right.\end{aligned}$$ which is the Fenchel-Legendre transform of $\tau(u) = e^u-u-1, u \in \mathbb{R}$. We recall the following large deviation principle (LDP) for the sequence $\{p_{\nu_N}^{(N)}\}_{N \geq 1}$ on $D([0,T], M_1(\mathcal{Z}))$ (see [[@leonard-95 Theorem 3.1]]{}, [[@borkar-sundaresan-12 Theorem 3.2]]{}). See [[@dembo-zeitouni Section 1.2]]{} for the definition of LDP and a good rate function.

Suppose that the initial conditions $\nu_N \to \nu$ in $M_1(\mathcal{Z})$. Then the sequence of probability measures $\{p_{\nu_N}^{(N)}, N\geq 1\}$ on the space $D([0,T], M_1(\mathcal{Z}))$ satisfies the LDP with a good rate function $S_{[0,T]}(\mu|\nu)$. Moreover, if $S_{[0,T]}(\mu|\nu) < \infty$, then $\mu \in \mathcal{AC}[0,T],\,  \mu(0) = \nu$ and there exists a family of rate matrices $L(t), 0 \leq t \leq T$ such that $\mu$ is the unique solution to $$\begin{aligned}
\dot{\mu}(t) = L(t)^* \mu(t), \, 0 \leq t \leq T, \, \mu(0) = \nu,\end{aligned}$$ and $$\begin{aligned}
& S_{[0,T]}(\mu|\nu) =  \int_{[0,T]} \sum_{(i,j)\in \mathcal{E}} \mu(t)(i) \lambda_{i,j}(\mu(t)) \tau^*\left( \frac{l_{i,j}(t)}{\lambda_{i,j}(\mu(t))} -1 \right) dt.\end{aligned}$$ \[thm:finite-duration-ldp\]

We can interpret the rate function $S_{[0,T]}$ as follows. Starting at $\nu_N$, the process $\mu_N$ is likely to be in the neighbourhood of the solution to the McKean-Vlasov equation (\[eqn:MVE\]) with initial condition $\nu$ (with very high probability). In order for the process $\mu_N$ to be in the neighbourhood of some other path, we need to apply a control given by the rate matrix $L$; $S_{[0,T]}(\mu|\nu)$ is the cost of this control. In particular, since the solution to the McKean-Vlasov equation starting at $\nu$ has zero-cost (i.e. $S_{[0,T]}(\mu_{\nu}|\nu) = 0$ where $\mu_\nu$ denotes the solution to (\[eqn:MVE\]) starting at $\nu$), the limiting behaviour that $\mu_N(\cdot) \xrightarrow{P} \mu_\nu(\cdot)$ in $D([0,T],M_1(\mathcal{Z}))$ as $N \to  \infty$ follows.

Here is an outline of the proof of Theorem \[thm:finite-duration-ldp\]: one looks at a system of non-interacting particles where the transition rates of a particle do not depend on the empirical measure, and considers the corresponding empirical measure process over $[0,T]$. Since at most one particle can jump at a given point of time, the measure $p_{\nu_N}^{(N)}$ is absolutely continuous with the measure corresponding to the above non-interacting system on $D([0,T],M_1(\mathcal{Z}))$. One can then write the Radon-Nikodym derivative using the Girsanov formula and show continuity properties of the same. An application of an extension of Sanov’s theorem (see [[@dawson-gartner-87 Theorem 3.5]]{}) tells us that the non-interacting particle system obeys the LDP on $D([0,T],M_1(\mathcal{Z}))$. The above theorem then follows by an application of Varadhan’s integral lemma (see [[@dembo-zeitouni Theorem 4.3.1]]{}). This approach has been carried out for a system of interacting diffusions in [@dawson-gartner-87] and for jump processes in [@leonard-95; @borkar-sundaresan-12].

We now recall a theorem that gives the large deviation principle for the sequence $\{p_{\nu_N,T}^{(N)}\}_{N \geq 1}$ on $M_1(\mathcal{Z})$. This can be obtained from the above theorem by an application of the contraction principle to the coordinate projection map $D([0,T], M_1(\mathcal{Z})) \ni \mu \mapsto \mu(T)$ (see [@dembo-zeitouni Theorem 4.2.1], [@borkar-sundaresan-12 Theorem 3.3]).

Suppose that the initial conditions $\nu_N \to \nu$ in $M_1(\mathcal{Z})$. Then the sequence of probability measures $\{p_{\nu_N,T}^{(N)}\}_{N \geq 1}$ on the space $M_1(\mathcal{Z})$ satisfies the LDP with the good rate function $$\begin{aligned}
S_T(\xi|\nu) \coloneqq \inf \{S_{[0,T]}(\mu|\nu): &\,  \mu(0) = \nu, \mu(T) = \xi,  \mu \in \mathcal{AC}[0,T]\}.\end{aligned}$$ Moreover, the infimum is attained, i.e., there exists a path $\hat{\mu} \in \mathcal{AC}[0,T] $, and a rate matrix $L (t) = (l_{ij}(t), (i,j) \in \mathcal{E})$ such that $$\begin{aligned}
\frac{d\hat{\mu}(t)}{dt} =L^*(t) \hat{\mu}(t),\,  \hat{\mu} (0)=\nu,\,  \hat{\mu} (T) = \xi,\end{aligned}$$ and $S_{[0,T]}(\hat{\mu}|\nu) = S_T(\xi|\nu)$. \[thm:ldp\_terminal\_time\]

Here, $S_T(\xi|\nu)$ can be interpreted as the minimum cost of passage from the profile $\nu$ to the profile $\xi$ in time $T$, among all paths from $\nu$ to $\xi$ in time $T$.

We also have the following *uniform* LDP for the sequence $\{p_{\nu_N}^{(N)}\}_{ N \geq 1}$ (see [[@borkar-sundaresan-12 Corollary 3.1]]{}) when the initial condition is allowed to lie in a compact set.

For any compact set $K \subset M_1(\mathcal{Z})$, any closed set $F \subset D([0,T], M_1(\mathcal{Z}))$, and any open set $G \subset D([0,T], M_1(\mathcal{Z}))$, we have $$\begin{aligned}
\limsup_{N \to \infty} \frac{1}{N} \log \sup_{\nu \in K} p_\nu^{(N)} \{\mu_N \in F\} \leq - \inf_{\nu \in K } \inf_{\mu \in F} S_{[0,T]} (\mu|\nu),\end{aligned}$$ and $$\begin{aligned}
\liminf_{N \to \infty} \frac{1}{N} \log \sup_{\nu \in K} p_\nu^{(N)} \{\mu_N \in G\} \geq - \sup_{\nu \in K} \inf_{\mu \in G} S_{[0,T]} (\mu|\nu).\end{aligned}$$ \[cor:uniform\_ldp\]

For a proof of the above, see [[@dembo-zeitouni Corollary 5.6.15]]{}. Note that, since the space $M_1(\mathcal{Z})$ is compact, we may take $K = M_1(\mathcal{Z})$ in the above corollary.

Large time behaviour {#section:large_time_behaviour}
====================

In the study of large-time behaviour of $\mu_N$, an important role is played by the Freidlin-Wentzell quasipotential $V : M_1(\mathcal{Z}) \times M_1(\mathcal{Z}) \to [0, \infty)$ defined by $$\begin{aligned}
V(\nu,\xi) \coloneqq \inf \{S_{[0,T]}(\mu|\nu):\mu(T)= \xi, T > 0\},\end{aligned}$$ i.e., $V(\nu, \xi)$ denotes the minimum cost of transport from $\nu$ to $\xi$ in an arbitrary but finite time.

We say that $\nu \sim \xi$ ($\nu$ is equivalent to $\xi$) if $V(\nu, \xi) = 0$ and $V(\xi, \nu) = 0$. It is easy to see that $\sim$ defines an equivalence relation on $M_1(\mathcal{Z})$. To study the large time behaviour of the process $\mu_N$, we make the following assumptions on the McKean-Vlasov equation (\[eqn:MVE\]) (see [@freidlin-wentzell Chapter 6, Section 2, Condition A]):

1.  There exists a finite number of compact sets $K_1, K_2, \ldots, K_l$ such that

    -   For each $i = 1,2, \ldots l$, $\nu_1, \nu_2 \in K_i$ implies $\nu_1 \sim \nu_2$.

    -   For each $i \neq j$, $\nu_1 \in K_i$ and $\nu_2 \in K_j$ implies $\nu_1 \nsim \nu_2$.

    -   Every $\omega$-limit set of the dynamical system (\[eqn:MVE\]) lies completely in one of the compact sets $K_i$.

    \[assm:b1\]

It can be shown that $V(\nu_1, \nu_2) = 0$ whenever $\nu_1,\nu_2 \in K_i$ for any $1 \leq i \leq l$. We can therefore define $$\begin{aligned}
V(K_i, K_j) \coloneqq \inf\{S_{[0,T]}(\mu|\nu):\nu \in K_i, \mu(T) \in K_j\},\end{aligned}$$ which is interpreted as the minimum cost of going from $K_i$ to $K_j$. We also define the minimum cost of going from $K_i$ to $K_j$ without touching the other compact sets $K_k, k \neq i,j$ by $$\begin{aligned}
\tilde{V}(K_i, K_j) \coloneqq \inf & \{S_{[0,T]}(\mu|\nu):\nu \in K_i, \mu(t) \notin \cup_{k\neq i, j} K_k \\
&  \text{ for all } 0 \leq t \leq T, \mu(T) \in K_j, T>0\}.\end{aligned}$$

Preliminary results
-------------------

It turns out that, under assumption \[assm:b1\], the large time behaviour of the process $\mu_N$ can be studied via a discrete time Markov chain whose state space is the union of small neighbourhoods of the compact sets $K_i, 1 \leq i \leq l$. To study this chain, we introduce some notation. Let $L = \{1,2,\ldots, l\}$. Given $0 < \rho_1 < \rho_0$, let $\gamma_i$ (resp. $\Gamma_i$) denote the $\rho_1$-open neighbourhood (resp. $\rho_0$-open neighbourhood) of $K_i$. Let $\gamma = \cup_{i=1}^l \gamma_i$, $\Gamma = \cup_{i=1}^l \Gamma_i$, and $C =M_1(\mathcal{Z}) \setminus \overline{\Gamma}$. For a set $A \subset M_1(\mathcal{Z})$ and $\delta>0$, let $[A]_\delta$ denote the $\delta$-open neighbourhood of $A$, and for a subset $W \subset L$, abusing notation, let $[W]_\delta$ denote the $\delta$-open neighbourhood of $\cup_{i \in W} K_i$. For each $n \geq 1$, we define the sequence of stopping times: $\tau_0\coloneqq 0$, $\sigma_n \coloneqq \inf\{t>\tau_{n-1}: \mu_N(t) \in C\}$, $\tau_n \coloneqq \inf\{t > \sigma_n : \mu_N(t) \in \gamma\}$, and define $Z^N_n \coloneqq \mu_N(\tau_n)$, which is a discrete time Markov chain on the state space $\gamma \cap M^N_1(\mathcal{Z})$. For a measurable set $A \in M_1(\mathcal{Z})$, we define the stopping time $\tau_A \coloneqq \inf\{t > 0: \mu_N(t) \notin A\}$, which denotes the time exit from the set $A$. Finally, for a subset $W \subset L$, we define the stopping time $\hat{\tau}_W \coloneqq \inf\{t >0 : \mu_N(t) \in \cup_{i \in W}\gamma_i\}$, and $\bar{\tau}_W \coloneqq \inf \{t > 0: \mu_N(t) \in \cup_{i \in L \setminus W} \gamma_i \}$, which denote the time of entry into the $\rho_1$-neighbourhood of $W$ and the time of entry into the $\rho_1$-neighbourhood of $L \setminus W$, respectively.

We now state some results on the behaviour of the exit time from certain sets, which will be used in the paper subsequently. These results are known in the case of both Markov jump processes as well as diffusion processes; see [[@borkar-sundaresan-12 Appendix]]{}, and [[@freidlin-wentzell Chapter 6, Section 2]]{}. The main ingredients that are used in proving these results are (i) the strong Markov property of the $\mu_N$ process, (ii) Theorem \[thm:finite-duration-ldp\] and Corollary \[cor:uniform\_ldp\] on the LDP for finite time durations, and (iii) the joint continuity of the terminal time rate function $S_T(\cdot|\cdot)$ (see [[@borkar-sundaresan-12 Lemma 3.3]]{}). In the following results, $P_\nu$ denotes the solution to the $D([0,\infty),M_1(\mathcal{Z}))$-valued martingale problem for $L^N$ with initial condition $\nu \in M_1^N(\mathcal{Z})$ and $E_\nu$ denotes the corresponding expectation; note that in $P_\nu$ and $E_\nu$ we suppress the dependence on $N$ for ease of readability.

Let $K \subset M_1(\mathcal{Z})$ be a compact set such that all points in $K$ are equivalent to each other. Then, given $\varepsilon> 0$, there exist $\delta > 0$ and $N_0 \geq 1$ such that for all $N \geq N_0$ and $\nu \in  [K]_{\delta}\cap M^N_1(\mathcal{Z})$, $$\begin{aligned}
E_\nu \tau_{[K]_{\delta}} \leq \exp\{N\varepsilon\}.\end{aligned}$$ \[lemma:fw17\]

Let $K \subset M_1(\mathcal{Z})$ be a compact set and $G$ be a neighbourhood of $K$. Then, given $\varepsilon > 0$, there exist $\delta>0$ and $N_0 \geq 1$ such that for all $\nu \in \overline{[K]_{\delta}} \cap M_1^N(\mathcal{Z})$ and $N \geq N_0$ $$\begin{aligned}
E_\nu \left( \int_0^{\tau_G}  {1_}{\{\mu_N(t) \in \overline{[K]_\delta}\}} dt \right) \geq \exp\{-N\varepsilon\}.\end{aligned}$$ \[lemma:fw18\]

Let $K \subset M_1(\mathcal{Z})$ be a compact set that does not contain any $\omega$-limit set of (\[eqn:MVE\]) entirely. Then, there exist positive constants $c, T_0$ and $N_0 \geq 1$ such that for all $T \geq T_0$, $N \geq N_0$ and any $\nu \in K \cap M_1^N(\mathcal{Z})$, we have $$\begin{aligned}
P_{\nu}( \tau_K \geq T ) \leq \exp\{-Nc(T-T_0)\}.\end{aligned}$$ \[lemma:fw19\]

Under the conditions of Lemma \[lemma:fw19\], there exist $ C>0$ and $N_0 \geq 1$ such that for all $\nu \in K \cap M_1^N(\mathcal{Z})$ and $N \geq N_0$, $$\begin{aligned}
E_\nu \tau_K \leq C.\end{aligned}$$ \[cor:fw19\]

Recall the definition of the discrete time Markov chain $Z^N$ on $\gamma \cap M_1^N(\mathcal{Z})$. The next lemma gives upper and lower bounds on the one-step transition probabilities of the chain $Z^N$. These estimates play an important role in the study of large-time behaviour of the process $\mu_N$, as we shall see in the sequel.

\[lemma:bsa6\] Given $\varepsilon >0$, there exist $\rho_0 >0$ and $N_0 \geq 1$ such that, for any $\rho_2  < \rho_0$, there exists $\rho_1 < \rho_2$ such that for any $\nu \in [K_i]_{\rho_2} \cap M_1^N(\mathcal{Z})$ and $N \geq N_0$, the one-step transition probability of the chain $Z^N$ satisfies $$\begin{aligned}
\exp\{-N(\tilde{V}(K_i, K_j)+\varepsilon)\} \leq P(\nu, \gamma_j) \leq \exp\{-N(\tilde{V}(K_i, K_j)-\varepsilon)\}.
\label{eqn:tpm_zn}\end{aligned}$$

The key ingredient in the proof of the above lemma is Corollary \[cor:uniform\_ldp\] on the uniform large deviation principle on bounded sets. For the lower bound, one constructs a specific trajectory from $\nu$ to $K_j$ and examines its cost. For the upper bound, one uses the strong Markov property at the hitting time of $[L]_{\rho_1}$ and the uniform large deviation principle. For details, the reader is referred to proof of [[@borkar-sundaresan-12 Lemma A.6]]{} for the case of Markov jump processes, and proof of [@freidlin-wentzell Lemma 2.1, page 152] for the case of small noise diffusions.

Behaviour near attractors indexed by subsets of L
-------------------------------------------------

We now recall some results on the behaviour of the process $\mu_N$ near a small neighbourhood of attractors indexed by a given subset of $L$. Let $W \subset L$. A $W$-graph is a directed graph on $L$ such that (i) each element of $L \setminus W$ has exactly one outgoing arrow and (ii) there are no closed cycles in the graph. We denote the set of $W$-graphs by $G(W)$. For a $W$-graph $g$, define $\tilde{V}(g) = \sum_{(m\to n) \in g} \tilde{V}(K_m, K_n)$. Note that, using the estimate (\[eqn:tpm\_zn\]), $\tilde{V}$ can be used to estimate the probability that the process $\mu_N$ traverses through a sequence of neighbourhoods in the order specified by the graph $g$.

For $i \in L\setminus W$ and $j \in W$, let $G_{i,j}(W)$ denote the set of $W$-graphs in which there is a sequence of arrows leading from $i$ to $j$. Define $$\begin{aligned}
I_{i,j}(W) \coloneqq \min\{\tilde{V}(g):g \in G_{i,j}(W)\} - \min\{\tilde{V}(g): g \in G(W)\}.\end{aligned}$$ We recall the following result on the probability that the first entry of $\mu_N$ into a neighbourhood of a set $W \subset L$ takes place via a given compact set $K_j$, starting from a neighbourhood of $K_i$.

Let $W \subset L$, and let $i \in L \setminus W$ and $j \in W$. Given $\varepsilon > 0$, there exist $\rho > 0$ and $N_0 \geq 1 $ such that for any $\rho_1 \leq \rho$, $\nu \in \gamma_i \cap M^N_1(\mathcal{Z})$ and $N \geq N_0$, we have $$\begin{aligned}
 \exp\{-N(I_{i,j}(W)+\varepsilon)\} \leq P_\nu(\mu_N(\hat{\tau}_W) \in \gamma_j) \leq \exp\{-N(I_{i,j}(W)-\varepsilon)\}.\end{aligned}$$ \[lemma:hs15\]

The proof of [[@freidlin-wentzell Lemma 3.3, page 159]]{} holds verbatim, by making use of the estimates in Lemma \[lemma:bsa6\].

Our next step is to understand the mean entry time $E_\nu \hat{\tau}_W$. For this, we need the following estimate on the stopping time $\tau_1$; see [[@hwang-sheu-90 Lemma 1.3, Part I]]{} for a similar estimate for small noise diffusion processes.

Given $\varepsilon >0$, there exist $\rho_1 >0$ and $N_0 \geq 1$ such that, for any $\nu \in \gamma \cap M_1^N(\mathcal{Z})$ and $N \geq N_0$, we have $$\begin{aligned}
E_\nu \tau_1 \leq \exp\{N\varepsilon\}.\end{aligned}$$ \[lemma:hs13\]

With a sufficiently small $\rho_1 > 0$ to be chosen later, let $\rho_0 = 2 \rho_1$ so that $[K_i]_{\rho_0}$ does not intersect with $[K_j]_{\rho_0}$ for all $j \neq i$. Note that, for any $\nu \in \gamma$, $$\begin{aligned}
E_{\nu} \tau_1 = E_\nu \sigma_0  +E_\nu (\tau_1 - \sigma_0).\end{aligned}$$ Consider the first term. By Lemma \[lemma:fw17\], there exist $\rho > 0$ and $N_0 \geq 1$ such that for all $\rho_1 \leq \rho$, $\nu \in \gamma \cap M_1^N(\mathcal{Z})$ and $N \geq N_0$, we have $$\begin{aligned}
E_\nu \sigma_0 \leq \exp\{N\varepsilon/2\}.\end{aligned}$$ Let $F = M_1(\mathcal{Z}) \setminus \gamma$. By the strong Markov property, the second term is $$\begin{aligned}
E_\nu (\tau_1 - \sigma_0) = E_{\mu_N(\sigma_0)} (\tau_{F}).\end{aligned}$$ Therefore, it suffices to estimate $E_{\nu^\prime} \tau_F$ for $\nu^\prime \in F$. Since the compact set $F$ does not contain any $\omega$-limit set, by Corollary \[cor:fw19\], there exist a constant $C >0$ and $N_1 \geq N_0$ such that for any $\nu^\prime \in F \cap M_1^N(\mathcal{Z})$ $$\begin{aligned}
E_{\nu^\prime} \tau_{F} \leq C.\end{aligned}$$ This completes the proof of the lemma.

Define $$\begin{aligned}
I_i(W) \coloneqq &\min\{\tilde{V}(g): g \in G(W)\} -  \min\{\tilde{V}(g): g \in G( W \cup \{i\}) \text{ or } \\&  g \in G_{i,j}(W \cup \{j\}), i \neq j, j \in L\setminus W\} \\end{aligned}$$ The next lemma is about the mean entry time into a neighbourhood of a given set $W \subset L$ starting from a neighbourhood of $K_i$; see [[@hwang-sheu-90 Lemma 1.6, Part I]]{}\] for a similar estimate on small noise diffusion processes.

\[lemma:hs16\] Let $W \subset L$, and let $i \in L \setminus W$. Given $\varepsilon > 0$, there exist $\rho > 0$ and $N_0 \geq 1 $ such that for any $\rho_1 \leq \rho$, $\nu \in \gamma_i \cap M^N_1(\mathcal{Z})$ and $N \geq N_0$, we have $$\begin{aligned}
\exp\{N(I_i(W)-\varepsilon)\} \leq E_\nu \hat{\tau}_W \leq \exp\{N(I_i(W)+\varepsilon)\}.\end{aligned}$$

We first prove the upper bound. Note that, by the strong Markov property, we have $$\begin{aligned}
E_\nu \hat{\tau}_W = E_\nu \tau_v \leq \sum_{m=1}^\infty E_\nu \left({1_}{v = m} \times m \sup_{\nu^\prime \in \gamma} E_{\nu^\prime} \tau_1 \right),\end{aligned}$$ where $v$ is the hitting time of the chain $Z_n^N$ on the set $W$. Using Lemma \[lemma:hs13\] and the upper bound on $E_\nu v$ derived in [[@freidlin-wentzell Lemma 3.4, page 162]]{}, for sufficiently small $\rho_1$ and sufficiently large $N$, we have that $$\begin{aligned}
E_\nu \hat{\tau}_W \leq \exp\{N(I_i(W) +\varepsilon)\}\end{aligned}$$ holds for all $\nu \in \gamma_i \cap M_1^N(\mathcal{Z})$. For the lower bound, Lemma \[lemma:fw18\] implies that, for all sufficiently small $\rho_1$ and sufficiently large $N$, we have that $$\begin{aligned}
E_\nu \tau_1 \geq \exp\{-N\varepsilon\}\end{aligned}$$ holds for all $\nu \in \gamma$. Also, $$\begin{aligned}
E_\nu \hat{\tau}_W = E_\nu \tau_v \geq  \sum_{m=1}^\infty E_\nu \left(1_{v = m} \times m \inf_{\nu^\prime \in \gamma} E_{\nu^\prime} \tau_1 \right),\end{aligned}$$ hence, using the lower bound on $E_\nu v$ derived in [[@freidlin-wentzell Lemma 3.4, page 162]]{}, we get $$\begin{aligned}
E_\nu \hat{\tau}_W \geq \exp\{N(I_i(W) - \varepsilon)\}\end{aligned}$$ for all $\nu \in \gamma_i \cap M_1^N(\mathcal{Z})$ and sufficiency large $N$.

Cycles
------

We now define the notion of cycles, which helps us to describe the most probable way in which the process $\mu_N$, for large $N$, traverses neighbourhoods of various compact sets $K_i$, and the time required to go from one to another. Define $\tilde{V}(K_i) \coloneqq \min_{j \neq i} \tilde{V}(K_i, K_j)$. We say that $i \to j$ if $\tilde{V}(K_i) = \tilde{V}(K_i,K_j)$. Note that, using the estimates (\[eqn:tpm\_zn\]) on the transition probability of the discrete time Markov chain $Z^N$, we see that the indices that attain the minimum above are the most likely sets that will be visited by the process $\mu_N$, for large enough $N$, starting from a neighbourhood of $K_i$. For $i, j \in L$, we say that $i \Rightarrow j$ if there exists a sequence of arrows leading from $i$ to $j$, i.e., there exists $i_1, i_2 , \ldots, i_n$ in $L$ such that $i \to i_1 \to i_2 \to \cdots \to i_n \to j$. Again, the above sequence of arrows from $i$ to $j$ is one among the *locally* most likely sequences in which the process traverses from a neighbourhood of $K_i$ to that of $K_j$ for large $N$.

A cycle $\pi$ is a subgraph of $L$ satisfying

1.  $i \in \pi$ and $i \Rightarrow j$ implies $j \in \pi$.

2.  For any $i \neq j$ in $\pi$, we have $i \Rightarrow j $ and $j \Rightarrow i$.

It can be shown that there exists a cycle (see the proof of [@hwang-sheu-90 Lemma 1.9, Part I]). We now define cycle of cycles. Let $L_0 = L$. Define $$\begin{aligned}
L_1 \coloneqq \{\pi: \pi \text{ is a cycle in } L\} \cup \{i \in L: i \text{ is not in any cycle}\}.\end{aligned}$$ For $\pi_1, \pi_2 \in L_1$, $\pi_1 \neq \pi_2$, define $$\begin{aligned}
\hat{V}(\pi_1) \coloneqq \max \{\tilde{V}(K): K \in \pi_1\},\end{aligned}$$ $$\begin{aligned}
\tilde{V}(\pi_1, \pi_2) \coloneqq \hat{V}(\pi_1) + \min \{\tilde{V}(K_1, K_2)-\tilde{V}(K_1): K_1 \in \pi_1, K_2 \in \pi_2\},\end{aligned}$$ and $$\begin{aligned}
\tilde{V}(\pi_1) \coloneqq \min\{\tilde{V}(\pi_1, \pi_2): \pi_2 \in L_1, \pi_2 \neq \pi_1\}.\end{aligned}$$ We say that $\pi_1 \to \pi_2$ if $ \tilde{V}(\pi_1) = \tilde{V}(\pi_1, \pi_2)$, and we say that $\pi_1 \Rightarrow \pi_2$ if there is a sequence of arrows leading from $\pi_1$ to $\pi_2$. This gives a cycle of cycles, which we call 2-cycles.

Let us now define the hierarchy of cycles. Having defined $(m-1)$-cycles and the sets $L_0, L_1, \ldots, L_{m-2}$, we define $m$-cycles as follows. Note that $$\begin{aligned}
L_{m-1} = \{\pi^{m-1}: &\pi^{m-1} \text{ is an }  (m-1)\text{-cycle}\} \\
&  \cup \{\pi^{m-2} \in L_{m-2} : \pi^{m-2} \text{ is not in any } (m-1)\text{-cycle}\}.\end{aligned}$$ For $\pi^{m-1} \in L_{m-1}$, define $$\begin{aligned}
\hat{V}(\pi^{m-1}) \coloneqq  \max \{\tilde{V}(\pi^{m-2}): \pi^{m-2} \in \pi^{m-1}\},\end{aligned}$$ $$\begin{aligned}
\tilde{V}(\pi_1^{m-1}, \pi_2^{m-1}) \coloneqq \hat{V}(\pi_1^{m-1}) + &  \min \{\tilde{V}(\pi_1^{m-2}, \pi_2^{m-2})-\tilde{V}(\pi_1^{m-2}): \\
& \pi_1^{m-2} \in \pi_1^{m-1}, \pi_2^{m-2} \in \pi_2^{m-1}\},\end{aligned}$$ and $$\begin{aligned}
\tilde{V}(\pi_1^{m-1}) \coloneqq \min\{\tilde{V}(\pi_1^{m-1}, \pi_2^{m-1}): \pi_2^{m-1} \in L_{m-1}, \pi_2^{m-1} \neq \pi_1^{m-1}\}.\end{aligned}$$ We say that $\pi_1^{m-1} \to \pi_2^{m-1}$ if $\tilde{V}(\pi_1^{m-1}) = \tilde{V}(\pi_1^{m-1}, \pi_2^{m-1})  $. We have

An $m$-cycle $\pi^m$ is a subgraph of $L_{m-1}$ satisfying

1.  For $\pi_1^{m-1}, \pi_2^{m-1} \in L_{m-1}$, $\pi_1^{m-1} \in \pi^m$ and $\pi_1^{m-1} \Rightarrow \pi_2^{m-1}$ implies $\pi_2^{m-1} \in \pi^m$.

2.  For any $\pi_1^{m-1}, \pi_2^{m-1} \in \pi^m$, we have $\pi_1^{m-1} \Rightarrow \pi_2^{m-1}$ and $\pi_2^{m-1}\Rightarrow \pi_1^{m-1}$.

If we continue this way, for some $m \geq 1$, the set $L_m$ will eventually be a singleton, at which point we stop.

We now state some results on the mean exit time from a cycle and the most probable cycle the process $\mu_N$ visits upon exit from a given cycle. For convenience, the set of elements of $L$ constituting a $k$-cycle $\pi^k$ (through the hierarchy of cycles) is also denoted by $\pi^k$. Also, for $W \subset L$, we define $\gamma_W = \cup_{i \in W} \gamma_i$.

Let $\pi^k$ be a $k$-cycle and $K_i \in \pi^k$. Let $W = L \setminus \pi^k$. Given $\varepsilon > 0$, there exist $\rho >0$ and $N_0 \geq 1$ such that for all $\rho_1 \leq \rho$, $\nu \in \gamma_i \cap M_1^N(\mathcal{Z})$ and $N \geq N_0$, we have $$\begin{aligned}
\exp \{N(\tilde{V}(\pi^k) - \varepsilon)\} \leq E_\nu \hat{\tau}_W \leq \exp \{N(\tilde{V}(\pi^k) + \varepsilon)\}.\end{aligned}$$ \[cor:hs110\]

Let $\pi_1^k, \pi_2^k$ be $k$-cycles, $\pi_1^k \neq \pi_2^k$, and $K_i \in \pi_1^k$. Let $W = L \setminus \pi_1^k$. Given $\varepsilon > 0$, there exist $\rho >0$ and $N_0 \geq 1$ such that for all $\rho_1 \leq \rho$, $\nu \in \gamma_i \cap M_1^N(\mathcal{Z})$ and $N \geq N_0$, we have $$\begin{aligned}
\exp \{-N(\tilde{V}(\pi_1^k, \pi_2^k) - \tilde{V}(\pi_1^k) + \varepsilon)\} & \leq  P_\nu (\mu_N(\hat{\tau}_W) \in \gamma_{\pi_2^k})  \\
&\leq \exp \{-N(\tilde{V}(\pi_1^k, \pi_2^k) - \tilde{V}(\pi_1^k) - \varepsilon)\}.\end{aligned}$$ \[cor:hs111\]

Note that Corollary \[cor:hs110\] follows from Lemma \[lemma:hs16\] and the fact that $I_i(W) = \tilde{V}(\pi^k)$ (which is shown in [@hwang-sheu-90 Corollary A.4, Appendix]). Corollary \[cor:hs111\] is a consequence of Lemma \[lemma:hs15\] along with the fact that $\min\{I_{i,j}(W) : i \in \hat{\pi}^k\} = \tilde{V}(\pi^k, \hat{\pi}^k) - \tilde{V}(\pi^k)$ (see  [@hwang-sheu-90 Corollary A.6, Appendix]). Similar estimates as in Corollaries \[cor:hs110\] and \[cor:hs111\] in the case of small noise diffusion processes have been shown in [[@hwang-sheu-90 Corollary 1.10, Part I]]{} and [[@hwang-sheu-90 Corollary 1.11, Part I]]{}, respectively.

We also need the following lemmas that provide estimates on the probabilities of exit within certain times from given cycles.

Let $\pi_1^k, \pi_2^k$ be $k$-cycles and let $\pi_1^k \to \pi_2^k$. Then, given $\varepsilon >0$, there exist $\delta >0$, $\rho >0$ and $N_0 \geq 1$ such that for all $\rho_1 \leq \rho$, $\nu \in \gamma_{\pi_1^k} \cap M_1^N(\mathcal{Z})$ and $N \geq N_0$, we have $$\begin{aligned}
P_\nu \left(\bar{\tau}_{\pi_1^k} \leq \exp\{N(\tilde{V}(\pi_1^k)-\delta)\}, \mu_N(\bar{\tau}_{\pi_1^k}) \in \gamma_{\pi_2^k} \right) \geq \exp\{-N\varepsilon\}.\end{aligned}$$ \[lemma:hitting\_place\]

Let $\pi^k$ be a $k$-cycle. Then, given $\varepsilon > 0$, there exists $\rho > 0$ such that for all $\rho_1 \leq \rho$, we have $$\begin{aligned}
\lim_{N \to \infty} \sup_{\nu \in \gamma_{\pi^k} \cap M_1^N(\mathcal{Z})} P_\nu\left(  \exp\{N(\tilde{V}(\pi^k) - \varepsilon)\} \leq \bar{\tau}_{\pi^k} \leq \exp\{N(\tilde{V}(\pi^k) + \varepsilon)\} \right) =1.\end{aligned}$$ Furthermore, given $\varepsilon > 0$, there exist $\delta >0$, $\rho > 0$ and $N_0 \geq 1$ such that for all $\rho_1 \leq \rho$, $N \geq N_0$ and $\nu \in \gamma_{\pi^k} \cap M^N_1(\mathcal{Z})$, we have $$\begin{aligned}
P_\nu\left(  \bar{\tau}_{\pi^k}  < \exp\{N(\tilde{V}(\pi^k) - \delta)\} \right) \leq \exp\{-N\varepsilon\}, \text{ and} \\
P_\nu\left(  \bar{\tau}_{\pi^k}  > \exp\{N(\tilde{V}(\pi^k) + \delta)\} \right) \leq \exp\{-N\varepsilon\}.\end{aligned}$$ \[lemma:hitting\_time\]

Lemma \[lemma:hitting\_place\] can be proved using Lemma 3.3 and [[@freidlin-wentzell Chapter 6, Theorem 6.2]]{}, and Lemma \[lemma:hitting\_time\] can be proved using the same arguments used in the proof of [[@freidlin-wentzell Chapter 6, Theorem 6.2]]{}. Similar estimates as in Lemmas \[lemma:hitting\_place\] and \[lemma:hitting\_time\] in the case of small noise diffusion processes have been shown in [[@hwang-sheu-90 Lemma 2.1, Part I]]{} and [[@hwang-sheu-90 Lemma 2.2, Part I]]{}, respectively.

Let $\pi^k$ be a $k$-cycle and assume that $\tilde{V}(\pi^k) > 0$. Given $\varepsilon > 0$, there exist $\delta>0, \rho >0$ and $N_0 \geq 1$ such that for all $\rho_1 \leq \rho, \nu \in M_1^N(\mathcal{Z})$ and $N \geq N_0$, we have $$\begin{aligned}
P_{0,\nu}(\bar{\tau}_{\pi^k} \leq \exp\{N(\hat{V}(\pi^k)+\delta\}) \leq \exp\{-N(\tilde{V}(\pi^k) - \hat{V}(\pi^k) - \varepsilon)\}.\end{aligned}$$ \[lemma:exit\_time\_vhat\]

We proceed via the steps in the proof of [[@hwang-sheu-90 Lemma 2.1, Part III]]{}. Let $\pi^{k-1} \in \pi^k$ be a $(k-1)$-cycle such that $\tilde{V}(\pi^{k-1}) = \hat{V}(\pi^k)$. With $\rho_1>0$ to be chosen later, for each $n \geq 1$, define the minimum of $\bar{\tau}_{\pi^k}$ and successive entry and exit times from a $\rho_1$-neighbourhood of $\pi^{k-1}$ as follows: $$\begin{aligned}
\hat{\theta}_0 & \coloneqq \inf\{ t >0 : \mu_N(t) \in [\pi^{k-1}]_{\rho_1}\} \wedge \bar{\tau}_{\pi^k}, \\
\bar{\theta}_n & \coloneqq \inf\{t > \hat{\theta}_{n-1}: \mu_N(t) \in [L \setminus \pi^{k-1}]_{\rho_1} \} \wedge \bar{\tau}_{\pi^k} , \\
\hat{\theta}_{n+1}&  \coloneqq \inf\{t > \bar{\theta}_n : \mu_N(t) \in  [\pi^{k-1}]_{\rho_1} \} \wedge \bar{\tau}_{\pi^k}.\end{aligned}$$ With $\delta > 0$ to be chosen later, using the strong Markov property, for any $\nu \in [\pi^k]_{\rho_1} \cap M_1^N(\mathcal{Z})$, we have $$\begin{aligned}
P_{\nu}&(\bar{\tau}_{\pi^k}   \leq \exp\{N(\hat{V}(\pi^k)+\delta)\})  = P_\nu (\hat{\theta}_0 = \bar{\tau}_{\pi^k}, \bar{\tau}_{\pi^k} \leq \exp\{N(\hat{V}(\pi^k)+\delta)\}) \nonumber \\
 + & P_\nu \left(\hat{\theta}_0 < \bar{\tau}_{\pi^k}, \bigcup_{n \geq 1} \left\{\bar{\tau}_{\pi^k} = \bar{\theta}_n, \bar{\tau}_{\pi^k} \leq \exp\{N(\hat{V}(\pi^k)+\delta)\}, \bar{\tau}_{\pi^k} \geq \hat{\theta}_{n-1} \right\} \right) \nonumber \\
+ & P_\nu \left(\hat{\theta}_0 < \bar{\tau}_{\pi^k}, \bigcup_{n\geq 1} \left\{\bar{\tau}_{\pi^k} = \hat{\theta}_n, \bar{\tau}_{\pi^k} \leq \exp\{N(\hat{V}(\pi^k)+\delta)\}, \bar{\tau}_{\pi^k} \geq \bar{\theta}_n \right\}  \right).
\label{eqn:temp10}\end{aligned}$$ We now upper bound each of the terms in \[eqn:temp10\].Consider the first term. It can be shown using Corollary \[cor:hs111\] and [@hwang-sheu-90 Corollary A.6, Appendix] that, there exist $\rho_1>0$ and $\delta > 0$ such that for any $\nu \in [\pi^k]_{\rho_1}$ and sufficiently large $N$, we have $$\begin{aligned}
P_\nu(\hat{\theta}_0 = \bar{\tau}_{\pi^k}) \leq \exp\{-N(\tilde{V}(\pi^k) - \hat{V}(\pi^k) - \varepsilon)\}.\end{aligned}$$

Consider the second term in \[eqn:temp10\]. For any $\nu_1 \in [\pi^{k-1}]_{\rho_1} \cap M_1^N(\mathcal{Z})$, the probability of the unionised event can be upper bounded by $$\begin{aligned}
P_{\nu_1} & \left(\bigcup_{n \geq 1}\left\{\bar{\tau}_{\pi^k} = \bar{\theta}_n, \bar{\tau}_{\pi^k} \leq \exp\{N(\hat{V}(\pi^k)+\delta)\}, \bar{\tau}_{\pi^k} \geq \hat{\theta}_{n-1} \right\} \right)\\
& \leq P_{\nu_1} \left(\bigcup_{n=1}^M \left\{\bar{\tau}_{\pi^k} = \bar{\theta}_n, \bar{\tau}_{\pi^k} \leq \exp\{N(\hat{V}(\pi^k)+\delta)\}, \bar{\tau}_{\pi^k} \geq \hat{\theta}_{n-1} \right\} \right) \\
& \, \, \, \, + P_{\nu_1} \left( \bigcup_{n \geq M+1}  \left\{\bar{\tau}_{\pi^k} = \bar{\theta}_n, \bar{\tau}_{\pi^k} \leq \exp\{N(\hat{V}(\pi^k)+\delta)\}, \bar{\tau}_{\pi^k} \geq \hat{\theta}_{n-1} \right\} \right) \\
& \leq P_{\nu_1} (\bar{\tau}_{\pi^k} = \bar{\theta}_n \text{ and } \bar{\tau}_{\pi^k} \geq \hat{\theta}_{n-1} \text{ for some } n \leq M) \\
&  \, \, \, \, + P_{\nu_1} (\hat{\theta}_M \leq \exp\{N(\hat{V}(\pi^k)+\delta)\} \text{ and } \hat{\theta}_M \leq \bar{\tau}_{\pi^k})\\
& \leq P_{\nu_1}(\hat{\theta}_M = \bar{\tau}_{\pi^k}) + P_{\nu_1} (\hat{\theta}_M \leq \exp\{N(\hat{V}(\pi^k)+\delta)\} \text{ and } \hat{\theta}_M \leq \bar{\tau}_{\pi^k}).\end{aligned}$$ Again, the first term above can be bounded by $$\begin{aligned}
P_{\nu_1}(\hat{\theta}_M \leq \bar{\tau}_{\pi^k}) \leq \exp\{-N(\tilde{V}(\pi^k) - \hat{V}(\pi^k) - \varepsilon)\},\end{aligned}$$ for all $\nu_1 \in [\pi^{k-1}]_{\rho_1} \cap M_1^N(\mathcal{Z})$ and sufficiently large $N$. The second term can be bounded by $\exp\{-NM\}$ for large enough $M$, by the same argument used in the proof of [@hwang-sheu-90 Lemma 1.7, Part I]. Choosing $M$ sufficiently large, the above implies that the second term in (\[eqn:temp10\]) is bounded by $\exp\{-N(\tilde{V}(\pi^k) - \hat{V}(\pi^k) - \varepsilon)\}$. A similar argument gives the same bound for the third term in (\[eqn:temp10\]).

We also remark that, using the estimates (\[eqn:tpm\_zn\]) of the transition probabilities of the discrete time Markov chain $Z^N$, we can study large deviations for the process $\mu_N$ in the stationary regime. Since $\mu_N$ is a Markov process on a finite state space, and since the graph $(\mathcal{Z},\mathcal{E})$ of allowed particle transitions is irreducible (Assumption \[assm:a1\]), there exists a unique invariant probability measure $\wp_N$ on $M_1(\mathcal{Z})$ for the process $\mu_N$. We state the following result:

Assume \[assm:a1\], \[assm:a2\] and \[assm:b1\]. Then, the sequence of invariant measures $\{\wp_N\}_{N \geq 1}$ satisfies the large deviation principle on $M_1(\mathcal{Z})$ with good rate function $s$ given by $$\begin{aligned}
s(\xi) = \min_{1 \leq i \leq l} \{W(i) + V(K_i, \xi)\} - \min_{1 \leq j \leq l} W(j),
$$ where $$\begin{aligned}
W(i) = \min_{g \in G(i)} \sum_{(m,n) \in G} \tilde{V}(m,n).\end{aligned}$$ \[thm:invariant-measure-gase\]

Convergence to the invariant measure
------------------------------------

In this section, we prove our first main result on the convergence of $\mu_N$ to its invariant measure. Let $i_0 \in L$ be such that $ \min\{\tilde{V}(g): g \in G(i_0)\} = \min\{\tilde{V}(g): g \in G(i), i \in L \} $. We anticipate that $K_{i_0}$ is one of the most stable compact sets (among possibly others). This is because Theorem \[thm:invariant-measure-gase\] tells us that the rate function that governs the LDP for $\{\wp_N\}_{N \geq 1}$ vanishes on $K_{i_0}$. Hence, for a large but fixed $N$, over large time intervals, one expects that there is positive probability (in the exponential scale) for the process $\mu_N$ to be in a small neighbourhood of $K_{i_0}$.

Define $$\begin{aligned}
\Lambda \coloneqq \min\{\tilde{V}(g): g \in G(i), i \in L \} - \min\{\tilde{V}(g): g \in G(i, j), i, j \in L, i \neq j\}.\end{aligned}$$ Let $P_T(\nu, \cdot ) = P_{\nu}(\mu_N(T)  \in \cdot )$ denote the transition probability kernel associated with the process $\mu_N$. Note that we suppress the dependence on $N$ for ease of readability. We first show a lower bound for the transition probability $P_T(\nu_1, K_{i_0} ) $ of reaching a small neighbourhood of $K_{i_0}$ when $T$ is of the order $\exp\{N(\Lambda-\delta_0)\}$ for some $\delta_0>0$.

Given $\varepsilon >0$, there exist $\delta_0 > 0$, $\rho > 0$ and $N_0 \geq 1$ such that for all $\rho_1 \leq \rho$, $N \geq N_0$, $\nu \in M_1^N(\mathcal{Z})$, we have $$\begin{aligned}
P_{T_0}(\nu, \gamma_{i_0}) \geq \exp\{-N\varepsilon\},
\label{eqn:lb_tpm_i0}\end{aligned}$$ where $T_0 =\exp\{N(\Lambda - \delta_0)\}$. Furthermore, there exist $\nu_0 \in M_1(\mathcal{Z})$ and $\beta >0$ such that for all $N \geq N_0$ and $\nu \in [\nu_0]_{\rho_1} \cap M_1^N(\mathcal{Z})$ $$\begin{aligned}
P_{T_0}(\nu, \gamma_{i_0}) \leq \exp\{-N\beta\}.
\label{eqn:ub_tpm}\end{aligned}$$ \[thm:mixing\]

We follow the steps in Hwang and Sheu [[@hwang-sheu-90 Part I, Theorem 2.3]]{}. With $\rho > 0$ to be chosen later, we first show that (\[eqn:lb\_tpm\_i0\]) holds for all $\nu \in \gamma \cap M_1^N(\mathcal{Z})$. Towards this, let $m$ be the smallest integer such that $L_{m+1}$ is a singleton. For $0 \leq k \leq m$, let $\pi_0^k \in L_k$ be the $k$-cycle containing $i_0$. Let $V_k = \max \{\tilde{V}(\pi^k) : \pi^k \subset \pi_0^{k+1}, \pi^k \neq \pi_0^k\}$. Using [@hwang-sheu-90 Lemma A.10, Appendix], we have $\Lambda = \max\{V_k: 0 \leq k \leq m\}$.

Fix $j \in L$ and consider $\nu \in [K_j]_{\rho}$. Let $\pi_1^m \in L_m$ be such that $K_j \in \pi_1^m$. If $\pi_1^m \neq \pi_0^m$, then we have $\pi_1^m \Rightarrow \pi_0^m$, that is, there exists $\pi_2^m, \pi_3^m, \ldots, \pi_n^m =\pi_0^m, n \leq l$ such that $\pi_1^m \to \pi_2^m \to \pi_3^m \to \cdots \to \pi_n^m = \pi_0^m$. Therefore, with $\delta$ to be chosen later, by the strong Markov property (we use the standard notation $E_\nu(A; B)$ for $E_\nu(1_A 1_B)$ where $A$ and $B$ are measurable sets), $$\begin{aligned}
P_\nu (\hat{\tau}_{\pi^m_0} & \leq n \exp\{N(V_m - \delta)\})  \geq E_\nu ( \bar{\tau}_{\pi^m_1} \leq  \exp\{N(V_m -\delta )\}, \mu_N(\bar{\tau}_{\pi^m_1}) \in \pi_2^m;  \\
& E_{\mu_N(\bar{\tau}_{\pi^m_1})}(\bar{\tau}_{\pi_2^m} \leq  \exp\{N(V_m -\delta )\},\mu_N(\bar{\tau}_{\pi^m_2}) \in \pi_3^m; \\
& \cdots  E_{\mu_N(\bar{\tau}_{\pi^m_{n-2}})}( \bar{\tau}_{\pi^m_{n-1}} \leq  \exp\{N(V_m -\delta )\},\mu_N(\bar{\tau}_{\pi^m_{n-1}}) \in \pi_0^m)\\
& \cdots )).\end{aligned}$$ Since $V(\pi_i^m) \leq V_m$ for all $1 \leq i \leq n$, the above becomes

$$\begin{aligned}
P_\nu (\hat{\tau}_{\pi^m_0} & \leq n \exp\{N(V_m - \delta)\}) \\
&  \geq E_\nu ( \bar{\tau}_{\pi^m_1} \leq  \exp\{N(\tilde{V}(\pi_1^m) -\delta )\}, \mu_N(\bar{\tau}_{\pi^m_1}) \in \pi_2^m;  \\
& E_{\mu_N(\bar{\tau}_{\pi^m_1})}(\bar{\tau}_{\pi_2^m} \leq  \exp\{N(\tilde{V}(\pi_2^m)-\delta )\},\mu_N(\bar{\tau}_{\pi^m_2}) \in \pi_3^m; \\
& \cdots  E_{\mu_N(\bar{\tau}_{\pi^m_{n-2}})}( \bar{\tau}_{\pi^m_{n-1}} \leq  \exp\{N(\tilde{V}(\pi_{n-1}^m) -\delta )\},\mu_N(\bar{\tau}_{\pi^m_{n-1}}) \in \pi_0^m)\\
& \cdots )).\end{aligned}$$

By Lemma \[lemma:hitting\_place\], there exist $\rho >0$, $\delta > 0$ and $N_0 \geq 1 $ such that each of the above probabilities is at least $\exp\{-N\varepsilon/l\}$ for sufficiently large $N$, i.e. we have $$\begin{aligned}
P_\nu (\hat{\tau}_{\pi^m_0} \leq n \exp\{N(V_m - \delta))\}) \geq \exp\{-N n \varepsilon/l\} \geq \exp\{-N\varepsilon\},\end{aligned}$$ On the other hand, if $K_j$ is such that $K_j \in \pi_0^m$, the above holds trivially. Therefore, there exist $\delta_1 > 0$ and $N_1 \geq 1$ such that for all $\nu \in \gamma \cap M_1^N(\mathcal{Z})$ and $N \geq N_1$, we have $$\begin{aligned}
P_\nu (\hat{\tau}_{\pi^m_0} \leq \exp\{N(V_m - \delta_1)\})  \geq \exp\{-N  \varepsilon\}.\end{aligned}$$ We now use the above bound to show (\[eqn:lb\_tpm\_i0\]). Let $T = \exp\{N(\Lambda - \delta_1)\}, T_m = \exp\{N(V_m - \delta_1)\}$ and $T_{m-1} =\exp\{N(V_{m-1}-\delta_1)\}$. Then, for any $\nu \in \gamma \cap M_1^N(\mathcal{Z})$ and $N \geq N_1$, we have $$\begin{aligned}
P_\nu (\mu_N(T) \in \gamma_{i_0})& \geq E_\nu (\hat{\tau}_{\pi^m_0} \leq T_m; E_{\mu_N(\hat{\tau}_{\pi^m_0})}(\mu_N(T-\hat{\tau}_{\pi^m_0}) \in \gamma_{i_0})) \nonumber \\
& \geq \inf_{\substack{\nu \in [\pi_0^m]_{\rho}\cap M_1^N(\mathcal{Z}) \\  T-T_m \leq t \leq T}} P_\nu(\mu_N(t) \in \gamma_{i_0}) P_\nu (\hat{\tau}_{\pi^m_0}\leq T_m) \nonumber \\
& \geq  \inf_{\substack{\nu \in [\pi_0^m]_{\rho}\cap M_1^N(\mathcal{Z}) \\  T-T_m \leq t \leq T}} P_\nu(\mu_N(t) \in \gamma_{i_0})  \exp\{-N\varepsilon\}.
\label{eqn:temp1}\end{aligned}$$ To get a lower bound for the above infimum, fix $\nu \in [\pi_0^m]_\rho \cap M_1^N(\mathcal{Z})$ and $T-T_{m} \leq t \leq T$. Define the stopping time $\theta \coloneqq \inf\{s> t-T_{m-1} : \mu_N(s) \in [\pi_0^m]_{\rho}\}$. Then, for a large $T^*$ (not depending on $N$) to be chosen later, we have $$\begin{aligned}
P_\nu &(\mu_N(t) \in \gamma_{i_0}) \nonumber \\
 &\geq E_\nu (\theta \leq t-T_{m-1}+T^* , \bar{\tau}_{\pi_0^m} > T;  E_{\mu_N(\theta)}(\mu_N(t-\theta)) \in \gamma_{i_0})  \nonumber \\
& \geq P_\nu(\theta \leq t-T_{m-1}+T^* , \bar{\tau}_{\pi_0^m} > T)  \inf_{\substack{\nu^\prime \in [\pi_0^m]_{\rho}\cap M_1^N(\mathcal{Z}) \\ T_{m-1}-T^*\leq t \leq T_{m-1}}} P_{\nu^\prime} (\mu_N(t) \in \gamma_{i_0}).
\label{eqn:temp2}\end{aligned}$$ Note that $$\begin{aligned}
P_\nu(\theta \leq t-T_{m-1}+T^* & , \bar{\tau}_{\pi_0^m} > T) \\
&= P_\nu(\bar{\tau}_{\pi^m_0} > T) - P_\nu(\theta > t-T_{m-1}+T^* , \bar{\tau}_{\pi_0^m} > T).\end{aligned}$$ By Lemma \[lemma:hitting\_time\], since $\Lambda \leq \tilde{V}(\pi^m_0)$, we have $$\begin{aligned}
P_\nu(\bar{\tau}_{\pi^m_0} > T) \geq P_\nu(\bar{\tau}_{\pi^m_0} > \exp\{N(\tilde{V}(\pi^m_0) - \delta)\}) \to 1\end{aligned}$$ as $N \to \infty$. For the second term, note that $$\begin{aligned}
P_\nu& (\theta > t-T_{m-1}+T^* , \bar{\tau}_{\pi_0^m} > T) & \\
& = P_\nu (\mu_N(s) \notin [\pi_0^m]_\rho \text{ for all } t-T_{m-1}\leq s \leq t-T_{m-1}+T^*, \bar{\tau}_{\pi_0^m} > T) \\
& = P_\nu (\mu_N(s) \notin \gamma \text{ for all } t-T_{m-1}\leq s \leq t-T_{m-1}+T^*, \bar{\tau}_{\pi_0^m} > T) \\
& \leq P_\nu (\mu_N(s) \notin \gamma \text{ for all } t-T_{m-1}\leq s \leq t-T_{m-1}+T^*).\end{aligned}$$ The second equality follows since $\mu_N(s) \notin [\pi_0^m]_\rho$ and $\bar{\tau}_{\pi_0^m} >  T$ implies that we have exited $[\pi_0^m]_\rho$ and we have not yet entered a neighbourhood of any other attractor, which is the same as saying $\mu_N(t) \notin \gamma$ and $\bar{\tau}_{\pi_0^m} >T$. By the Markov property, the above probability equals $$\begin{aligned}
E_\nu  & \left( E_{\mu_N(t-T_{m-1})}(\mu_N(s) \notin \gamma \text{ for all } s \in [t-T_{m-1}, t-T_{m-1}+T^*]) \right)\\ 
& \leq \sup_{\nu^\prime \in F} P_{\nu^\prime} (\tau_F \geq T^*),\end{aligned}$$ where $F = M_1(\mathcal{Z}) \setminus \gamma$. By Lemma \[lemma:fw19\], $T^*$ can be chosen large enough (not depending on $N$) that the above probability is at most $1/2$. Therefore, (\[eqn:temp2\]) becomes $$\begin{aligned}
\inf_{\substack{\nu \in [\pi_0^m]_\rho \cap M_1^N(\mathcal{Z}) \\ T-T_m \leq t \leq T}} P_\nu(\mu_N(t) \in \gamma_{i_0}) \geq \frac{1}{2}   \inf_{\substack{\nu^\prime \in [\pi_0^m]_{\rho} \cap M_1^N(\mathcal{Z}) \\ T_{m-1}-T^* \leq t \leq T_{m-1}}} P_{\nu^\prime} (\mu_N(t) \in \gamma_{i_0}),\end{aligned}$$ and (\[eqn:temp1\]) becomes $$\begin{aligned}
P_\nu (\mu_N(T) \in \gamma_{i_0}) \geq \frac{1}{2} \exp\{-N\varepsilon\} \inf_{\substack{\nu^\prime \in [\pi_0^m]_{\rho} \cap M_1^N(\mathcal{Z}) \\  T_{m-1}-T^* \leq t \leq T_{m-1}}} P_{\nu^\prime} (\mu_N(t) \in \gamma_{i_0}),\end{aligned}$$ for sufficiently large $N$ and $\nu \in \gamma \cap M_1^N(\mathcal{Z})$. Repeating the above argument $m$ times, we see that there exists $N_2 \geq 1$ such that for all $\nu \in \gamma$ and $N \geq N_2$, we have $$\begin{aligned}
P_\nu(\mu_N(T) \in \gamma_{i_0}) & \geq \left(\frac{1}{2}\right)^m\exp\{-Nm\varepsilon\}  \inf_{\substack{\nu^\prime \in [\pi_0^1]_{\rho}\cap M_1^N(\mathcal{Z}) \\ T_0 -T^*\leq t \leq T_0}} P_{\nu^\prime} (\mu_N(t) \in \gamma_{i_0}) \\
& \geq \left(\frac{1}{2}\right)^{m}\exp\{-N(m+1)\varepsilon\} \inf_{\substack{\nu^\prime \in [K_0]_{\rho} \cap M_1^N(\mathcal{Z})\\ T_0 -T^*\leq t \leq T_0}} P_{\nu^\prime} (\mu_N(t) \in \gamma_{i_0}) \\
& \geq \left(\frac{1}{2}\right)^{m+1}\exp\{-N(m+1)\varepsilon\},\end{aligned}$$ where $T_0 = \exp\{N(V_0 - m\delta)\}$. Thus, we conclude that there is $N_3 \geq 1$, $\delta_3>0$ and $\rho > 0$ such that for all $\nu \in \gamma \cap M_1^N(\mathcal{Z})$ and $N \geq N_3$, we have $$\begin{aligned}
P_\nu(\mu_N(T) \in \gamma_{i_0})  \geq \exp\{-N(m+3)\varepsilon\},\end{aligned}$$ where $T = \exp\{N(\Lambda-\delta_3)\}$. This establishes (\[eqn:lb\_tpm\_i0\]) for all $\nu \in \gamma \cap M_1^N(\mathcal{Z})$. For any $\nu \in M_1^N(\mathcal{Z})\setminus \gamma$, from Lemma \[lemma:fw19\], there exists $T^\prime$ large enough and $N_4 \geq N_3$ such that $P_\nu(\tau_{M_1(\mathcal{Z}) \setminus \gamma} \leq T^\prime) \leq \frac{1}{2}$ for all $N \geq N_4$. Therefore, we have $$\begin{aligned}
P_\nu(\mu_N(T) \in \gamma_{i_0}) & \geq E_\nu (\tau_{M_1(\mathcal{Z}) \setminus \gamma} \leq T^\prime, P_{\mu_N(\tau_F)} (\mu_N(T-T^\prime) \in \gamma_{i_0})) \\
& \geq \frac{1}{2}  \inf_{\nu^\prime  \in \gamma} P_{\nu^\prime}(\mu_N(T-T^\prime) \in \gamma_{i_0}) \\
& \geq \frac{1}{2}\exp\{-N(m+3)\varepsilon\}.\end{aligned}$$ Thus, we have established (\[eqn:lb\_tpm\_i0\]) for any $\nu \in M_1^N(\mathcal{Z})$.

We now turn to (\[eqn:ub\_tpm\]). Since $\Lambda = \max\{V_k, 0 \leq k \leq m\}$, there exists a $k$ such that $V_k = \Lambda$. From the definition of $V_k$, we see that there exists $\pi^k \in L_k$ such that $$\begin{aligned}
\tilde{V}(\pi^k) = \Lambda, \pi^k \subset \pi_0^{k+1}, \text{ and }\pi^k \neq \pi^k_0.\end{aligned}$$ where $\pi_0^{k+1}$ is the $(k+1)$-cycle that contain $K_{i_0}$. Therefore, Lemma \[lemma:hitting\_time\] implies that, for some $\beta > 0$, for some $\delta_4 < \delta_3$ and an appropriately chosen $\rho > 0$, with $T = \exp\{N(\Lambda-\delta_3)\} = \exp\{N(\tilde{V}(\pi^k) - \delta_3)\}$, we have $$\begin{aligned}
P_\nu(\mu_N(T) \in \gamma_{i_0})  \leq P_\nu(\bar{\tau}_{\pi^k} \leq T) \leq \exp\{-N\beta\},\end{aligned}$$ for any $\nu \in [\pi^k]_{\rho} \cap M_1^N(\mathcal{Z})$ and sufficiently large $N$. This completes the proof of the theorem.

The above theorem immediately gives a lower bound on $P_T(\nu, \xi)$ for any $\xi$ in a small neighbourhood of $K_{i_0}$, over time durations of order $\exp\{N(\Lambda-\delta)\}$ for some $\delta > 0$. Let us make this precise.

Under the conditions of Theorem \[thm:mixing\], for all $\nu \in M_1^N(\mathcal{Z})$, $\xi \in \gamma_{i_0} \cap M_1^N(\mathcal{Z})$ and $N$ sufficiently large, we have $$\begin{aligned}
P_{T_0}(\nu, \xi) \geq \exp\{-2N\varepsilon\}.\end{aligned}$$ \[cor:lowerboundtransition\]

Given $\varepsilon > 0$, let $\rho, N_0$ and $T_0$ be as in the statement of Theorem \[thm:mixing\]. Choose $t$ large enough (not depending on $N$) and $\rho^\prime < \rho$ such that for all $\rho_1 \leq \rho^\prime$ we have $S_t(\nu_1|\nu_2) \leq \varepsilon/2$ for all $\nu_1, \nu_2 \in \gamma_{i_0}$. This is possible by the joint continuity of the rate function $S_t(\cdot|\cdot)$ and the fact that $V(\nu_1, \nu_2) = 0$ whenever $\nu_1, \nu_2 \in K_{i_0}$. Therefore, using the large deviation lower bound, there exists $N_2 \geq N_1$ such that $$\begin{aligned}
P_t(\nu_1, \nu_2) \geq \exp\{-N(S_t(\nu_2 | \nu_1) + \varepsilon/2)\} \geq \exp\{-N\varepsilon\},\end{aligned}$$ for all $\nu_1, \nu_2 \in \gamma_{i_0} \cap M_1^N(\mathcal{Z})$ and $N \geq N_2$. Therefore, by Theorem \[thm:mixing\], for $\nu \in M_1^N(\mathcal{Z}), \xi \in \gamma_{i_0} \cap M_1^N(\mathcal{Z})$ and $N \geq N_2$, we have $$\begin{aligned}
P_{T_0}(\nu, \xi) & = \sum_{\nu_2 \in \gamma_{i_0} \cap M_1^N(\mathcal{Z})} P_{T_0-t}(\nu_1, \nu_2) P_t(\nu_2, \xi)  \\
&  \geq P_{T_0-t}(\nu_1, \gamma_{i_0}) \inf_{\nu_2 \in \gamma_{i_0} \cap M_1^N(\mathcal{Z})} P_t(\nu_2, \xi) \\
& \geq \exp\{-2N \varepsilon\}.\end{aligned}$$

We now prove our first main result, namely convergence of $\mu_N$ to the invariant measure. Intuitively, the result says that, over a time duration $\exp\{N(\Lambda+\delta)\}$ for any $\delta>0$, the process is very close to its invariant measure $\wp_N$. Define $\tilde{L}_0 \coloneqq \{i \in L : W(K_i) = 0\}$, i.e, $\tilde{L}_0$ denotes the set of minimisers of the rate function $s$ (see Theorem \[thm:invariant-measure-gase\]).

Given $\delta > 0$, there exist $\varepsilon > 0$ and $N_0 \geq 1 $ such that for all $\nu \in M_1^N(\mathcal{Z})$ and $N \geq N_0$ $$\begin{aligned}
\left| E_\nu (f(\mu_N(T) ))- \langle f, \wp_N \rangle \right| \leq \|f\|_\infty \exp\{-\exp(N\varepsilon)\},\end{aligned}$$ where $T = \exp\{N(\Lambda+\delta)\}$ and $f \in B(M_1(\mathcal{Z}))$. \[thm:conv\]

We follow the steps in Hwang and Sheu [[@hwang-sheu-90 Part I, Theorem 2.5]]{}. Let $\varepsilon > 0$, and let $T_0, \delta_0, \rho, \rho_1$ and $N_0 \geq1$ be as in the statement of Theorem \[thm:mixing\]. Note that, for any $\nu \in M_1^N(\mathcal{Z})$, $\xi \notin [\tilde{L}_0]_{\rho_1}$ and for some fixed $t > 0$, $$\begin{aligned}
P_{T_0}(\nu,\xi)& = \sum_{\nu^\prime \in [K_{i_0}]} P_{T_0-t}(\nu, \nu^\prime) P_t(\nu^\prime, \xi)\\
& \geq \exp\{-2N\varepsilon\} \inf_{\nu^\prime \in [K_{i_0}]} P_t(\nu^\prime, \xi) \\
& \geq \exp\{-2N\varepsilon\} \exp\{-N\sup_{\nu^\prime \in [K_{i_0}]} S_t(\xi|\nu^\prime)\}\end{aligned}$$ where the first inequality follows from Corollary \[cor:lowerboundtransition\] and the second from the uniform LPD (Corollary \[cor:uniform\_ldp\]). Hence, we can find a function $U : M_1(\mathcal{Z}) \to [0, \infty)$ such that $U(\xi) = 0$ for $\xi \in [\tilde{L}_0]_{\rho_1}$ and $$\begin{aligned}
P_{T_0}(\nu,\xi) \geq c_N \exp\{-NU(\xi)\}
\label{eqn:temp8}\end{aligned}$$ holds for all $\nu \in M_1^N(\mathcal{Z})$, $\xi \notin [\tilde{L}_0]_{\rho_1}$ and sufficiency large $N$; here $c_N$ is such that $$\begin{aligned}
\pi_N(\xi) = c_N\exp\{-NU(\xi)\}\end{aligned}$$ is a probability measure on $M_1^N(\mathcal{Z})$. Define $Q_{T_0}(\nu ,\cdot) \coloneqq P_{T_0}(\nu, \cdot)/ \pi(\cdot)$. We have, for any $\nu_1, \nu_2 \in M_1^N(\mathcal{Z})$ and sufficiently large $N$, $$\begin{aligned}
E_{\nu_1}&(f(\mu_N(T_0))) - E_{\nu_2}(f(\mu_N(T_0)))  \\
& = \sum_{\xi \in M_1^N(\mathcal{Z})}P_{T_0}(\nu_1,\xi) f(\xi) - \sum_{\xi \in M_1^N(\mathcal{Z})}P_{T_0}(\nu_2,\xi) f(\xi) \\
& = \sum_{\xi \in M_1^N(\mathcal{Z})}Q_{T_0}(\nu_1,\xi) f(\xi)  \pi_N(\xi)- \sum_{\xi \in M_1^N(\mathcal{Z})}Q_{T_0}(\nu_2,\xi) f(\xi) \pi_N(\xi) \\
& = \sum_{\xi \in M_1^N(\mathcal{Z})}(Q_{T_0}(\nu_1,\xi)- \exp\{-2N\varepsilon\})f(\xi) \pi_N(\xi) \\
& \, \, \, \, \, \, \, \, -\sum_{\xi \in M_1^N(\mathcal{Z})}(Q_{T_0}(\nu_2,\xi) - \exp\{-2N\varepsilon\}) f(\xi) \pi_N(\xi) \\
& \leq (1-\exp\{-2N\varepsilon\}) (\sup_\xi f(\xi) - \inf_\xi f(\xi)),\end{aligned}$$ where the last inequality follows from (\[eqn:temp8\]) and the fact that $Q_{T_0}(\cdot, \cdot) \geq 1$. Therefore, we have that $$\begin{aligned}
\sup_{\nu_1, \nu_2} | E_{\nu_1}&(f(\mu_N(T_0))) - E_{\nu_2}(f(\mu_N(T_0)))  | \leq (1-\exp\{-2N\varepsilon\}) \| f\|_\infty.\end{aligned}$$ Continuing this procedure $k$ times, and by using the Markov property, we get $$\begin{aligned}
\sup_{\nu_1, \nu_2} |E_{\nu_1}&(f(\mu_N(kT_0))) - E_{\nu_2}(f(\mu_N(kT_0))) |  \leq (1-\exp\{-2N\varepsilon\})^k \| f\|_\infty,\end{aligned}$$ and hence, we have $$\begin{aligned}
\sup_{\nu} | E_{\nu}&(f(\mu_N(kT_0))) - \langle f, \wp_N \rangle | \leq (1-\exp\{-2N\varepsilon\})^k \| f\|_\infty.\end{aligned}$$ Choose $k = \exp\{N(\delta_0+\delta)\}$, then we have $kT_0 = \exp\{N(\Lambda + \delta)\}$ and the above becomes $$\begin{aligned}
\sup_{\nu} | E_{\nu}&(f(\mu_N(kT_0))) - \langle f, \wp_N \rangle | \leq \exp\{-\exp(N(-2\varepsilon+\delta_0 + \delta))\}.\end{aligned}$$ We can choose $\varepsilon$ small enough such that the quantity $-2\varepsilon+ \delta > 0$, and hence for some $\varepsilon^\prime > 0$, we have $$\begin{aligned}
\sup_{\nu} | E_{\nu}&(f(\mu_N(T))) - \langle f, \wp_N \rangle | \leq \exp\{-\exp(N\varepsilon^\prime)\},\end{aligned}$$ for sufficiently large $N$, where $T = \exp\{N(\Lambda+\delta)\}$. This establishes the result.

Asymptotics of the second eigenvalue for reversible processes {#section:eval_problem}
=============================================================

In this section, our goal is to understand the convergence rate of $\mu_N$ to its invariant measure for a fixed $N$. For this purpose, we shall assume that the Markov process $\mu_N$ is reversible. That is, the operator $L^N$ is self-adjoint in $L^2(\wp_N)$ and it admits a spectral expansion; let $0 =\lambda_1^N > -\lambda_2^N \geq -\lambda_3^N \ldots$ denote its eigenvalues in the decreasing order, and let $u_1^N \equiv 1, u_2^N, u_3^N,\ldots$ denote their corresponding eigenfunctions. The spectral expansion enables us to write, for any $f \in B(M_1(\mathcal{Z}))$, $$\begin{aligned}
E_\nu f(\mu_N(t)) = \langle f, \wp_N\rangle + \sum_{k \geq 1} e^{-t\lambda_k^N} ( f, u_k^N ) u_k^N(\nu),
\label{eqn:spectral_expansion}\end{aligned}$$ where $( \cdot, \cdot )$ denotes the inner product in $L^2(\wp_N)$. Therefore, the convergence rate of $E_\nu f(\mu_N(t))$ to its stationary value $\langle f, \wp_N \rangle$ is determined by the leading term in the above sum, which is the second eigenvalue $\lambda_2^N$. Hence, to understand convergence of $\mu_N$ to its invariant measure, we study the asymptotics of the second eigenvalue $\lambda_2^N$.

We first need the following lemma that estimates the probability that the process $\mu_N$ is outside a small neighbourhood of the set $\cup_{i=1}^l K_i$. This can be shown using Theorem \[thm:conv\] with deals with the convergence to the invariant measure and Theorem \[thm:invariant-measure-gase\] which addresses large deviations of the invariant measure $\{\wp_N\}_{N \geq 1}$.

Fix $\rho_1 >0$ and let $B$ be the $\rho_1$-neighbourhood of $\cup_{i \in L} K_i$. Given $\varepsilon > 0$, there exist $\delta >0$ and $N_0 \geq 1$ such that for each $\nu \in M_1^N(\mathcal{Z})$ and $N \geq N_0$, we have $$\begin{aligned}
P_\nu \left(\mu_N(T) \in M_1^N(\mathcal{Z}) \setminus B\right) \leq \exp\{-N\delta\},\end{aligned}$$ where $T = \exp\{N(\Lambda+ \varepsilon)\}$.

We are now ready to prove our next main result on the asymptotics of the second eigenvalue $\lambda_2^N$.

$$\begin{aligned}
\lim_{N \to \infty} \frac{1}{N} \log \lambda_2^N = -\Lambda.\end{aligned}$$

\[thm:eval\_problem\]

(Lower bound): Suppose that there exists a subsequence $\{N_k\}_{k \geq 1}$ such that $$\begin{aligned}
\log \lambda_2^{N_k} < -N_k(\Lambda + \varepsilon)
\label{eqn:temp-assumption}\end{aligned}$$ for some $\varepsilon > 0$. We will show that this contradicts $\int (u_2^{N_k}(\nu))^2 \wp_N(d\nu) =1 $ for sufficiently large $k$. Fix $\rho >0 $ and define $B \coloneqq \cup_{i=1}^l [K_i]_{\rho}$. Then, using the lower semicontinuity of the rate function $S_t(\cdot|\cdot)$ and Corollary \[cor:uniform\_ldp\] on uniform LDP, we see that for sufficiently large $t$, there exists $\delta_1 >0$ such that $\inf\{S_t(\xi|\nu):\xi, \nu \in B^c\} = \delta_1 > 0$. Therefore, for any $\nu \in B^c \cap M_1^N(\mathcal{Z})$ and any $\delta_2>0$, there exists $N_0 \geq 1$ such that for all $N \geq N_0$, $$\begin{aligned}
P_\nu(\mu_N(t) = \nu) \leq \exp\{-N(S_t(\nu|\nu) - \delta_2)\} \leq \exp\{-N(\delta_1 + \delta_2)\}.\end{aligned}$$ On the other hand, (\[eqn:spectral\_expansion\]) implies that, $$\begin{aligned}
P_\nu(\mu_N(t) = \nu) & = E_\nu(1_{\nu}(\mu_N(t))) \\
&\geq e^{-\lambda_2^Nt} (u_2^N(\nu))^2 \wp_N(\nu),\end{aligned}$$ so that $$\begin{aligned}
\int_{B^c} |u_2^N|^2 \wp_N (d \nu) \leq \exp\{-N(\delta_1 + \delta_2)\}
\label{eqn:temp11}\end{aligned}$$ for all $N \geq N_0$. To bound the integral over $B$, by Theorem \[thm:conv\], with $T = \exp\{N(\Lambda+\varepsilon/2)\}$, there exist $\delta_3>0$ and $N_1 \geq N_0$ such that for all $N \geq N_1$, $$\begin{aligned}
\left|E_\nu f(\mu_N(T)) - \langle f, \wp_N \rangle \right| \leq \|f\|_\infty \exp\{-\exp(N\delta_3)\},\end{aligned}$$ for any $f \in B(M_1(\mathcal{Z}))$. On the other hand, from (\[eqn:spectral\_expansion\]), for any $\nu \in B \cap M_1^N(\mathcal{Z})$, with $f = 1_\nu$, we have

$$\begin{aligned}
\left| E_\nu f(\mu_N(T)) - \langle f, \wp_N \rangle \right| & = \sum_{i \geq 2} \exp\{-\lambda_i^NT\} \langle f, \wp_N(\nu) \rangle u_i^{N}(\nu) \\
& \geq \exp\{-\lambda_2^{N}T\} (u_2^{N}(\nu))^2 \wp_N(\nu),\end{aligned}$$

so that, by our assumption (\[eqn:temp-assumption\]), there exists a $k_0 \geq 1$ such that $$\begin{aligned}
u_2^{N_k}(\nu))^2 \wp_{N_k}(\nu) & \leq \exp\{\lambda_2^{N_k}T\}  \exp\{-\exp(N_k\delta_3)\} \\
& \leq  \exp\{2\exp(-N_k(\Lambda+\varepsilon)) \exp(N_k(\Lambda+\varepsilon/2))\} \exp\{-N_k\delta_3\}\end{aligned}$$ for all $k \geq k_0$. Since $|M_1^{N_k}(\mathcal{Z})| \leq (N_k+1)^{|\mathcal{Z}|}$ for all $k$, the above implies that, for some $\delta_4 > 0$, $$\begin{aligned}
\int_B (u_2^{N_k}(\nu))^2 \wp_{N_k}(d\nu) \leq \exp\{-N_k\delta_4\}
\label{eqn:temp12}\end{aligned}$$ for all $k \geq k_0$. Therefore, (\[eqn:temp11\]) and (\[eqn:temp12\]) implies that, for some $\delta > 0$, $$\begin{aligned}
\int_{M_1(\mathcal{Z})}  (u_2^{N_k}(\nu))^2 \wp_{N_k}(d\nu) \leq \exp\{-N_k\delta\}\end{aligned}$$ for all sufficiently large $k$, which is a contradiction to $\int  (u_2^{N_k}(\nu))^2 \wp_{N_k} (d\nu) =1$ for all sufficiently large $k$.

(Upper bound): Suppose that there exists a subsequence $\{N_k\}_{k \geq 1}$ such that $\log \lambda_2^N > N_k(-\Lambda + \varepsilon)$ for some $\varepsilon>0$. Let $\nu_0, \delta_0<\varepsilon/2, \rho, N_0$ be as in Theorem \[thm:mixing\]. Then, with $f(\nu) =1_{[K_{i_0}]_{\rho/2}}(\nu)$ and $T = \exp\{N(\Lambda-\delta_0/2)\}$, (\[eqn:ub\_tpm\]) implies that $$\begin{aligned}
E_\nu f(\mu_N(T)) = P_\nu(\mu_N(T) \in [K_{i_0}]_{\rho/2}) \leq \exp\{-N\beta\}\end{aligned}$$ for all $N \geq N_0$ and $\nu \in  [\nu_0]_{\rho/2 } \cap M_1^N(\mathcal{Z})$. Also, by Theorem \[thm:invariant-measure-gase\], for any $\delta >0$, there exists $N_1 \geq N_0$ such that for all $N \geq N_1$, we have $$\begin{aligned}
\langle f, \wp_N \rangle = \wp_N([K_{i_0}]_{\rho/2}) \geq \exp\{-N\delta\}.\end{aligned}$$ This is possible since $\inf_{\xi \in [K_{i_0}]_{\rho/2}}s(\xi) =0$. Therefore, for all $N \geq N_1$, $$\begin{aligned}
\int_{M_1(\mathcal{Z})} |E_\nu(f(\mu_N(T))) & - \langle f, \wp_N \rangle |^2 \wp_N(d\nu) \\
&\geq \int_{[\nu_0]_{\rho/2}} \left|E_\nu(f(\mu_N(T))) - \langle f, \wp_N \rangle \right|^2 \wp_N(d\nu) \\
& \geq \wp_N([\nu_0]_{\rho/2}) (\exp\{-N\beta\} - \exp\{-N\delta\}) \\
&\geq \wp_N([\nu_0]_{\rho/2}) \exp\{-N\delta_1\}, \text{ for some } \delta_1 > 0 \\
&\geq \exp\{-N\delta_2\}, \text{ for some } \delta_2 > 0,\end{aligned}$$ where the last inequality follows by Theorem \[thm:invariant-measure-gase\]. On the other hand, for any function $f$ with $\int |f|^2 d\wp_N \leq 1$, we have $$\begin{aligned}
\int_{M_1(\mathcal{Z})} |E_\nu(f(\mu_N(T))) & - \langle f, \wp_N \rangle |^2 \wp_N(d\nu)  \\
& =  \int_{M_1(\mathcal{Z})} \sum_{k\geq 2} e^{-2\lambda_k^NT} \langle f, u_2^N\rangle u_2^N(\nu)^2 \wp_N(d\nu) \\
&\leq \exp\{-2\lambda_2^NT\} \int_{M_1(\mathcal{Z})} |f|^2 d\wp_N  \\
&\leq \exp\{-2\lambda_2^NT\}.\end{aligned}$$ Therefore, we have $ \exp\{-2\lambda_2^{N}T\} \geq \exp\{-N\delta_2\}$ whenever $N \geq N_1$. By our assumption, we see that $$\begin{aligned}
 \exp\{-2\exp(-N_k(\Lambda-\varepsilon)) \exp(N_k(\Lambda-\delta_0))\} \geq \exp\{-N_k\delta_1\}\end{aligned}$$ for sufficiently large $k$, which is a contradiction since $\delta_0 < \varepsilon/2$.

Using the above theorem, we see that, if $\Lambda>0$, then as $N$ becomes large, it takes longer for the process $\mu_N$ to be close to its invariant measure. This particularly means that metastable states reduce the rates of convergence of $\mu_N$ to its invariant measure. On the other hand, if there is a unique global attractor of the limiting McKean-Vlasov equation (\[eqn:MVE\]), then we see that $\Lambda = 0$, and convergence rate of $\mu_N$ to its invariant measure does not suffer from such a slowing down phenomenon.

Convergence to the global minimum {#section:conv_global_minimum}
=================================

In this section, our goal is to increase the number of particles $N$ over time so as to obtain, with very high probability, convergence of the empirical measure process to a global minimum of the rate function $s$ that governs the LDP for the sequence of invariant measure $\{\wp_N\}_{N\geq 1}$.

Fix $c>0$. Let $N_0 = \min\{n \in \mathbb{N} : \exp\{nc\} - 2 \geq 0 \}$, $t_{N_0} = 0$, and for each $N > N_0$, let $t_N = \exp\{Nc\}-2$. For each $N \geq N_0$ define the generator $L^N_t$ acting on bounded measurable functions on $M_1(\mathcal{Z})$ by $$\begin{aligned}
L_t^Nf (\xi) \coloneqq \sum_{(z,z^\prime) \in E} N_t \xi(z) \lambda _{z,z^\prime}(\xi) \left[ f\left(\xi+\frac{e_{z^\prime}}{N_t}- \frac{e_z}{N_t}\right) - f(\xi) \right], \, t\in [t_{N}, t_{N+1}).\end{aligned}$$ where $N_t = N$ for $t \in [t_N, t_{N+1})$. Let $z_0 \in \mathcal{Z}$ be a fixed state and let $\nu \in M_1^{N_0}(\mathcal{Z})$. We say that a probability measure $P_{0,\nu}$ on $D([0,\infty),M_1(\mathcal{Z}))$ is a solution to the martingale problem for $\{L^N\}_{N \geq N_0}$ with initial condition $\nu$ if $P_{0,\nu}(\bar{\mu}: \bar{\mu}(0) = \nu)=1$, for each $N \geq N_0$, the restriction of $P_{0,\nu}$ on $D([t_N, t_{N+1}), M_1^{N}(\mathcal{Z}))$ is a solution to the $D([t_N, t_{N+1}), M_1^{N}(\mathcal{Z}))$-valued martingale problem for $L^N$, and $$\begin{aligned}
P_{0,\nu}\left(\bar{\mu}: \bar{\mu}(t_{N+1}) = \frac{N}{1+N}\bar{\mu}(t_{N+1}^-) + \frac{1}{N+1} \delta_{z_0}\right)  =1.\end{aligned}$$ Again, by the boundedness assumption on transition rates \[assm:a2\], for each $\nu \in M_1^{N_0}(\mathcal{Z})$, there exists a unique probability measure $P_{0,\nu}$ that solves the martingale problem for $\{L^N\}_{N \geq 1}$ with initial condition $\nu$. Let $\bar{\mu}$ be the process on $D([0,\infty),M_1(\mathcal{Z}))$ whose law is $P_{0,\nu}$. To describe the process in words, we start with $N_0$ particles and follow the mean-field interaction described in Section \[section:introduction\], except that at each time instant $t_N, N > N_0$, we add a new particle whose state is set to $z_0$.

We anticipate that if $c$ is small then $N_t$ is so large that the fluid limit kicks in too quickly over time and the process $\bar{\mu}$ converges (over time) to a local minimum of $s$ with positive probability depending on the initial condition $\bar{\mu}(0)$. When $c$ is sufficiently large, we anticipate that there is enough time for exploration and therefore we will converge to a global minimum of $s$. Recall that the set of global minimisers of $s$ is denoted by $\tilde{L}_0$. Our interest in this section is in finding a constant $c^*$ such that for all $c >  c^*$ and $\nu \in M_1^{N_0}(\mathcal{Z})$, we have, $$\begin{aligned}
P_{0,\nu} (\bar{\mu}(t) \text{ lies in a neighbourhood of }\tilde{L}_0) \to  1
\label{eqn:conv_globalmin}\end{aligned}$$ as $t \to \infty$.

We use the results in the previous sections to identify the constant $c^*$. Since $N_t \to \infty$ as $t \to \infty$, for a fixed $T > 0$ and large enough $t$, the large deviation properties of the process $\{\bar{\mu}(s),  t \leq s \leq t+T \}$ from the limiting dynamics (\[eqn:MVE\]) starting at an arbitrary $\bar{\mu}(t)$ can be obtained similar to the LDP of the process $\mu_N$ studied in Theorem \[thm:finite-duration-ldp\] and Corollary \[cor:uniform\_ldp\]. Therefore, the results in the previous sections on the large time behaviour for the process $\{\mu_N(t), t\geq 0\}$ are also valid for $\{\bar{\mu}(t) , t \geq 0\}$ when time $t$ is large enough; we make these precise now.

Let $\pi_1^k$ and $\pi_2^k$ be $k$-cycles and suppose that $\pi_1^k \to \pi_2^k$ and $\tilde{V}(\pi_1^k)/c < 1$. Then, given $\varepsilon > 0$, there exist $\delta>0$ and $\rho>0$ such that for all $\rho_1 < \rho$, there is $t^* >0$ such that $$\begin{aligned}
P_{t,\nu}(\bar{\tau}_{\pi^k_1} \leq t + t^{(\tilde{V}(\pi_1^k) -\delta)/c}, \bar{\mu}(\bar{\tau}_{\pi_1^k}) \in \gamma_{\pi_2^k}) \geq t^{-\varepsilon/c}\end{aligned}$$ holds uniformly for all $\nu \in [\pi_1^k]_{\rho_1} \cap M_1^{N_{t}}(\mathcal{Z})$ and $t \geq t^*$. \[lemma:hs22\]

The condition $\tilde{V}(\pi_1^k) /c <1$ in the above lemma ensures that during the time duration $[t, t^{\tilde{V}(\pi_1^k)/c}]$, for large enough $t$, the number of particles does not change so that Lemma \[lemma:hitting\_place\] for the process $\mu_N$ is applicable for the process $\bar{\mu}$.

Let $\pi^k$ be a $k$-cycle and suppose that $\tilde{V}(\pi^k)/c < 1$. Then, given $\delta > 0$ such that $(\tilde{V}(\pi^k)+\delta)/c < 1$, there exist $\varepsilon > 0$ and $\rho>0$ such that for all $\rho_1 < \rho$, there is $t^* > 0$ such that $$\begin{aligned}
P_{t,\nu}(\bar{\tau}_{\pi^k} & <  t + t^{(\tilde{V}(\pi^k) -\delta)/c}) \leq t^{-\varepsilon/c}, \text{ and }\\
P_{t,\nu}(\bar{\tau}_{\pi^k}& > t + t^{(\tilde{V}(\pi^k) +\delta)/c}) \leq t^{-\varepsilon/c}\end{aligned}$$ holds uniformly for all $\nu \in [\pi^k]_{\rho_1} \cap M_1^{N_{t}}(\mathcal{Z})$ and $t \geq t^*$. \[lemma:hs23\]

Let $\pi^k$ be a $k$-cycle and suppose that $\hat{V}(\pi^k)/c < 1$. Given $\varepsilon>0$, there exist $\delta  \in (0, c-\hat{V}(\pi^k))$ and $\rho>0$ such that for all $\rho_1 \leq \rho$, there is $t^* >0$ such that $$\begin{aligned}
P_{t,\nu}(\bar{\tau}_{\pi^k}\leq t + t^{(\hat{V}(\pi^k)+\delta)/c}) \leq t^{-(\tilde{V}(\pi^k) - \hat{V}(\pi^k)-\varepsilon)/c}\end{aligned}$$ holds uniformly for all $\nu \in [\pi^k]_{\rho_1} \cap M_1^{N_{t}}(\mathcal{Z})$ and $t \geq t^*$. \[lemma:hs24\]

Recall the definition of the sets $L$ and $C$ from Section \[section:large\_time\_behaviour\].

\[lemma:conv-fw19\] Given $\rho_0 > 0$ and $\rho_1 <\rho_0$ and their associated sets $L$ and $C$, given $v>0$, there exist $T^* > 0$ and $t^* >0 $ such that $$\begin{aligned}
P_{t,\nu}(\hat{\tau}_L \geq t + T^*) \leq t^{-v/c}\end{aligned}$$ holds uniformly for all $\nu \in C \cap M_1^{N_{t}}(\mathcal{Z})$ and $t \geq t^*$.

To answer the question on the convergence of $\bar{\mu}$ to the global minimum of $s$, we define the following quantities, analogous to what is done in Hwang and Sheu [@hwang-sheu-90]. Let $m$ be such that $L_{m+1}$ is a singleton (denote it by $\{\pi^{m+1}\}$). Define $$\begin{aligned}
A_m \coloneqq \{\pi^m \in L_m:\tilde{V}(\pi^m) = \hat{V}(\pi^{m+1})\}.\end{aligned}$$ Inductively define, for each $\pi^{k+1} \in L_{k+1}$, $$\begin{aligned}
A_{k}(\pi^{k+1}) \coloneqq \{\pi^k \in \pi^{k+1} : \tilde{V}(\pi^k) = \hat{V}(\pi^{k+1})\},\end{aligned}$$ and for each $k \geq 1$, define $$\begin{aligned}
A_k \coloneqq \bigcup_{\pi^{k+1} \in A_{k+1}} A_k(\pi^{k+1}).\end{aligned}$$ Also, for each $\pi^k \in L_k$, define $$\begin{aligned}
c_{k-1}(\pi^k)  \coloneqq \left\{\begin{array}{ll}
0,  \text{ if } \{ \pi^{k-1} \in \pi^k : \pi^{k-1} \notin A_{k-1}(\pi^k) \} = \emptyset, \\
\max\{\tilde{V}(\pi^{k-1}):\pi^{k-1} \notin A_{k-1}(\pi^k), \pi^{k-1} \in \pi^k\}, \text{  otherwise},
\end{array}
\right.\end{aligned}$$ and for each $k \geq 1$, define $$\begin{aligned}
c_{k-1} \coloneqq \max\{c_{k-1}(\pi^k), :\pi^k \in A_k\}.\end{aligned}$$ Finally, define $$\begin{aligned}
c^* \coloneqq \max\{c_k, 0 \leq k \leq m\}.\end{aligned}$$ Similar to [@hwang-sheu-90 Lemma A.11, Appendix], we can show that $A_0 = \tilde{L}_0$, the set of minimisers of the rate function $s$ that governs the LDP for the invariant measure $\{\wp_N\}_{N\geq 1}$. We now have the following theorem on the convergence of $\bar{\mu}$ to the global minimum of the rate function $s$.

For $c > c^*$ and any $\rho_1 > 0$, $$\begin{aligned}
P_{0,\nu} (\bar{\mu}(t) \in [\tilde{L}_0]_{\rho_1}) \to 1\end{aligned}$$ as $t \to \infty$, uniformly for all $\nu \in M_1^{N_0}(\mathcal{Z})$. \[thm:conv-globalmin\]

It suffices to show that, for any $\delta > 0$ with $(c^*+\delta)/c<1$, there exist $\varepsilon > 0$, $\rho_1>0$ and $t^* > 0$ such that $$\begin{aligned}
P_{t, \nu} (\bar{\mu}(t + t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1}) \geq 1- t^{-\varepsilon/c}\end{aligned}$$ for all $t > t^*$ and $\nu \in M_1^{N_{t}}(\mathcal{Z})$. Define the stopping time $$\begin{aligned}
\theta \coloneqq \inf\{s>t: \bar{\mu}(s) \in [L]_{\rho_1}\}.\end{aligned}$$ By Lemma \[lemma:conv-fw19\], for any $M >0$, there exists $T^*>0$ such that for all $\nu \in M_1^{N_0}(\mathcal{Z})$ and large enough $t$, we have $$\begin{aligned}
P_{t, \nu} (\theta > t + T^*) \leq t^{-M/c}.\end{aligned}$$ By the strong Markov property, we have $$\begin{aligned}
P_{t, \nu}&( \bar{\mu}(t + t^{(c^*+\delta)/c})\in [\tilde{L}_0]_{\rho_1}) \nonumber \\
& \geq E_{t,\nu} (\theta \leq t + T^*; E_{\theta, \bar{\mu}(\theta)} (\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1})) \nonumber \\
& \geq \inf_{\substack{t \leq t_1 \leq t+T^* \\ \nu_1 \in [L]_{\rho_1}}} P_{t_1, \nu_1} (\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1}) (1-t^{-M/c}).
\label{eqn:temp7}\end{aligned}$$ To bound the first term above, fix a $t_1$ such that $t \leq t_1 \leq t+T^*$ and $\nu_1 \in [L]_{\rho_1}$. Define the stopping time $\theta_m \coloneqq \inf \{t>t_1: \bar{\mu}(t) \in [A_m]_{\rho_1}\}$. We have $$\begin{aligned}
P_{t_1, \nu_1} &(\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1}) \nonumber \\
& \geq E_{t_1, \nu_1} (\theta_m < t+t^{(c^*+\delta/2)/c}; E_{\theta_m, \bar{\mu}(\theta_m)}(\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1})) \nonumber \\
& \geq \inf_{t \leq t_2 \leq t+t^{(c^*+\delta/2)/c}, \nu_2 \in [A_m]_{\rho_1}} P_{t_2, \nu_2}(\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1})  \nonumber \\
& \, \, \, \, \, \, \, \, \, \, \times P_{t_1, \nu_1}(\theta_m  \leq t+t^{(c^*+\delta/2)/c}). \label{eqn:temp6}\end{aligned}$$ We first bound the second term $P_{t_1, \nu_1}(\theta_m  \leq t+t^{(c^*+\delta/2)/c})$. Note that, by Lemma \[lemma:hs22\], for any $M_1>0$, there exists $\delta_1>0$ such that $$\begin{aligned}
P_{t_1, \nu_1}(\theta_m  > t_1+t_1^{(c_m-\delta_1)/c}) \leq 1-t_1^{-M_1/c}\end{aligned}$$ for sufficiently large $t$. Let $T_1 = t_1 + t_1^{(c_m-\delta_1)/c}$, and define the stopping time $\hat{\theta} \coloneqq \inf\{t>T_1: \bar{\mu}(t) \in [L]_{\rho_1} \}$. Again, by Lemma \[lemma:conv-fw19\], there exists a large enough $T^*$ such that $P_{T_1, \nu}(\hat{\theta} > T_1+T^*) \leq T_1^{-M/c}$ for all $\nu \in M_1^{N_{T_1}}(\mathcal{Z})$. Therefore, using the strong Markov property, we have $$\begin{aligned}
P_{t_1, \nu_1}&(\theta_m  > t+t^{(c^*+\delta/2)/c}) \nonumber \\
& \leq E_{t_1, \nu_1}(\theta_m \geq \hat{\theta}, \hat{\theta}< T_1+T^*; E_{\hat{\theta}, \bar{\mu}(\hat{\theta})}(\theta_m >t+t^{(c^*+\delta/2)/c})) \nonumber \\
& \, \, \, \, \, \, \, \, + P_{t_1, \nu_1}(\hat{\theta} > T_1+T^*) \nonumber \\
& \leq P_{t_1, \nu_1}(\theta_m > T_1) \sup_{\substack{T_1 \leq t \leq T_1 + T^* \\  \nu \in [L]_{\rho_1}}} P_{t,\nu}(\theta_m > t+t^{(c^*+\delta/2)/c}) +t_1^{-M/c} \nonumber\\
& \leq (1-t_1^{-M_1/c} ) \sup_{\substack{T_1 \leq t \leq T_1 + T^* \\ \nu \in [L]_{\rho_1}}} P_{t,\nu}(\theta_m > t+t^{(c^*+\delta/2)/c}) +t_1^{-M/c}.  \label{eqn:temp5}\end{aligned}$$ We now focus on $P_{t,\nu}(\theta_m > t+t^{(c^*+\delta/2)/c})$ for a fixed $t \in [T_1, T_1+T^*]$ and $\nu \in [L]_{\rho_1}$, and repeat the above steps; this will introduce a multiplication factor of $(1-T_1^{-M_1/c})$ along with $$\begin{aligned}
\sup_{\substack{T_2 \leq t \leq T_2 + T^* \\ \nu \in [L]_{\rho_1}}} P_{t,\nu}(\theta_m > t+t^{(c^*+\delta/2)/c}),\end{aligned}$$ where $T_2 = T_1 + T_1^{(c_m-\delta_1)/c}$, in the first term in (\[eqn:temp5\]), and an addition of $t_1^{-M/c}$ in the second term. Therefore, repeating the above steps $r \sim t_1^{\delta/2c}$ times, we get $$\begin{aligned}
P_{t_1, \nu_1}(\theta_m  > t+t^{(c^*+\delta/2)/c}) \leq  \prod_{n=0}^r (1-T_n^{*{-M_1/c}}) + rt_1^{-M/c},\end{aligned}$$ where $T_0^* = t_1$, and $$\begin{aligned}
T_{n+1}^* = T_n^* + T_n^{*{(c_m-\delta_1)/c}} + T^*.\end{aligned}$$ Note that, $$\begin{aligned}
 \prod_{n=0}^r (1-T_n^{*{-M_1/c}}) & \leq  \exp\left\{-\sum_{n=0}^r T_n^{*{-M_1/c}} \right\} \nonumber \\
 & = \exp\left\{ -\sum_{n=0}^r T_n^{*{-M_1/c - (c_m-\delta_1)/c}}(T_{n+1}^* - T_n^*) \right\} \nonumber \\
 & \leq  \exp\left\{- \int_{T_0^*}^{T_r^*} u^{-(M_1/c) - (c_m-\delta_1)/c} du\right\} \nonumber \\
& = \exp \left\{ - \left( T_r^{*{1-(c_m+M_1-\delta_1)/c}} -  t_1^{1-(c_m+M_1-\delta_1)/c} \right)\right\}. \label{eqn:temp14}\end{aligned}$$ Since $T_n \geq t_1$ for all $n \geq 1$, we see that $T_r^* \geq t_1 + r t_1^{(c_m-\delta_1)/c} \sim t_1 + t_1^{(c_m-\delta_1+\delta/2)/c}$. Therefore, $$\begin{aligned}
-  & \left(T_r^{*{1-(c_m+M_1-\delta_1)/c}} -  t_1^{1-(c_m+M_1-\delta_1)/c} \right) \\
& \leq -\left( (t_1+t_1^{(c_m-\delta_1+\delta/2)/c})^{1-(c_m+M_1-\delta_1)/c} - t_1^{1-(c_m+M_1-\delta_1)/c}\right) \\
& \leq -\left( t_1^{1-(c_m+M_1-\delta_1)/c} \left( 1+t_1^{(c_m-\delta_1+\delta/2)/c-1}\right)^{1-(c_m+M_1-\delta_1)/c} -1\right) \\
& \leq -c^\prime \left(t_1^{1-(c_m+M_1-\delta_1)/c} t_1^{(c_m-\delta_1+\delta/2)/c-1} \right)  \\
& = -c^\prime t_1^{(\delta/2 - M_1)/c},\end{aligned}$$ for some constant $c^\prime  >0$ and large enough $t_1$. Hence, (\[eqn:temp14\]) becomes $$\begin{aligned}
 \prod_{n=0}^r (1-T_n^{*^{-M_1/c}}) \leq \exp\{-c^\prime t_1^{(\delta/2-M_1)/c}\}.\end{aligned}$$ We choose $M_1 = \delta/4$; the above and (\[eqn:temp5\]) then implies $$\begin{aligned}
P_{t_1, \nu_1}&(\theta_m  > t+t^{(c^*+\delta/2)/c}) \leq \exp\{-c^\prime t_1^{\delta/4c}\} + t_1^{-(M-\delta/2)/c},\end{aligned}$$ and this implies that, for any $M^\prime > 0$, $$\begin{aligned}
P_{t_1,\nu_1} (\theta_m > t+t^{(c^*+\delta/2)/c}) \leq t^{-M^\prime/c}
\label{eqn:temp13}\end{aligned}$$ for sufficiently large $t$, $t \leq t_1 \leq t+T^*$ and for all $\nu \in [L]_{\rho_1}$.

We now bound the first term in (\[eqn:temp6\]), $P_{t_2,\nu_2}(\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1})$ where $t \leq t_2 \leq t + t^{(c^*+\delta/2)/c}$ and $\nu_2 \in [A_m]_{\rho_1}$. Let $\pi_0^m \in A_m$ be the $m$-cycle such that $\nu_2 \in [\pi_0^m]_{\rho_1}$. Define the following quantities: $$\begin{aligned}
\tilde{t}_0 \coloneqq t+t^{(c^*+\delta)/c} - t^{(c_{m-1}(\pi^m_0)+\delta)/c}, \text{ and } \\
\tilde{t}_1 \coloneqq t+t^{(c^*+\delta)/c} - t^{(c_{m-1}(\pi^m_0)+\delta/2)/c}.\end{aligned}$$ Define the stopping time $\theta \coloneqq \inf \{t>\tilde{t}_0: \bar{\mu}(t) \in [\pi^m_0]_{\rho_1}\}$, if $c^* > c_{m-1}(\pi^m_0)$ and $\theta = t_2$ otherwise. By the strong Markov property, $$\begin{aligned}
P_{t_2,\nu_2}& (\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1}) \nonumber \\
& \geq E_{t_2,\nu_2}(\theta \leq \tilde{t}_1; E_{\theta, \bar{\mu}(\theta)}(\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1} )\nonumber \\
& \geq P_{t_2, \nu_2} (\theta \leq \tilde{t}_1) \inf_{\tilde{t}_0 \leq t_3 \leq \tilde{t}_1, \nu_3 \in [\pi_0^m]_{\rho_1}} P_{t_3,\nu_3}(\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1}).
\label{eqn:temp9}\end{aligned}$$ We first estimate $P_{t_2, \nu_2}(\theta \leq \tilde{t}_1)$ when $c^* > c_{m-1}(\pi_0^m)$ (if this is not the case, then by definition of $\theta$, we have $P_{t_2, \nu_2}(\theta \leq \tilde{t}_1)=1$) . Note that $$\begin{aligned}
P_{t_2,\nu_2} (\theta > \tilde{t}_1)  & = P_{t_2,\nu_2} (\bar{\mu}(t) \notin [\pi^m_0]_{\rho_1} \text{ for all } \tilde{t}_0 \leq t \leq \tilde{t}_1) \\
& \leq P_{t_2,\nu_2} (\bar{\mu}(t) \notin [L]_{\rho_1} \text{ for all } \tilde{t}_0 \leq t \leq \tilde{t}_1)  + P_{t_2, \nu_2}(\bar{\tau}_{\pi^m_0} \leq \tilde{t}_1).\end{aligned}$$ Lemma \[lemma:hs23\] implies that $$\begin{aligned}
 P_{t_2, \nu_2}(\bar{\tau}_{\pi^m_0} \leq \tilde{t}_1) \leq t^{-\delta/c}\end{aligned}$$ for large $t$ and small enough $\rho_1 > 0$. Also, with this $\rho_1$, by using Lemma \[lemma:conv-fw19\], we see that $$\begin{aligned}
P_{t_2,\nu_2} (\bar{\mu}(t) \notin [L]_{\rho_1} \text{ for all } \tilde{t}_0 \leq t \leq \tilde{t}_1)  \leq t^{-M_1/c}\end{aligned}$$ for large $t$, where $M_1$ can be chosen as large as we want. This shows that there exists $\varepsilon_1>0$ such that $$\begin{aligned}
P_{t_2,\nu_2} (\theta \leq \tilde{t}_1) \geq 1-2t^{-\varepsilon_1/c}\end{aligned}$$ uniformly for all $\nu_2 \in [\pi_0^m]_{\rho_1}$ and large enough $t$. Hence, from (\[eqn:temp13\]), (\[eqn:temp9\]) and (\[eqn:temp6\]), we get $$\begin{aligned}
P_{t_1,\nu_1}&(\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1}) \\
& \geq (1-t^{-M^\prime/c}) (1-2t^{-\varepsilon_1/c}) \\
& \, \, \, \, \, \, \, \, \times \inf_{\substack{t_2 \geq \tilde{t}_0, \\ \nu_2 \in [\pi_0^m]_{\rho_1} \\  \pi_0^m \in A_m \\  \tilde{\delta} \in [\delta/4, \delta]}} P_{t_2,\nu_2}(\bar{\mu}(t_2+t_2^{(c_{m-1}(\pi^m_0)+\tilde{\delta})/c}) \in [\tilde{L}_0]_{\rho_1})\end{aligned}$$ and therefore, for some $\varepsilon>0$, we have $$\begin{aligned}
\inf_{\substack{t \leq t_1  \leq t+T^*, \\ \nu_1 \in [L]_{\rho_1}}}&P_{t_1,\nu_1}(\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1}) \\
& \geq (1-t^{-\varepsilon/c}) \inf_{\substack{t_2 \geq \tilde{t}_0 \\ \nu_2 \in [\pi^m_0]_{\rho_1} \\ \pi_0^m \in A_m \\ \tilde{\delta} \in [\delta/4, \delta]}} P_{t_2,\nu_2}(\bar{\mu}(t_2+t_2^{(c_{m-1}(\pi^m_0)+\tilde{\delta})/c}) \in [\tilde{L}_0]_{\rho_1}).\end{aligned}$$ We now focus on the second term. This probability inside the infimum can be lower bounded using similar steps above starting with (\[eqn:temp9\]); instead of the random variable $\theta$, we consider the hitting time of a suitable $(m-1)$-cycle. Continuing this procedure $m$ times, we eventually reach $A_0$. Therefore, we can show $$\begin{aligned}
\inf_{\substack{t \leq t_1  \leq t+T^* \\ \nu_1 \in [\tilde{L}_0]_{\rho_1}}}&P_{t_1,\nu_1}(\bar{\mu}(t+t^{(c^*+\delta)/c}) \in [\tilde{L}_0]_{\rho_1})  \geq (1-t^{-\varepsilon/c})^{m+1},\end{aligned}$$ and the result now follows from (\[eqn:temp7\]).

We now show that the conclusion of Theorem \[thm:conv-globalmin\] fails if we choose $c < c^*$. Given $c < c^*$, let $\pi^k \in L_k$ be such that $\hat{V}(\pi^k) \leq c < \tilde{V}(\pi^k)$; this is possible from the definition of $c^*$. Note that $\tilde{L}_0 \cap \pi^k = \emptyset$. The below result shows that the exit time from a neighbourhood of $\pi^k$ is infinite with positive probability, and this in particular implies that (\[eqn:conv\_globalmin\]) fails.

Let $\pi^k$ be a $k$-cycle such that $\hat{V}(\pi^k) \leq c < \tilde{V}(\pi^k)$. There exist $\varepsilon \in (0, \tilde{V}(\pi^k)-c)$, $c^\prime >0, \rho_1>0$ and $t^*>0$ such that for all $\nu \in [\pi^k]_{\rho_1}\cap M_1^{N_{t}}(\mathcal{Z})$ and $t \geq t^*$, we have $$\begin{aligned}
P_{t, \nu}(\bar{\tau}_{\pi^k} <\infty) \leq c^\prime t^{1-(\tilde{V}(\pi^k) - \varepsilon)/c}.\end{aligned}$$

We proceed via the steps in Hwang and Sheu [@hwang-sheu-90]. Let $T_0 = t$, and define, for all $n \geq 1$, $$\begin{aligned}
T_{n+1} \coloneqq T_n + T_n^{\hat{V}(\pi^k)/c}, \text{ and}\\
T^*_{n+1} \coloneqq T_n + \frac{1}{2} T_n^{\hat{V}(\pi^k)/c}.\end{aligned}$$ (In the above definitions, we assume that $\hat{V}(\pi^k) > 0$; if this is not the case, then we replace $T_n^{\hat{V}(\pi^k)/c}$ in the above definitions by a sufficiently large constant, and the following arguments will go through.) We have, for any $r \geq 1$, $$P_{t, \nu} (\bar{\tau}_{\pi^k} <T_r) = P_{t, \nu} (\bar{\tau}_{\pi^k} <T_{r-1}) + P_{t, \nu} (T_{r-1} \leq \bar{\tau}_{\pi^k} <T_r).
\label{eqn:temp3}$$ To bound the second term, define the stopping time $\theta \coloneqq \inf\{t>T^*_{r-1}:\bar{\mu}(t) \in [L]_{\rho_1}\}$ where $\rho_1$ is to be chosen later. Then, $$\begin{aligned}
P_{t, \nu} (T_{r-1} \leq \bar{\tau}_{\pi^k} <T_r) &  = P_{t, \nu} (T_{r-1} \leq \bar{\tau}_{\pi^k}  <T_r, \theta \leq T_{r-1}^*+T^* )  \nonumber \\ 
&\, \, \, \, \, \, \, \, \, \, + P_{t, \nu} (T_{r-1} \leq \bar{\tau}_{\pi^k} <T_r, \theta > T_{r-1}^*+T^*) ,
\label{eqn:temp4}\end{aligned}$$ where $T^*$ is such that the second term above is upper bounded by $T_{r-1}^{*^{-M/c}}$ for some $M>0$ to be chosen later (this is possible by Lemma \[lemma:conv-fw19\]). To bound the first term, note that $$\begin{aligned}
P_{t, \nu} (T_{r-1} \leq &\bar{\tau}_{\pi^k} <T_r,  \theta \leq T_{r-1}^*+T^* )  \\
& \leq P_{t, \nu} (\theta\leq \bar{\tau}_{\pi^k} <T_r, \theta \leq T_{r-1}^*+T^* ) \\
& \leq E_{t,\nu} (\bar{\mu}(\theta) \in [\pi^k]_{\rho_1}, \theta \leq  T_{r-1}^*+T^* ; E_{\theta, \bar{\mu}(\theta)}(\bar{\tau}_{\pi^k} < T_r)) \\
& \leq T_{r-1}^{*-(\tilde{V}(\pi^k) - \hat{V}(\pi^k) - \varepsilon)/c}\end{aligned}$$ holds for sufficiently large $t$ and small enough $\rho_1$. Here, the second inequality follows by the strong Markov property and the third from Lemma \[lemma:hs24\]. Choose $M$ sufficiently large, so that (\[eqn:temp3\]), (\[eqn:temp4\]) and the above implies $$\begin{aligned}
P_{t,\nu}(\bar{\tau}_{\pi^k} < T_r) \leq P_{t,\nu}(\bar{\tau}_{\pi^k} < T_{r-1}) + 2T_{r-1}^{*^{-(\tilde{V}(\pi^k) - \hat{V}(\pi^k) -\varepsilon)/c}}.\end{aligned}$$ Therefore, we have $$\begin{aligned}
P_{t,\nu}(\bar{\tau}_{\pi^k} < T_r)  &\leq 2\sum_{n=0}^r T_n^{*^{-(\tilde{V}(\pi^k) - \hat{V}(\pi^k) -\varepsilon)/c}} \\
& \leq c_1^\prime  \sum_{n=0}^r T_n^{-(\tilde{V}(\pi^k) - \hat{V}(\pi^k) -\varepsilon)/c} \\
& = c_1^\prime \sum_{n=0}^r T_n^{-(\tilde{V}(\pi^k) - \varepsilon)/c} (T_{n+1} - T_n)\\
& \leq c_1^\prime \int_{t}^{T_r} u^{-(\tilde{V}(\pi^k)-\varepsilon)/c} du,\end{aligned}$$ where $c_1^\prime $ is a positive constant. Choose $\varepsilon $ such that $\tilde{V}(\pi^k) - \varepsilon > c$ so that the above implies $$\begin{aligned}
P_{t,\nu}(\bar{\tau}_{\pi^k} < T_r) &\leq c_1^\prime \int_{t}^ \infty u^{-(\tilde{V}(\pi^k)-\varepsilon)/c} du \\
& \leq c^\prime t^{1-(\tilde{V}(\pi^k)-\varepsilon)/c},\end{aligned}$$ where $c^\prime$ is a positive constant. Let $r \to \infty$, and the result follows since $T_r \to  \infty$.

Acknowledgements {#acknowledgements .unnumbered}
================

The authors would like to thank Laurent Miclo for fruitful discussions. This work was supported by the Indo-French Centre for Applied Mathematics. The first author was also supported by the IISc-Cisco Research Fellowship grant.
