# Self-Switching Markov Chains: emerging dominance phenomena

S. Gallo<EMAIL_ADDRESS>G. Iacobelli<EMAIL_ADDRESS>G. Ost
<EMAIL_ADDRESS>D. Y. Takahashi<EMAIL_ADDRESS>Universidade de
São Carlos, São Paulo, Brazil  Universidade Federal do Rio de Janeiro, Rio de
Janeiro, Brazil  Universidade Federal do Rio Grande do Norte, Natal, Brazil

###### Abstract

The law of many dynamical systems changes with the evolution of the system.
These changes are often associated with the occurrence of certain events whose
time of occurrence depends on the trajectory of the system itself. Dynamics
that take longer to change will be observed more frequently and may dominate
in the long run (the only ones observed). This article proposes a Markov chain
model, called Self-Switching Markov Chain, in which the emergence of dominant
dynamics can be rigorously addressed. We present conditions and scaling under
which we observe with probability one only the subset of dominant dynamics.

###### keywords:

Markov Chains, Scaling limits, animal behavior, evolution

††journal: Stochastic Processes and Application

###### Contents

  1. 1 Introduction
  2. 2 Model and main results
    1. 2.1 Self-Switching Markov Chains
    2. 2.2 Sequence of Self-switching Markov chains
      1. 2.2.1 Emerging dominance
      2. 2.2.2 Metastability
  3. 3 Self-switching environment Random Walks
    1. 3.1 Physical interpretation
    2. 3.2 Biological interpretation
    3. 3.3 Flat potential SSERW
    4. 3.4 Single-well potential SSERW
    5. 3.5 Alternating-wells potential SSERW
  4. 4 Final Comments
    1. 4.1 A biological consequence
  5. A Proofs
    1. A.1 $\widehat{P}_{N}$ and its asymptotic analysis
      1. A.1.1 A key Lemma for proving emerging dominance
      2. A.1.2 Proofs of the theorems on emerging dominance
    2. A.2 Expectation of hitting times
    3. A.3 Metastability/cut-off
  6. B Auxiliary Lemmas

##  1 Introduction

In many dynamical systems observed in Nature, the law of the dynamics changes
along with the systems’ temporal evolution. These changes are usually
associated with the occurrence of certain events. For example, during
foraging, an animal searches for food until coming across a predator. If the
animal successfully escapes, it will resume the search blue soon after. As
another example, a robot explores an environment until it hits a wall, after
which it continues the exploration by following some rule. As a third example,
animals exploit a behavior (e.g., sleeping, eating) until an event happens
(e.g., body temperature increases, becomes satiated), making them explore
another behavior (e.g., wakes up, takes a nap). All these instances have in
common that the timing of a change in the dynamics depends on its trajectory.
Naturally, trajectories that take longer to satisfy the event (e.g., meeting a
predator) will last longer. Therefore, we expect to observe more frequently
those dynamics that take longer to change in the long run. The consequence is
that, in general, few dynamical states might dominate our observations of
natural phenomena. This article proposes a simple Markov chain model that
modifies the dynamics depending on its trajectory, similar to the examples
described above. We call the model Self-Switching Markov Chains (SSMC). Under
general conditions and scaling, we prove that we observe with probability one
only a subset of the dynamics, and we characterize these dominant dynamics.
Furthermore, we show that the switching between dynamics exhibits
metastability-like properties.

The phenomenon of dominant dynamics emergence exhibits a mechanism that is
akin to natural selection in the theory of evolution. In evolution, the
phenotypes that we consider more adapted are the ones that last more. The
difference between natural selection and the dominance phenomenon that we
describe is that in evolution, the selection happens in a population ensemble
and not at the individual trajectories. The precise formulation of the idea
that selection at the individual level can explain the predominance of certain
animal behaviors seems to be new. The standard approach for the predominance
of a subset of actions in an individual is to assume a learning mechanism [1].
Our result suggests that learning is not the only mechanism that modulates the
preference for one dynamics over the other. A behavior can be dominant simply
because it takes longer to change.

Our model is related to some other popular models in the literature. Hidden
Markov Models (HMM) have been widely used to model switching dynamics like
animal behavior. HMM is similar to SSMC because the dynamics change depending
on the state of the hidden process, but in HMM the change of hidden state is
independent of the trajectory of the observed process [2]. Therefore, we do
not observe the dominance phenomenon in HMM. Markov decision processes select
actions based on its current sate. It also models the predominance of specific
behaviors but uses the idea of reward learning mechanism [3]. Finally, Hybrid
Switching Diffusions are closely related to SSMC, but there is no description
of emergent dominant phenomena for this class of processes to the best of our
knowledge [4].

The article is organized as follows. In Section 2.1 we introduce the model of
Self-Switching Markov Chains (SSMC) and discuss some of its properties. In
Section 2.2 we study the asymptotics of sequences of SSMC and provide the main
results about emergence of dominant behaviors. Section 3 provides a few
concrete examples of SSMC based on random walks models. Finally, Section 4
concludes the paper with a brief discussion about possible extensions of this
work. The proofs of the technical results are postponed to A, while in B the
proofs of couple of auxiliary lemmas are given.

##  2 Model and main results

##### General notation.

Let $\mathbb{N}:=\\{0,1,\ldots\\}$ be the set of natural numbers. Henceforth,
we shall use the following notation: $\mathcal{X}$ denotes a finite set
(describing the possible configuration of a system) and $\Xi$ a compact metric
space (set of possible states).

###  2.1 Self-Switching Markov Chains

A _Self-Switching Markov Chain_ (SSMC) is a Markov chain
$\\{(X_{i},\eta_{i})\\}_{i\in\mathbb{N}}$ taking values on
$\mathcal{X}\times\Xi$ which depends on four parameters:

  * 1.

$\mu$, a probability measure on $\Xi$ (_state distribution_);

  * 2.

$\boldsymbol{Q}:=(Q^{(\theta)})_{\theta\in\Xi}$, a family of
$\mathcal{X}\times\mathcal{X}$ stochastic matrices (_dynamic in state
$\theta$_);

  * 3.

$x_{0}\in\mathcal{X}$ (_origin_);

  * 4.

$T\subset\mathcal{X}$, a set which does not contain the origin (_target set_).

The dynamics of a SSMC is defined as follows:
$(X_{0},\eta_{0})\sim\delta_{x_{0}}\otimes\mu$, and for all $i\geq 1$, all
$x_{<i}:=(x_{0},\ldots,x_{i-1})\in\mathcal{X}^{i}$ and all
$\theta_{<i}:=(\theta_{0},\ldots,\theta_{i-1})\in\Xi^{i}$

$\displaystyle(X_{i},\eta_{i})|X_{<i}=x_{<i},\eta_{<i}=\theta_{<i}\sim\begin{cases}\delta_{x_{0}}\otimes\mu,&\text{
if $x_{i-1}\in T$}\;,\\\
Q^{(\theta_{i-1})}(x_{i-1},\cdot)\otimes\delta_{\theta_{i-1}},&\text{otherwise}\;.\end{cases}$

We denote by $\mathbb{P}_{x_{0},\mu}$ the law of
$\\{(X_{i},\eta_{i})\\}_{i\in\mathbb{N}}$ when
$(X_{0},\eta_{0})\sim\delta_{x_{0}}\otimes\mu$, and by
$\mathbb{E}_{x_{0},\mu}$ the corresponding expectation, while the expectation
with respect to $\mu$ is denoted by $\mathbf{E}_{\mu}$. The first coordinate
process $\boldsymbol{X}=\\{X_{i}\\}_{i\in\mathbb{N}}$ may be seen as a
_location_ process, while the second coordinate
$\boldsymbol{\eta}=\\{\eta_{i}\\}_{i\in\mathbb{N}}$ as a process determining
the _state_ of the process $\boldsymbol{X}$. The location and the state
process are coupled; on one hand, at time $i$, the location $X_{i}$ is updated
through a transition matrix which is parametrized by $\eta_{i}$, while the
process $\boldsymbol{\eta}$ is updated as soon as the location process
$\boldsymbol{X}$ hits the target set $T\subset\mathcal{X}$. After each such
event, the location process restarts from the origin $x_{0}$ and a new state
is sampled according to $\mu$ and independently of everything else. In other
words, the random times when the location process hits the target set are
renewal times for the location process.

##### Example

As an example of a SSMC consider a random walk $\boldsymbol{X}$ on a weighted
finite (connected) graph $G=(V,E,w)$, where $w:E\to[a,b]$, with $b>a>0$, is a
function assigning to every edge $e\in E$ a weight $w(e)\in[a,b]$. In this
case $\mathcal{X}=V$, $\Xi=[a,b]^{E}$ and $Q^{(\theta)}$, with $\theta\in\Xi$,
is the transition matrix of a random walk on $G$ with edge weights $w=\theta$.
The edge weights correspond to a particular state and $\eta_{i}$ denotes the
weights used at time $i$. Given an origin $x_{0}\in V$, and a set of target
vertices $T\subset V$, the dynamics of this SSMC consists in drawing the edge
weights according to a distribution $\mu$ and letting the random walk move on
the corresponding weighted graph, starting from $x_{0}$. As soon as the random
walk hits the target set $T$, a new weight function is sampled according to
$\mu$ and the random walk restarts from the origin.

Throughout the paper, we assume that $Q^{(\theta)}$ is irreducible for any
$\theta\in\Xi$. This guarantees that the process $\boldsymbol{X}$ will visit
$T$ infinitely often, since $\mathcal{X}$ is finite. However, this does not
automatically grant positive recurrence of $\boldsymbol{X}$, due to the
coupled dynamics with the state process $\boldsymbol{\eta}$.

To better understand the coupled dynamics, let us define the following
sequence of stopping times: $S_{0}:=0$ and for any $i\geq 1$

$S_{i}:=\inf\\{n>S_{i-1}:X_{n}\in T\\}\;.$

Note that the distribution of the stopping time $S_{i}$ depends on the whole
past of the chain, and in particular depends on the processes
$\boldsymbol{\eta}$ up to time $S_{i-1}+1$. However, conditioned on $S_{i-1}$,
the distribution of $S_{i}$ depends on $\boldsymbol{\eta}$ only through
$\eta_{S_{i-1}+1}$. By the definition of the model, $\eta_{S_{i-1}+1}$ is
distributed according to $\mu$ and is independent of everything else. Thus, if
for every $i\geq 1$, we define the _inter-switching_ times
$\tau_{i}:=S_{i}-S_{i-1}$, and denote by $\\{\Theta_{i}\\}_{i\geq 1}$ an
i.i.d. sequence of random variables with distribution $\mu$ (independent of
everything else), we have that
$\tau_{i}(\eta_{S_{i-1}+1})\sim\tau_{i}(\Theta_{i})$, for every $i\geq 1$.

######  Remark 1.

The random variables $\\{\tau_{i}(\Theta_{i})\\}_{i\geq 1}$ are i.i.d.
However,
$\mathbb{P}_{x_{0},\mu}(\tau_{i}(\Theta_{i})=\cdot|\Theta_{i}=\theta)$
strongly depends on $\theta\in\Xi$, i.e., different states give rise to
different inter-switching times.

Given the i.i.d. nature of the sequence $\\{\tau_{i}(\Theta_{i})\\}_{i\geq
1}$, we shall denote by $\tau_{1}(\Theta_{1})$ anyone of them. We shall also
use the notation $\tau(\Theta)$ or simply $\tau$, when there is no risk of
confusion. Throughout the paper we shall work under the following assumption.

######  Assumption 1.

The function

$\Xi\ni\theta\mapsto
m(\theta):={\mathbb{E}}_{x_{0},\mu}\left[\tau_{1}(\Theta_{1})|\Theta_{1}=\theta\right]\;,$
(1)

is continuous.

Assumption 1 guarantees that the process $\boldsymbol{X}$ is positive
recurrent, i.e., the time elapsed between consecutive visits to $T$ has finite
expectation. In fact, since $Q^{(\theta)}$ is irreducible for every
$\theta\in\Xi$ and $\mathcal{X}$ is finite, we know that $m(\theta)<\infty$.
Moreover, since $\Xi$ is compact, the function $m$ is uniformly bounded and
thus

${\mathbb{E}}_{x_{0},\mu}\left[\tau_{1}(\Theta_{1})\right]=\mathbf{E}_{\mu}[m]=\int_{\Xi}m(\theta)\mu(d\theta)<\infty\;.$
(2)

##### Occupation measure of the state process

For each integer $n\geq 1$ and Borelian set $A\subseteq\Xi$, let us denote by
$\hat{p}_{n}(A)$ the _empirical occupation measure_ of $A$ for the process
$\boldsymbol{\eta}$, defined as

$\hat{p}_{n}(A):=\frac{1}{n}\displaystyle\sum_{k=1}^{n}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize 1}_{(\eta_{k}\in A)}\;.$ (3)

The following proposition provides the limiting measure, as time $n$ goes to
infinity, of the empirical occupation measure  (Proof in A.1).

######  Proposition 1.

Let $m:\Xi\to\mathbb{R}$ be the function defined in (1). Under Assumption 1,
for every Borel measurable $A\subseteq\Xi$ it holds that

$\hat{p}_{n}(A)\underset{n\to\infty}{\longrightarrow}\;\widehat{P}(A):=\frac{\mathbf{E}_{\mu}\left[\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{A}m\right]}{\mathbf{E}_{\mu}[m]}\;,\quad\text{${\mathbb{P}}_{x_{0},\mu}$-almost
surely}\;.$

Note that the limiting probability measure $\widehat{P}$ on $\Xi$ is
absolutely continuous with respect to the probability measure $\mu$ since

$\widehat{P}(d\theta)=\frac{m(\theta)}{\mathbf{E}_{\mu}[m]}\mu(d\theta)\;.$

###  2.2 Sequence of Self-switching Markov chains

Recall that a SSMC $\boldsymbol{Y}=\\{(X_{i},\eta_{i})\\}_{i\in\mathbb{N}}$ is
defined by the pair $(\Xi,\mu)$, and the tuple
$(\boldsymbol{Q},\mathcal{X},x_{0},T)$. In this section, we will consider a
sequence $\boldsymbol{Y}_{N},N\geq 1$ of SSMCs using a sequence of tuples
$(\boldsymbol{Q}_{N},\mathcal{X}_{N},x_{0},T_{N}),N\geq 1$ in which
$\mathcal{X}_{N},N\geq 1$ is an increasing sequence of finite sets,
$x_{0}\in\mathcal{X}_{1}$, $T_{N}\subset\mathcal{X}_{N}$ are subsets which do
not contain $x_{0}$, and finally, $\boldsymbol{Q}_{N},N\geq 1$ are irreducible
stochastic matrices on $\mathcal{X}_{N}$. With the exception of $\Xi$, $\mu$
and $x_{0}$, all the quantities which were introduced in Section 2.1 are
affected by the dependence on $N$, and for this reason, they will be indexed
by $N$. In particular, $\widehat{P}$, $\\{\tau_{i}\\}_{i\geq 1}$, $\tau$ and
$m(\theta)$ will now be denoted respectively as $\widehat{P}_{N}$,
$\\{\tau_{i,N}\\}_{i\geq 1}$, $\tau_{N}$ and $m_{N}(\theta)$ for any $N\geq
1$. The sets $T_{N}$ and the parameter $N\geq 1$ control the size of the
configuration space of the location process.

####  2.2.1 Emerging dominance

In this section, we investigate the possible limits of the sequence of
probability measures $\\{\widehat{P}_{N}\\}_{N\geq 1}$ where we recall that,
for any $N\geq 1$,
$\widehat{P}_{N}(A):=\frac{\mathbf{E}_{\mu}\left[\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize 1}_{A}m_{N}\right]}{\mathbf{E}_{\mu}[m_{N}]}$. We
will present general conditions under which the sequence
$\\{\widehat{P}_{N}\\}_{N\geq 1}$ converges weakly to a mixture of Dirac
deltas.

In what follows, we write ${\rm supp}(\mu)$ to indicate the support of the
probability measure $\mu$.

######  Terminology (Emerging dominance).

Given $\\{\theta^{*}_{1},\ldots,\theta^{*}_{K}\\}\subsetneq{\rm supp}(\mu)$
(proper inclusion), we say that there is “ _emerging dominance at
$\\{\theta^{*}_{1},\ldots,\theta^{*}_{K}\\}$ with positive weights
$\\{w_{i},\ldots,w_{K}\\}$_” if the sequence of probability measures
$\\{\widehat{P}_{N}\\}_{N\geq 1}$ converges weakly, when $N$ diverges, to the
mixture of Dirac deltas $\sum_{i=1}^{K}w_{i}\delta_{\theta^{*}_{i}}$, and
$\sum_{i=1}^{K}w_{i}=1$.

We emphasize that emerging dominance requires that the sequence
$\\{\widehat{P}_{N}\\}_{N\geq 1}$ converges weakly to a mixture of Dirac
deltas supported on a proper subset of ${\rm supp(\mu)}$. In light of that,
note that, if $\limsup_{N\to\infty}m_{N}(\theta)\leq L$,
$\forall\theta\in\Xi$, then
$\liminf_{N\to\infty}\widehat{P}_{N}(A):=\liminf_{N\to\infty}\frac{\mathbf{E}_{\mu}\left[\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{A}m_{N}\right]}{\mathbf{E}_{\mu}[m_{N}]}\geq\frac{\mu(A)}{L}$. Hence, the
support of any weak limit of $\\{\widehat{P}_{N}\\}_{N\geq 1}$ coincides with
${\rm supp(\mu)}$, and therefore there is no emerging dominance. Thus,
henceforth, we consider only situations in which $m_{N}(\theta)$ diverges, as
$N$ tends to infinity.

The simplest situation is when ${\rm supp}(\mu)$ is a finite set. In this case
we have the following theorem (Proof in A.1).

######  Theorem 1.

Let $(\Xi,d)$ be a compact metric space and $\mu$ a discrete probability
measure on $\Xi$ with finite support. Assume that there exists
$\\{\theta^{*}_{1},\ldots,\theta^{*}_{K}\\}\subsetneq{{\rm supp}(\mu)}$
satisfying

  1. (1)

there exists $1\leq i\leq K$ such that for all $\theta\in{\rm
supp}(\mu)\setminus\\{\theta^{*}_{1},\ldots,\theta^{*}_{K}\\}$,

$\frac{m_{N}(\theta)}{m_{N}(\theta^{*}_{i})}\underset{N\to\infty}{\longrightarrow}0\;,$

  2. (2)

for each $1\leq i,j\leq K$ with $i\neq j$, it holds

$\frac{m_{N}(\theta^{*}_{j})}{m_{N}(\theta^{*}_{i})}\underset{N\to\infty}{\longrightarrow}d_{i,j}>0\;.$

Then, we have emerging dominance at
$\\{\theta^{*}_{1},\ldots,\theta^{*}_{K}\\}$ with weights

$w_{i}=\frac{1}{1+\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{K}\frac{\mu(\theta^{*}_{j})}{\mu(\theta^{*}_{i})}d_{i,j}}\,,\,\,i=1,\ldots,K.$

This result solves the question in the finite case in a rather satisfactory
way. Indeed, the conditions are quite natural. Condition (1) states that the
time spent in any state is asymptotically negligible compared to the $K$
dominating states, while on the other hand Condition (2) asks that the
asymptotic time spent in the dominating states be comparable. Condition (1)
cannot be relaxed in general as will be explained in Remark 4. Condition (2),
as far as the convergence holds, cannot be relaxed in general, since if for
some pair $(\theta^{*}_{i},\theta^{*}_{j})$ the ratio diverges or vanishes,
this means that one the two is asymptotically negligible and should be removed
from the set of candidates to dominant states in first place.

The second result relies on assuming some regularity on the sequence of
functions $h_{N}(\theta)=N^{-1}\log(m_{N}(\theta))$, and it provides
sufficient conditions for the emergence of a unique dominant state  (Proof in
A.1).

######  Theorem 2.

Assume that the function $\Xi\ni\theta\mapsto
h_{N}(\theta)=N^{-1}\log(m_{N}(\theta))$ converges uniformly to a function $h$
as $N\to\infty$. If there exists a unique parameter $\theta^{*}\in{\rm
supp}(\mu)$ such that $\arg\max_{\theta\in\Xi}h(\theta)=\theta^{*}$, and
$h(\theta^{*})>0$, then we have emerging dominance at $\\{\theta^{*}\\}$, with
weight $1$.

######  Remark 2.

Theorem 2 may also be formulated in a more general setting which relates the
problem to the so-called Laplace’s Principle.

Let $\\{g_{N}\\}_{N\geq 1}$ be a sequence of functions defined on a compact
metric space $(\Xi,d)$ which converges uniformly to a function $g$. Let $\mu$
be a probability measure on $\Xi$. If
$\theta^{*}=\arg\max_{\theta\in\Xi}g(\theta)$ (that is, $g$ has a unique
global maximum at $\theta^{*}$), $g$ is continuous at $\theta^{*}$, and
$\theta^{*}\in{\rm supp}(\mu)$, then the following generalized Laplace’s
Principle holds: for any continuous function $f:\Xi\to\mathbb{R}$

$\frac{\int_{\Xi}f(\theta)e^{Ng_{N}(\theta)}\mu(d\theta)}{\int_{\Xi}e^{Ng_{N}(\theta)}\mu(d\theta)}\;\underset{N\to\infty}{\longrightarrow}\;f(\theta^{*})\;.$

One advantage of Theorem 2 is that it dispenses any condition on the
probability measure $\mu$ and its support. The drawback is that it gives
emerging dominance only for a single state. However, from the analysis of the
sequence of functions $h_{N}(\theta)=N^{-1}\log(m_{N}(\theta))$, and assuming
that $\mu$ is absolutely continuous w.r.t. the Lebesgue measure it is also
possible to infer the emergence of more than one dominant state. Our next
theorem provides sufficient conditions under which
$\\{\widehat{P}_{N}\\}_{N\geq 1}$ converges to a combination of two Dirac
deltas in the one-dimensional case.

######  Theorem 3.

Let $\Xi=[a,b]\subset\mathbb{R}$ with $a<b$ and assume that the probability
measure $\mu$ on $\Xi$ has continuous density $g_{\mu}$ with respect to the
Lebesgue measure. Assume moreover that

  1. 1.

the sequence $h_{N}$ converges uniformly to a function $h\in C^{1}([a,b])$,

  2. 2.

the function $h$ satisfies $\arg\max_{\theta\in\Xi}h(\theta)\cap\,{\rm
supp}(\mu)=\\{\theta^{*}_{1},\theta^{*}_{2}\\}=\\{a,b\\}$ with $h(a)=h(b)>0$,
$h^{\prime}(a)<0$ and $h^{\prime}(b)>0$111With an abuse of notation, we are
denoting by $h^{\prime}(a)$ the right derivative at $a$, and by
$h^{\prime}(b)$ the left derivative at $b$. ,

  3. 3.

for each $1\leq i\leq 2$, it holds that

$N\left(h_{N}(\theta^{*}_{i})-h(\theta^{*}_{i})\right)\to d_{i}\;,\text{ with
}|d_{i}|<\infty\;,$

and

$\sup_{\theta\in[\theta^{*}_{i}-\delta,\theta^{*}_{i}+\delta]\cap[a,b]}|h^{\prime}_{N}(\theta)-h^{\prime}(\theta)|\to
0\;,$

for all $\delta>0$ sufficiently small.

Then there is emerging dominance at $\\{\theta_{1}^{*},\theta_{2}^{*}\\}$ with
weights $\\{w_{1},w_{2}\\}$ given by

$w_{i}=\frac{(-1)^{i}e^{d_{i}}g_{\mu}(\theta^{*}_{i})/h^{\prime}(\theta^{*}_{i})}{e^{d_{2}}g_{\mu}(\theta^{*}_{2})/h^{\prime}(\theta^{*}_{2})-e^{d_{1}}g_{\mu}(\theta^{*}_{1})/h^{\prime}(\theta^{*}_{1})}\;,\quad\
i=1,2\;.$

The third condition is slightly technical, on the convergence of $h$ and
$h^{\prime}$ at (or around) $a$ and $b$. Observe that Assumption 1 was already
present in Theorem 2, and that Assumption 2 is rather natural, telling us that
behaviors close to $a$ and $b$ have negligible expectation compared to
behaviors $a$ and $b$, which have comparable (equal) expected time.

######  Remark 3.

Theorem 3 deals with the case in which the dominant states are at the boundary
of the state space $\Xi$. One can also deal with the case in which the
dominant states are in the interior of $\Xi$. This can be obtained under
conditions slightly different than those of Theorem 3. Still with $\Xi=[a,b]$,
$a,b\in\mathbb{R}$ with $a<b$, and assuming that the probability measure $\mu$
on $\Xi$ has continuous density $g_{\mu}$ with respect to the Lebesgue
measure. Assume moreover that the functions
$h_{N}(\theta)=N^{-1}\log(m_{N}(\theta))\in C^{2}([a,b])$ satisfy the
following conditions:

  1. 1.

$h_{N}$ converges uniformly to a function $h\in C^{2}([a,b])$.

  2. 2.

The function $h$ satisfies $\arg\max_{\theta\in\Xi}h(\theta)\cap{\rm
supp}(\mu)=\\{\theta^{*}_{1},\theta^{*}_{2}\\}$, where
$\theta^{*}_{1},\theta^{*}_{2}\in(a,b)$ are such that
$\theta^{*}_{1}\neq\theta^{*}_{2}$, $h(\theta^{*}_{1})=h(\theta^{*}_{2})>0$,
$h^{\prime}(\theta^{*}_{1})=h^{\prime}(\theta^{*}_{2})=0$ and
$h^{\prime\prime}(\theta^{*}_{1})=h^{\prime\prime}(\theta^{*}_{2})<0.$

  3. 3.

Moreover, for each $1\leq i\leq 2$, it holds that
$N(h_{N}(\theta^{*}_{i})-h(\theta^{*}_{i}))\to d_{i}$ where $|d_{i}|<\infty$,
$|h^{\prime}_{N}(\theta^{*}_{i})|\leq C/N$ for all $N$ sufficiently large and
for all $\delta>0$ sufficiently small
$\sup_{\theta\in[\theta^{*}_{i}-\delta,\theta^{*}_{i}+\delta]}|h^{\prime\prime}_{N}(\theta)-h^{\prime\prime}(\theta)|$
converges to $0$ as $N\to\infty$.

Then there is emerging dominance at $\\{\theta_{1}^{*},\theta_{2}^{*}\\}$ with
weights $\\{w_{1},w_{2}\\}$ given by ,

$w_{i}=\frac{e^{d_{i}}g_{\mu}(\theta^{*}_{i})/\sqrt{-h^{\prime\prime}(\theta^{*}_{i})}}{e^{d_{1}}g_{\mu}(\theta^{*}_{1})/\sqrt{-h^{\prime\prime}(\theta^{*}_{1})}+e^{d_{2}}g_{\mu}(\theta^{*}_{2})/\sqrt{-h^{\prime\prime}(\theta^{*}_{2})}}\;,\quad\
i=1,2\;.$

Theorem 3 and Remark 3 are proven in A.1. Their proof rely on Laplace’s method
for asymptotic evaluation of integrals which has been extensively used in
statistical theory, specially in Bayesian framework, to approximate integrals
with respect to posterior distributions (see for instance [5] and [6]).

Our last theorem of the section complements the previous results by providing
sufficient conditions under which there is no emergence of dominant state,
i.e., the sequence of probability measures $\\{\widehat{P}_{N}\\}_{N\geq 1}$
converges weakly to a probability measure on $\Xi$ which is not a mixture of
Dirac deltas.

######  Theorem 4.

If there exists a sequence $(a_{N})_{N\geq 1}$ such that $m_{N}/a_{N}$
converges monotonically $\mu$-almost surely to a positive function
$\overline{m}$ such that $\mathbf{E}_{\mu}\left[\overline{m}\right]<\infty$,
then
$\widehat{P}_{N}(A)\to\frac{\mathbf{E}_{\mu}\left[\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{A}\overline{m}\right]}{\mathbf{E}_{\mu}[\overline{m}]}$.

The proof of Theorem 4 follows directly from Monotone Convergence Theorem.

####  2.2.2 Metastability

We say that a state $\theta$ is _metastable_ if the inter-switching time
$\tau_{N}$ corresponding to $\theta$ is asymptotically exponentially
distributed, that is,

${\mathbb{P}}_{x_{0},\delta_{\theta}}\left(\frac{\tau_{N}}{{\mathbb{E}}_{x_{0},\delta_{\theta}}[\tau_{N}]}>t\right)\;\underset{N\to\infty}{\longrightarrow}\;e^{-t}\;.$

Here, ${\mathbb{P}}_{x_{0},\delta_{\theta}}$ is the probability corresponding
to a SSMC with $\mu=\delta_{\theta}$. Observe that
${{\mathbb{E}}_{x_{0},\delta_{\theta}}[\tau_{N}]}={\mathbb{E}}_{x_{0},\mu}\left[\tau_{N}(\Theta_{1})|\Theta_{1}=\theta\right]$
was denoted by $m_{N}(\theta)$ in the previous subsections. This terminology
comes from the fact that exponential distribution of escape times from
potential wells is the main feature of metastability [7].

Conversely, we say that a state $\theta\in\Xi$ exhibits _cut-off_ (following
[8]), if there exist positive constants $c_{1}$ and $c_{2}$ (independent of
$N$), such that

${\mathbb{P}}_{x_{0},\delta_{\theta}}\left(c_{1}<\frac{\tau_{N}}{{\mathbb{E}}_{x_{0},\delta_{\theta}}[\tau_{N}]}<c_{2}\right)\;\underset{N\to\infty}{\longrightarrow}\;1\;.$

Naturally, metastability and cut-off are two extreme situations, and many
other situations can occur in between. However, the duality metastability
_vs._ cut-off has an interesting interpretation. The former corresponds to
states that last an unpredictable random time – the switching time cannot be
predicted, while the later corresponds to states that last for deterministic
time. For SSMC metastability and cut-off may alternate in a single path as we
will illustrate in the next section by simple examples.

In order to establish metastability, we will make use of the following
theorem, due to [7].

######  Theorem 5 (Theorem 2.7 in [7]).

Let $\tau_{N}$ be the inter-switching time and denote by $\tau_{x_{0}}$ the
first time the location process $\boldsymbol{X}$ visits the origin $x_{0}$.
Suppose there exist two sequences of real numbers $(R_{N})_{N\geq 1}$ and
$(r_{N})_{N\geq 1}$ satisfying $R_{N}>0$,
$\frac{R_{N}}{{\mathbb{E}}_{x_{0},\delta_{\theta}}[\tau_{N}]}\rightarrow 0$,
$r_{N}\in(0,1)$, $r_{N}\rightarrow 0$ such that

$\sup_{x\in\mathcal{X}_{N}}{\mathbb{P}}_{x,\delta_{\theta}}(\min\\{\tau_{N},\tau_{x_{0}}\\}>R_{N})\leq
r_{N}\;,\quad N\geq 1\;.$

Then, $\frac{\tau_{N}}{{\mathbb{E}}_{x_{0},\delta_{\theta}}[\tau_{N}]}$
converges in distribution (with respect to
${\mathbb{P}}_{x_{0},\delta_{\theta}}$) to an exponential random variable with
parameter $1$; thus the state $\theta$ is metastable.

##  3 Self-switching environment Random Walks

The SSMCs were introduced in a rather general way, without detailing the
dynamic of the location process, encoded by the matrices
$Q^{(\theta)},\theta\in\Xi$. We now consider specific cases to illustrate the
phenomena discussed in Section 2.2. These examples are built upon one-
dimensional simple random walks models on increasing subsets of $\mathbb{Z}$.
In all the examples, we assume that $\Xi=[0,1]$ and that $\mu$ has support in
a compact subset of $(0,1]$.

###  3.1 Physical interpretation

Given a transition matrix $Q$ of nearest neighbors random walk on
$\mathcal{X}\subset{\mathbb{Z}}$ (containing $0$), we call “potential” the
function $V:\mathbb{R}\rightarrow\mathbb{R}$ interpolating the following
values

$V(n)=\left\\{\begin{array}[]{cc}\sum_{i=1}^{n}\log\frac{Q(i,i-1)}{Q(i,i+1)}&n\in\\{1,2,\ldots\\}\cap\mathcal{X}\;,\\\
0&n=0\\\
-\sum_{i=n+1}^{0}\log\frac{Q(i,i-1)}{Q(i,i+1)}&n\in\\{-1,-2,\ldots\\}\cap\mathcal{X}\;.\end{array}\right.$
(4)

The potential gives us a physical intuition of the different dynamics. We
refer to Figure 3 for a schematic illustration of the three types of
potentials we are considering below.

###  3.2 Biological interpretation

Animal behaviors are often thought to be random walks in a state space with
transition probabilities controlled by few parameters [9]. For example, when
observing the movement of a fly inside a chamber, we think of the sequence of
positions of the fly as following a random walk in constrained state space. As
another example, we can use random walks with barriers to model the neural
process of making decisions [10]. In these models, when a random walk reaches
one of the barriers in the state space, it means that the person made a
decision. Different behaviors of the animal are modeled by distinct transition
probabilities of the random walk. In both of our examples, whenever the random
walk reaches the barrier, we can think that it restarts the dynamics following
transition probabilities that are chosen dynamically. The SSERW introduced
below are simple one-dimensional models that capture these ideas. The key
phenomenon is the emergence of dominating states (transition probabilities)
even when the states are chosen independently of the process. In the fly
example, that would imply that, in the long run, we would expect few flying
strategies to dominate the observations even without a learning mechanism.
Similarly, for the decision-making, we expect that, in the long run, we
primarily observe few decision-making strategies, despite the lack of
learning. The dominance of few states is in agreement with the observation
that only few major behavioral states are observed in animals [11].

###  3.3 Flat potential SSERW

Let $\mathcal{X}_{N}=[-N,N]\cap{\mathbb{Z}}$, $T_{N}=\\{-N,N\\}$ and
$x_{0}=0$. For any $N\geq 1$, let $\boldsymbol{Q}_{N}={\bf Q}$, where for any
$\theta\in\Xi$, $Q^{(\theta)}$ is defined as follows: for
$x\in\mathcal{X}_{N}\setminus\\{-N,N\\}$

$\displaystyle Q^{(\theta)}(x,y)=\begin{cases}\theta\;,&\text{if}\ y=x+1\;,\\\
1-\theta\;,&\text{if}\ y=x-1\;,\\\ 0\;,&\text{otherwise}\;,\end{cases}$ (5)

whereas $Q_{N}^{(\theta)}(x,\cdot)$ can be chosen arbitrary for
$x\in\\{-N,N\\}$ because it does not influence the dynamics. We call this
model flat potential SSERW because of the linear shape of the corresponding
potential function $V(n)$ (see Figure 3). In this example the state $\theta$
corresponds to the transition probability of jumping one step to the right. At
time $0$ a state is sampled according to $\mu$ and the random walk starts in
$0$. When the walker hits the target set $\\{-N,N\\}$ the SSMC starts afresh.
Note that the hitting time depends on the current state. Specifically, the
quantity $m_{N}(\theta)$ defined by (1), denotes here the expected time taken
by a simple random walk started at the origin to hit $\\{-N,N\\}$, when it has
probability $\theta$ to jump to the right (classical Gambler’s ruin on
$[-N,N]\cap{\mathbb{Z}}$ starting from $0$). Thus, it is well known that, for
all $\theta\in[0,1]$

$\displaystyle m_{N}(\theta)=\begin{cases}N^{2}\;,&\text{ if
}\theta=\frac{1}{2}\;,\\\
\frac{N}{1-2\theta}-\frac{2N}{1-2\theta}\frac{1}{\left(\frac{1-\theta}{\theta}\right)^{N}+1}\;,&\text{
if }\theta\neq\frac{1}{2}\;.\end{cases}$ (6)

As the above equation shows, the expected switching time for $\theta=1/2$
grows faster in $N$ than the expected switching time for any $\theta\neq 1/2$.
This suggests that there might be an emergence of dominant state, namely the
one corresponding to $\theta=1/2$. Specifically, we have that:

  * 1.

If $\mu$ is discrete with finite support and $1/2\in{\rm supp}(\mu)$, Theorem
1 implies that there is emerging dominance at $\theta=1/2$.

For general $\mu$ the question is more delicate. Note that, although the
function $m_{N}$ above is continuous on $[0,1]$, symmetric around $1/2$ and
$\arg\max_{\theta\in[0,1]}m_{N}(\theta)=1/2$, we cannot apply Theorem 2 (since
the corresponding limiting function is $h\equiv 0$).

Let us consider the functions
$\overline{m}_{N}(\theta)=N^{-1}m_{N}(\theta),\theta\in[0,1],N\geq 1$ and
observe from (6) that $\overline{m}_{N}(\theta)$ converges (pointwise)
monotonically to

$\overline{m}(\theta)=\frac{1}{|1-2\theta|}\;,\quad\theta\in[0,1]\;,$ (7)

(with the convention that $\frac{1}{0}=\infty$). We then obtain:

  * 1.

If $\mu$ is such that $\mathbf{E}{{}_{\mu}}(\overline{m})<\infty$, Theorem 4
implies that the corresponding sequence of probability measures
$\\{\widehat{P}_{N}\\}_{N\geq 1}$ converges weakly, as $N\to\infty$, to a
probability measure $\mathbf{P_{\mu}}$ on $[0,1]$ , where

$\mathbf{P_{\mu}}(d\theta)=\frac{\overline{m}(\theta)}{\mathbf{E}_{\mu}[\overline{m}]}\mu(d\theta)\;.$

Thus, in this case, there is no emergence of dominant states.

  * 2.

If $\mu$ is such that $\mathbf{E}{{}_{\mu}}(\overline{m})=+\infty$, it can be
proved222The proof goes along the same lines as the proof of Theorem 2. that
there is emerging dominance at $\theta=1/2$ also.

######  Remark 4.

Suppose that ${\rm supp}(\mu)$ is any finite set of real numbers in $(0,1/2)$.
In this case we see that, for any $\theta_{1},\theta_{2}\in{\rm supp}(\mu)$

$\frac{m_{N}(\theta_{1})}{m_{N}(\theta_{2})}\rightarrow\frac{1-2\theta_{2}}{1-2\theta_{1}}\neq
0,$

showing that Assumption (1) of Theorem 1 does not hold, while Assumption (2)
holds. But since $\mathbf{E}{{}_{\mu}}(\overline{m})<\infty$, there is no
emergence of dominant states, showing that Assumption (1) cannot be relaxed in
general.

The next result states that, for the flat potential SSERW, any state
$\theta\neq 1/2$ cuts-off asymptotically  (Proof in A.3).

######  Proposition 2.

Let $\tau_{N}$ denotes the first time the flat-potential random walk hits the
set $\\{-N,N\\}$. For any $\theta\neq 1/2$, it holds that

$\frac{\tau_{N}}{{\mathbb{E}}_{0,\delta_{\theta}}[\tau_{N}]}\underset{N\to\infty}{\longrightarrow}1\;,\quad\text{
${\mathbb{P}}_{0,\delta_{\theta}}$-almost surely}\;.$

For $\theta=1/2$, it is known that
$\frac{\tau_{N}}{{\mathbb{E}}_{0,\delta_{1/2}}[\tau_{N}]}$ converges in
distribution to an unbounded random variable whose distribution is known [12]
but is not exponential, meaning that this state is neither metastable nor
asymptotically cut-off.

###  3.4 Single-well potential SSERW

As in the previous section, let $\mathcal{X}_{N}=[-N,N]\cap{\mathbb{Z}}$,
$T_{N}=\\{-N,N\\}$ and $x_{0}=0$. For $N\geq 1$, let $\boldsymbol{Q}_{N}={\bf
Q}$, where for any $\theta\in\Xi$, $Q^{(\theta)}$ is defined as follows:

$\displaystyle\text{ if }x\in[1,N-1]\cap{\mathbb{Z}}\;:$
$\displaystyle\qquad\qquad Q^{(\theta)}(x,y)=\begin{cases}\theta\;,&\text{if}\
y=x+1\;,\\\ 1-\theta\;,&\text{if}\ y=x-1\;,\\\
0\;,&\text{otherwise}\;,\end{cases}$ $\displaystyle\text{ if
}x\in[-N+1,0]\cap{\mathbb{Z}}\;:$ $\displaystyle\qquad\qquad
Q^{(\theta)}(x,y)=\begin{cases}1-\theta\;,&\text{if}\ y=x+1\;,\\\
\theta\;,&\text{if}\ y=x-1\;,\\\ 0\;,&\text{otherwise}\;,\end{cases}$

whereas $Q_{N}^{(\theta)}(x,\cdot)$ can be chosen arbitrary for
$x\in\\{-N,N\\}$ because it does not influence the dynamics. We call this
model single-well potential SSERW because of the single peak/through shape of
the corresponding potential function $V(n)$ (see Figure 3). Figure 1
represents the dynamic of the single-well walker. As opposed to the flat
potential random walk discussed in the previous section, here a state $\theta$
corresponds to the probability of increasing by one unit the distance from the
origin $x_{0}=0$. Thus, for small values of $\theta$, the single-well random
walk may take a very long time to reach the target set $\\{-N,N\\}$, while if
$\theta$ is close to $1$, the random walk is pushed away from the origin and
“rapidly” reaches $\\{-N,N\\}$. See Figure 3, graphics C and D, for a
pictorial representation. This intuition is formalized in the following
proposition  (Proof in A.2).

$0$$1$$N$$-1$$-N$$\theta$$1-\theta$$\theta$$1-\theta$ Figure 1: Single-well
random walk between $-N$ and $N$ in a $\theta$-environment. White states (from
$1$ to $N$) have transition probabilities $\theta$ to the right and $1-\theta$
to the left; black states (from $-N$ to $0$) have opposite transition
probabilities.

######  Proposition 3.

For every integer $N\geq 1$ and $\theta\in(0,1]$, it holds that

$m_{N}(\theta)=\begin{cases}N^{2}\;,&\text{if}\ \theta=1/2\;,\\\
\frac{2\theta(1-\theta)}{(1-2\theta)^{2}}e^{N\log((1-\theta)/\theta)}-\frac{1}{1-2\theta}\left(N+\frac{2\theta(1-\theta)}{1-2\theta}\right)\;,&\text{otherwise}\;.\end{cases}$
(8)

######  Remark 5.

It turns out that $m_{N}(\theta)$ does not depend on the transition
probabilities at $0$. However, these transition probabilities determine the
probability that the walker hits the state $N$ before $-N$, i.e.,
${\mathbb{P}}_{0,\mu}(X_{\tau_{1}}=N|\Theta_{1}=\theta)=1-\theta$.

From Proposition 3 we obtain that for any $N\geq 1$, the function $m_{N}$ is
continuous. Moreover, the function $h_{N}(\theta)=N^{-1}\log(m_{N}(\theta))$
is continuous and monotonically decreasing, converging pointwise on any
compact subset of $(0,1]$ to

$h(\theta)=\begin{cases}\log\left((1-\theta)/\theta\right)\;,&\theta<1/2\;,\\\
0\;,&\theta\geq 1/2\;.\end{cases}$ (9)

The function $h$ is continuous and non-increasing on $[0,1]$. Finally, by
Lemma 2 in B, the convergence is uniform on $[a,1]$ for any fixed $a\in(0,1)$.
Hence, we obtain that:

  * 1.

If $a^{*}:=\sup\\{a>0:\mu([0,a))=0\\}\in(0,1/2)$, Theorem 2 implies that there
is emerging dominance at $\theta=a^{*}$.

On the contrary, if $a^{*}:=\sup\\{a>0:\mu([0,a))=0\\}\geq 1/2$, the
assumption of Theorem 2 does not hold. We therefore analyze
$\overline{m}_{N}(\theta)=N^{-1}m_{N}(\theta),N\geq 1$, observing that it
monotonically converges (pointwise) to

$\overline{m}(\theta):=\frac{1}{2\theta-1}\;,\quad\theta\geq 1/2\;,$

(with the convention that $\frac{1}{0}=\infty$). We then obtain that:

  * 1.

If $a^{*}:=\sup\\{a>0:\mu([0,a))=0\\}>1/2$, we have that
$\mathbf{E}_{\mu}[\overline{m}]<+\infty$, and Theorem 4 implies that the
corresponding sequence of probability measures $\\{\widehat{P}_{N}\\}_{N\geq
1}$ converges weakly, as $N\to\infty$, to a probability measure
$\mathbf{P_{\mu}}$ on $[0,1]$ , where

$\mathbf{P_{\mu}}(d\theta)=\frac{\overline{m}(\theta)}{\mathbf{E}_{\mu}[\overline{m}]}\mu(d\theta)\;.$

In this case, there is no emergence of dominant states.

  * 2.

If $a^{*}:=\sup\\{a>0:\mu([0,a))=0\\}=1/2$, we further split in two cases:

    * (a)

If $\mathbf{E}_{\mu}[\overline{m}]<+\infty$, Theorem 4 implies that
$\\{\widehat{P}_{N}\\}_{N\geq 1}$ converges weakly, as $N\to\infty$, to
$\mathbf{P_{\mu}}(d\theta)=\frac{\overline{m}(\theta)}{\mathbf{E}_{\mu}[\overline{m}]}\mu(d\theta)$,
and there is no emergence of dominant states.

    * (b)

If $\mathbf{E}_{\mu}[\overline{m}]=+\infty$, it can be shown333The proof goes
along the same lines as the proof of Theorem 2. that there is emerging
dominance at $\theta=1/2$.

As far as the metastability in the single-well SSERW is concerned, we have the
following result  (Proof in A.3).

######  Theorem 6.

Let $\tau_{N}$ denote the first time the single-well random walk hits the
target set $\\{-N,N\\}$. Then

  1. i)

For any $0<\theta<1/2$, it holds that

$\frac{\tau_{N}}{{\mathbb{E}}_{0,\delta_{\theta}}[\tau_{N}]}\underset{N\to\infty}{\longrightarrow}\mbox{Exp}(1)\
\text{(in distribution ${\mathbb{P}}_{0,\delta_{\theta}}$)}\;.$

  2. ii)

For any $1/2<\theta\leq 1$, it holds that

$\frac{\tau_{N}}{{\mathbb{E}}_{0,\delta_{\theta}}[\tau_{N}]}\underset{N\to\infty}{\longrightarrow}1\;,\quad\text{
${\mathbb{P}}_{0,\delta_{\theta}}$-almost surely}\;.$

Thus, states $\theta\in(0,1/2)$ are metastable, while states
$\theta\in(1/2,1]$ are asymptotically cut-off. Interestingly, depending on the
support of $\mu$, the chain may alternate between these two phenomena when $N$
is sufficiently large. Observe that the case $\theta=1/2$ is exactly the same
as $\theta=1/2$ in the flat potential SSERW seen before; hence, also here the
state $\theta=1/2$ is none of the above.

###  3.5 Alternating-wells potential SSERW

In this section, building upon the single-well random walk, we introduce a
simple model whose main feature consists in the emergence of two dominant
states (on the contrary of the previous examples where we always had either
emergence of a unique dominant state or no emergence at all).

Let $\mathcal{X}_{N}=[-2N,2N]\cap{\mathbb{Z}}$, $T_{N}=\\{-2N,2N\\}$ and
$x_{0}=0$. For $N\geq 1$, let $\boldsymbol{Q}_{N}$ be such that, for any
$\theta\in\Xi$, $Q_{N}^{(\theta)}$ is defined as follows:

$\displaystyle\text{ if
}x\in\left([-2N+1,-N-1]\cup[N+1,2N-1]\right)\cap{\mathbb{Z}}\;:$
$\displaystyle\qquad\qquad\qquad\qquad
Q_{N}^{(\theta)}(x,y)=\begin{cases}\theta\;,&\text{if}\ y=x+1\;,\\\
1-\theta\;,&\text{if}\ y=x-1\;,\\\ 0\;,&\text{otherwise}\;,\end{cases}$
$\displaystyle\text{ if }x\in[-N,N]\cap{\mathbb{Z}}\;:$
$\displaystyle\qquad\qquad\qquad\qquad
Q_{N}^{(\theta)}(x,y)=\begin{cases}1-\theta\;,&\text{if}\ y=x+1\;,\\\
\theta\;,&\text{if}\ y=x-1\;,\\\ 0\;,&\text{otherwise}\;,\end{cases}$

whereas $Q_{N}^{(\theta)}(x,\cdot)$ can be chosen arbitrary for
$x\in\\{-2N,2N\\}$ because it does not influence the dynamics. We call this
model alternating-well potential SSERW because of the double peak/through
shape of the corresponding potential function $V(n)$ (see Figure 3). The
dynamic is depicted in Figure 2. Intuitively, for large values of $\theta$,
the random walk has a bias towards reaching state $-N$. Once in $-N$, since
$\theta$ is large the walker spends a lot of time around $-N$ before reaching
the target state $-2N$ or coming back to state $0$. If $\theta$ is small, the
situation is analogous around the state $N$, rather than $-N$. In essence, for
large (_resp._ small) values of $\theta$, the state $-N$ (_resp._ $N$) plays
the same role as the origin in the single-well random walk in Section 3.4.
However, the random walk can now alternate between $-N$ and $N$ depending on
the value of $\theta$. See Figure 3, graphics E and F, for a pictorial
representation.

$0$$0$$1$$N+1$$2N$$-1$$-N-1$$-2N$$1-\theta$$\theta$$\theta$$1-\theta$$1-\theta$$\theta$
Figure 2: Alternating-wells random walk between $-2N$ and $2N$ in a
$\theta$-environment. White states (from $-2N$ to $-N-1$ and from $N+1$ to
$2N$) have transition probabilities $\theta$ to the right and $1-\theta$ to
the left; black states (from $-N$ to $N$) have opposite transition
probabilities.

In the following proposition we compute the expected switching time
corresponding to each state $\theta$, for any $N\geq 1$ (Proof in A.2).

######  Proposition 4.

For any integer $N\geq 1$ and $\theta\in(0,1)$, it holds that

$m_{N}(\theta)=\begin{cases}4N^{2}\;,&\text{if}\ \theta=1/2\;,\\\
\frac{\frac{2\theta(1-\theta)}{(1-2\theta)^{2}}}{\theta\left(\frac{\theta}{1-\theta}\right)^{N}+1-\theta}\left(1-\left(\frac{\theta}{1-\theta}\right)^{N}\right)\left(\left(\frac{1-\theta}{\theta}\right)^{N}-\left(\frac{\theta}{1-\theta}\right)^{N}\right)\;,&\text{otherwise}\;.\end{cases}$

From Proposition 4 we obtain that the function $m_{N}$ is continuous and
symmetric around $1/2$, for every $N\geq 1$. Moreover, the function
$h_{N}(\theta)=N^{-1}\log(m_{N}(\theta))$ is continuous, monotonically
decreasing on $(0,1/2]$ and monotonically increasing on $[1/2,1)$. It
converges pointwise on $(0,1)$ to

$h(\theta)=|\log\left((1-\theta)/\theta\right)|\;,$ (10)

and, by Lemma 3 in B, the convergence is uniform on $[a,b]$ for any fixed
$a\in(0,1/2)$ and $b\in(1/2,1)$. The function $h$ is monotonically decreasing
on $(0,1/2]$ and monotonically increasing on $[1/2,1)$.

Let us define $a^{*}=\sup\\{a\geq 0:\mu([0,a])=0\\}$ and $b^{*}=\inf\\{b\geq
a^{*}:\mu([a^{*},b])=1\\}$; thus $\text{supp}(\mu)\subseteq[a^{*},b^{*}]$. We
have the following situations.

  * 1.

If $a^{*}\neq 1-b^{*}$, Theorem 2 implies that there is emerging dominance at
$\theta^{*}=\\{a^{*}\\}$ if $a^{*}<1-b^{*}$, and at $\theta^{*}=\\{b^{*}\\}$
if $a^{*}>1-b^{*}$.

  * 2.

If $a^{*}=1-b^{*}$, then $\arg\max_{\theta\in[a^{*},b^{*}]}h(\theta)$ is not
unique, and Theorem 2 does not apply. In this case, if we assume that $\mu$
has continuous density $g_{\mu}$ with respect to the Lebesgue measure, we can
use Theorem 3. First notice that, due to the symmetry of the functions $m_{N}$
and $h$ in (10), it holds that $h(a^{*})=h(b^{*})$,
$-h^{\prime}(a^{*})=h^{\prime}(b^{*})>0$ and $d_{1}=d_{2}$. In this case,
there is emerging dominance at $\\{a^{*},b^{*}\\}$ with weights

$w_{a^{*}}=\frac{g_{\mu}(a^{*})}{g_{\mu}(a^{*})+g_{\mu}(b^{*})}\;,\quad
w_{b^{*}}=1-w_{a^{*}}\;.$

In passing, note that if the density $g_{\mu}$ is constant (i.e., $\mu$ is
uniform on $[a^{*},b^{*}]$), then $w_{a^{*}}=w_{b^{*}}=1/2$.

We conclude this section with the following result stating that, in the
alternating-wells SSERW, any state $\theta\neq 1/2$ is metastable  (Proof in
A.3).

######  Theorem 7.

Let $\tau_{N}$ denote the first time the alternating-wells random walk hits
the target set $\\{-2N,2N\\}$. Then, for any
$\theta\in[0,1]\setminus\\{1/2\\}$, it holds that

$\frac{\tau_{N}}{{\mathbb{E}}_{0,\delta_{\theta}}[\tau_{N}]}\underset{N\to\infty}{\longrightarrow}\mbox{Exp}(1)\
\text{(in distribution ${\mathbb{P}}_{0,\delta_{\theta}}$)}\;.$

For $\theta=1/2$, the alternating-wells random walk is equivalent to the
single-well (as well as flat potential).

Figure 3 depicts intuitively the potentials corresponding to different states
in the three examples: flat-potential, single-well and alternating-wells
potential.

Figure 3:  Rough representation of the potential for different models,
according to definition (4).

##  4 Final Comments

In this article, we introduced the class of SSMCs. A SSMC is a bivariate
Markov chain where the interaction between the components is both ways. On one
hand, the first component (the location process) is driven by the second
component (the state process). On the other hand, the second component changes
its current value at random times corresponding to hitting times of the first
component. For this class of models, we exhibited some conditions under which
we observe the emerging dominance phenomenon. These conditions also allow us
to characterize the dominant states. Our results were illustrated through the
SSERWs (see, Section 3), simple examples of SSMCs. A few natural extensions to
the SSMCs and results introduced in this paper could be considered.

  1. (a)

Changing the starting point. In our model, every time the location process
$\\{X_{i}\\}_{i\in\mathbb{N}}$ hits the target set $T$, the SSMC
$\\{(X_{i},\eta_{i})\\}_{i\in\mathbb{N}}$ start afresh according to the
distribution $\delta_{x_{0}}\times\mu$; that is the location process is set to
the origin $x_{0}$ and a new state is sampled according to $\mu$
(independently). One could consider a variant in which when the SSMC starts
afresh, the new starting point of the chain is chosen according to a
distribution $\nu\times\mu$, or even according to $\nu^{x}\times\mu$, with
$x\in T$. These cases would account for the situation in which the origin is
sampled according to a distribution $\nu$, or even according to a distribution
$\nu^{x}$ which depends on the target point $x\in T$, which was hit in the
previous “round” of the SSMC. Note however, that when the starting point of
the chain is chosen according to $\nu^{x}\times\mu$, with $x\in T$, the inter-
switching times would not necessarily be i.i.d.

  2. (b)

Markovian dependence of the parameter process. In SSMC, the state process is
kept constant during inter-switching times. A possible variation may consider
a Markovian dependence on the state process. This could be done by using a
transition kernel $\mathcal{K}:\Xi\times\Xi\rightarrow[0,1]$, and now, $\mu$
would represent the initial distribution of this Markov process. This would
introduce a stronger dependence between the location process and the state
process and it is not clear whether the emergence of dominant states still
holds.

  3. (c)

Convergence of the state process. We showed the metastability and cut-off only
for a fixed value of the state process. This is not very satisfactory as we do
not know if similar convergence holds for the entire process. The main
difficulty is that different states have distinct normalizing constant,
therefore, a single normalizing constant for the state process does not result
in a interesting limit process. On the other hand, considering a case of
multiple metastable dominant states with comparable $m_{N}(\theta_{i}^{*})$
(as in the alternated wells SSERW for example), the normalizing constants
$\mathbb{E}_{x_{0},\delta_{\theta^{*}_{i}}}(\tau_{N})$ would be comparable
too. So, rescaling time by their order may yield a jump process between
dominant states with exponential waiting times with parameter depending on the
current state. This is a question we are planning to investigate in the
future.

###  4.1 A biological consequence

Although animals typically have a large degree of freedom for producing
movements, only relatively few behaviors are observed in Nature. For example,
humans can create many different postures, but generally, we only observe few
types of behaviors. The relatively small number of observed behaviors is what
allows ethologists to study animal behavior [11]. The standard explanation for
the predominance of a specific behavior is usually associated with the
animal’s predisposition to produce the behavior or some learning mechanism
that makes the behavior more frequent. In our model, we can think of modeling
the predisposition or learning by a fixed or history-dependent state
distribution $\mu$, respectively. Our results suggest that a third explanation
exists: Emergence of dominance state by the typical duration of the behavior -
_the longer it lasts the merrier_.

## Acknowledgements

The authors thank the anonymous referee for the helpful remarks and
corrections. This research has been conducted as part of FAPESP project
Research, Innovation and Dissemination Center for Neuromathematics (grant
2013/07699-0). SG thanks CNPq (Universal 439422/2018-3) and FAPESP
(2019/23439-4) for financial support, and DME-UFRJ for hospitality during part
of the redaction of this paper. GI and GO thank PIPGE-UFSCar (CAPES) for
supporting a short visit to UFSCar where substantial part of this paper were
done. DYT thanks PIPGE-UFSCar (CAPES) and IM-UFRJ (CAPES) for supporting the
visits that gave the opportunity to collaborate on this work.

##  Appendix A Proofs

The proofs are separated by “themes” so that proofs using similar arguments
appear together. There are three main themes:

  * 1.

asymptotic distribution of $\widehat{P}_{N},N\geq 1$, in A.1 (proofs of
Proposition 1, Theorems 1, 2 and 3 and Remark 3);

  * 2.

expectation of hitting times $\tau_{N},N\geq 1$, in A.2 (proofs of
Propositions 3 and 4);

  * 3.

metastability/cut-off, in A.3 (proofs of Proposition 2 and Theorems 6 and 7).

Finally, in B, we give some auxiliary lemmas used in the proofs.

###  A.1 $\widehat{P}_{N}$ and its asymptotic analysis

See 1

###### Proof of Proposition 1.

To avoid clutter, we shall denote $\tau_{i}(\Theta_{i})$ simply as $\tau_{i}$.
If we define $M_{n}=\sup\\{k\geq 1:\tau_{1}+\ldots+\tau_{k}\leq n\\}$, for
$n\geq 1$, the empirical measure $\hat{p}_{n}(A)$ can be written as

$\hat{p}_{n}(A)=\frac{1}{n}\sum_{i=1}^{M_{n}}\tau_{i}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize 1}_{(\Theta_{i}\in
A)}+\frac{1}{n}\left(n-\sum_{i=1}^{M_{n}}\tau_{i}\right)\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize 1}_{(\Theta_{M_{n}+1}\in A)}\;.$

Moreover, $\sum_{i=1}^{M_{n}}\tau_{i}\leq n<\sum_{i=1}^{M_{n}+1}\tau_{i}$,
which implies

$\frac{\sum_{i=1}^{M_{n}}\tau_{i}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize 1}_{(\Theta_{i}\in
A)}}{\sum_{i=1}^{M_{n}+1}\tau_{i}}\leq\widehat{p}_{n}(A)\leq\frac{\sum_{i=1}^{M_{n}}\tau_{i}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize 1}_{(\Theta_{i}\in
A)}}{\sum_{i=1}^{M_{n}}\tau_{i}}+\frac{\left(n-\sum_{i=1}^{M_{n}}\tau_{i}\right)\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize 1}_{(\Theta_{M_{n}+1}\in A)}}{n}\;.$ (11)

As mentioned in Remark 1 the random variables $\\{\tau_{i}\\}_{i\geq 1}$ are
i.i.d. and under Assumption 1 they have finite expectation
$\mathbf{E}_{\mu}[m]$. In particular, this implies that $M_{n}\to\infty$,
${\mathbb{P}}_{x_{0},\mu}$-almost surely as $n\to\infty$. Since the
$\Theta_{i},i\geq 1$ are also i.i.d., it follows that
$\leavevmode\hbox{\rm\small 1\kern-3.15005pt\normalsize 1}_{(\Theta_{i}\in
A)}\tau_{i},i\geq 1$ are i.i.d. with expectation
$\mathbf{E}_{\mu}[\leavevmode\hbox{\rm\small 1\kern-3.15005pt\normalsize
1}_{A}m]$. Thus, by the Strong Law of Large Numbers, the term of the lhs and
first term of rhs of Equation (11) converge to $\widehat{P}(A)$, while the
second term of the rhs vanishes, since
$\frac{\left(n-\sum_{i=1}^{M_{n}}\tau_{i}\right)\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize 1}_{(\Theta_{M_{n}+1}\in
A)}}{n}\leq\frac{\left(n-\sum_{i=1}^{M_{n}}\tau_{i}\right)}{n}\leq\frac{\tau_{M_{n}+1}}{n}$
and $\tau_{M_{n}+1}/n\to 0$ almost surely.

∎

####  A.1.1 A key Lemma for proving emerging dominance

Before we give the proofs of the theorems concerning the asymptotic
distribution of $\widehat{P}_{N},N\geq 1$, we state and prove a general “Key
Lemma”, which gives the more general conditions under which we were able to
prove emerging dominance. Before we can state it, we need some further
notation.

First, recall that, for any $N\geq 1$,
$\widehat{P}_{N}(A):=\frac{\mathbf{E}_{\mu}\left(\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize 1}_{A}m_{N}\right)}{\mathbf{E}_{\mu}(m_{N})}$ for
any measurable set $A\subset\Xi$. We write ${\rm supp}(\mu)$ to indicate the
support of a probability measure $\mu$. For any $r>0$ and $\theta\in\Xi$, we
denote $B_{r}(\theta)=\\{\hat{\theta}\in\Xi:d(\hat{\theta},\theta)<r\\}$ the
ball of radius $r$ centerred at $\theta$ according to some metric $d$ on
$\Xi$. For any measurable set $V\subset\Xi$, we define

$I_{N}[V]:=\int_{V}m_{N}(\theta)\mu(d\theta)\;.$

######  Lemma 1 (Key Lemma).

Let $(\Xi,d)$ be a compact metric space and $\mu$ a probability measure on
$\Xi$. Assume that there are
$\theta^{*}_{1},\ldots,\theta^{*}_{K}\in\Xi\cap{\rm supp}(\mu)$ satisfying the
following conditions:

  * (A)

For every $\delta>0$ sufficiently small there exists $1\leq i\leq K$ such that

$\frac{I_{N}\left[\left(\bigcup_{j=1}^{K}B_{\delta}(\theta^{*}_{j})\right)^{c}\right]}{I_{N}\left[B_{\delta}(\theta^{*}_{i})\right]}\underset{N\to\infty}{\longrightarrow}0\;.$

  * (B)

For every $\delta>0$ sufficiently small and for each $1\leq i,j\leq K$, $i\neq
j$, it holds

$C_{1,i,j}(\delta)\leq\liminf_{N\to\infty}\frac{I_{N}\left[B_{\delta}(\theta^{*}_{j})\right]}{I_{N}\left[B_{\delta}(\theta^{*}_{i})\right]}\leq\limsup_{N\to\infty}\frac{I_{N}\left[B_{\delta}(\theta^{*}_{j})\right]}{I_{N}\left[B_{\delta}(\theta^{*}_{i})\right]}\leq
C_{2,i,j}(\delta)\;.$

Moreover, the limits $\lim_{\delta\to 0}C_{1,i,j}(\delta)$ and
$\lim_{\delta\to 0}C_{2,i,j}(\delta)$ exist and

$\lim_{\delta\to 0}C_{1,i,j}(\delta)=\lim_{\delta\to
0}C_{2,i,j}(\delta)=:c_{i,j}>0\;.$

Then, there is emerging dominance at
$\\{\theta^{*}_{1},\ldots,\theta^{*}_{K}\\}$ with weights

$w_{i}=\frac{1}{1+\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{K}c_{i,j}}\;,\quad i=1,\ldots,K.$

######  Remark 6.

One can easily check that a sufficient condition which does not depend on the
probability measure $\mu$ implying condition $(A)$ in Key Lemma 1 is the
following:

  * (A’)

There exist $\theta^{*}_{1},\ldots,\theta^{*}_{K}\in\Xi\cap{\rm supp}(\mu)$
such that for every $\delta_{1}>0$ sufficiently small there exists
$0<\delta_{2}<\delta_{1}$ and $1\leq i\leq K$ such that

$\frac{\sup_{\theta\in\left(\bigcup_{j=1}^{K}B_{\delta_{1}}(\theta^{*}_{j})\right)^{c}}m_{N}(\theta)}{\inf_{\theta\in
B_{\delta_{2}}(\theta^{*}_{i})}m_{N}(\theta)}\underset{N\to\infty}{\longrightarrow}0.$

For any continuous function $g:\Xi\to\mathbb{R}$, we define

$\widehat{P}_{N}(g):=\frac{\mathbf{E}_{\mu}(gm_{N})}{\mathbf{E}_{\mu}(m_{N})}\;.$

We shall also write, for any continuous function $g:\Xi\to\mathbb{R}$ and any
measurable set $V\subset\Xi$

$I_{N}(g,V):=\int_{V}g(\theta)m_{N}(\theta)\mu(d\theta)\;.$

When $g\equiv 1$, we have $I_{N}(1,V)=I_{N}[V]$.

###### Proof of Lemma 1.

We need to show that for any continuous function $g:\Xi\to\mathbb{R}$, we have

$\widehat{P}_{N}(g)\underset{N\to\infty}{\longrightarrow}\sum_{i=1}^{K}g(\theta^{*}_{i})w_{i}.$

First, notice that for any $\delta>0$ sufficiently small, we can decompose
$\widehat{P}_{N}(g)$ as

$\widehat{P}_{N}(g)=\frac{\sum_{i=1}^{K}I_{N}(g,B_{\delta}(\theta^{*}_{i}))+I_{N}(g,F_{\delta,K})}{\sum_{j=1}^{K}I_{N}[B_{\delta}(\theta^{*}_{j})]+I_{N}[F_{\delta,K}]}\;.$

where
$F_{\delta,K}=\left(\bigcup_{i=1}^{K}B_{\delta}(\theta^{*}_{i})\right)^{c}$.
Now by continuity of $g$, given $\varepsilon>0$, there exists $\delta>0$ small
enough such that for each $1\leq i\leq K$ and all $\theta\in
B_{\delta}(\theta^{*}_{i})$,

$g(\theta^{*}_{i})-\varepsilon<g(\theta)<g(\theta^{*}_{i})+\varepsilon\;,$

which implies that
$(g(\theta^{*}_{i})-\varepsilon)I_{N}[B_{\delta}(\theta^{*}_{i})]\leq
I_{N}(g,B_{\delta}(\theta^{*}_{i}))\leq(g(\theta^{*})+\varepsilon)I_{N}[B_{\delta}(\theta^{*}_{i})]$
for all $1\leq i\leq K.$ Hence, it follows that

$\widehat{P}_{N}(g)\geq\frac{\sum_{i=1}^{K}(g(\theta_{i}^{*})-\varepsilon)I_{N}[B_{\delta}(\theta^{*}_{i})]+\inf_{\theta\in
F_{\delta,K}}g(\theta)\;I^{N}[F_{\delta,K}]}{\sum_{j=1}^{K}I_{N}[B_{\delta}(\theta^{*}_{j})]+I_{N}[F_{\delta,K}]}\;,$

and

$\widehat{P}_{N}(g)\leq\frac{\sum_{i=1}^{K}(g(\theta_{i}^{*})+\varepsilon)I_{N}[B_{\delta}(\theta^{*}_{i})]+\sup_{\theta\in
F_{\delta,K}}g(\theta)\;I^{N}[F_{\delta,K}]}{\sum_{j=1}^{K}I_{N}[B_{\delta}(\theta^{*}_{j})]+I_{N}[F_{\delta,K}]}\;.$

Note that, Condition (A) implies that

$\frac{I_{N}[F_{\delta,K}]}{\sum_{j=1}^{K}I_{N}[B_{\delta}(\theta^{*}_{j})]+I_{N}[F_{\delta,K}]}\leq\frac{I_{N}[F_{\delta,K}]}{\sum_{j=1}^{K}I_{N}[B_{\delta}(\theta^{*}_{j})]}\underset{N\to\infty}{\longrightarrow}0\;,$

and Condition (B) implies that

$\displaystyle\frac{1}{1+\sum_{j=1:j\neq i}^{K}C_{2,i,j}(\delta)}$
$\displaystyle\leq\liminf_{N\to\infty}\frac{I_{N}[B_{\delta}(\theta^{*}_{i})]}{\sum_{j=1}^{K}I_{N}[B_{\delta}(\theta^{*}_{j})]}$
$\displaystyle\leq\limsup_{N\to\infty}\frac{I_{N}[B_{\delta}(\theta^{*}_{i})]}{\sum_{j=1}^{K}I_{N}[B_{\delta}(\theta^{*}_{j})]}\leq\frac{1}{1+\sum_{j=1:j\neq
i}^{K}C_{1,i,j}(\delta)}\;.$

Thus, it follows that for any $\varepsilon>0$ and all $\delta>0$ small enough,

$\displaystyle\sum_{i=1}^{K}\frac{g(\theta_{i}^{*})-\varepsilon}{1+\sum_{j=1:j\neq
i}^{K}C_{2,i,j}(\delta)}$
$\displaystyle\leq\liminf_{N\to\infty}\widehat{P}_{N}(g)$
$\displaystyle\leq\limsup_{N\to\infty}\widehat{P}_{N}(g)\leq\sum_{i=1}^{K}\frac{g(\theta_{i}^{*})+\varepsilon}{1+\sum_{j=1:j\neq
i}^{K}C_{1,i,j}(\delta)}\;.$

By Condition (B), we can take $\delta\to 0$ to conclude that for any
$\varepsilon>0$,

$\sum_{i=1}^{K}(g(\theta_{i}^{*})-\varepsilon)w_{i}\leq\liminf_{N\to\infty}\widehat{P}_{N}(g)\\\
\leq\limsup_{N\to\infty}\widehat{P}_{N}(g)\leq\sum_{i=1}^{K}(g(\theta_{i}^{*})+\varepsilon)w_{i}\;.$

By taking $\varepsilon\to 0$, the result follows. ∎

####  A.1.2 Proofs of the theorems on emerging dominance

See 1

###### Proof of Theorem 1.

We need to show that conditions (1) and (2) imply conditions (A) and (B) of
Lemma 1. To that end, observe that for any $\delta>0$ small enough

$\frac{I_{N}\left[F_{\delta,K}\right]}{I_{N}\left[B_{\delta}(\theta^{*}_{i})\right]}=\frac{I_{N}\left[F_{\delta,K}\right]}{m_{N}(\theta^{*}_{i})\mu(\theta^{*}_{i})}=\sum_{\theta\in
F_{\delta,K}\cap\text{Supp}(\mu)}\frac{m_{N}(\theta)\mu(\theta)}{m_{N}(\theta^{*}_{i})\mu(\theta^{*}_{i})}\;,$

where
$F_{\delta,K}=\left(\bigcup_{i=1}^{K}B_{\delta}(\theta^{*}_{i})\right)^{c}$.
Since by Condition (1) each term of the finite sum above goes to $0$ as
$N\to\infty$, it follows that
$\frac{I_{N}\left[F_{\delta,K}\right]}{I_{N}\left[B_{\delta}(\theta^{*}_{i})\right]}\to
0$ as $N\to\infty$ and Condition $(A)$ holds.

It remains to show that Condition $(2)$ implies $(B)$. To see this, fix $1\leq
i,j\leq K$ with $i\neq j$ and take $\delta>0$ small enough in such a way

$\frac{I_{N}\left[B_{\delta}(\theta^{*}_{j})\right]}{I_{N}\left[B_{\delta}(\theta^{*}_{i})\right]}=\frac{\mu(\theta^{*}_{j})m_{N}(\theta^{*}_{j})}{\mu(\theta^{*}_{i})m_{N}(\theta^{*}_{i})}\;.$

Hence, by Condition $(2)$ for all $\delta>0$ small enough

$\lim_{N\to\infty}\frac{I_{N}\left[B_{\delta}(\theta^{*}_{j})\right]}{I_{N}\left[B_{\delta}(\theta^{*}_{i})\right]}=\frac{\mu(\theta^{*}_{j})}{\mu(\theta^{*}_{i})}d_{i,j}\;.$

In this case, condition (B) holds with
$C_{1,i,j}(\delta)=C_{2,i,j}(\delta)=\frac{\mu(\theta^{*}_{j})}{\mu(\theta^{*}_{i})}d_{i,j}$
for all $\delta>0$ small enough and the result follows. ∎

See 2

###### Proof of Theorem 2.

By Key Lemma 1, it suffices to show that for any open neighborhood
$V\subset\Xi$ of $\theta^{*}$ we have

$\frac{I_{N}[V^{c}]}{I_{N}[V]}\underset{N\to\infty}{\longrightarrow}0\;.$ (12)

Observe that Assumption 1 implies that $h_{N},N\geq 1$ are continuous, and by
uniform convergence, we conclude that $h$ itself is continuous.

To show 12, let $\tilde{\theta}\in\arg\max_{\theta\in V^{c}}h(\theta)$ (the
maximum exists since $h$ is continuous, $V^{c}$ is closed and $\Xi$ compact)
and observe that $h(\tilde{\theta})<h(\theta^{*})$, by the definition of
$\theta^{*}$. Thus, let $\delta>0$ be such that

$h(\tilde{\theta})+\delta<h(\theta^{*})-2\delta\;.$

Since $h_{N}$ converges uniformly to $h$, it follows that for all $N$
sufficiently large

$I_{N}[V^{c}]\leq\mu(V^{c})e^{N\sup_{\theta\in
V^{c}}h_{N}(\theta)}\leq\mu(V^{c})e^{N({h}(\tilde{\theta})+\delta)}\;.$

Similarly, we also have for all $N$ sufficiently large,

$I_{N}[V]\geq\int_{V}e^{N({h}(\theta)-\delta)}\mu(d\theta)\;.$

Finally, since ${h}$ is continuous at $\theta^{*}$, there exists a
neighborhood $V^{\prime}\subseteq V$ of $\theta^{*}$ such that
${h}(\theta)>{h}(\theta^{*})-\delta$ for all $\theta\in V^{\prime}$, which
implies that

$I_{N}[V]\geq e^{N({h}(\theta^{*})-2\delta)}\mu(V^{\prime})\;.$

Since $\theta^{*}\in\text{supp}(\mu)$, we have that $\mu(V^{\prime})>0$. As a
consequence, for all $N$ sufficiently large, we have that

$\frac{I_{N}[V^{c}]}{I_{N}[V]}\leq\frac{e^{N({h}(\tilde{\theta})+\delta)}\mu(V^{c})}{e^{N({h}(\theta^{*})-2\delta)}\mu(V^{\prime})}\;\underset{N\to\infty}{\longrightarrow}0\;,$

and the result follows. ∎

See 3

######  Proof of Remark 3.

The exact same proof of Theorem 2 ensures Condition (A) of Key Lemma 1 holds
with either $i=1$ or $i=2$.

To conclude the proof, we need to show that Condition (B) of Key Lemma 1 holds
with
$c_{1,2}=(e^{d_{2}}g_{\mu}(\theta^{*}_{2})\sqrt{-h^{\prime\prime}(\theta^{*}_{1})})/(e^{d_{1}}g_{\mu}(\theta^{*}_{1})\sqrt{-h^{\prime\prime}(\theta^{*}_{2})}).$
To that end, take $\delta>0$ small enough and observe that by the Mean Valued
Theorem,

$\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}{\int_{\theta^{*}_{1}-\delta}^{\theta^{*}_{1}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}=\frac{g_{\mu}(\xi_{2})\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}+\delta}e^{Nh_{N}(\theta)}d\theta}{g_{\mu}(\xi_{1})\int_{\theta^{*}_{1}-\delta}^{\theta^{*}_{1}+\delta}e^{Nh_{N}(\theta)}d\theta}\;,$
(13)

where, $\theta^{*}_{1}-\delta<\xi_{1}<\theta^{*}_{1}+\delta$ and
$\theta^{*}_{2}-\delta<\xi_{2}<\theta^{*}_{2}+\delta$.

Since $h^{\prime\prime}(\theta^{*}_{i})<0$ for each $1\leq i\leq 2$, one can
take $\varepsilon>0$ such that
$h^{\prime\prime}(\theta^{*}_{i})+2\varepsilon<0$, for both $i=1$ and $i=2$.
By the continuity of $h^{\prime\prime}$, one can find $\delta$ sufficiently
small such that

$h^{\prime\prime}(\theta^{*}_{i})-\varepsilon\leq h^{\prime\prime}(\theta)\leq
h^{\prime\prime}(\theta^{*}_{i})+\varepsilon,$ (14)

for all $\theta\in[\theta^{*}_{i}-\delta,\theta^{*}_{i}+\delta]$ and both
$i=1$ and $i=2$.

The uniform convergence of $h^{\prime\prime}_{N}$ to $h^{\prime\prime}$ around
$\theta^{*}_{i}$ and (14) ensure that there exists
$N_{0}=N_{0}(\delta,\varepsilon)$ such that for all $N\geq N_{0}$,

$h^{\prime\prime}(\theta^{*}_{i})-2\varepsilon\leq
h^{\prime\prime}_{N}(\theta)\leq
h^{\prime\prime}(\theta^{*}_{i})+2\varepsilon,$ (15)

for all $\theta\in[\theta^{*}_{i}-\delta,\theta^{*}_{i}-\delta]$ and $1\leq
i\leq 2$.

Now, since $h_{N}\in C^{2}([a,b])$, for each $1\leq i\leq 2$, we can expand
$h_{N}$ around $\theta^{*}_{i}$ up to order 2 to deduce that for all
$\theta\in[\theta^{*}_{i}-\delta,\theta^{*}_{i}-\delta]$,

$h_{N}(\theta)=h_{N}(\theta^{*}_{i})+h^{\prime}_{N}(\theta^{*}_{i})(\theta-\theta^{*}_{i})+h_{N}^{\prime\prime}(\zeta_{i,\theta})(\theta-\theta^{*}_{i})^{2}/2\;,$

where $\zeta_{i,\theta}$ is between $\theta$ and $\theta^{*}_{i}$. By using
that for all $N$ sufficiently large $|h^{\prime}_{N}(\theta^{*}_{i})|\leq C/N$
and (15), we can suppose (by increasing $C$ if necessary) that for all $N\geq
N_{0}$, $\theta\in[\theta^{*}_{i}-\delta,\theta^{*}_{i}-\delta]$ and $1\leq
i\leq 2,$ we have that

$\displaystyle-(C\delta)/N+(h^{\prime\prime}(\theta^{*}_{i})-2\varepsilon)(\theta-\theta^{*}_{i})^{2}/2$
$\displaystyle\leq h_{N}(\theta)-h_{N}(\theta^{*}_{i})$ $\displaystyle\leq$
$\displaystyle(C\delta)/N+(h^{\prime\prime}(\theta^{*}_{i})+2\varepsilon)(\theta-\theta^{*}_{i})^{2}/2.$
(16)

By observing that $N(h_{N}(\theta^{*}_{i})-h(\theta^{*}_{i}))\to d_{i}$ and by
increasing $N_{0}$ if necessary, we deduce from (A.1.2) that the following
inequalities hold for all $N\geq N_{0}$,
$\theta\in[\theta^{*}_{i}-\delta,\theta^{*}_{i}-\delta]$ and $1\leq i\leq 2:$

$N(h_{N}(\theta)-h(\theta^{*}_{i}))\leq
d_{i}+\varepsilon+C\delta+N(h^{\prime\prime}(\theta^{*}_{i})+2\varepsilon)(\theta-\theta^{*}_{i})^{2}/2.$
(17)

and

$N(h_{N}(\theta)-h(\theta^{*}_{i}))\geq
d_{i}-\varepsilon-C\delta+N(h^{\prime\prime}(\theta^{*}_{i})-2\varepsilon)(\theta-\theta^{*}_{i})^{2}/2.$
(18)

Hence, we deduce from the inequalities above that for all $N\geq N_{0}$
(recall that $m_{N}(\theta)=e^{Nh_{N}(\theta)}$ and that
$h(\theta^{*}_{1})=h(\theta^{*}_{2})$ by assumption), it holds

$\displaystyle\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}+\delta}m_{N}(\theta)d\theta}{\int_{\theta^{*}_{1}-\delta}^{\theta^{*}_{1}+\delta}m_{N}(\theta)d\theta}$
$\displaystyle\leq\frac{e^{(d_{2}+\varepsilon+\delta
C)}\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}+\delta}e^{N(h^{\prime\prime}(\theta^{*}_{2})+2\varepsilon)(\theta-\theta^{*}_{2})^{2}/2}d\theta}{e^{(d_{1}-\varepsilon-\delta
C)}\int_{\theta^{*}_{1}-\delta}^{\theta^{*}_{1}+\delta}e^{N(h^{\prime\prime}(\theta^{*}_{1})-2\varepsilon)(\theta-\theta^{*}_{1})^{2}/2}d\theta}\;.$
(19)

By making the change of variables $x=\sqrt{N}(\theta-\theta^{*}_{i})$ in the
right-most integrals above, we obtain

$\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}+\delta}e^{N(h^{\prime\prime}(\theta^{*}_{2})+2\varepsilon)(\theta-\theta^{*}_{2})^{2}/2}d\theta}{\int_{\theta^{*}_{1}-\delta}^{\theta^{*}_{1}+\delta}e^{N(h^{\prime\prime}(\theta^{*}_{1})-2\varepsilon)(\theta-\theta^{*}_{1})^{2}/2}d\theta}=\frac{\int_{-\delta\sqrt{N}}^{\delta\sqrt{N}}e^{(h^{\prime\prime}(\theta^{*}_{2})+2\varepsilon)x^{2}/2}dx}{\int_{-\delta\sqrt{N}}^{\delta\sqrt{N}}e^{N(h^{\prime\prime}(\theta^{*}_{1})-2\varepsilon)x^{2}/2}dx}\;.$
(20)

Therefore, from (13), (19) and (20), we have that for all $N\geq N_{0}$,

$\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}{\int_{\theta^{*}_{1}-\delta}^{\theta^{*}_{1}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}\leq\frac{g_{\mu}(\xi_{2})e^{(d_{2}+\varepsilon+\delta
C)}\int_{-\delta\sqrt{N}}^{\delta\sqrt{N}}e^{(h^{\prime\prime}(\theta^{*}_{2})+2\varepsilon)x^{2}/2}dx}{g_{\mu}(\xi_{1})e^{(d_{1}-\varepsilon-\delta
C)}\int_{-\delta\sqrt{N}}^{\delta\sqrt{N}}e^{N(h^{\prime\prime}(\theta^{*}_{1})-2\varepsilon)x^{2}/2}dx}\;,$

where, $\theta^{*}_{1}-\delta<\xi_{1}<\theta^{*}_{1}+\delta$ and
$\theta^{*}_{2}-\delta<\xi_{2}<\theta^{*}_{2}+\delta$. In particular, it
follows that

$\limsup_{N\to\infty}\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}{\int_{\theta^{*}_{1}-\delta}^{\theta^{*}_{1}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}\leq\frac{g_{\mu}(\xi_{2})e^{(d_{2}+\varepsilon+\delta
C)}}{g_{\mu}(\xi_{1})e^{(d_{1}-\varepsilon-\delta
C)}}\sqrt{\frac{2\varepsilon-h^{\prime\prime}(\theta^{*}_{1})}{-2\varepsilon-h^{\prime\prime}(\theta^{*}_{2})}}.$

By similar arguments, one can also show that

$\liminf_{N\to\infty}\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}{\int_{\theta^{*}_{1}-\delta}^{\theta^{*}_{1}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}\geq\frac{g_{\mu}(\xi_{2})e^{(d_{2}-\varepsilon-\delta
C)}}{g_{\mu}(\xi_{1})e^{(d_{1}+\varepsilon+\delta
C)}}\sqrt{\frac{-2\varepsilon-h^{\prime\prime}(\theta^{*}_{1})}{2\varepsilon-h^{\prime\prime}(\theta^{*}_{2})}}.$

By taking first $\delta\to 0$ and using the continuity of $g_{\mu}$, and then
$\varepsilon\to 0$, the result follows. ∎

See 3

###### Proof of Theorem 3.

First notice that by following the proof of Theorem 2, one can check that
Condition (A) of Key Lemma 1 holds with either $i=1$ or $i=2$.

To conclude the proof, it remains to show that Condition (B) of Key Lemma 1
holds with
$c_{1,2}=(-e^{d_{2}}g_{\mu}(\theta^{*}_{2})h^{\prime}(\theta^{*}_{1}))/(e^{d_{1}}g_{\mu}(\theta^{*}_{1})h^{\prime}(\theta^{*}_{2})).$
The proof of this fact is very similar to that of Remark 3.

In what follows, for any $\delta>0$, denote
$V_{1}(\delta)=(\theta^{*}_{1},\theta^{*}_{1}+\delta)$,
$\bar{V}_{1}(\delta)=[\theta^{*}_{1},\theta^{*}_{1}+\delta]$,
$V_{2}(\delta)=(\theta^{*}_{2}-\delta,\theta^{*}_{2})$ and
$\bar{V}_{2}(\delta)=[\theta^{*}_{2}-\delta,\theta^{*}_{2}]$.

Take $\delta>0$ small enough and apply the Mean Valued Theorem to conclude
that

$\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}}m_{N}(\theta)g_{\mu}(\theta)d\theta}{\int_{\theta^{*}_{1}}^{\theta^{*}_{1}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}=\frac{g_{\mu}(\xi_{2})\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}}e^{Nh_{N}(\theta)}d\theta}{g_{\mu}(\xi_{1})\int_{\theta^{*}_{1}}^{\theta^{*}_{1}+\delta}e^{Nh_{N}(\theta)}d\theta}\;,$
(21)

where $\xi_{i}\in V_{i}(\delta)$ for $1\leq i\leq 2$.

Since $h^{\prime}(\theta^{*}_{1})<0$ and $h^{\prime}(\theta^{*}_{2})>0$, one
can take $\varepsilon>0$ such that $h^{\prime}(\theta^{*}_{1})+2\varepsilon<0$
and $h^{\prime}(\theta^{*}_{2})-2\varepsilon>0$. By the continuity of
$h^{\prime}$, one can find $\delta$ sufficiently small such that

$h^{\prime}(\theta^{*}_{i})-\varepsilon\leq h^{\prime}(\theta)\leq
h^{\prime}(\theta^{*}_{i})+\varepsilon,$ (22)

for all $\theta\in\bar{V}_{i}(\delta)$ and both $i=1$ and $i=2$.

The uniform convergence of $h^{\prime}_{N}$ to $h^{\prime}$ around
$\theta^{*}_{i}$ and (22) ensure that there exists
$N_{0}=N_{0}(\delta,\varepsilon)$ such that for all $N\geq N_{0}$,

$h^{\prime}(\theta^{*}_{i})-2\varepsilon\leq h^{\prime}_{N}(\theta)\leq
h^{\prime}(\theta^{*}_{i})+2\varepsilon,$ (23)

for all $\theta\in\bar{V}_{i}(\delta)$ and $1\leq i\leq 2$.

Now, since $h_{N}\in C^{1}([a,b])$, for each $1\leq i\leq 2$, we can expand
$h_{N}$ around $\theta^{*}_{i}$ up to order 1 to deduce that for all
$\theta\in\bar{V}_{i}(\delta)$,

$h_{N}(\theta)=h_{N}(\theta^{*}_{i})+h^{\prime}_{N}(\zeta_{i,\theta})(\theta-\theta^{*}_{i})\;,$

where $\zeta_{i,\theta}$ is between $\theta$ and $\theta^{*}_{i}$.

It follows from (22) and (23) that for all $\theta\in\bar{V}_{1}(\delta)$ and
$N\geq N_{0}$, it holds

$\displaystyle
N(h^{\prime}(\theta^{*}_{1})-2\varepsilon)(\theta-\theta^{*}_{1})\leq
N(h_{N}(\theta)-h_{N}(\theta^{*}_{1}))\leq
N(h^{\prime}(\theta^{*}_{1})+2\varepsilon)(\theta-\theta^{*}_{1}).$ (24)

Similarly, for all $\theta\in\bar{V}_{2}(\delta)$ and $N\geq N_{0}$, it holds
that

$\displaystyle
N(h^{\prime}(\theta^{*}_{2})+2\varepsilon)(\theta-\theta^{*}_{2})\leq
N(h_{N}(\theta)-h_{N}(\theta^{*}_{2}))\leq
N(h^{\prime}(\theta^{*}_{2})-2\varepsilon)(\theta-\theta^{*}_{2}).$ (25)

By using the fact that $N(h_{N}(\theta^{*}_{i})-h(\theta_{i}^{*}))\to d_{i}$
together with inequalities (24) and (25), we deduce that for all $N\geq N_{0}$
and any $\theta\in\bar{V_{1}}(\delta)$,

$\displaystyle
d_{1}-\varepsilon+N(h^{\prime}(\theta^{*}_{1})-2\varepsilon)(\theta-\theta^{*}_{1})$
$\displaystyle\leq N(h_{N}(\theta)-h(\theta^{*}_{1}))$ $\displaystyle\leq
d_{1}+\varepsilon+N(h^{\prime}(\theta^{*}_{1})+2\varepsilon)(\theta-\theta^{*}_{1}).$
(26)

and similarly, for all $N\geq N_{0}$ and any $\theta\in\bar{V_{2}}(\delta),$

$\displaystyle
d_{2}-\varepsilon+N(h^{\prime}(\theta^{*}_{2})+2\varepsilon)(\theta-\theta^{*}_{2})$
$\displaystyle\leq N(h_{N}(\theta)-h(\theta^{*}_{2}))$ $\displaystyle\leq
d_{2}+\varepsilon+N(h^{\prime}(\theta^{*}_{2})-2\varepsilon)(\theta-\theta^{*}_{2}).$
(27)

Therefore, we deduce from the inequalities above that for all $N\geq N_{0}$
(recall that $m_{N}(\theta)=e^{Nh_{N}(\theta)}$ and that
$h(\theta^{*}_{1})=h(\theta^{*}_{2})$ by assumption), it holds

$\displaystyle\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}}m_{N}(\theta)d\theta}{\int_{\theta^{*}_{1}}^{\theta^{*}_{1}+\delta}m_{N}(\theta)d\theta}$
$\displaystyle\leq\frac{e^{(d_{2}+\varepsilon)}\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}}e^{N(h^{\prime}(\theta^{*}_{2})-2\varepsilon)(\theta-\theta^{*}_{2})}d\theta}{e^{(d_{1}-\varepsilon)}\int_{\theta^{*}_{1}}^{\theta^{*}_{1}+\delta}e^{N(h^{\prime}(\theta^{*}_{1})-2\varepsilon)(\theta-\theta^{*}_{1})}d\theta}\;.$
(28)

By making the change of variables $x=-N(\theta-\theta^{*}_{2})$ (respectively
$x=N(\theta-\theta^{*}_{1})$) in the integral appearing in the numerator
(respectively denominator) of the right-most ratio, we then obtain

$\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}}e^{N(h^{\prime}(\theta^{*}_{2})-2\varepsilon)(\theta-\theta^{*}_{2})}d\theta}{\int_{\theta^{*}_{1}}^{\theta^{*}_{1}+\delta}e^{N(h^{\prime}(\theta^{*}_{1})-2\varepsilon)(\theta-\theta^{*}_{1})}d\theta}=\frac{\int_{0}^{\delta
N}e^{-(h^{\prime}(\theta^{*}_{2})-2\varepsilon)x}dx}{\int_{0}^{\delta
N}e^{-(2\varepsilon-h^{\prime}(\theta^{*}_{1}))x}dx}\;.$ (29)

Therefore, from (21), (28) and (29), we have that for all $N\geq N_{0}$,

$\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}}m_{N}(\theta)g_{\mu}(\theta)d\theta}{\int_{\theta^{*}_{1}}^{\theta^{*}_{1}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}\leq\frac{g_{\mu}(\xi_{2})e^{(d_{2}+\varepsilon)}\int_{0}^{\delta
N}e^{-(h^{\prime}(\theta^{*}_{2})-2\varepsilon)x}dx}{g_{\mu}(\xi_{1})e^{(d_{1}-\varepsilon)}\int_{0}^{\delta
N}e^{-(2\varepsilon-h^{\prime}(\theta^{*}_{1}))x}dx}\;,$

where $\xi_{1}\in V_{i}(\delta)$ for $1\leq i\leq 2.$ As a consequence, it
follows that

$\limsup_{N\to\infty}\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}{\int_{\theta^{*}_{1}-\delta}^{\theta^{*}_{1}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}\leq\frac{g_{\mu}(\xi_{2})e^{(d_{2}+\varepsilon)}}{g_{\mu}(\xi_{1})e^{(d_{1}-\varepsilon)}}\frac{2\varepsilon-h^{\prime}(\theta^{*}_{1})}{h^{\prime}(\theta^{*}_{2})-2\varepsilon}.$

By similar arguments, one can also deduce that

$\liminf_{N\to\infty}\frac{\int_{\theta^{*}_{2}-\delta}^{\theta^{*}_{2}}m_{N}(\theta)g_{\mu}(\theta)d\theta}{\int_{\theta^{*}_{1}}^{\theta^{*}_{1}+\delta}m_{N}(\theta)g_{\mu}(\theta)d\theta}\geq\frac{g_{\mu}(\xi_{2})e^{(d_{2}-\varepsilon)}}{g_{\mu}(\xi_{1})e^{(d_{1}+\varepsilon)}}\frac{(-2\varepsilon-h^{\prime}(\theta^{*}_{1}))}{2\varepsilon+h^{\prime}(\theta^{*}_{2})}.$

By taking first $\delta\to 0$ and using the continuity of $g_{\mu}$, and then
$\varepsilon\to 0$, we conclude the proof. ∎

###  A.2 Expectation of hitting times

We give below the computations of the expected hitting time for the Single-
well and Alternating-wells random walk presented in Section 3.4 and Section
3.5, respectively.

See 3

###### Proof of Proposition 3.

We have $\mathcal{X}_{N}=[-N,N]\cap{\mathbb{Z}}$ and let $\tau_{\\{-N,N\\}}$
the time to hit the target set $\\{-N,N\\}$. We shall prove only the case
$\theta\neq\\{1/2,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}\\}$.
The case $\theta=1/2$ is the classical Gambler’s ruin on
$[-N,N]\cap{\mathbb{Z}}$ starting from $0$ and the case $\theta=1$ is
immediate. Also, given a set $A$, we denote by $\tau_{A}$ the corresponding
hitting time.

By the Strong Markov property and the symmetry, we have

$\displaystyle{\mathbb{E}}_{0,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]$
$\displaystyle=1+\theta{\mathbb{E}}_{-1,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]+(1-\theta){\mathbb{E}}_{1,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]$
$\displaystyle=1+{\mathbb{E}}_{1,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]\;.$

On the other hand, by the strong Markov property, we also get

$\displaystyle{\mathbb{E}}_{1,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]={\mathbb{E}}_{1,\delta_{\theta}}\left[\tau_{\\{0,N\\}}\right]+{\mathbb{P}}_{1,\delta_{\theta}}(\tau_{\\{0\\}}<\tau_{\\{N\\}}){\mathbb{E}}_{0,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]\;,$

and thus

$\displaystyle{\mathbb{E}}_{0,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]$
$\displaystyle=1+{\mathbb{E}}_{1,\delta_{\theta}}\left[\tau_{\\{0,N\\}}\right]+{\mathbb{P}}_{1,\delta_{\theta}}(\tau_{\\{0\\}}<\tau_{\\{N\\}}){\mathbb{E}}_{0,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]\;.$

Solving the above equation for
${\mathbb{E}}_{0,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]$, we obtain
that

${\mathbb{E}}_{0,\delta_{\theta}}\left[\tau_{\\{-N,N\\}}\right]=\frac{1+{\mathbb{E}}_{1,\delta_{\theta}}\left[\tau_{\\{0,N\\}}\right]}{{\mathbb{P}}_{1,\delta_{\theta}}(\tau_{\\{0\\}}\geq\tau_{\\{N\\}})}\;.$
(30)

Finally, since the dynamics of the Single-well random walk on
$\\{1,\ldots,N\\}$ is the same as the classical Gambler’s Ruin random walk on
$\\{0,\ldots,N\\}$, we obtain that

${\mathbb{E}}_{1,\delta_{\theta}}\left[\tau_{\\{0,N\\}}\right]=\frac{1}{1-2\theta}-\frac{N}{\theta}\frac{1}{(((1-\theta)/\theta)^{N}-1)}\;,$

and that

${\mathbb{P}}_{1,\delta_{\theta}}(\tau_{\\{0\\}}>\tau_{\\{N\\}})=\frac{1-2\theta}{\theta(((1-\theta)/\theta)^{N}-1)}\;.$

By plugging these expressions in (30), the result follows.

∎

See 4

###### Proof of Proposition 4.

To facilitate the exposition, in this proof we shall carry the dependence on
the state $\theta$ and an initial state $i$ in the random variable $\tau$,
rather than in the probability/expectation. Thus, given $i\in\mathcal{X}_{N}$,
and a set $A\subset\mathcal{X}_{N}$, we denote by $\tau^{i,\theta}_{A}$ the
first time the random walk with state $\theta$ hits the set $A$, starting from
the state $i$, and we write ${\mathbb{E}}[\tau^{i,\theta}_{A}]$ and
${\mathbb{P}}(\tau^{i,\theta}_{A}<\tau^{i,\theta}_{B})$ instead of
${\mathbb{E}}_{i,\delta_{\theta}}[\tau_{A}]$ and
${\mathbb{P}}_{i,\delta_{\theta}}(\tau_{A}<\tau_{B})$. Moreover, since the
proof also relies upon comparison across different models, we shall upper
indexing ${\mathbb{P}}$ and ${\mathbb{E}}$ by ${\rm GR}$ (gambler ruin), ${\rm
SW}$ (single-well) and ${\rm AW}$ (alternating-wells), to emphasize which
model we are referring to.

We have $\mathcal{X}_{N}=[-2N,2N]\cap{\mathbb{Z}}$ and we need to compute
${\mathbb{E}}^{{\rm AW}}[\tau^{0,\theta}_{\\{-2N,2N\\}}]$. The random variable
$\tau^{0,\theta}_{\\{-2N,2N\\}}$ can be decomposed as follows:

$\displaystyle\tau^{0,\theta}_{\\{-2N,2N\\}}$
$\displaystyle=\big{(}\tau^{0,\theta}_{\\{N\\}}+T_{1}\big{)}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{0,\theta}_{\\{N\\}}\leq\tau^{0,\theta}_{\\{-N\\}})}+\big{(}\tau^{0,\theta}_{\\{-N\\}}+T_{2}\big{)}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{0,\theta}_{\\{-N\\}}<\tau^{0,\theta}_{\\{N\\}})}$
$\displaystyle=\tau^{0,\theta}_{\\{-N,N\\}}+T_{1}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{0,\theta}_{\\{N\\}}\leq\tau^{0,\theta}_{\\{-N\\}})}+T_{2}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{0,\theta}_{\\{-N\\}}<\tau^{0,\theta}_{\\{N\\}})}\;,$

where $T_{1}$ and $T_{2}$ are random variables independent of everything else
and have the same distribution as $\tau^{N,\theta}_{\\{-2N,2N\\}}$ and
$\tau^{-N,\theta}_{\\{-2N,2N\\}}$, respectively. These random variables, in
turn, can be decomposed as:

$\displaystyle T_{1}$
$\displaystyle=\tau^{N,\theta}_{\\{0,2N\\}}+\tau^{\prime}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{N,\theta}_{\\{0\\}})\leq\tau^{N,\theta}_{\\{2N\\}})}\;,$
$\displaystyle T_{2}$
$\displaystyle=\tau^{-N,\theta}_{\\{0,-2N\\}}+\tau^{\prime\prime}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{-N,\theta}_{\\{0\\}})\leq\tau^{-N,\theta}_{\\{-2N\\}})}\;,$

with $\tau^{\prime},\tau^{\prime\prime}$ random variables with the same
distribution as $\tau^{0,\theta}_{\\{-2N,2N\\}}$, independent of everything
else. Overall, we can write $\tau^{0,\theta}_{\\{-2N,2N\\}}$ as

$\displaystyle\tau^{0,\theta}_{\\{-2N,2N\\}}$
$\displaystyle=\tau^{0,\theta}_{\\{-N,N\\}}+\tau^{N,\theta}_{\\{0,2N\\}}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{0,\theta}_{\\{N\\}}\leq\tau^{0,\theta}_{\\{-N\\}})}+\tau^{-N,\theta}_{\\{0,-2N\\}}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{0,\theta}_{\\{-N\\}}<\tau^{0,\theta}_{\\{N\\}})}$
$\displaystyle+\tau^{\prime}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{0,\theta}_{\\{N\\}}\leq\tau^{0,\theta}_{\\{-N\\}})}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{N,\theta}_{\\{0\\}}<\tau^{N,\theta}_{\\{2N\\}})}+\tau^{\prime\prime}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{0,\theta}_{\\{-N\\}}<\tau^{0,\theta}_{\\{N\\}})}\leavevmode\hbox{\rm\small
1\kern-3.15005pt\normalsize
1}_{(\tau^{-N,\theta}_{\\{0\\}}\leq\tau^{-N,\theta}_{\\{-2N\\}})}\;.$

Using independence between the random variables, we obtain that

$\displaystyle{\mathbb{E}}^{{\rm AW}}(\tau^{0,\theta}_{\\{-2N,2N\\}})$
$\displaystyle={\mathbb{E}}^{{\rm
AW}}(\tau^{0,\theta}_{\\{-N,N\\}})+{\mathbb{E}}^{{\rm
AW}}(\tau^{N,\theta}_{\\{0,2N\\}}){\mathbb{P}}^{{\rm
AW}}(\tau^{0,\theta}_{\\{N\\}}\leq\tau^{0,\theta}_{\\{-N\\}})$ (31)
$\displaystyle+{\mathbb{E}}^{{\rm
AW}}(\tau^{-N,\theta}_{\\{0,-2N\\}}){\mathbb{P}}^{{\rm
AW}}(\tau^{0,\theta}_{\\{-N\\}}<\tau^{0,\theta}_{\\{N\\}})$
$\displaystyle+{\mathbb{E}}^{{\rm
AW}}(\tau^{0,\theta}_{\\{-2N,2N\\}}){\mathbb{P}}^{{\rm
AW}}(\tau^{0,\theta}_{\\{N\\}}\leq\tau^{0,\theta}_{\\{-N\\}}){\mathbb{P}}^{{\rm
AW}}(\tau^{N,\theta}_{\\{0\\}}<\tau^{N,\theta}_{\\{2N\\}})$
$\displaystyle+{\mathbb{E}}^{{\rm
AW}}(\tau^{0,\theta}_{\\{-2N,2N\\}}){\mathbb{P}}^{{\rm
AW}}(\tau^{0,\theta}_{\\{-N\\}}<\tau^{0,\theta}_{\\{N\\}}){\mathbb{P}}^{{\rm
AW}}(\tau^{-N,\theta}_{\\{0\\}}\leq\tau^{-N,\theta}_{\\{-2N\\}})\;.$

Using the Strong Markov property, we have that:

  * 1.

${\mathbb{E}}^{{\rm AW}}(\tau^{N,\theta}_{\\{0,2N\\}})={\mathbb{E}}^{{\rm
SW}}(\tau^{0,\theta}_{\\{-N,N\\}})$, where the right-hand side (rhs) is the
expected hitting time of $\\{-N,N\\}$ for a SW random walk in a
$\theta$-environment starting from $0$ (see, Proposition 3);

  * 2.

${\mathbb{E}}^{{\rm AW}}(\tau^{-N,\theta}_{\\{0,-2N\\}})={\mathbb{E}}^{{\rm
SW}}(\tau^{0,1-\theta}_{\\{-N,N\\}})$, where the rhs is the expected hitting
time of $\\{-N,N\\}$ for a SW random walk in a $(1-\theta)$-environment
starting from $0$;

  * 3.

${\mathbb{E}}^{{\rm AW}}(\tau^{0,\theta}_{\\{-N,N\\}})={\mathbb{E}}^{{\rm
GR}}(\tau^{0,1-\theta}_{\\{-N,N\\}})$, where the rhs is the expected hitting
time of $\\{-N,N\\}$ for a GR random walk starting from $0$ (when it jumps to
the right with probability $1-\theta$; note that by symmetry
${\mathbb{E}}^{{\rm GR}}(\tau^{0,1-\theta}_{\\{-N,N\\}})={\mathbb{E}}^{{\rm
GR}}(\tau^{0,\theta}_{\\{-N,N\\}})$);

  * 4.

${\mathbb{P}}^{{\rm
AW}}(\tau^{0,\theta}_{\\{N\\}}\leq\tau^{0,\theta}_{\\{-N\\}})={\mathbb{P}}^{{\rm
GR}}(\tau^{0,1-\theta}_{\\{N\\}}\leq\tau^{0,1-\theta}_{\\{-N\\}})=\frac{1}{1+\left(\frac{\theta}{1-\theta}\right)^{N}}$,
where the rhs is the probability of a Gambler’s ruin hitting $N$ before $-N$
starting from $0$ (when it jumps to the right with probability $1-\theta$);

  * 5.

${\mathbb{P}}^{{\rm
AW}}(\tau^{-N,\theta}_{\\{0\\}}\leq\tau^{-N,\theta}_{\\{-2N\\}})={\mathbb{P}}^{{\rm
SW}}(\tau^{0,1-\theta}_{\\{N\\}}\leq\tau^{0,1-\theta}_{\\{-N\\}})=1-\theta$,
which can be proved by a standard first-step analysis.

Therefore, from (31) we then obtain

$\displaystyle{\mathbb{E}}^{{\rm AW}}(\tau^{0,\theta}_{\\{-2N,2N\\}})=$
$\displaystyle\frac{1}{\frac{\theta\left(\frac{\theta}{1-\theta}\right)^{N}+1-\theta}{1+\left(\frac{\theta}{1-\theta}\right)^{N}}}\left({\mathbb{E}}^{{\rm
GR}}(\tau^{0,1-\theta}_{\\{-N,N\\}})+\frac{{\mathbb{E}}^{{\rm
SW}}(\tau^{0,\theta}_{\\{-N,N\\}})}{1+\left(\frac{\theta}{1-\theta}\right)^{N}}+\frac{{\mathbb{E}}^{{\rm
SW}}(\tau^{0,1-\theta}_{\\{-N,N\\}})\left(\frac{\theta}{1-\theta}\right)^{N}}{1+\left(\frac{\theta}{1-\theta}\right)^{N}}\right)\;.$

Using Proposition 3 and (6), the claim follows.

∎

###  A.3 Metastability/cut-off

In this section, we prove Theorem 6, Proposition 2 and Theorem 7.

See 6

###### Proof of Theorem 6.

Let us start proving item (i). Given a subset $A\subset\mathcal{X}_{N}$, let
us denote $\tau_{A}$ the first time the single-well random walk hits the set
$A$. With this notation, we have $\tau_{N}=\tau_{\\{-N,N\\}}$. Since the proof
relies upon comparison with the gambler ruin, we shall upper indexing
${\mathbb{P}}$ and ${\mathbb{E}}$ by ${\rm GR}$ (gambler ruin) and ${\rm SW}$
(single-well) to emphasize which model we are referring to.

According to Theorem 5, to show item $i)$ it suffices to find $R_{N}>0$ and
$r_{N}\in(0,1)$ such that $r_{N}\underset{N\to\infty}{\longrightarrow}0$,
$R_{N}/{\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\underset{N\to\infty}{\longrightarrow}0$
and

$\sup_{x\in\\{-N+1,\ldots,-1,1,\ldots,N-1\\}}{\mathbb{P}}^{{\rm
SW}}_{x,\delta_{\theta}}(\tau_{\\{-N,0,N\\}}>R_{N})\leq r_{N}\;.$

By the dynamics of the single-well random walk, for each
$i\in\\{1,\ldots,N-1\\}:$

${\mathbb{P}}^{{\rm
SW}}_{i,\delta_{\theta}}(\tau_{\\{-N,0,N\\}}>R_{N})={\mathbb{P}}^{{\rm
GR}}_{i,\theta}(\tau_{\\{0,N\\}}>R_{N})\;,$

where, ${\mathbb{P}}^{{\rm GR}}_{i,\theta}$ denotes the probability of a
random walk starting from $i$ with transition probability to the right equal
to $\theta$ (we shall denote by ${\mathbb{E}}^{{\rm GR}}_{i,\theta}$ the
corresponding expectation). Similarly, we also have that for each
$i\in\\{-1,\ldots,-N+1\\}:$

${\mathbb{P}}^{{\rm
SW}}_{i,\delta_{\theta}}(\tau_{\\{-N,0,N\\}}>R_{N})={\mathbb{P}}^{{\rm
GR}}_{i,\theta}(\tau_{\\{-N,0\\}}>R_{N})={\mathbb{P}}^{{\rm
GR}}_{-i,\theta}(\tau_{\\{0,N\\}}>R_{N})\;.$

Hence, by Markov’s inequality,

$\sup_{x\in\\{-N+1,\ldots,-1,1,\ldots,N-1\\}}{\mathbb{P}}^{{\rm
SW}}_{x,\delta_{\theta}}(\tau_{\\{-N,0,N\\}}>R_{N})\leq\frac{1}{R_{N}}\max_{i\in\\{1,\ldots,N-1\\}}{\mathbb{E}}^{{\rm
GR}}_{i,\theta}(\tau_{\\{0,N\\}})\;.$

It is well know that for any $i\in\\{1,\ldots,N-1\\},$

${\mathbb{E}}^{{\rm
GR}}_{i,\theta}[\tau_{\\{0,N\\}}]=\frac{i}{1-2\theta}-\frac{N}{1-2\theta}\frac{\left(\frac{1-\theta}{\theta}\right)^{i}-1}{\left(\frac{1-\theta}{\theta}\right)^{N}-1}\;.$

Thus, for all $\theta<1/2$ and $i\in\\{1,\ldots,N-1\\},$

${\mathbb{E}}^{{\rm
GR}}_{i,\theta}[\tau_{\\{0,N\\}}]\leq\frac{i}{1-2\theta}\leq\frac{N-1}{1-2\theta}\;,$

so that

$\sup_{x\in\\{-N+1,\ldots,-1,1,\ldots,N-1\\}}{\mathbb{P}}^{{\rm
SW}}_{x,\delta_{\theta}}(\tau_{\\{-N,0,N\\}}>R_{N})\leq\frac{N-1}{R_{N}(1-2\theta)}\;.$

Therefore, by taking $R_{N}=((N-1)/(1-2\theta))^{1+\varepsilon}$ for any fixed
$\varepsilon>0$ and
$r_{N}=\frac{N-1}{R_{N}(1-2\theta)}=((1-2\theta)/(N-1))^{\varepsilon}$, and
recalling that by Proposition 3 ${\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{\\{-N,N\\}}]$ grows exponentially in $N$ for
any $0<\theta<1/2$, the result follows.

We now prove item (ii). Let $\\{X_{n}\\}_{n\geq 0}$ be the location chain with
state $\theta$, that is, the Markov chain started at $0$ with transition
matrix $Q^{(\theta)}$ defined in Section 3.4. Notice that
$\\{|X_{n}|\\}_{n\geq 0}$ is a simple random walk reflected at $0$, with
probability $1$ to go from $0$ to $1$ and probability $\theta$ to go from $i$
to $i+1$ for any $i\geq 1$. Since here we consider $\theta>1/2$, the strong
law of large numbers gives

$\frac{|X_{n}|}{n}\underset{n\rightarrow\infty}{\rightarrow}2\theta-1\,,\,\,\text{a.s.}$

Since $\tau_{N}\stackrel{{\scriptstyle
N\rightarrow\infty}}{{\rightarrow}}\infty$ a.s., it follows that ,
$\frac{|X_{\tau_{N}}|}{\tau_{N}}\rightarrow 2\theta-1$ a.s. as well. Moreover,
by definition, $|X_{\tau_{N}}|=N,N\geq 1$. On the other hand, since
$\theta>1/2$, by Proposition 3, we have $\frac{{\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{N}]}{N}\rightarrow\frac{1}{2\theta-1}$. Thus

$\frac{\tau^{N}}{{\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{N}]}=\frac{\tau^{N}}{N}\frac{N}{{\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{N}]}=\frac{\tau^{N}}{|X_{\tau_{N}}|}\frac{N}{{\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{N}]}\rightarrow 1\,,\,\,\text{a.s.}$

∎

See 2

###### Proof of Proposition 2.

The proof follows the same lines as the proof of Item ii) of Theorem 6 with
very minor changes. ∎

See 7

###### Proof of Theorem 7.

Given a subset $A\subset\mathcal{X}_{N}=[-2N,2N]\cap\mathbb{Z}$, let us denote
$\tau_{A}$ the first time the alternating-wells random walk hits the set $A$.
With this notation, we have $\tau_{N}=\tau_{\\{-2N,2N\\}}$. Since the proof
relies upon comparison with the single-well, we shall upper indexing
${\mathbb{P}}$ and ${\mathbb{E}}$ by ${\rm SW}$ (single-well) and ${\rm AW}$
(alternating-wells) to emphasize which model we are referring to.

According to Theorem 5, it suffices to find $R_{N}>0$ and $r_{N}\in(0,1)$ such
that $r_{N}\underset{N\to\infty}{\longrightarrow}0$, $R_{N}/{\mathbb{E}}^{{\rm
AW}}_{0,\delta_{\theta}}[\tau_{\\{-2N,2N\\}}]\underset{N\to\infty}{\longrightarrow}0$
and

$\sup_{x\in\\{-2N+1,\ldots,-N-1,-N+1,\ldots,2N-1\\}}{\mathbb{P}}^{{\rm
AW}}_{x,\delta_{\theta}}(\tau_{\\{-2N,0,2N\\}}>R_{N})\leq r_{N}\;.$

By Markov’s inequality, the left-hand side above is less than or equal to
$\frac{1}{R_{N}}\max_{x\in\mathcal{X}_{N}}{\mathbb{E}}^{{\rm
AW}}_{x,\delta_{\theta}}[\tau_{\\{-2N,0,2N\\}}]$. The following claim holds:

Claim:

$\displaystyle\max_{x\in\mathcal{X}_{N}}{\mathbb{E}}^{{\rm
AW}}_{x,\delta_{\theta}}[\tau_{\\{-2N,0,2N\\}}]=\begin{cases}{\mathbb{E}}^{{\rm
AW}}_{-N,\delta_{\theta}}[\tau_{\\{-2N,0,2N\\}}]\;,&\text{ if
$\theta>1/2$,}\\\\[5.0pt] {\mathbb{E}}^{{\rm
AW}}_{N,\delta_{\theta}}[\tau_{\\{-2N,0,2N\\}}]\;,&\text{ if
$\theta<1/2$.}\end{cases}$

Note that ${\mathbb{E}}^{{\rm
AW}}_{-N,\delta_{\theta}}[\tau_{\\{-2N,0,2N\\}}]={\mathbb{E}}^{{\rm
AW}}_{-N,\delta_{\theta}}[\tau_{\\{-2N,0\\}}]$ and ${\mathbb{E}}^{{\rm
AW}}_{N,\delta_{\theta}}[\tau_{\\{-2N,0,2N\\}}]={\mathbb{E}}^{{\rm
AW}}_{N,\delta_{\theta}}[\tau_{\\{0,2N\\}}]$. By comparison with the single-
well random walk in Section 3.4, we obtain that

$\begin{split}{\mathbb{E}}^{{\rm
AW}}_{N,\delta_{\theta}}[\tau_{\\{0,2N\\}}]&={\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\;,\\\ {\mathbb{E}}^{{\rm
AW}}_{-N,\delta_{\theta}}[\tau_{\\{-2N,0\\}}]&={\mathbb{E}}^{{\rm
SW}}_{0,\delta_{(1-\theta)}}[\tau_{\\{-N,N\\}}]\;.\end{split}$ (32)

From Proposition 3, we have that

$\begin{cases}{\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\leq\frac{N}{2\theta-1}\;,&\text{
if $\theta>1/2$,}\\\\[5.0pt] {\mathbb{E}}^{{\rm
SW}}_{0,\delta_{(1-\theta)}}[\tau_{\\{-N,N\\}}]\leq\frac{N}{1-2\theta}\;,&\text{
if $\theta<1/2$.}\end{cases}$

Thus, for every $\theta\neq 1/2$ we obtain that

$\sup_{x\in\mathcal{X}_{N}}{\mathbb{P}}^{{\rm
AW}}_{x,\delta_{\theta}}(\tau_{\\{-N,0,N\\}}>R_{N})\leq\frac{N}{R_{N}|2\theta-1|}\;.$

Therefore, by taking $R_{N}=(N/|2\theta-1|)^{1+\varepsilon}$ for any fixed
$\varepsilon>0$ and
$r_{N}=\frac{N}{R_{N}|2\theta-1|}=(|2\theta-1|/N)^{\varepsilon}$, and
recalling that by Proposition 4 ${\mathbb{E}}^{{\rm
AW}}_{0,\delta_{\theta}}[\tau_{\\{-2N,2N\\}}]$ grows exponentially in $N$ for
any $\theta\neq 1/2$, the result follows.

Proof of the Claim: Let us begin observing that for every
$x\in[-2N,2N]\cap\mathbb{Z}$ we have

${\mathbb{E}}^{{\rm
AW}}_{x,\delta_{\theta}}[\tau_{\\{-2N,0,2N\\}}]=\begin{cases}{\mathbb{E}}^{{\rm
AW}}_{x,\delta_{\theta}}[\tau_{\\{-2N,0\\}}]={\mathbb{E}}^{{\rm
SW}}_{x+N,\delta_{(1-\theta)}}[\tau_{\\{-N,N\\}}]\;,&x<0\;,\\\
{\mathbb{E}}^{{\rm
AW}}_{x,\delta_{\theta}}[\tau_{\\{0,2N\\}}]={\mathbb{E}}^{{\rm
SW}}_{x-N,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\;,&x>0\;,\\\
0\;,&x=0\;,\end{cases}$

where, we used a comparison with the single-well random walk (see, Section
3.4). Thus, $\max_{x\in\mathcal{X}_{N}}{\mathbb{E}}^{{\rm
AW}}_{x,\delta_{\theta}}[\tau_{\\{-2N,0,2N\\}}]$ can be written as

$\max\left\\{\max_{\begin{subarray}{c}x\in\mathcal{X}_{N}\\\
x<0\end{subarray}}{\mathbb{E}}^{{\rm
SW}}_{x+N,\delta_{(1-\theta)}}[\tau_{\\{-N,N\\}}],\max_{\begin{subarray}{c}x\in\mathcal{X}_{N}\\\
x>0\end{subarray}}{\mathbb{E}}^{{\rm
SW}}_{x-N,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\right\\}\;.$

Hence, to prove the claim it suffices to show that for every $\theta\in(0,1]$

$\displaystyle\max_{i\in\\{-N+1,\ldots,-1,0,+1,\ldots,N-1\\}}{\mathbb{E}}^{{\rm
SW}}_{i,\delta_{\theta}}[\tau_{\\{-N,N\\}}]={\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\;.$ (33)

As a matter of fact, if (33) holds, we obtain

$\max_{x\in\mathcal{X}_{N}}{\mathbb{E}}^{{\rm
AW}}_{x,\delta_{\theta}}[\tau_{\\{-2N,0,2N\\}}]=\max\left\\{{\mathbb{E}}^{{\rm
SW}}_{0,\delta_{(1-\theta)}}[\tau_{\\{-N,N\\}}],{\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\right\\}$

and the claim follows from Proposition 3 and (32). To show that (33) holds,
note that, for every $\theta\in(0,1]$ and for every $x\in\\{1,\ldots,N-1\\}$,
it holds that ${\mathbb{E}}^{{\rm
SW}}_{x,\delta_{\theta}}[\tau_{\\{-N,N\\}}]={\mathbb{E}}^{{\rm
SW}}_{-x,\delta_{\theta}}[\tau_{\\{-N,N\\}}]$ (due to the symmetry of the
single-well). Therefore, showing (33) reduces to show
$\max_{i\in\\{0,1,\ldots,N-1\\}}{\mathbb{E}}^{{\rm
SW}}_{i,\delta_{\theta}}[\tau_{\\{-N,N\\}}]={\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{\\{-N,N\\}}]$. The latter condition follows
from noticing that ${\mathbb{E}}^{{\rm
SW}}_{x,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\leq{\mathbb{E}}^{{\rm
SW}}_{x-1,\delta_{\theta}}[\tau_{\\{-N,N\\}}]$, for every
$x\in\\{1,\ldots,N-1\\}$. In fact, ${\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{\\{-N,N\\}}]=1+{\mathbb{E}}^{{\rm
SW}}_{1,\delta_{\theta}}[\tau_{\\{-N,N\\}}]$ and thus ${\mathbb{E}}^{{\rm
SW}}_{1,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\leq{\mathbb{E}}^{{\rm
SW}}_{0,\delta_{\theta}}[\tau_{\\{-N,N\\}}]$. Then, recursively applying that,
for every $x\in\\{1,\ldots,N-1\\}$ it holds that

${\mathbb{E}}^{{\rm
SW}}_{x,\delta_{\theta}}[\tau_{\\{-N,N\\}}]=1+(1-\theta){\mathbb{E}}^{{\rm
SW}}_{x-1,\delta_{\theta}}[\tau_{\\{-N,N\\}}]+\theta{\mathbb{E}}^{{\rm
SW}}_{x+1,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\;,$

and ${\mathbb{E}}^{{\rm
SW}}_{x,\delta_{\theta}}[\tau_{\\{-N,N\\}}]\leq{\mathbb{E}}^{{\rm
SW}}_{x-1,\delta_{\theta}}[\tau_{\\{-N,N\\}}]$, the claim follows. ∎

##  Appendix B Auxiliary Lemmas

######  Lemma 2.

Let $h_{N}(\theta)=N^{-1}\log m_{N}(\theta)$ be the Single Well potential with
parameter $N\geq 1$ at the value $\theta\in(0,1]$, where $m_{N}(\theta)$ is
given in Equation (8), and $h(\theta)$ be the function defined in Definition
(9). For any $a\in(0,1)$, it holds that

$\sup_{\theta\in[a,1]}|h_{N}(\theta)-h(\theta)|\underset{N\to\infty}{\longrightarrow}0\;.$

###### Proof of Lemma 2.

Fix $\varepsilon>0$. The continuity of the function $h$ implies that $h$ is
uniformly continuous on $[a,1]$. From this it follows that there exists
$\delta=\delta(\varepsilon)$ such that if $\theta,\theta^{\prime}\in[a,1]$
satisfies $|\theta-\theta^{\prime}|<\delta$, then
$|h(\theta)-h(\theta^{\prime})|<\varepsilon$. For fixed $\delta>0$, define
$M=\lfloor(1-a)/\delta\rfloor$, $\theta_{i}=a+i\delta$ for $0\leq i\leq M$ and
$\theta_{M+1}=1\vee\theta_{M}$.

We recall that $h_{N}$ converges pointwise to $h$ and that all these functions
are monotonically decreasing (see the discussion below Proposition 3). It
follows from the convergence that there exists $N_{0}=N_{0}(\delta)$ such that
for all $N\geq N_{0}$ and $0\leq i\leq M+1$,

$|h_{N}(\theta_{i})-h(\theta_{i})|<\varepsilon\;.$

Note that by construction $|h(\theta_{i})-h(\theta)|<\varepsilon$ and
$|h(\theta_{i+1})-h(\theta)|<\varepsilon$ for all
$\theta_{i}<\theta<\theta_{i+1}$. On the other hand, using now the
monotonicity of both $h_{N}$ and $h$, we deduce that for all $N\geq N_{0}$ and
$\theta_{i}<\theta<\theta_{i+1}$,

$h_{N}(\theta)\leq
h_{N}(\theta_{i})\leq{h}(\theta_{i})+\varepsilon\leq{h}(\theta)+2\varepsilon\;.$
(34)

Similarly, we also have

$h_{N}(\theta)\geq
h_{N}(\theta_{i+1})\geq{h}(\theta_{i+1})-\varepsilon\geq{h}(\theta)-2\varepsilon\;.$
(35)

Thus, by combining (34) and (35) we conclude that for all $N\geq N_{0}$ and
all $0\leq i\leq M+1$,

$\sup_{\theta\in[\theta_{i},\theta_{i+1}]}|h_{N}(\theta)-h(\theta)|<2\varepsilon\;,$

implying the lemma. ∎

######  Lemma 3.

Let $h_{N}(\theta)=N^{-1}\log m_{N}(\theta)$ be the Alternating Wells
potential with parameter $N\geq 1$ at the value $\theta\in(0,1)$, where
$m_{N}(\theta)$ is given in Proposition 4, and $h(\theta)$ be the function
defined in (10). For any $0<a<1/2<b<1$, it holds that

$\sup_{\theta\in[a,b]}|h_{N}(\theta)-h(\theta)|\underset{N\to\infty}{\longrightarrow}0\;.$

###### Proof of Lemma 3.

First, apply the exact same proof of Lemma 2 to show the uniform convergence
holds on $[a,1/2]$. To show the uniform convergence on $[1/2,b]$, one can
proceed as in the proof of Lemma 2 but now using $\theta_{i+1}$ instead of
$\theta_{i}$ in (34) and $\theta_{i}$ instead of $\theta_{i+1}$ in (35). ∎

## References

  * [1] P. J. Slater, Essentials of animal behaviour, Cambridge University Press, 1999.
  * [2] O. Cappé, E. Moulines, T. Rydén, Inference in hidden Markov models, Springer Science & Business Media, 2006.
  * [3] M. L. Puterman, Markov decision processes: discrete stochastic dynamic programming, John Wiley & Sons, 2014.
  * [4] G. G. Yin, C. Zhu, Hybrid switching diffusions: properties and applications, Vol. 63, Springer Science & Business Media, 2009.
  * [5] R. E. Kass, L. Tierney, J. B. Kadane, The validity of posterior expansions based on laplace’s method, Bayesian and Likelihood Methods in Statistics and Econometrics. In Essays in Honor of George Bernard (eds S. Geisser, J. S. Hodges, S. J. Press and A. Zellner) (1990) 473–488.
  * [6] R. Wong, Asymptotic Approximations of Integrals, Academic Press, 1989.
  * [7] R. Fernandez, F. Manzo, F. Nardi, E. Scoppola, Asymptotically exponential hitting times and metastability: a pathwise approach without reversibility, Electronic Journal of Probability 20 (2015).
  * [8] O. Bertoncini, J. Barrera, R. Fernández, Cut-off and exit from metastability: two sides of the same coin, Comptes Rendus Mathematique 346 (11-12) (2008) 691–696.
  * [9] E. A. Codling, M. J. Plank, S. Benhamou, Random walk models in biology, Journal of the Royal society interface 5 (25) (2008) 813–834.
  * [10] M. Fific, D. R. Little, R. M. Nosofsky, Logical-rule models of classification response times: a synthesis of mental-architecture, random-walk, and decision-bound approaches., Psychological Review 117 (2) (2010) 309.
  * [11] A. E. Brown, B. De Bivort, Ethology as a physical science, Nature Physics 14 (7) (2018) 653–657.
  * [12] P. ERD&, M. Kac, On certain limit theorems of the theory of probability, Bulletin of the American Mathematical Society 52 (1946) 292–302.