Paper deep dive
Scaling Laws for Majority-based Opinion Dynamics in the Presence of Stubborn Agents
Luke Meredith, Arpan Mukhopadhyay
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 8/13/2026, 3:36:26 AM
Summary
This paper analyzes the opinion dynamics in a multi-agent system where non-stubborn agents update their opinions based on the 2k-choices rule, while a fraction of agents are stubborn and hold fixed opinions. The study identifies three distinct regimes based on the proportions of stubborn agents (gamma_0 and gamma_1): a sub-critical regime with exponential mixing time, a super-critical regime with logarithmic mixing time, and a critical boundary with polynomial mixing time. The steady-state distribution concentrates on the opinion with the higher proportion of stubborn followers.
Entities (6)
Relation Signals (6)
2k-choices rule → usedby → Non-stubborn Agents
confidence 95% · each non-stubborn agent updates its opinion according to the 2k-choices rule
Proportions of Stubborn Agents → determines → Mixing Time Regime
confidence 90% · the time to reach steady-state depends heavily on the values of the parameters gamma_0 and gamma_1
Sub-critical Regime → has → Exponential Mixing Time
confidence 90% · it can take an exponentially long time (in the network size) to reach the steady-state
Super-critical Regime → has → Logarithmic Mixing Time
confidence 90% · the network reaches the steady-state in a time that is only logarithmic in the network size
Stubborn Agents → influences → Steady-State Distribution
confidence 90% · the steady-state distribution of the opinions in the network will be dominated by the opinion with the larger proportion of stubborn followers
Stein's Method → usedtoanalyze → Critical Boundary Behavior
confidence 85% · we show using Stein’s method that the dynamics are driven by a diffusion process which takes polynomial time to mix
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In a multi-agent system, there are often stubborn followers of specific opinions or beliefs. Motivated by this observation, in this paper, we aim to understand how stubborn agents affect the distribution of opinions in a network where both stubborn and non-stubborn agents interact with each other. To do so, we assume that all agents have an opinion in the set $\{0,1\}$ and each non-stubborn agent updates its opinion according to the $2k$\textit{-choices rule}, where the agent samples $2k$ neighbours (including both stubborn and non-stubborn neighbours) uniformly at random and adopts the majority opinion among the sampled group of neighbours and itself. We assume that a proportion of agents, $\gamma_i$, are stubborn followers of opinion $i\in \{0,1\}$. It is natural to expect that the steady-state distribution of the opinions in the network will be dominated by the opinion with the larger proportion of stubborn followers. We show that while this is true, the time to reach steady-state depends heavily on the values of the parameters $\gamma_0$ and $\gamma_1$. When the individual values of these parameters, as well as their difference, are small, it can take an exponentially long time (in the network size) to reach the steady-state. In sharp contrast, when at least one of the parameters $\gamma_0$ and $\gamma_1$ is large, the network reaches the steady-state in a time that is only logarithmic in the network size. Hence, there exists a sharp phase transition in the network dynamics based on the proportions of stubborn agents. We also characterise the behaviour of the system when the parameters $\gamma_0$ and $\gamma_1$ lie on the boundary of the phase transition. In this boundary region, we show using Stein's method that the dynamics are driven by a diffusion process which takes polynomial time to mix.
Tags
Links
- Source: https://arxiv.org/abs/2608.11071v1
- Canonical: https://arxiv.org/abs/2608.11071v1
Trouble viewing inline? Open PDF directly →
Full Text
147,454 characters extracted from source content.
Expand or collapse full text
Scaling Laws for Majority-based Opinion Dynamics in the Presence of Stubborn Agents Luke Meredith Arpan Mukhopadhyay Affiliation: University of Warwick Abstract In a multi-agent system, there are often stubborn followers of specific opinions or beliefs. Motivated by this observation, in this paper, we aim to understand how stubborn agents affect the distribution of opinions in a network where both stubborn and non-stubborn agents interact with each other. To do so, we assume that all agents have an opinion in the set 0,1\0,1\ and each non-stubborn agent updates its opinion according to the 2k2k-choices rule, where the agent samples 2k2k neighbours (including both stubborn and non-stubborn neighbours) uniformly at random and adopts the majority opinion among the sampled group of neighbours and itself. We assume that a proportion of agents, γi _i, are stubborn followers of opinion i∈0,1i∈\0,1\. It is natural to expect that the steady-state distribution of the opinions in the network will be dominated by the opinion with the larger proportion of stubborn followers. We show that while this is true, the time to reach steady-state depends heavily on the values of the parameters γ0 _0 and γ1 _1. When the individual values of these parameters, as well as their difference, are small, it can take an exponentially long time (in the network size) to reach the steady-state. In sharp contrast, when at least one of the parameters γ0 _0 and γ1 _1 is large, the network reaches the steady-state in a time that is only logarithmic in the network size. Hence, there exists a sharp phase transition in the network dynamics based on the proportions of stubborn agents. We also characterise the behaviour of the system when the parameters γ0 _0 and γ1 _1 lie on the boundary of the phase transition. In this boundary region, we show using Stein’s method that the dynamics are driven by a diffusion process which takes polynomial time to mix. 1 Introduction Consensus formation in multi-agent systems is a central topic across statistical physics [6] and computer science [18]. Research in this domain investigates how collective behaviour emerges from simple local interactions, and how factors like noise, bias, faults, and communication constraints shape these dynamics [14, 24]. In this paper, we analyse how stubborn agents [25] or zealots [21], whose opinions remain permanently fixed, affect consensus formation. This is motivated by both social networks, where certain individuals hold immovable beliefs or fixed roles [1], and distributed systems, where stuck-at faults can occur, resulting in some nodes’ states being frozen permanently [13]. Specifically, we consider the 2k2k-choices rule, a generalisation of the 2-choices rule, which is a well-studied distributed consensus protocol [10]. We assume that all agents/nodes initially have opinions in the set 0,1\0,1\. Furthermore, a fraction γi _i of stubborn agents have a fixed opinion i∈0,1i∈\0,1\ at all times. The non-stubborn agents update their opinions according to independent unit-rate Poisson processes with the 2k2k-choices algorithm, where an agent samples 2k2k agents from their neighbourhood uniformly at random (including both stubborn and non-stubborn agents), and then updates their own opinion to the majority opinion among the sampled agents and itself. Unlike in the classical 2k2k-choices dynamics, a consensus state is no longer absorbing for these modified dynamics due to the presence of stubborn agents. It is natural to expect that, at steady-state, the opinion with the larger number of stubborn followers will hold the majority support among non-stubborn agents. We show that while this is true, the time to reach this steady-state can differ significantly, depending on the values of γ0 _0 and γ1 _1. In particular, we identify three distinct regimes for the parameters (γ0,γ1)( _0, _1). In the first regime, referred to as the sub-critical regime, the system exhibits metastability [3] wherein the opinion initially holding the majority support among non-stubborn agents may continue to hold its majority for an exponentially long time (in the network size n) before the opinion with the higher number of stubborn followers starts to dominate. In sharp contrast, in the second regime, referred to as the super-critical regime, the opinion with the higher number of stubborn followers emerges as the majority opinion among non-stubborn agents in only O(logn)O( n) time. Finally, in the critical regime, we show that the initial majority opinion among non-stubborn agents may continue to hold its majority for Θ(np) (n^p) time where p∈1/3,1/2p∈\1/3,1/2\. One of the main challenges in our analysis comes from the fact that the dynamics of the 2k2k-choices rule under stubborn agents lacks the global monotonicity property that ensures that the distance between two independent copies of the process started at two different initial states will always reduce on average. This makes proving mixing time bounds more challenging. Furthermore, obtaining precise rates of convergence at the critical boundary becomes quite challenging due to the presence of degenerate roots in the drift. We overcome this challenge using Stein’s method [4] which allows us to expand the generator of the underlying process and compare the drift and diffusion terms precisely. We also characterise the boundary at which the phase transition occurs. Hence, our contributions are as follows: 1. We characterise the limiting steady-state distribution of the dynamics and show that it concentrates on a point where the opinion with the higher number of stubborn followers becomes the majority opinion. 2. We identify parameter regimes where the system exhibits exponential and logarithmic convergence rates to steady-state. We also analytically characterise the phase transition boundary. 3. At the phase transition boundary, we derive exact convergence rates that are polynomial in the network size. To derive these rates, we use Stein’s framework based on generator expansion. 1.1 Related Literature A foundational model in distributed computing is the voter model [15, 7] where a node simply copies the opinion of another randomly chosen node in its neighbourhood. In this model, the total number of agents holding a specific opinion is a martingale, and hence the consensus probability of an opinion is equal to its initial fraction. Due to its simplicity and duality with coalescing random walks, several variants of the voter model have been studied in the literature including models on lattices and expanders [11, 8], models where agents exhibit bias [23], and models where spontaneous opinion switching/mutation occurs independent of the regular update [14]. In [25], stubborn agents were incorporated into the voter model. The authors show that, in the presence of stubborn agents with opposing opinions, convergence to consensus is not possible. Instead, if the underlying network is connected, the dynamics converge to a stationary distribution. The authors analyse the first two moments of the stationary distribution and characterise its dependence on the network structure and the positions of the stubborn individuals. Also studied is the optimal placement of agents on a graph such that stubborn agents have a maximal effect on the bias of the society toward a specific opinion. A natural extension of the voter model is the 2-choices rule, where instead of simply copying other agents, an agent samples two other agents from their neighbourhood and adopts the majority opinion among sampled agents and itself. This rule was first analysed on complete graphs in [17] and on expander graphs in [10, 9]. Several variants of this rule have been considered in the recent literature. In [2, 12, 22] agents are assumed to exhibit a bias toward a specific opinion. A variant of this rule with competing biases was recently analysed in [5]. A model where agents may occasionally fail to follow the rule was analysed in [20]. Many of these models exhibit rich phase transition properties. However, one fundamental difference between these models and our present work is that the existing models assume that all agents behave in exactly the same way, whereas in our model the agents are inherently heterogeneous due to the presence of stubborn agents with opposing opinions and non-stubborn agents. In [23], the authors introduce stubborn agents into the 2-choices rule. The main focus of this work is the analysis of the mean-field limit of the system and characterisation of the stationary distribution in this limit; no result is provided for finite population sizes. Our work provides a major extension to this by fully analysing the 2k-choices rule with stubborn agents for finite populations. We are able to characterise the stationary distribution for all parameter configurations, identify three distinct parameter regimes, and provide scaling laws for the rate of convergence to stationarity in each regime. 1.2 General Notations We use ℝR and ℕN to denote the set of real and natural numbers, respectively. For x∈ℝx , ⌊x⌋ x and ⌈x⌉ x denote the highest integer not exceeding x and the smallest integer above x, respectively. Similarly, [x]+=max(0,x)[x]_+= (0,x) and [x]−=max(0,−x)[x]_-= (0,-x). For two positive functions f and g defined on positive integers we write f(n)=O(g(n))f(n)=O(g(n)) when lim supn→∞f(n)/g(n)<∞ _n→∞f(n)/g(n)<∞; f(n)=o(g(n))f(n)=o(g(n)) when lim supn→∞f(n)/g(n)=0 _n→∞f(n)/g(n)=0; f(n)=Ω(g(n))f(n)= (g(n)) when g(n)=O(f(n))g(n)=O(f(n)); f(n)=ω(g(n))f(n)=ω(g(n)) when g(n)=o(f(n))g(n)=o(f(n)). 1.3 Organisation The remaining sections of this paper are organised as follows. Section 2 introduces the 2k2k-choices model with stubborn agents and defines some preliminary objects required for our analysis. In Section 3, we state and discuss our main results. In Section 4, we state and prove a central lemma required throughout our analysis. In Sections 5-8, we provide the detailed proofs of the main theorems. Section 9 concludes the paper. 2 Model and Preliminaries We consider a fully connected network of n∈ℕn agents/nodes where each agent has an opinion in the set 0,1\0,1\ at each instant of time. For each opinion i∈0,1i∈\0,1\, we assume that there are Nin=⌈nγi⌉N_i^n= n _i stubborn agents whose opinion remains i at all times, where γ0,γ1∈(0,1) _0, _1∈(0,1) satisfy 0<γ0+γ1<10< _0+ _1<1. The remaining agents are referred to as non-stubborn agents that update their opinions as follows. Each non-stubborn agent updates their opinion according to a unit-rate Poisson process. At each update, the agent samples 2k2k neighbours uniformly at random (with replacement) from its neighbourhood, with k≥1k≥ 1 fixed independently of n. The agent then updates its opinion by adopting the majority opinion among the group of sampled neighbours and itself. The opinion dynamics can be described by the continuous-time process Xn=(Xn(t),t≥0)X^n=(X^n(t),t≥ 0), where Xn(t)X^n(t) denotes the proportion of agents holding opinion 11 at time t≥0t≥ 0. Define bn=n/(n−1)b_n=n/(n-1), the set =[γ1,1−γ0]S=[ _1,1- _0], and the polynomial Pk:→ℝP_k:S as Pk(x)=∑r=k+12k(2kr)xr(1−x)2k−rP_k(x)= _r=k+1^2k 2krx^r (1-x )^2k-r. It is easy to see that the transition rates of the chain XnX^n from state x∈n:=N1n/n,(N1n+1)/n,…,1−N0n/nx ^n:=\N_1^n/n,(N_1^n+1)/n,…,1-N_0^n/n\ to states x±1/nx± 1/n, denoted respectively by q+n(x)q_+^n(x) and q−n(x)q_-^n(x), satisfy q+n(x)=nfkn(x), q^n_+(x)=nf^n_k(x), (1) q−n(x)=ngkn(x), q^n_-(x)=ng^n_k(x), (2) where fkn,gkn:→ℝ+f^n_k,g^n_k:S _+ are given by fkn(x) f^n_k(x) =(1−x−N0n)Pk(bnx), = (1-x- N_0^nn )P_k(b_nx), gkn(x) g^n_k(x) =(x−N1n)Pk(bn(1−x)). = (x- N_1^nn )P_k(b_n(1-x)). Clearly, the process XnX^n is ergodic. Hence, XnX^n has a unique stationary distribution whose probability mass function we denote by πnπ^n. Our interest lies in studying πnπ^n for large n and how quickly (as a function of n) the distribution of XnX^n converges to πnπ^n as this rate of convergence determines whether the network is able to maintain its proximity to the initial distribution of opinions (the law of Xn(0)X^n(0)) for a long time or not. For our analysis, it will be useful to define the drift Δkn:→ℝ ^n_k:S and diffusion coefficient σkn:→ℝ+ _k^n:S _+ as Δkn(x)=fkn(x)−gkn(x), _k^n(x)=f^n_k(x)-g^n_k(x), σkn(x)=fkn(x)+gkn(x), _k^n(x)=f_k^n(x)+g_k^n(x), respectively. The drift Δkn(x) _k^n(x) captures the expected rate at which the proportion of agents holding opinion 11 increases when the current state is x∈nx ^n. Similarly, the diffusion coefficient σkn(x) _k^n(x) captures the normalised jump rate out of a given state x∈nx ^n. To characterise the rate at which a function ϕ:→ℝφ:S changes along the trajectory of the process XnX^n, we will use the generator operator XnG_X^n which, applied to the function ϕφ, takes the form Xnϕ(x) _X^nφ(x) =limh→0[ϕ(Xn(t+h))−ϕ(Xn(t))|Xn(t)=x]h = _h→ 0 E[φ(X^n(t+h))-φ(X^n(t))|X^n(t)=x]h =q+n(x)(ϕ(x+1/n)−ϕ(x))+q−n(x)(ϕ(x−1/n)−ϕ(x)). =q^n_+(x)(φ(x+1/n)-φ(x))+q^n_-(x)(φ(x-1/n)-φ(x)). Thus, when the test function ϕ∈Cl()φ∈ C^l(S) is at least l times continuously differentiable at x∈x , using the Taylor series expansion of ϕφ around x in the above expression we obtain Xnϕ(x)≤Δkn(x)∑i=0⌊(l−2)/2⌋1n2i(2i+1)!ϕ(2i+1)(x)+σkn(x)∑i=1⌊(l−1)/2⌋1n2i−1(2i)!ϕ(2i)(x) _X^nφ(x)≤ _k^n(x) _i=0 (l-2)/2 1n^2i(2i+1)!φ^(2i+1)(x)+ _k^n(x) _i=1 (l-1)/2 1n^2i-1(2i)!φ^(2i)(x) +σkn(x)1nl−1l!ϕmax(l), 10.00002pt+ _k^n(x) 1n^l-1l!φ^(l)_ , (3) where ϕ(i)φ^(i) denotes the ithi th derivative of ϕφ and ϕmax(i)=supx∈|ϕ(i)(x)|φ^(i)_ = _x |φ^(i)(x)| for odd i and ϕmax(i)=supx∈ϕ(i)(x)φ^(i)_ = _x φ^(i)(x) for even i. Also define the limiting drift Δk:→ℝ _k:S and the limiting diffusion coefficient σk:→ℝ+ _k:S _+ as Δk(x)=fk(x)−gk(x) _k(x)=f_k(x)-g_k(x) and σk(x)=fk(x)+gk(x) _k(x)=f_k(x)+g_k(x), where fk(x) f_k(x) =(1−x−γ0)Pk(x), = (1-x- _0 )P_k(x), gk(x) g_k(x) =(x−γ1)Pk(1−x), = (x- _1 )P_k(1-x), are the pointwise limits of fknf_k^n and gkng_k^n, respectively. It is easy to see that there exists a constant C>0C>0 such that |fkn(x)−fk(x)|<C/n,|gkn(x)−gk(x)|<C/n,|Δkn(x)−Δk(x)|<C/n|f_k^n(x)-f_k(x)|<C/n,|g_k^n(x)-g_k(x)|<C/n,| _k^n(x)- _k(x)|<C/n for all x∈x and all sufficiently large n. In the lemma below (whose proof is given in Section A of the Appendix), we characterise some important properties of the limiting drift Δk _k. Lemma 1. The limiting drift Δk _k satisfies the following properties for all k≥1k≥ 1. 1. Δk(γ1)>0>Δk(1−γ0) _k( _1)>0> _k(1- _0) and Δk _k has at least one and at most three real roots (counting multiplicity) in the interval S. 2. Let r1r_1 and r2r_2 denote the smallest and the largest real roots of Δk _k in S, respectively, with the possibility of r1=r2r_1=r_2 when the root is unique. Then, for γ0≠γ1 _0≠ _1 we have (γ1−γ0)(r1+r2−1+γ0−γ1)>0, ( _1- _0)(r_1+r_2-1+ _0- _1)>0, (4) Similarly, for γ0=γ1 _0= _1, we have r1+r2=1r_1+r_2=1 and we always have a root of Δk _k at 1/21/2. Thus, according to the above lemma, depending on the values of the parameters γ0 _0 and γ1 _1, the limiting drift Δk _k can have either one, two or three real roots in the interval S. This is a crucial property that holds for the polynomial Δk _k, of degree 2k+12k+1 for all k≥1k≥ 1, and allows us to partition the parameter space Γ=(γ0,γ1)∈(0,1)2:0<γ0+γ1<1 =\( _0, _1)∈(0,1)^2:0< _0+ _1<1\ of possible values of (γ0,γ1)( _0, _1) into three disjoint sets Γsubk,Γcritk, _sub^k, _crit^k, and Γsupk _sup^k as defined below. Definition 2. The parameter space Γ=(γ0,γ1)∈(0,1)2:0<γ0+γ1<1 =\( _0, _1)∈(0,1)^2:0< _0+ _1<1\ is partitioned into three disjoint sets Γsubk,Γcritk, _sub^k, _crit^k, and Γsupk _sup^k such that for (γ0,γ1)∈Γsupk( _0, _1)∈ _sup^k, the polynomial Δk _k has exactly one real root (with multiplicity one) in S, for (γ0,γ1)∈Γsubk( _0, _1)∈ _sub^k the polynomial Δk _k has exactly three distinct real roots (each with multiplicity one) in the interval S, and for (γ0,γ1)∈Γcritk( _0, _1)∈ _crit^k, the polynomial Δk _k has either one simple root and one double root, or one triple root. Figure 1: Plot of (a) the regions in the (γ0,γ1)( _0, _1) plane for which the function Δk _k (with k=1k=1) has 3 roots (blue) and 1 root (white), and (b) the same plot for different values of k. In both plots, the regions were calculated numerically and red-dashed boundary lines displaying Γcritk _crit^k were plotted using the parametric form in Proposition 3, where the parameter ranges were solved numerically for each value of k. In Figure 1(a) we show these three regions for k=1k=1. We will see later that the dynamics of XnX^n depend crucially on the region in which the parameters (γ0,γ1)( _0, _1) lie. Figure 1(b) shows how the regions change with k. In the proposition below we analytically characterise the region Γcritk _crit^k for any k≥1k≥ 1. The proof of Proposition 3 is given in Appendix B. Proposition 3. The parametric form of the boundary Γcritk _crit^k is (γ0(w),γ1(w)),w∈(wmin,wmax),\( _0(w), _1(w)),w∈(w_ ,w_ )\, where γ1(w)=w−Pk(w)(Pk(w)+Pk(1−w))Pk′(1−w)Pk(w)+Pk′(w)Pk(1−w), _1(w)=w- P_k(w)(P_k(w)+P_k(1-w))P _k(1-w)P_k(w)+P_k (w)P_k(1-w), γ0(w)=γ1(1−w) _0(w)= _1(1-w), wminw_ solves γ0(wmin)=0 _0(w_ )=0, and wmax=1−wminw_ =1-w_ . Here, Pk′P _k denotes differentiation with respect to the argument of PkP_k. Furthermore, we have γ0(1/2)=γ1(1/2)=γk∗ _0(1/2)= _1(1/2)= _k^*, where γk∗=12+14k−22k4k(2k), γ^*_k= 12+ 14k- 2^2k4k 2kk, (5) is the point at which Γcritk _crit^k intersects the line γ0=γ1 _0= _1. 3 Main Results In this section, we state and discuss the main results of the paper. Our first main result characterises the stationary distribution πnπ^n of the proportion of agents with opinion 11 as a function of the proportions γ0 _0 and γ1 _1 of stubborn agents. We use ⇒ to denote weak convergence and δx _x to denote the Dirac measure concentrated at x∈ℝx . Theorem 4. Let r1r_1 and r2r_2 denote the smallest and largest real roots of Δk _k in S, respectively, with the possibility of r1=r2r_1=r_2 in case Δk _k has a unique root in S. Then, we have πn⇒π^n π as n→∞n→∞ where π is given by π=δr2, if γ1>γ0,δr1, if γ1<γ0,12(δr1+δr2), if γ1=γ0.π= cases& _r_2, if _1> _0,\\ & _r_1, if _1< _0,\\ & 12 ( _r_1+ _r_2 ), if _1= _0. cases (6) The above theorem shows that when γ0≠γ1 _0≠ _1, the stationary distribution of opinions tends to concentrate on a point where the majority opinion among the non-stubborn agents is the opinion with the higher proportion of stubborn followers. To see this, note that for γ1>γ0 _1> _0 (resp. γ0>γ1 _0> _1), according to the above theorem, the stationary proportion of nodes with opinion 11 among the entire population concentrates on r2r_2 (resp. r1r_1) and therefore the proportion of nodes with opinion 11 among non-stubborn agents concentrates on (r2−γ1)/(1−γ0−γ1)(r_2- _1)/(1- _0- _1) (resp. (r1−γ1)/(1−γ0−γ1)(r_1- _1)/(1- _0- _1)) which by the second statement of Lemma 1 satisfies (r2−γ1)/(1−γ0−γ1)≥(r1+r2−2γ1)/2(1−γ0−γ1)>1/2(r_2- _1)/(1- _0- _1)≥(r_1+r_2-2 _1)/2(1- _0- _1)>1/2 (resp. (r1−γ1)/(1−γ0−γ1)≤(r1+r2−2γ1)/2(1−γ0−γ1)<1/2(r_1- _1)/(1- _0- _1)≤(r_1+r_2-2 _1)/2(1- _0- _1)<1/2). Hence, at steady-state, the majority of non-stubborn agents follow the opinion which has the higher proportion of stubborn followers. This is natural to expect given that the update rule favours the opinion having the higher number of followers. In contrast, when the proportions of stubborn followers of the two opinions are equal, i.e., γ0=γ1 _0= _1, the stationary distribution is symmetric around 1/21/2 since in this case we have r1=1−r2r_1=1-r_2 (as shown in Lemma 1, meaning that no opinion strictly dominates at the steady-state. The result of Theorem 4 seems to indicate that the long-term behaviour of the non-stubborn agents is determined primarily by the larger stubborn group. However, our next set of results show that the speed at which the distribution of Xn(t)X^n(t) converges to πnπ^n varies drastically depending on the proportions γ0 _0 and γ1 _1 of stubborn agents and, as a result, the non-stubborn agents may (in case of slow convergence to πnπ^n) be able to retain their initial majority opinion for a long period of time before their majority opinion switches to the one with the higher number of stubborn followers. To state our results, for any p∈p and any δ>0δ>0, we denote Bδ(p)=(p−δ,p+δ)B_δ(p)=(p-δ,p+δ) and for any B⊆B we define Texitn(B)=inft≥0:Xn(t)∉BT_exit^n(B)= \t≥ 0:X^n(t)∉ B\ and Tentern(B)=inft≥0:Xn(t)∈BT_enter^n(B)= \t≥ 0:X^n(t)∈ B\ as the first times the chain XnX^n exits and enters the set B, respectively. For p∈p we denote by ℙp(⋅)P_p(·) and p[⋅]E_p[·] the probability and expectation, respectively, conditioned on Xn(0)=⌈np⌉/nX^n(0)= np /n. Furthermore, we define the maximum total variation distance between the distribution of Xn(t)X^n(t) and πnπ^n as dn(t)=maxx∈nmax∈(n)|ℙx(Xn(t)∈)−πn()|d^n(t)= _x ^n _X (S^n)|P_x(X^n(t) )-π^n(X)| where (n)P(S^n) denotes the power set of nS^n. For any ϵ>0ε>0, we define tmixn(ϵ)=inft:dn(t)≤ϵt_mix^n(ε)= \t:d^n(t)≤ε\. Thus, tmixn(ϵ)t_mix^n(ε) denotes the first time the maximum total variation distance between the distribution of Xn(t)X^n(t) and πnπ^n falls below a threshold of ϵε. In particular, for ϵ=1/4ε=1/4, we define tmixn:=tmixn(1/4)t_mix^n:=t_mix^n(1/4). Thus, a higher value of tmixnt_mix^n indicates a slower convergence to the stationary distribution πnπ^n. We say that an event occurs “with high probability” or in short “w.h.p.” when its probability of occurrence converges to one as n→∞n→∞. The next theorem characterises the process XnX^n when (γ0,γ1)∈Γsubk( _0, _1)∈ _sub^k. Theorem 5. Fix (γ0,γ1)∈Γsubk( _0, _1)∈ _sub^k and let r1<rm<r2r_1<r_m<r_2 denote the three distinct real roots (each having a multiplicity of one) of Δk _k in S. Then we have tmixn=Ω(exp(Θ(n)))t_mix^n= ( ( (n))). Furthermore, for any constant p≠rmp≠ r_m and any sufficiently small δ,ϵ>0δ,ε>0, we have ℙp(Tentern(Bδ(r∗))>Clogn/ϵ)≤ϵP_p(T_enter^n(B_δ(r^*))>C n/ε)≤ε for some positive constant C and for all sufficiently large n where r∗=r1(p<rm)+r2(p>rm)r^*=r_11_ (p<r_m )+r_21_ (p>r_m ). For any i∈1,2i∈\1,2\, we also have Texitn(Bδ(ri))=Ω(exp(Θ(n)))T_exit^n(B_δ(r_i))= ( ( (n))) w.h.p. for any starting state Xn(0)∈Bδ/2(ri)X^n(0)∈ B_δ/2(r_i). Figure 2: Plot of the logarithm of the mixing time of the process against n in sub-critical parameter regime (γ0,γ1)∈Γsubk( _0, _1)∈ _sub^k. To compute the mixing time, the transient distribution of Xn(t)X^n(t) was calculated by solving the forward Kolmogorov equation, and the stationary distribution πnπ^n was calculated by solving the detailed balance equations. Discussion on the result: This result demonstrates that when (γ0,γ1)∈Γsubk( _0, _1)∈ _sub^k, the dynamics’ mixing time grows exponentially with n which we numerically validate in Figure 2. Specifically, if the system starts with a proportion p of agents holding opinion 11, the chain Xn(t)X^n(t) rapidly converges in just O(logn)O( n) time to whichever root among r1r_1 and r2r_2 of Δk _k lies on the same side of rmr_m as p. After reaching one of the roots r1r_1 or r2r_2, the chain remains trapped near this root for an exponentially long duration before switching to the other root. Thus, in the sub-critical regime Γsubk _sub^k, the opinion that initially holds the majority among non-stubborn agents may continue to do so for an exponentially long period even if the opposite opinion has a larger proportion of stubborn followers. As shown in Figure 1, the region Γsubk _sub^k corresponds to small values of both γ0 _0 and γ1 _1 and a small difference between them. Intuitively, when stubborn populations are small and balanced, their influence is negligible, leaving the majority rule as the primary driver of the network dynamics. Intuitive explanation using the drift: In Figure 3, we see that the limiting drift Δk _k has three simple roots, r1,rmr_1,r_m, and r2r_2 in S when (γ0,γ1)∈Γsubk( _0, _1)∈ _sub^k. Furthermore, the two extreme roots r1r_1 and r2r_2 are both stable in the sense that for each of these roots there is an interval [a,b][a,b] containing the root such that Δk(x)>0 _k(x)>0 for all x∈[a,r)x∈[a,r) and Δk(x)<0 _k(x)<0 for all x∈(r,b]x∈(r,b]. This implies that the proportion of agents with opinion 11 increases when the process XnX^n is below the stable root and decreases when the process is above the stable root. Hence, the process XnX^n is driven towards the stable root from either side. The middle root rmr_m is unstable in the sense that when the process XnX^n is sufficiently close (but not equal) to rmr_m, the drift takes it further away from this root. We show that this nature of the drift results in the process XnX^n visiting the stable root closest to its current state exponentially many times before crossing the unstable root. Figure 3: Plot of the limiting drift Δk _k for (γ0,γ1)∈Γsubk( _0, _1)∈ _sub^k, with k=1k=1. The red arrows indicate the direction of the drift around the roots. Next, we analyse the process XnX^n when (γ0,γ1)∈Γsupk( _0, _1)∈ _sup^k. Our main result for this regime is the following. Theorem 6. Fix (γ0,γ1)∈Γsupk( _0, _1)∈ _sup^k and let r be the unique simple root of Δk _k in S. Then, for any δ>0δ>0 and any x∈nx ^n, we have x[Tentern(Bδ(r))]=O(logn)E_x[T_enter^n(B_δ(r))]=O( n). Furthermore, the mixing time of the process is tmixn=O(logn)t_mix^n=O( n). Figure 4: Plot of the mixing time of the process against logn n in super-critical parameter regime (γ0,γ1)∈Γsupk( _0, _1)∈ _sup^k. To compute the mixing time numerically, the transient distribution of Xn(t)X^n(t) was calculated by solving the forward Kolmogorov equation, and the stationary distribution πnπ^n was calculated by solving the detailed balance equations. Discussion on the result: The result above shows that when (γ0,γ1)∈Γsupk( _0, _1)∈ _sup^k, the dynamics converge arbitrarily close to the unique root r of Δk _k in S in only O(logn)O( n) time. This is numerically validated in Figure 4. From Theorem 4, r is also the point where the stationary distribution πnπ^n concentrates as n→∞n→∞. Consequently, the mixing time of the dynamics is also O(logn)O( n). This implies that the majority opinion among non-stubborn agents rapidly shifts toward the opinion with the larger number of stubborn followers, regardless of the network’s initial state. Intuitively, as illustrated in Figure 1, at least one of the stubborn proportions (γ0 _0 or γ1 _1) is large in Γsupk _sup^k. This stronger stubborn presence provides enough momentum to swiftly overcome any initial bias in the population. Figure 5: Plot of the limiting drift Δk _k for (γ0,γ1)∈Γsupk( _0, _1)∈ _sup^k, with k=1k=1. The red arrows indicate the direction of the drift around the roots. Intuitive explanation using the drift: In Figure 5, we see that the unique simple root r of Δk _k in S is globally stable in the sense that for all x<rx<r the drift Δk _k is positive, and for all x>rx>r, the drift Δk _k is negative. As a result, the limiting drift geometrically decreases the distance |Xn(t)−r||X^n(t)-r|. This causes the chain to converge to the root r exponentially fast from anywhere in the state-space. We now turn to the regime where (γ0,γ1)∈Γcritk( _0, _1)∈ _crit^k. The analysis of the process XnX^n is most challenging at this critical boundary since at the boundary the drift Δk _k has a root with multiplicity higher than one in S; for (γ0,γ1)∈Γcritk∩γ0=γ1( _0, _1)∈ _crit^k∩\ _0= _1\ there exists a unique root at 1/21/2 with multiplicity three (which follows from the second statement of Lemma 1 and the definition of Γcritk _crit^k) and for (γ0,γ1)∈Γcritk∩γ0≠γ1( _0, _1)∈ _crit^k∩\ _0≠ _1\ there are two distinct roots, one with multiplicity one and the other with multiplicity two (which again follows from the second statement of Lemma 1 and the definition of Γcritk _crit^k). As shown below, the existence of such roots significantly alters the dynamics as compared to the sub- and super-critical regimes. Theorem 7. Fix (γ0,γ1)∈Γcritk( _0, _1)∈ _crit^k. The two possibilities are γ0=γ1 _0= _1 and γ0≠γ1 _0≠ _1. For γ0=γ1 _0= _1, let r be the unique root of Δk _k in S with multiplicity three and for γ0≠γ1 _0≠ _1, let r denote the root of Δk _k in S with multiplicity one. The following statements hold. 1. If γ0≠γ1 _0≠ _1, then, for each sufficiently small δ>0δ>0 and x∈nx ^n, we have x[Tentern(Bδ(r))]=O(n1/3)E_x[T_enter^n(B_δ(r))]=O(n^1/3), and the mixing time of the process XnX^n satisfies tmixn=Θ(n1/3)t_mix^n= (n^1/3). 2. If γ0=γ1 _0= _1, then for any x∈nx ^n, we have x[Tentern(B1/n(r))]=O(n1/2)E_x[T^n_enter(B_1/n(r))]=O(n^1/2) and the mixing time of the process XnX^n satisfies tmixn=Θ(n1/2)t_mix^n= (n^1/2). Figure 6: Plot of the logarithm of the mixing time of the process against logn n in sub-critical parameter regime (γ0,γ1)∈Γcritk( _0, _1)∈ _crit^k. To compute the mixing time numerically, the transient distribution of Xn(t)X^n(t) was calculated by solving the forward Kolmogorov equation, and the stationary distribution πnπ^n was calculated by solving the detailed balance equations. Discussion on the result: The above result shows that when (γ0,γ1)∈Γcritk( _0, _1)∈ _crit^k, unlike the sub- and super-critical regimes, the mixing time of the dynamics grows polynomially with n. This is numerically validated in Figure 6. Thus, the non-stubborn agents may retain the majority of the initially prevalent opinion for a duration that grows polynomially with n. Although this is smaller than the exponential retention window in the sub-critical case, it is still significantly larger than the logarithmic retention window at supercriticality. Figure 7: Plot of the limiting drift Δk _k for (γ0,γ1)∈Γcritk( _0, _1)∈ _crit^k, with k=1k=1. The red arrows indicate the direction of the drift around the roots. Intuitive explanation using the drift and diffusion: In Figure 7, the limiting drift Δk _k is plotted for (γ0,γ1)∈Γcritk∩γ0<γ1( _0, _1)∈ _crit^k∩\ _0< _1\. In this case, there exist two distinct real roots of Δk _k in S of which the higher root r2r_2 has a multiplicity of one and the lower root r1r_1 has a multiplicity of two. We also note that r2r_2 is a stable root since on either side of this root the drift points to the root. However, to reach a neighbourhood of the root r2r_2 from below r1r_1 the process XnX^n needs to cross the degenerate root r1r_1 where the drift becomes zero. Hence, near the degenerate root r1r_1 the drift alone is not sufficient to push the process XnX^n toward r2r_2. Near r1r_1, the process is mainly driven by stochastic fluctuations arising from the diffusion term σk _k. Indeed, choosing ϕ(x)=(x−r1)2φ(x)=(x-r_1)^2 in (3) and observing that Δk(x)≈c(x−r1)2 _k(x)≈ c(x-r_1)^2 for some c>0c>0 near the root r1r_1 which has a multiplicity of two we obtain GXnϕ(x)≈c(x−r1)3+σk(r1)/nG_X^nφ(x)≈ c(x-r_1)^3+ _k(r_1)/n for all x near the root r1r_1. In particular, when |x−r1|≤1/n1/3|x-r_1|≤ 1/n^1/3, the first term (x−r1)3(x-r_1)^3 becomes O(1/n)O(1/n) which is comparable in order to the second term σk(r1)/n _k(r_1)/n. Hence, the rate at which the variance (x−r1)2(x-r_1)^2 increases in the region |x−r1|≤1/n1/3|x-r_1|≤ 1/n^1/3 is O(1/n)O(1/n). Therefore, crossing the region |x−r1|≤1/n1/3|x-r_1|≤ 1/n^1/3 requires at least Ω((1/n1/3)2/(1/n))=Ω(n1/3) ((1/n^1/3)^2/(1/n))= (n^1/3) time on average since ϕφ needs to change by at least Ω((1/n1/3)2) ((1/n^1/3)^2) to cross this region. A similar explanation can be given for the case γ0=γ1 _0= _1 where the drift behaves as Δk(x)≈−c(x−r)3 _k(x)≈-c(x-r)^3 for some c>0c>0 near the unique root r=1/2r=1/2 and therefore to cross a region of width Θ(1/n1/4) (1/n^1/4) around r it takes at least Ω(n1/2) (n^1/2) time on average. 4 A central lemma Before delving into the proofs of our main results, we state and prove a lemma which is central in all our proofs. The lemma holds for any one-dimensional birth-death process XnX^n defined on S whose limiting inifinitesimal drift Δk _k is a polynomial. We emphasize here that the lemma does not require any global monotonicity property of the limiting inifinitesimal drift Δk _k and hence is applicable to non-monotone systems. Lemma 8. Suppose that the polynomial Δk _k has a simple root r∈r that is stable, i.e., there exists an interval (region of attraction) [a,b]⊆[a,b] containing the root such that Δk(x)>0 _k(x)>0 for x∈[a,r)x∈[a,r) and Δk(x)<0 _k(x)<0 for x∈(r,b]x∈(r,b]. Then the following properties hold. 1. There exist constants η,C1>0η,C_1>0 such that for all x∈Bη(r)x∈ B_η(r) we have Δk′(x)<−C1 _k (x)<-C_1. Furthermore, there exists a constant C2>0C_2>0 such that for all x∈[a,b]x∈[a,b], we have Δk(x)(x−r)≤−C2(x−r)2 _k(x)(x-r)≤-C_2(x-r)^2. 2. For any δ>0δ>0 satisfying Bδ(r)⊆[a,b]B_δ(r) [a,b], there exists κδ>0 _δ>0 such that ℙx(Texitn(Bδ(r))≤exp(κδn))≤C4nexp(−κδn/4)P_x(T_exit^n(B_δ(r))≤ ( _δn))≤ C_4n (- _δn/4) for all sufficiently large n and for any x∈Bδ/2(r)x∈ B_δ/2(r) where C4>0C_4>0 is a constant independent of n. 3. For any δ>0,ϵ>0δ>0,ε>0, there exists n0(δ,ϵ)>0n_0(δ,ε)>0 such that whenever n≥n0(δ,ϵ)n≥ n_0(δ,ε) we have x[Tentern(Bδ(r))∧Texitn([a,b])]≤ClognE_x[T^n_enter(B_δ(r)) T^n_exit([a,b])]≤ C n and ℙx(Tentern(Bδ(r))>C′logn/ϵ)≤ϵP_x(T^n_enter(B_δ(r))>C n/ε)≤ε for all initial state x∈[a,b]x∈[a,b] where C and C′C are positive constants independent of n. 4. If XnX^n and X¯n X^n are chains evolved independently until their first meeting time and synchronously thereafter, started at x and x¯ x, respectively, and each following the transition rates (1)-(2), then for any ϵ>0ε>0 and all n sufficiently large, we have ℙx,x¯(Xn(t)≠X¯n(t))≤ϵP_x, x(X^n(t)≠ X^n(t))≤ε whenever t>C3lognϵt> C_3 nε for some positive constant C3C_3 and x,x¯∈Bη(r)x, x∈ B_η(r) for sufficiently small η>0η>0. 4.1 Proof of the first statement Since Δk _k has exactly one real root r with multiplicity one in [a,b][a,b], we must have Δk(x)=(x−r)Rk(x) _k(x)=(x-r)R_k(x) for some polynomial RkR_k such that Rk(r)≠0R_k(r)≠ 0. Furthermore, since we have Δk(x)>0 _k(x)>0 for x∈[a,r)x∈[a,r) and Δk(x)<0 _k(x)<0 for x∈(r,b]x∈(r,b] we must have Rk(x)<0R_k(x)<0 for all y∈[a,b]−ry∈[a,b]-\r\. The continuity of RkR_k at r combined with the fact Rk(r)≠0R_k(r)≠ 0 then implies that we must have Δ′(r)=Rk(r)<0 (r)=R_k(r)<0. Let Δk′(r)=−2C1 _k (r)=-2C_1 where C1>0C_1>0 is some constant. Then, the continuity of Δk′ _k at r implies that there exists η>0η>0 such that for all y∈Bη(r)y∈ B_η(r) we have Δk′(y)<−C1 _k(y)<-C_1. Now, we define the map x↦T(x)x T(x) on the compact set [a,b][a,b] as T(x)=Δk(x)x−r for x≠r,Δk′(x) for x=r.T(x)= cases& _k(x)x-r for x≠ r,\\ & _k (x) for x=r. cases Clearly, T is strictly negative and continuous on the compact set [a,b][a,b]. Hence, there exists C2>0C_2>0 such that T(x)≤−C2T(x)≤-C_2 for all x∈[a,b]x∈[a,b]. Hence, we have Δk(x)≤−C2(x−r) _k(x)≤-C_2(x-r) for all x∈(r,b]x∈(r,b] and Δk(x)≥C2(r−x) _k(x)≥ C_2(r-x) for x∈[a,r)x∈[a,r). This completes the proof of the first statement. 4.2 Proof of the second statement Consider the Lyapunov function ϕθn(x)=exp(nθ2(x−r)2)φ^n_θ(x)= (n θ2(x-r)^2 ) for θ∈(0,θ¯)θ∈(0, θ). It is easy to see that ϕθn(x±1n)=ϕθn(x)exp(±θ(x−r)+θ2n).φ^n_θ (x± 1n )=φ^n_θ(x) (±θ(x-r)+ θ2n ). Hence, applying the generator XnG_X^n to ϕθnφ^n_θ we obtain GXnϕθn(x) G_X^nφ^n_θ(x) =nfkn(x)ϕθn(x)(exp(θ(x−r)+θ2n)−1) =nf_k^n(x)φ^n_θ(x) ( (θ(x-r)+ θ2n )-1 ) +ngkn(x)ϕθn(x)(exp(−θ(x−r)+θ2n)−1). 20.00003pt+ng_k^n(x)φ^n_θ(x) ( (-θ(x-r)+ θ2n )-1 ). Now, using the fact that exp(z)≤1+z+CMz2 (z)≤ 1+z+C_Mz^2 for some CM>0C_M>0 for all z∈[−M,M]z∈[-M,M] and the definitions of Δkn _k^n and σkn _k^n we obtain for all sufficiently large n GXnϕθn(x)≤nϕθn(x)(Δkn(x)θ(x−r)+θ2nσkn(x)+Cθ¯,δθ2), G_X^nφ^n_θ(x)≤ nφ^n_θ(x) ( _k^n(x)θ(x-r)+ θ2n _k^n(x)+C_ θ,δθ^2 ), (7) for some constant Cθ¯,δ>0C_ θ,δ>0 since θ|x−r|+θ/2n≤2¯θδθ|x-r|+θ/2n≤ 2θδ for x∈Bδ(r)x∈ B_δ(r) and n sufficiently large. But from the first part of the lemma and the fact that |Δkn(x)−Δk(x)|<Cn| _k^n(x)- _k(x)|< Cn we can bound the first term in the parenthesis on the RHS as Δkn(x)(x−r)≤Δk(x)(x−r)+Cn(x−r)≤−C2(x−r)2+Cn(x−r)≤−C22(x−r)2 _k^n(x)(x-r)≤ _k(x)(x-r)+ Cn(x-r)≤-C_2(x-r)^2+ Cn(x-r)≤- C_22(x-r)^2 where to obtain the last inequality we assume |x−r|≥η|x-r|≥η for some η∈(0,δ/2)η∈(0,δ/2) and choose n>2CηC2n> 2Cη C_2. Similarly, since σkn _k^n converges uniformly to σk _k and σmin<σk(x)<σmax _ < _k(x)< _ for all x∈x for some σmin,σmax>0 _ , _ >0 it follows that for all sufficiently large n we have σmin<σkn(x)<σmax _ < _k^n(x)< _ . Hence, from (7) we obtain GXnϕθn(x)≤nϕθn(x)(−C2θ2(x−r)2+θ2nσmax+Cθ¯,δθ2). G_X^nφ^n_θ(x)≤ nφ^n_θ(x) (- C_2θ2(x-r)^2+ θ2n _ +C_ θ,δθ^2 ). Hence, for |x−r|≥η|x-r|≥η we obtain GXnϕθn(x)≤nϕθn(x)(−C2θ2η2+θ2nσmax+Cθ¯,δθ2). G_X^nφ^n_θ(x)≤ nφ^n_θ(x) (- C_2θ2η^2+ θ2n _ +C_ θ,δθ^2 ). Now choosing n>2σmaxC2η2n> 2 _ C_2η^2 and θ<C2η24Cθ¯,δθ< C_2η^24C_ θ,δ we obtain GXnϕθn(x)≤nϕθn(x)(−C2θ4η2+Cθ¯,δθ2)<0.G_X^nφ^n_θ(x)≤ nφ^n_θ(x) (- C_2θ4η^2+C_ θ,δθ^2 )<0. Thus, for suitable choice of θ∈(0,θ¯∧C2η24Cθ¯,δ)θ∈ (0, θ C_2η^24C_ θ,δ ), we have GXnϕθn(x)≤0G_X^nφ^n_θ(x)≤ 0 for all x∈Bδ(r)−Bη(r)x∈ B_δ(r)-B_η(r) and all sufficiently large n. This implies that (ϕθn(Xn(t∧Tentern(Bη(r))∧Texitn(Bδ(r)))),t≥0)(φ^n_θ(X^n(t T^n_enter(B_η(r)) T^n_exit(B_δ(r)))),t≥ 0) is a super-martingale. Therefore, applying the optional sampling theorem we obtain x[ϕθn(Xn(Tentern(Bη(r))∧Texitn(Bδ(r))))]≤ϕθn(x)≤exp(nθδ28),E_x [φ^n_θ(X^n(T^n_enter(B_η(r)) T^n_exit(B_δ(r)))) ]≤φ^n_θ(x)≤ (n θδ^28 ), for any starting state x∈Bδ/2(r)x∈ B_δ/2(r). But x[ϕθn(Xn(Tentern(Bη(r))∧Texitn(Bδ(r))))]≥exp(nθδ22)ℙx(Texitn(Bδ(r))≤Tentern(Bη(r))).E_x [φ^n_θ(X^n(T^n_enter(B_η(r)) T^n_exit(B_δ(r)))) ]≥ (n θδ^22 )P_x (T^n_exit(B_δ(r))≤ T^n_enter(B_η(r)) ). Hence, we have ℙx(Texitn(Bδ(r))≤Tentern(Bη(r)))≤exp(−nκδ),∀x∈Bδ/2(r)−Bη(r),P_x (T^n_exit(B_δ(r))≤ T^n_enter(B_η(r)) )≤ (-n _δ ), ∀ x∈ B_δ/2(r)-B_η(r), where κδ=3θδ28 _δ= 3θδ^28. Hence, if N denotes the number of times the chain enters the set Bη(r)B_η(r) before exiting Bδ(r)B_δ(r) starting from x∈Bδ/2(r)x∈ B_δ/2(r), then ℙx(N≤m)=1−ℙx(N>m)≤1−(1−exp(−κδn))m+1≤(m+1)exp(−κδn)P_x(N≤ m)=1-P_x(N>m)≤ 1-(1- (- _δn))^m+1≤(m+1) (- _δn). Let J(t)J(t) denote the number of times the process Xn(t)X^n(t) jumps by time t. Since the total jump rate is bounded above by nσmaxn _ , we have x[J(t)]≤nσmaxtE_x[J(t)]≤ n _ t. Now since for any m∈ℕm , we have Texitn(Bδ(r))≤t⊆N≤J(t)⊆N≤m∪J(t)≥m\T^n_exit(B_δ(r))≤ t\ \N≤ J(t)\ \N≤ m\∪\J(t)≥ m\ it follows that ℙx(Texitn(Bδ(r))≤t)≤ℙx(N≤m)+ℙx(J(t)≥m)≤(m+1)exp(−κδn)+x[J(t)]/m≤(m+1)exp(−κδn)+nσmaxt/mP_x(T^n_exit(B_δ(r))≤ t) _x(N≤ m)+P_x(J(t)≥ m)≤(m+1) (- _δn)+E_x[J(t)]/m≤(m+1) (- _δn)+n _ t/m. Now choosing t=exp(κδn4)t= ( _δn4) and m=⌈exp(κδn/2)⌉m= ( _δn/2) gives ℙx(Texitn(Bδ(r))≤exp(κδn4))≤nσmaxexp(−κδn4)+2exp(−κδn)+exp(−κδn2),P_x (T^n_exit(B_δ(r))≤ ( _δn4 ) )≤ n _ (- _δn4 )+2 (- _δn)+ (- _δn2 ), (8) from which the second statement follows. 4.3 Proof of the third statement We consider the drift of the Lyapunov function ϕ:→ℝφ:S defined as ϕ(x)=log(1+n(x−r)2)φ(x)= (1+n(x-r)^2). Clearly, we have for |x−r|≥δ|x-r|≥δ ϕ′(x) φ (x) =2n(x−r)1+n(x−r)2 = 2n(x-r)1+n(x-r)^2 ϕ′(x) φ (x) =2n(1−n(x−r)2)(1+n(x−r)2)2≤2n(1+n(x−r)2)≤2n1+nδ2≤2δ2. = 2n(1-n(x-r)^2)(1+n(x-r)^2)^2≤ 2n(1+n(x-r)^2)≤ 2n1+nδ^2≤ 2δ^2. Hence, applying the generator GXnG_X^n on ϕφ and using the above bound we have for x∈[a,b]−Bδ(r)x∈[a,b]-B_δ(r) GXnϕ(x) G_X^nφ(x) ≤Δkn(x)2n(x−r)1+n(x−r)2+σkn(x)2n2δ2 ≤ _k^n(x) 2n(x-r)1+n(x-r)^2+ _k^n(x)2n 2δ^2 ≤Δk(x)2n(x−r)1+n(x−r)2+2C(x−r)1+n(x−r)2+σmaxnδ2 ≤ _k(x) 2n(x-r)1+n(x-r)^2+ 2C(x-r)1+n(x-r)^2+ _ nδ^2 ≤(a)−2nC2(x−r)21+n(x−r)2+2C|x−r|1+n(x−r)2+σmaxnδ2 (a)≤- 2nC_2(x-r)^21+n(x-r)^2+ 2C|x-r|1+n(x-r)^2+ _ nδ^2 ≤(b)−2nC2(x−r)22n(x−r)2+2C|x−r|n(x−r)2+σmaxnδ2 (b)≤- 2nC_2(x-r)^22n(x-r)^2+ 2C|x-r|n(x-r)^2+ _ nδ^2 ≤−C2+2Cnδ+σmaxnδ2 ≤-C_2+ 2Cnδ+ _ nδ^2 ≤−C22, ≤- C_22, (9) where (a) follows from the first statement of the lemma, (b) follows by choosing n≥1/δ2n≥ 1/δ^2 so that n(x−r)2≥nδ2≥1n(x-r)^2≥ nδ^2≥ 1, and the last line again follows by choosing n sufficiently large. Hence, defining τ=Tentern(Bδ(r))∧Texitn([a,b])τ=T^n_enter(B_δ(r)) T^n_exit([a,b]) and applying Dynkin’s formula [16] we obtain for any t≥0t≥ 0 x[ϕ(Xn(t∧τ))] _x[φ(X^n(t τ))] =x[ϕ(Xn(0))]+x[∫0t∧τXnϕ(Xn(s))s] =E_x[φ(X^n(0))]+E_x [ _0^t τG_X^nφ(X^n(s))ds ] ≤log(1+n(b−a)2)−C2x[t∧τ]2, ≤ (1+n(b-a)^2)- C_2E_x[t τ]2, where in the last inequality we have used ϕ(x)≤log(1+n(b−a)2)φ(x)≤ (1+n(b-a)^2) for any x∈[a,b]x∈[a,b] and (9). Now, using x[ϕ(Xn(t∧τ))]≥0E_x[φ(X^n(t τ))]≥ 0 we obtain x[t∧τ]≤(2/C2)log(1+n(b−a)2)E_x[t τ]≤(2/C_2) (1+n(b-a)^2). Since this is true for all t≥0t≥ 0, using dominated convergence theorem it follows that x[τ]≤(2/C2)log(1+n(b−a)2)≤C′lognE_x[τ]≤(2/C_2) (1+n(b-a)^2)≤ C n for some C′>0C >0 and all sufficiently large n which proves the expectation bound in the statement. To complete the proof we note that using Markov inequality gives ℙx(τ≥C′logn/ϵ)≤ϵP_x(τ≥ C n/ε)≤ε. But we have ℙx(τ≥t) _x(τ≥ t) =ℙx(Tentern(Bδ(r))≥t,Texitn([a,b])≥t) =P_x(T^n_enter(B_δ(r))≥ t,T^n_exit([a,b])≥ t) ≥ℙx(Tentern(Bδ(r))≥t)−ℙx(Texitn([a,b])<t). _x(T^n_enter(B_δ(r))≥ t)-P_x(T^n_exit([a,b])<t). Now choosing t=C′logn/ϵt=C n/ε and using the previous part of the lemma we obtain ℙx(τ≥C′logn/ϵ)≤ℙx(Tentern(Bδ(r))≥C′logn/ϵ)−o(1)P_x(τ≥ C n/ε) _x(T^n_enter(B_δ(r))≥ C n/ε)-o(1). Thus, ℙx(Tentern(Bδ(r))≥C′logn/ϵ)≤ϵ+o(1)P_x(T^n_enter(B_δ(r))≥ C n/ε)≤ε+o(1) from which the statement of the lemma follows immediately. 4.4 Proof of the last statement Consider the joint chain (Xn,X¯n)(X^n, X^n) and assume without loss of generality that Xn(0)=x≤x¯=X¯n(0)X^n(0)=x≤ x= X^n(0). Furthermore, assume that both x and x¯ x are in Bη(r)B_η(r) where η>0η>0 is such that Δk′(x)<−C2 _k (x)<-C_2 for all x∈B2η(r)x∈ B_2η(r). Note that the existence of such η is guaranteed by the first part of the lemma. Now, since (Δkn)′( _k^n) uniformly converges to Δk′ _k and Δk′(x)<−C2 _k (x)<-C_2 for all x∈Bη(r)x∈ B_η(r), there exists n0(C2)n_0(C_2) such that we have (Δkn)′(x)<−C2/2( _k^n) (x)<-C_2/2 for all n≥n0(C2)n≥ n_0(C_2) and all x∈Bη(r)x∈ B_η(r). Hence, for all n≥n0(C2)n≥ n_0(C_2) and x,x¯∈Bη(r)x, x∈ B_η(r) with x¯≥x x≥ x we have Δkn(x¯)−Δkn(x)=∫x¯(Δkn)′(u)u≤−C22(x¯−x). _k^n ( x )- _k^n (x )= _x x( _k^n) (u)du≤- C_22 ( x-x ). (10) Now, define the Lyapunov function ϕ:2→ℝφ:S^2 as ϕ(x,x¯)=log(1+n|x¯−x|)φ(x, x)= (1+n| x-x|). If GXn,X¯nG_X^n, X^n denote the generator of the joint chain, then, due to the independence of the two chains XnX^n and X¯n X^n, we have Xn,X¯nϕ(x,x¯) _X^n, X^nφ(x, x) =X¯nϕ(x,x¯)+Xnϕ(x,x¯) =G_ X^nφ(x, x)+G_X^nφ(x, x) ≤Δkn(x¯)∂x¯ϕ(x,x¯)+σkn(x¯)2nsup(x,x¯)∈2∂x¯2ϕ(x,x¯) ≤ _k^n( x) _ xφ(x, x)+ _k^n( x)2n _(x, x) ^2 _ x^2φ(x, x) +Δkn(x)∂xϕ(x,x¯)+σkn(x)2nsup(x,x¯)∈2∂x2ϕ(x,x¯), 20.00003pt+ _k^n(x) _xφ(x, x)+ _k^n(x)2n _(x, x) ^2 _x^2φ(x, x), where ∂zi _z^i denotes the ithi th partial derivative w.r.t z. It is easy to see that for all x¯≥x x≥ x we have ∂x¯ϕ(x,x¯)=n1+n(x¯−x)=−∂xϕ(x,x¯), _ xφ(x, x)= n1+n( x-x)=- _xφ(x, x), ∂x¯2ϕ(x,x¯)=−n2(1+n(x¯−x))2=∂x2ϕ(x,x¯)<0, _ x^2φ(x, x)=- n^2(1+n( x-x))^2= _x^2φ(x, x)<0, Hence, for all x,x¯x, x satisfying x¯−x≥1/n x-x≥ 1/n we have XnX¯nϕ(x,x¯)≤n1+n(x¯−x)(Δkn(x¯)−Δkn(x))≤−nC2(x¯−x)2(1+n(x¯−x))≤−C24, _X^n X^nφ(x, x)≤ n1+n( x-x)( _k^n( x)- _k^n(x))≤- nC_2( x-x)2(1+n( x-x))≤- C_24, where in the second inequality we use (10) and in the last inequality we use the fact x¯−x≥1/n x-x≥ 1/n. We define Tcouplen=inft≥0:Xn(t)=X¯n(t)T_couple^n= \t≥ 0:X^n(t)= X^n(t)\, Texit,ηn=inft≥0:Xn(t)∉B2η(r) or X¯n(t)∉B2η(r)T_exit,η^n= \t≥ 0:X^n(t)∉ B_2η(r) or X^n(t)∉ B_2η(r)\, and τ=Tcouplen∧Texit,ητ=T_couple^n T_exit,η. Then applying Dynkin’s formula as in the previous part of the lemma we obtain x,x¯[τ]≤4log(1+n(x¯−x))C2≤4log(1+2nη)C2≤C3logn,E_x, x[τ]≤ 4 (1+n( x-x))C_2≤ 4 (1+2nη)C_2≤ C_3 n, for all (x,x¯)∈Bη(r)×Bη(r)(x, x)∈ B_η(r)× B_η(r) with x¯>x x>x for all sufficiently large n. Now, using the above and the same line of arguments as in the proof of the previous part it can be shown that ℙx,x¯(Tcouplen≥C′logn/ϵ)≤2ϵP_x, x(T_couple^n≥ C n/ε)≤ 2ε for any ϵ>0ε>0 and all sufficiently large n. This completes the proof of the lemma. 5 Proof of Theorem 4 Since XnX^n is a birth-death process, for any x∈[γ1,1−γ0]x∈[ _1,1- _0] we have πn(⌊nx⌋n) π^n ( nx n ) =1Zn∏j=N1n⌊nx⌋−1q+n(j/n)q−n((j+1)/n) = 1Z^n _j=N_1^n nx -1 q_+^n(j/n)q_-^n((j+1)/n) =1Zn∏j=N1n⌊nx⌋−1fkn(j/n)gkn((j+1)/n) = 1Z^n _j=N_1^n nx -1 f_k^n(j/n)g_k^n((j+1)/n) =1Znexp(∑j=N1n⌊nx⌋−1logfkn(j/n)gkn((j+1)/n)), = 1Z^n ( _j=N_1^n nx -1 f_k^n(j/n)g_k^n((j+1)/n) ), =1Znexp(n∫γ1xlog(hk(z))z+O(logn)), = 1Z^n (n _ _1^x (h_k(z))dz+O( n) ), where ZnZ^n is a normalising constant and hk=fk/gkh_k=f_k/g_k. Hence, we have πn([γ1,x])=∑N1n≤a≤⌊nx⌋exp(n∫γ1a/nlog(hk(z))z+O(logn))∑N1n≤a≤n−N0nexp(n∫γ1a/nlog(hk(z))z+O(logn)). π^n([ _1,x])= _N_1^n≤ a≤ nx (n _ _1^a/n (h_k(z))dz+O( n) ) _N_1^n≤ a≤ n-N_0^n (n _ _1^a/n (h_k(z))dz+O( n) ). From the above, it follows that if y↦∫γ1ylog(hk(z))zy _ _1^y (h_k(z))dz is maximised uniquely at y∗∈[γ1,1−γ0]y^*∈[ _1,1- _0], then πn([γ1,x])→0π^n([ _1,x])→ 0 for all x<y∗x<y^* and πn([γ1,x])→1π^n([ _1,x])→ 1 for all x>y∗x>y^* implying that πn⇒δy∗π^n _y^*. Similarly, if the maximiser is not unique and the integral ∫γ1ylog(hk(z))z _ _1^y (h_k(z))dz is maximised at m discrete values of y given by y1∗,y2∗,…,ym∗\y_1^*,y_2^*,…,y_m^*\, then we have πn⇒1m∑j=1mδyj∗π^n 1m _j=1^m _y_j^*. Hence, to establish the theorem it is sufficient to prove the following statements. 1. For γ0=γ1 _0= _1, the integral ∫γ1ylog(hk(z))z _ _1^y (h_k(z))dz is maximised both at y=r1y=r_1 and y=r2y=r_2 where r1r_1 and r2r_2 are the minimum and the maximum root of Δk _k in the interval [γ1,1−γ0][ _1,1- _0]. 2. For γ0<γ1 _0< _1, the integral ∫γ1ylog(hk(z))z _ _1^y (h_k(z))dz is maximised at y=r2y=r_2. 3. For γ0>γ1 _0> _1, the integral ∫γ1ylog(hk(z))z _ _1^y (h_k(z))dz is maximised at y=r1y=r_1. Below we prove each of the above statements in the order they appear above. When γ0=γ1 _0= _1, we have hk(z)=1/hk(1−z)h_k(z)=1/h_k(1-z) and Lemma 1 implies r2=1−r1r_2=1-r_1. Hence, ∫r1r2log(hk(z))z=∫r11/2log(hk(z))z+∫1/21−r1log(hk(z))z=∫r11/2log(hk(z))z−∫1/2r1log(hk(1−u))u=0 _r_1^r_2 (h_k(z))dz= _r_1^1/2 (h_k(z))dz+ _1/2^1-r_1 (h_k(z))dz= _r_1^1/2 (h_k(z))dz- _1/2^r_1 (h_k(1-u))du=0. Furthermore, by Lemma 1 we have Δk(z)>0 _k(z)>0 when z<r1z<r_1 and Δk(z)<0 _k(z)<0 for z>r2z>r_2. But since loghk(z) h_k(z) and Δk(z) _k(z) have the same sign for all z≠r1,r2z≠ r_1,r_2, it follows that the integral ∫γ1ylog(hk(z))z _ _1^y (h_k(z))dz is maximised at both y=r1y=r_1 and y=r2y=r_2. This proves the second statement. When γ0<γ1 _0< _1, we show that ∫r1r2log(hk(z))z>0 _r_1^r_2 (h_k(z))dz>0. This will then establish the third statement following similar line of arguments as used in the proof of the previous statement. We define I(γ0,γ1)=∫r1r2log(hk(z))zI( _0, _1)= _r_1^r_2 (h_k(z))dz. We study the function I(γ0,γ1)I( _0, _1) by varying γ1 _1 while keeping γ0 _0 constant. We note that when γ1=γ0 _1= _0, we have already shown that I(γ0,γ0)=0I( _0, _0)=0. Now, from the definition of hkh_k, we have ∂γ1I(γ0,γ1) ∂ _1I( _0, _1) =−∫r1r2∂γ1log((y−γ1)I1−y(k+1,k))dy =- _r_1^r_2 ∂ _1 ((y- _1)I_1-y(k+1,k))dy −log(hk(r2))∂r2∂γ1+log(hk(r1))∂r1∂γ1 56.9055pt- (h_k(r_2)) ∂ r_2∂ _1+ (h_k(r_1)) ∂ r_1∂ _1 =∫r1r21y−γ1y = _r_1^r_2 1y- _1dy =log(y−γ1)]r1r2 = (y- _1 ) ]_r_1^r_2 =log(r2−γ1r1−γ1)>0, = ( r_2- _1r_1- _1 )>0, where the second line follows since loghk(r1)=loghk(r2)=0 h_k(r_1)= h_k(r_2)=0. Hence, I(γ0,γ1)I( _0, _1) is strictly increasing with respect to γ1 _1. Combined with the fact that I(γ0,γ0)=0I( _0, _0)=0, it shows that I(γ0,γ1)>0I( _0, _1)>0 for γ1>γ0 _1> _0. The last statement follows using similar line of arguments as above by establishing ∫r1r2log(hk(z))z<0 _r_1^r_2 (h_k(z))dz<0 when γ0>γ1 _0> _1. ∎ 6 Proof of Theorem 5 By the first statement of Lemma 1 and the definitions of r1,r2r_1,r_2 it follows that both r1r_1 and r2r_2 are simple and stable roots of Δk _k. It also follows from Lemma 1 that for all sufficiently small ξ>0ξ>0 the intervals [γ1,rm−ξ][ _1,r_m-ξ] and [rm+ξ,1−γ0][r_m+ξ,1- _0] are regions of attraction of r1r_1 and r2r_2, respectively. Now, for any constant p≠rmp≠ r_m there exists ξ>0ξ>0 such that p lies either in [γ1,rm−ξ][ _1,r_m-ξ] which corresponds to the region of attraction of r1r_1 or it lies in [rm+ξ,1−γ0][r_m+ξ,1- _0] which corresponds to the region of attraction of r2r_2. Therefore, by the third statement of the Lemma 8 it follows that ℙp(Tentern(Bδ(r∗))>Clogn/ϵ)≤ϵP_p(T_enter^n(B_δ(r^*))>C n/ε)≤ε for some positive constant C and for all sufficiently large n where r∗=r1(p<rm)+r2(p>rm)r^*=r_11_ (p<r_m )+r_21_ (p>r_m ). Now since rir_i is a stable root for each i∈1,2i∈\1,2\, by the second statement of Lemma 8 it follows that ℙx(Texitn(Bδ(ri))≤exp(κδn))=o(1)P_x(T_exit^n(B_δ(r_i))≤ ( _δn))=o(1) for any x∈Bδ/2(ri)x∈ B_δ/2(r_i). This shows that Texitn(Bδ(ri))=Ω(exp(Θ(n)))T_exit^n(B_δ(r_i))= ( ( (n))) w.h.p. for any starting state Xn(0)∈Bδ/2(ri)X^n(0)∈ B_δ/2(r_i). To establish the mixing time bound, we observe that Theorem 4 implies that for some i∈1,2i∈\1,2\ we have πn(Bδ(ri))≥1/3π^n(B_δ(r_i))≥ 1/3 for all sufficiently large n and for all sufficiently small δ>0δ>0. But from the definition of maximum total variation distance it follows that dn(t)≥πn(Bδ(ri))−ℙx(Xn(t)∈Bδ(ri))≥1/3−ℙx(Tentern(Bδ(ri))≤t)d^n(t)≥π^n(B_δ(r_i))-P_x(X^n(t)∈ B_δ(r_i))≥ 1/3-P_x(T^n_enter(B_δ(r_i))≤ t). Now, if r−ir_-i is the only element of the set r1,r2−ri\r_1,r_2\-\r_i\ then for x∈Bδ/2(r−i)x∈ B_δ/2(r_-i) and sufficiently small δ from the second statement of Lemma 8 we have ℙx(Tentern(Bδ(ri))≤exp(κδn))≤ℙx(Texitn(Bδ(r−i))≤exp(κδn))=o(1)P_x(T^n_enter(B_δ(r_i))≤ ( _δn)) _x(T^n_exit(B_δ(r_-i))≤ ( _δn))=o(1). Hence, dn(exp(κδn))≥1/3−o(1)≥1/4d^n( ( _δn))≥ 1/3-o(1)≥ 1/4 which implies that tmixn=Ω(exp(Θ(n)))t_mix^n= ( ( (n))). This completes the proof of the theorem.∎ 7 Proof of Theorem 6 From the first statement of Lemma 1 it follows that r is a stable root and the whole interval S is the region of attraction of r. Hence, from the third statement of Lemma 8, it follows that for any x∈nx ^n we have x[Tentern(Bδ(r))]=x[Tentern(Bδ(r))∧Texitn()]≤Clogn.E_x[T^n_enter(B_δ(r))]=E_x[T^n_enter(B_δ(r)) T^n_exit(S)]≤ C n. We now prove the mixing time upper bound. Let η>0η>0 be as in the last statement of Lemma 8, and let δ′∈(0,η)δ ∈(0,η). Consider two chains XnX^n and X¯n X^n initialised at x,x¯∈nx, x ^n, respectively, and evolving independently until they first meet after which they move together. Let Tcouplen:=inft≥0:Xn(t)=X¯n(t)T_couple^n:= \t≥ 0:X^n(t)= X^n(t)\ be the first meeting time of the chains. Using the coupling lemma for Markov chain mixing [19], we have dn(t)≤maxx,x¯ℙx,x¯(Xn(t)≠X¯n(t))=maxx,x¯ℙx,x¯(Tcouplen>t).d^n(t)≤ _x, xP_x, x(X^n(t)≠ X^n(t))= _x, xP_x, x(T_couple^n>t). Thus, to establish the lemma it is sufficient to show that for every ϵ>0ε>0 there exists a constant C≡C(ϵ)>0C≡ C(ε)>0 such that ℙx,x¯(Tcouple>Clogn)<ϵP_x, x(T_couple>C n)<ε for all starting states x,x¯∈nx, x ^n. Similar to the chain XnX^n we denote the first entry time to and first exit from set B⊆B of the chain X¯n X^n as T¯entern(B) T^n_enter(B) and T¯exitn(B) T^n_exit(B), respectively. Define the event G(t):=Xn(t/2)∈Bδ′(r),X¯n(t/2)∈Bδ′(r)G(t):=\X^n(t/2)∈ B_δ (r), X^n(t/2)∈ B_δ (r)\. Then the complement G(t)cG(t)^c satisfies G(t)c⊆Tentern(Bδ′(r))>t/2∪T¯entern(Bδ′(r))>t/2∪Tentern(Bδ′(r))≤t/2,Xn(t/2)∉Bδ′(r)∪T¯entern(Bδ′(r))≤t/2,X¯n(t/2)∉Bδ′(r)G(t)^c \T^n_enter(B_δ (r))>t/2\∪\ T^n_enter(B_δ (r))>t/2\∪\T_enter^n(B_δ (r))≤ t/2,X^n(t/2)∉ B_δ (r)\∪\ T_enter^n(B_δ (r))≤ t/2, X^n(t/2)∉ B_δ (r)\. Now, for t=2C′logn/ϵt=2C n/ε it follows from the third statement of Lemma 8 that for any x,x¯∈x, x both ℙx(Tentern(Bδ′(r))>t/2)P_x(T^n_enter(B_δ (r))>t/2) and ℙx(T¯entern(Bδ′(r))>t/2)P_x( T^n_enter(B_δ (r))>t/2) are bounded above by ϵε. To bound the probability of the event Tentern(Bδ′(r))≤t/2,Xn(t/2)∉Bδ′(r)\T_enter^n(B_δ (r))≤ t/2,X^n(t/2)∉ B_δ (r)\ we observe that ℙx(Tentern(Bδ′(r))≤t/2,Xn(t/2)∉Bδ′(r)) _x (T_enter^n(B_δ (r))≤ t/2,X^n(t/2)∉ B_δ (r) ) ≤ℙx(Tentern(Bδ′(r))≤t/2,Xn(t/2)∉Bδ′(r),Tentern(Bδ′/2(r))≤t/2)+ℙx(Tentern(Bδ′/2(r))>t/2) _x (T_enter^n(B_δ (r))≤ t/2,X^n(t/2)∉ B_δ (r),T_enter^n(B_δ /2(r))≤ t/2 )+P_x (T_enter^n(B_δ /2(r))>t/2 ) ≤supy∈Bδ′/2(r)ℙy(Texitn(Bδ′(r))≤t/2)⏟(a)+ℙx(Tentern(Bδ′/2(r))>t/2)⏟(b). ≤ _y∈ B_δ /2(r)P_y (T^n_exit(B_δ (r))≤ t/2 )_(a)+ P_x (T_enter^n(B_δ /2(r))>t/2 )_(b). Using the second statement of Lemma 8, we can bound term (a) as follows. OPENℙy(Texitn(Bδ′(r))≤t/2)) _y (T^n_exit(B_δ (r))≤ t/2 )) =ℙy(Texitn(Bδ′(r))≤C′logn/ϵ) =P_y (T^n_exit(B_δ (r))≤ C n/ε ) ≤ℙy(Texitn(Bδ′(r))≤exp(κδn4)) _y (T^n_exit(B_δ (r))≤ ( _δn4 ) ) ≤(a)nσmaxexp(−κδn4)+2exp(−κδn)+exp(−κδn2), (a)≤n _ (- _δn4 )+2 (- _δn)+ (- _δn2 ), where (a) follows from (8). Since this bound does not depend on y, for all sufficiently large n we have supy∈Bδ′(r)ℙy(Texitn(Bδ′(r))≤t/2)≤ϵ _y∈ B_δ (r)P_y (T^n_exit(B_δ (r))≤ t/2 )≤ε. We use the third statement of Lemma 8 to bound term (b) above by ϵε. Hence, we have ℙx(Tentern(Bδ′(r))≤t/2,Xn(t/2)∉Bδ′(r))≤2ϵP_x (T_enter^n(B_δ (r))≤ t/2,X^n(t/2)∉ B_δ (r) )≤ 2ε for all sufficiently large n and all starting states x. We can similarly show that ℙx¯(T¯entern(Bδ′(r))≤t/2,X¯n(t/2)∉Bδ′(r))≤2ϵP_ x( T_enter^n(B_δ (r))≤ t/2, X^n(t/2)∉ B_δ (r))≤ 2ε for all x¯∈ x and all sufficiently large n. Hence, combining the above, we have that for any ϵ>0ε>0 ℙx,x¯(Gc(2C′logn/ϵ))≤6ϵ,P_x, x(G^c(2C n/ε))≤ 6ε, for all sufficiently large n and all initial states x and x¯ x. Now, we focus on the event Tcouplen>tT_couple^n>t. We have ℙx,x¯(Tcouplen>2C′logn/ϵ) _x, x(T_couple^n>2C n/ε) ≤ℙx,x¯(Tcouplen>2Clogn/ϵ,G(2C′logn/ϵ))+ℙx,x¯(Gc(2C′logn/ϵ)) _x, x(T_couple^n>2C n/ε,G(2C n/ε))+P_x, x(G^c(2C n/ε)) ≤ℙx,x¯(Tcouplen>2C′logn/ϵ|G(2C′logn/ϵ))+6ϵ _x, x(T_couple^n>2C n/ε|G(2C n/ε))+6ε ≤(a)supy,y¯∈Bδ′(r)ℙy,y¯(Tcouplen>C′logn/ϵ)+6ϵ (a)≤ _y, y∈ B_δ (r)P_y, y(T_couple^n>C n/ε)+6ε =supy,y¯∈Bδ′(r)ℙy,y¯(Xn(C′logn/ϵ)≠X¯n(C′logn/ϵ))+6ϵ = _y, y∈ B_δ (r)P_y, y(X^n(C n/ε)≠ X^n(C n/ε))+6ε ≤(b)7ϵ, (b)≤7ε, where (a)(a) follows by the Markov property and (b)(b) follows from the last statement of Lemma 8. This completes the proof of the theorem.∎ 8 Proof of Theorem 7 (Criticality) We divide the proof of Theorem 7 into two parts, one for each statement of the theorem. 8.1 Proof of the first statement We provide the proof for the case where r1r_1 has a multiplicity of two and r2r_2 has multiplicity of one which happens when (γ0,γ1)∈Γcritical∩γ1>γ0( _0, _1)∈ _critical∩\ _1> _0\. The proof for (γ0,γ1)∈Γcritical∩γ1<γ0( _0, _1)∈ _critical∩\ _1< _0\ is identical with the roles of γ1 _1 and γ0 _0 reversed. Thus, for the case under consideration, it follows from Lemma 1 that r2r_2 is a stable root with region attraction [r2−δ,1−γ0][r_2-δ,1- _0] for all sufficiently small δ>0δ>0. Furthermore, since r1r_1 has a multiplicity of two, we can write Δk(x)=(x−r1)2Δ~k(x), _k(x)=(x-r_1)^2 _k(x), where Δ~k _k is a polynomial with only one real root of multiplicity one at r2∈[γ1,1−γ0]r_2∈[ _1,1- _0]. Furthermore, by the first statement of Lemma 1 it follows that Δk _k is non-negative in [γ1,r2)[ _1,r_2). Hence, Δ~k(x)>0 _k(x)>0 for x∈[γ1,r2)x∈[ _1,r_2) . Hence, for any δ∈(0,r2−r1)δ∈(0,r_2-r_1), there exists Δmax,δ,Δmin,δ>0 _ ,δ, _ ,δ>0 such that Δmax,δ>Δ~k(x)>Δmin,δ _ ,δ> _k(x)> _ ,δ or equivalently Δmax,δ(x−r1)2≥Δk(x)≥Δmin,δ(x−r1)2 _ ,δ(x-r_1)^2≥ _k(x)≥ _ ,δ(x-r_1)^2 for all x∈[γ1,r1+δ]x∈[ _1,r_1+δ]. Furthermore, we have |Δkn(x)−Δk(x)|=O(1/n)| _k^n(x)- _k(x)|=O(1/n) for all x∈[γ1,1−γ0]x∈[ _1,1- _0]. Hence, there exists C>0C>0 such that Δmax,δ(x−r1)2+Cn≥Δkn(x)≥Δmin,δ(x−r1)2−Cn, _ ,δ(x-r_1)^2+ Cn≥ _k^n(x)≥ _ ,δ(x-r_1)^2- Cn, (11) for all sufficiently large n and all x∈[γ1,r1+δ]x∈[ _1,r_1+δ]. Similarly, since σk(x)=fk(x)+gk(x)>0 _k(x)=f_k(x)+g_k(x)>0 for all x∈[γ1,1−γ0]x∈[ _1,1- _0], there exists σmin,σmax>0 _ , _ >0 such that σmin<σk(x)<σmax _ < _k(x)< _ for all x∈[γ1,1−γ0]x∈[ _1,1- _0]. Since σkn _k^n converges uniformly to σk _k we have σmin<σkn(x)<σmax, _ < _k^n(x)< _ , for all x∈[γ1,1−γ0]x∈[ _1,1- _0] and all sufficiently large n. In the following subsections, we prove the upper and lower bounds in the first statement separately. 8.1.1 Upper Bound Now, we fix δ∈[0,r2−r1)δ∈[0,r_2-r_1) and define τδ=inft≥0:Xn(t)≥r1+δ _δ= \t≥ 0:X^n(t)≥ r_1+δ\. Hence, applying the generator XnG_X^n to ϕ∈C3[γ1,1−γ0]φ∈ C^3[ _1,1- _0] we obtain that for each x∈[γ1,1−γ0]x∈[ _1,1- _0] Xnϕ(x)≤Δkn(x)ϕ′(x)+σkn(x)2nϕ′(x)+σkn(x)6n2ϕmax′, _X^nφ(x)≤ _k^n(x)φ (x)+ _k^n(x)2nφ (x)+ _k^n(x)6n^2φ _ , where ϕmax′=supx∈|ϕ′(x)|φ _ = _x |φ (x)|. Now let Let us define Zn(t)=n1/3(Xn(t)−r1)Z^n(t)=n^1/3(X^n(t)-r_1) and similarly define z=n1/3(x−r1)z=n^1/3(x-r_1). Let ψ(z)=ϕ(x)ψ(z)=φ(x). Then we have from (3) Xnψ(z) _X^nψ(z) ≤Δkn(x)n1/3ψ′(z)+σkn(x)2nn2/3ψ′(x)+σkn(x)6n2nψmax′. ≤ _k^n(x)n^1/3ψ (z)+ _k^n(x)2nn^2/3ψ (x)+ _k^n(x)6n^2nψ _ . The following lemma in crucial to proving the upper bound. Lemma 9. For each κ1,κ2,α,n>0 _1, _2,α,n>0, there exists a non-negative function ψ∈C3[−n1/3κ1,n1/3κ2]ψ∈ C^3[-n^1/3 _1,n^1/3 _2] such that the following properties hold: 1. The function ψ solves the ODE (Stein’s equation) ψ′(z)+αz2ψ′(z)=−1,ψ (z)+α z^2ψ (z)=-1, (12) with boundary conditions ψ′(−n1/3κ1)=ψ(n1/3κ2)=0ψ (-n^1/3 _1)=ψ(n^1/3 _2)=0. 2. We have ψ′(z)≤0ψ (z)≤ 0 for all z∈[−n1/3κ1,n1/3κ2]z∈[-n^1/3 _1,n^1/3 _2] and supz∈[−n1/3κ1,n1/3κ2]|ψ′(z)|<C6 _z∈[-n^1/3 _1,n^1/3 _2]|ψ (z)|<C_6 for some positive constant C6C_6 independent of n. 3. We have supz∈[−n1/3κ1,n1/3κ2]ψ(z)<C7 _z∈[-n^1/3 _1,n^1/3 _2]ψ(z)<C_7 for some positive constant C7C_7 independent of n. 4. For all sufficiently large n we have supz∈[−n1/3κ1,n1/3κ2]|ψ′(z)|=n2/3ακ12 _z∈[-n^1/3 _1,n^1/3 _2]|ψ (z)|=n^2/3α _1^2. The proof of this lemma is given in Appendix C Choosing ψ according to the above lemma for κ1=r1−γ1,κ2=δ _1=r_1- _1, _2=δ and α=2Δmin,δσmaxα= 2 _ ,δ _ we obtain Xnψ(z) _X^nψ(z) ≤Δkn(x)n1/3ψ′(z)+σkn(x)2n1/3ψ′(z)+σkn(x)6nn2/3ακ12 ≤ _k^n(x)n^1/3ψ (z)+ _k^n(x)2n^1/3ψ (z)+ _k^n(x)6nn^2/3α _1^2 ≤(Δmin,δ(x−r1)2−Cn)n1/3ψ′(z)+σkn(x)2n1/3ψ′(z)+ακ12σkn(x)6n1/3 ≤ ( _ ,δ(x-r_1)^2- Cn )n^1/3ψ (z)+ _k^n(x)2n^1/3ψ (z)+ α _1^2 _k^n(x)6n^1/3 =Δmin,δn1/3z2ψ′(z)+σkn(x)2n1/3ψ′(z)+ακ12σkn(x)6n1/3−Cn2/3ψ′(z) = _ ,δn^1/3z^2ψ (z)+ _k^n(x)2n^1/3ψ (z)+ α _1^2 _k^n(x)6n^1/3- Cn^2/3ψ (z) ≤σkn(x)2n1/3(ψ′(z)+2Δmin,δσmaxz2ψ′(z)+ακ123)−Cn2/3ψ′(z) ≤ _k^n(x)2n^1/3 (ψ (z)+ 2 _ ,δ _ z^2ψ (z)+ α _1^23 )- Cn^2/3ψ (z) ≤σkn(x)2n1/3(−1+ακ123)+CC6n2/3. ≤ _k^n(x)2n^1/3 (-1+ α _1^23 )+ C_6n^2/3. where the second line follows from (11) since ψ′≤0ψ ≤ 0, and in the last line we have used (12). Then, for all x∈[γ1,r1+δ]x∈[ _1,r_1+δ], it holds that ακ12 α _1^2 =2Δmin,δσmax(γ1−r1)2≤2Δ~k(x)σk(x)(γ1−r1)2=2Δk(x)σk(x)(γ1−r1)2(x−r1)2≤2(γ1−r1)2(x−r1)2, = 2 _ ,δ _ ( _1-r_1)^2≤ 2 _k(x) _k(x)( _1-r_1)^2= 2 _k(x) _k(x) ( _1-r_1)^2(x-r_1)^2≤ 2 ( _1-r_1)^2(x-r_1)^2, and in particular for x=γ1x= _1 the above inequality reduces to ακ12≤2α _1^2≤ 2. Therefore, we can write Xnψ(z) _X^nψ(z) ≤σkn(x)2n1/3(−1+23)+CC6n2/3 ≤ _k^n(x)2n^1/3 (-1+ 23 )+ C_6n^2/3 =−σkn(x)6n1/3+CC6n2/3 =- _k^n(x)6n^1/3+ C_6n^2/3 ≤−σmin6n1/3(1−CC6n1/3) ≤- _ 6n^1/3 (1- C_6n^1/3 ) <0, <0, for sufficiently large n. We are now in a position where we can apply Dynkin’s formula. Let τδ=inft≥0:Xn(t)≥r1+δ _δ= \t≥ 0:X^n(t)≥ r_1+δ\. Then applying Dynkin’s formula, we can write for any j>0j>0 0≤γ1[ψ(Zn(τδ∧j))] 0 _ _1[ψ(Z^n( _δ j))] =γ1[ψ(Zn(0))]+γ1[∫0τδ∧jnψ(Zn(s))s] =E_ _1[ψ(Z^n(0))]+E_ _1 [ _0 _δ jG^nψ(Z^n(s))ds ] ≤γ1[ψ(Zn(0))]−σmin6n1/3[1−6CC6σminn1/3]γ1[τδ∧j]. _ _1[ψ(Z^n(0))]- _ 6n^1/3 [1- 6C_6 _ n^1/3 ]E_ _1[ _δ j]. Now using the fact that ψ(z)<C′ψ(z)<C for all z for some constant C′>0C >0 independent of n we obtain for all sufficiently large n that γ1[τδ∧j]≤(6C′σmin−6CC6n1/3)n1/3. _ _1[ _δ j]≤ ( 6C _ - 6C_6n^1/3 )n^1/3. Since the above holds for any j>0j>0, using the dominated convergence theorem we have γ1[τδ]=limj→∞γ1[τδ∧j]≤(6C′σmin−6CC6n1/3)n1/3.E_ _1[ _δ]= _j→∞E_ _1[ _δ j]≤ ( 6C _ - 6C_6n^1/3 )n^1/3. This shows that γ1[τδ]=O(n1/3)E_ _1[ _δ]=O(n^1/3) which implies that x[Tentern(Bδ(r))]=O(n1/3)E_x[T^n_enter(B_δ(r))]=O(n^1/3) for any x<r2x<r_2. Since r2r_2 is a stable root with region attraction [r2−μ,1−γ0][r_2-μ,1- _0] for all sufficiently small μ>0μ>0 we have from the third statement of Lemma 8 that x[Tentern(Bμ(r2))]=O(logn)E_x[T^n_enter(B_μ(r_2))]=O( n) for all x>r2x>r_2. Hence, we have shown x[Tentern(Bδ(r))]=O(n1/3)E_x[T^n_enter(B_δ(r))]=O(n^1/3) for all x∈x . We now proceed to establish the upper bound on the mixing time. To do this, we employ the same technique as in Theorem 6. We define two independent chains XnX^n and X¯n X^n, each evolving according to the rates (1)-(2) and initialised at x and x¯ x respectively. Define Tcouplen=inft≥0:Xn(t)=X¯n(t)T_couple^n= \t≥ 0:X^n(t)= X^n(t)\. To prove the mixing time upper bound of O(n1/3)O(n^1/3) it suffices to show that for every ϵ>0ε>0 there exists a constant C≡C(ϵ)>0C≡ C(ε)>0 such that ℙx,x¯(Tcouplen>Cn1/3)≤ϵP_x, x(T_couple^n>Cn^1/3)≤ε for all starting states x,x¯∈nx, x ^n. We first let η>0η>0 be such that the last statement of Lemma 8 holds for any x,x¯∈Bη(r2)x, x∈ B_η(r_2) and then choose δ′∈(0,η)δ ∈(0,η). Now, similar to the proof of Theorem 6, we define the event G(t):=Xn(t/2)∈Bδ′(r2),X¯n(t/2)∈Bδ′(r2)G(t):=\X^n(t/2)∈ B_δ (r_2), X^n(t/2)∈ B_δ (r_2)\. Now, similar to the proof of Theorem 6, it can be shown that ℙx,x¯(Gc(t))≤6ϵP_x, x(G^c(t))≤ 6ε for t=2Cn1/3/ϵt=2Cn^1/3/ε from which it follows that ℙx,x¯(Tcouplen>2Cn1/3/ϵ)≤7ϵP_x, x(T^n_couple>2Cn^1/3/ε)≤ 7ε. This completes the proof of the upper bound. 8.1.2 Lower Bound Choose ϕ(x)=(x−r1+ϵn)2φ(x)=(x-r_1+ _n)^2, with ϵn=n−1/3 _n=n^-1/3. Then for x∈[r1−ϵn,r1]x∈[r_1- _n,r_1] and all sufficiently large n, we have Xnϕ(x) _X^nφ(x) =Δkn(x)2(x−r1+ϵn)+σkn(x)n = _k^n(x)2(x-r_1+ _n)+ _k^n(x)n ≤2Δmax,δ(x−r1)2(x−r1+ϵn)+σmaxn+2C(x−r1+ϵn)n ≤ 2 _ ,δ(x-r_1)^2(x-r_1+ _n)+ _ n+ 2C(x-r_1+ _n)n ≤2Δmax,δϵn(x−r1)2+σmaxn+2Cϵn ≤ 2 _ ,δ _n(x-r_1)^2+ _ n+ 2C _nn ≤2Δmax,δ+σmaxn[1+C¯n1/3] ≤ 2 _ ,δ+ _ n [1+ Cn^1/3 ] ≤C′n, ≤ C n, for sufficiently large n. Then, for x<r1−ϵnx<r_1- _n, we have Xnϕ(x)=2Δkn(x)(x−r1+ϵn)+σkn(x)n≤σmaxn. _X^nφ(x)=2 _k^n(x)(x-r_1+ _n)+ _k^n(x)n≤ _ n. Combining both of the bounds above, we have Xnϕ(x)<Dn,∀x≤r1, _X^nφ(x)< Dn, ∀ x≤ r_1, where D>0D>0 and is independent of n and k. Now define τ′=inft≥0:|Xn(t)−r1+ϵn|≥ϵnτ = \t≥ 0:|X^n(t)-r_1+ _n|≥ _n\ and τr1′=inft≥0:Xn(t)≥r1τ _r_1= \t≥ 0:X^n(t)≥ r_1\. Clearly, for any x<r1x<r_1 we have x[τr1′]≥x[τ′]E_x[τ _r_1] _x[τ ]. Furthermore, starting from x=r1−ϵnx=r_1- _n and applying Dynkin’s formula gives r1−ϵn[ϕ(Xn(τ′∧δ′n1/3))] _r_1- _n[φ(X^n(τ δ n^1/3))] =ϕ(Xn(0))+r1−ϵn[∫0τ′∧δ′n1/3Xnϕ(Xn(s))s] =φ(X^n(0))+E_r_1- _n [ _0^τ δ n^1/3G_X^nφ(X^n(s))ds ] ≤1n2+Dnr1−ϵn[τ′∧δ′n1/3] ≤ 1n^2+ DnE_r_1- _n[τ δ n^1/3] ≤1n2+Dδ′n2/3. ≤ 1n^2+ Dδ n^2/3. We also have r1−ϵn[ϕ(Xn(τ′∧δ′n1/3))]≥r1−ϵn[ϕ(Xn(τ′))(τ′≤δ′n1/3)]≥ϵn2ℙr1−ϵn(τ′≤δ′n1/3). _r_1- _n[φ(X^n(τ δ n^1/3))] _r_1- _n [φ(X^n(τ ))1_ (τ ≤δ n^1/3 ) ]≥ _n^2P_r_1- _n (τ ≤δ n^1/3 ). Now let τr2−μ′=inft≥0:Xn≥r2−μτ _r_2-μ= \t≥ 0:X^n≥ r_2-μ\, with 0<μ<maxr2−r1,1−γ0−r20<μ< \r_2-r_1,1- _0-r_2\. Since τr2−μ′≤δn1/3⊆τ′≤δn1/3\τ _r_2-μ≤δ n^1/3\ \τ ≤δ n^1/3\, given that Xn(0)=r1−ϵnX^n(0)=r_1- _n, then we have that ℙr1−ϵn(τr2−μ′≤δ′n1/3)≤ℙr1−ϵn(τ′≤δ′n1/3)≤Dδ′+n−4/3. _r_1- _n (τ _r_2-μ≤δ n^1/3 ) _r_1- _n (τ ≤δ n^1/3 )≤ Dδ +n^-4/3. Since dn(t)=maxsupA⊆[γ1,1−γ0]x∈[0,1]|ℙx(Xn(t)∈A)−πn(A)|d^n(t)= _x∈[0,1] _A [ _1,1- _0] _x(X^n(t)∈ A)-π^n(A) . Hence, choosing x=(r1−ϵn)x=(r_1- _n) and A=AμA=A_μ where Aμ=[r2−μ,r2+μ]A_μ=[r_2-μ,r_2+μ], we obtain d(t)≥|ℙr1−ϵn(Xn(t)∈[r2−μ,r2+μ])−πn([r2−μ,r2+μ])|.d(t)≥ _r_1- _n(X^n(t)∈[r_2-μ,r_2+μ])-π^n([r_2-μ,r_2+μ]) . But, since πn⇒δr2π^n _r_2 as n→∞n→∞, we have for all sufficiently large n that πn([r2−μ,r2+μ])≥12π^n([r_2-μ,r_2+μ])≥ 12. Also define τr2−μ′=inft≥0:Xn(t)≥r2−μτ _r_2-μ= \t≥ 0:X^n(t)≥ r_2-μ\. Hence, d(t) d(t) ≥12−ℙr1−ϵn(Xn(t)∈[r2−μ,r2+μ]) ≥ 12-P_r_1- _n(X^n(t)∈[r_2-μ,r_2+μ]) ≥12−ℙr1−ϵn(τr2−μ′≤t). ≥ 12-P_r_1- _n(τ _r_2-μ≤ t). Choosing t=δ′n1/3t=δ n^1/3 with δ′=1/8Dδ =1/8D in the above we obtain for all sufficiently large n d(δ′n1/3) d(δ n^1/3) ≥12−ℙr1−ϵn(τr2−μ′≤δ′n1/3)≥12−Dδ′−n−4/3=12−18−n−4/3≥14 ≥ 12-P_r_1- _n(τ _r_2-μ≤δ n^1/3)≥ 12-Dδ -n^-4/3= 12- 18-n^-4/3≥ 14 This implies that tmixn≥n1/38D=Ω(n1/3)t_mix^n≥ n^1/38D= (n^1/3). Therefore, we have shown that tmix=Ω(n1/3)t_mix= (n^1/3) and tmix=O(n1/3)t_mix=O(n^1/3). This completes the proof of the first statement of Theorem 7. 8.2 Proof of the second statement Now we turn to the proof of the second statement. For (γ0,γ1)∈Γcritk( _0, _1)∈ _crit^k with γ0=γ1=γ _0= _1=γ the Δk _k has a single root of multiplicity three at r=1/2r=1/2, and hence Δk(x)=(x−r)3Δ~k(x), _k(x)=(x-r)^3 _k(x), where Δ~k(x)<0 _k(x)<0 for all x∈[γ1,1−γ0]x∈[ _1,1- _0]. Hence, there exist Δ~min,Δ~max>0 _ , _ >0 such that −Δ~max<Δ~k(x)<−Δ~min<0- _ < _k(x)<- _ <0. This implies that for all sufficiently large n, there exists a C>0C>0 such that we have −Δ~max(x−r)3+C/n>Δkn(x)>−Δ~min(x−r)3−C/n≥0- _ (x-r)^3+C/n> _k^n(x)>- _ (x-r)^3-C/n≥ 0 for x≤rx≤ r. As before, the generator acting on a test function ϕ∈C3()φ∈ C^3(S) can be written as Xnϕ(x)≤Δkn(x)ϕ′(x)+σkn(x)2nϕ′(x)+σkn(x)6n2ϕmax′, _X^nφ(x)≤ _k^n(x)φ (x)+ _k^n(x)2nφ (x)+ _k^n(x)6n^2φ _ , where where ϕmax′=supx∈|ϕ′(x)|φ _ = _x |φ (x)|. 8.2.1 Upper Bound We make the following transinformation Zn(t)=n1/4(Xn(t)−r)Z^n(t)=n^1/4(X^n(t)-r) and define ϕ(x)=ψ(z)φ(x)=ψ(z) with z=n1/4(x−r)z=n^1/4(x-r). Thus, the generator expansion in terms of ψ, can be written as Xnψ(z) _X^nψ(z) ≤Δkn(x)n1/4ψ′(z)+σkn(x)2n1/2ψ′(z)+σkn(x)6n5/4maxw|ψ′(w)|. ≤ _k^n(x)n^1/4ψ (z)+ _k^n(x)2n^1/2ψ (z)+ _k^n(x)6n^5/4 _w|ψ (w)|. Now, we choose ψ according to the following lemma. Lemma 10. For each κ,α,n>0κ,α,n>0, there exists a non-negative function ψ∈C3[−n1/4κ,0]ψ∈ C^3[-n^1/4κ,0] such that the following properties hold: 1. The function ψ solves the ODE (Stein’s equation) ψ′(z)−αz3ψ′(z)=−1,ψ (z)-α z^3ψ (z)=-1, (13) with boundary conditions ψ′(−n1/4κ)=ψ(0)=0ψ (-n^1/4κ)=ψ(0)=0. 2. We have ψ′(z)≤0ψ (z)≤ 0 for all z∈[−n1/4κ,0]z∈[-n^1/4κ,0] and supz∈[−n1/4κ,0]|ψ′(z)|<C1 _z∈[-n^1/4κ,0]|ψ (z)|<C_1 for some positive constant C1C_1 independent of n. 3. We have supz∈[−n1/4κ,0]ψ(z)<C2 _z∈[-n^1/4κ,0]ψ(z)<C_2 for some positive constant C2C_2 independent of n. 4. For all sufficiently large n we have supz∈[−n1/4κ,0]|ψ′(z)|=ακ3n3/4 _z∈[-n^1/4κ,0]|ψ (z)|=ακ^3n^3/4. The proof of the above lemma is given in Appendix D Choosing ψ according to the above lemma for κ=−γκ=-γ and α=2Δminσmaxα= 2 _ _ we obtain Xnψ(z) _X^nψ(z) ≤−Δ~min(x−r)3n1/4ψ′(z)+σkn(x)2n1/2ψ′(z)+σkn(x)6n5/4maxw∈[−κn1/4,0]|ψ′(w)|+Cn3/4|ψ′(z)| ≤- _ (x-r)^3n^1/4ψ (z)+ _k^n(x)2n^1/2ψ (z)+ _k^n(x)6n^5/4 _w∈[-κ n^1/4,0]|ψ (w)|+ Cn^3/4|ψ (z)| ≤−Δ~minz3n1/2ψ′(z)+σkn(x)2n1/2ψ′(z)+σkn(x)6n5/4ακ3n3/4+CC1n3/4 ≤- _ z^3n^1/2ψ (z)+ _k^n(x)2n^1/2ψ (z)+ _k^n(x)6n^5/4ακ^3n^3/4+ C_1n^3/4 =σkn(x)2n1/2[ψ′(z)−2Δ~minσmaxz3ψ′(z)+ακ33]+CC1n3/4 = _k^n(x)2n^1/2 [ψ (z)- 2 _ _ z^3ψ (z)+ ακ^33 ]+ C_1n^3/4 =σkn(x)2n1/2(ακ33−1)+CC1n3/4. = _k^n(x)2n^1/2 ( ακ^33-1 )+ C_1n^3/4. Now consider ακ3=2Δ~minσmax⋅(r−γ)3<2Δk(γ)σmax⋅(r−γ)3(r−γ)3<2σk(γ)σmax≤2. ακ^3= 2 _ _ ·(r-γ)^3< 2 _k(γ) _ · (r-γ)^3(r-γ)^3< 2 _k(γ) _ ≤ 2. Hence, Xnψ(z) _X^nψ(z) ≤σkn(x)2n1/2(23−1)+CC1n3/4 ≤ _k^n(x)2n^1/2 ( 23-1 )+ C_1n^3/4 ≤−σmin6n1/2+CC1n3/4 ≤- _ 6n^1/2+ C_1n^3/4 =−σmin6n1/2[1−6CC1σminn1/4]. =- _ 6n^1/2 [1- 6C_1 _ n^1/4 ]. Now we are in a position to apply Dynkin’s formula to bound the time Tentern(r)=inft≥0:(r−Xn(0))(r−Xn(t))≤0T_enter^n(r)= \t≥ 0:(r-X^n(0))(r-X^n(t))≤ 0\, i.e. the first time the root r is reached or crossed. Following similar line of arguments as in the first part we obtain γ[Tentern(r)]≤(6C2σmin−6CC1n1/4)n1/2=C′n1/2. _γ[T_enter^n(r)]≤ ( 6C_2 _ - 6C_1n^1/4 )n^1/2=C n^1/2. for some constant C′>0C >0. Using symmetry we can conclude that 1−γ[Tentern(r)]≤C′n1/2E_1-γ[T_enter^n(r)]≤ C n^1/2 for all sufficiently large n. This implies that maxx∈Snx[Tentern(r)]≤C′n1/2 _x∈ S^nE_x[T^n_enter(r)]≤ C n^1/2 for all sufficiently large n Now to prove the mixing time upper bound using the hitting time upper bound, we use the following lemma. Lemma 11. Suppose that N0n=N1n=⌈nγ⌉N_0^n=N_1^n= nγ for some γ∈(0,1/2)γ∈(0,1/2). Let XnX^n and X¯n X^n be two chains, each following the rates in (1)-(2) and started at x∈nx ^n and x¯∈n x ^n, respectively. Assume without loss generality that |x−1/2|≥|x¯−1/2||x-1/2|≥| x-1/2|. Then we have Tcouplen(Xn,X¯n)≤stTentern(r), T_couple^n(X^n, X^n) _stT_enter^n(r), where Tcouplen(Xn,X¯n)=inft≥0:Xn(t)=X¯n(t)T^n_couple(X^n, X^n)= \t≥ 0:X^n(t)= X^n(t)\ is the first time the two chains meet and Tentern(r)=inft≥0:(r−x)(r−Xn(t))≤0T_enter^n(r)= \t≥ 0:(r-x)(r-X^n(t))≤ 0\, as defined before, is the first time the chain XnX^n crosses r. Proof. If the two chains XnX^n, X¯n X^n are such that x=1−x¯x=1- x, then we construct a reflection-symmetric coupling, i.e., whenever the lower chain transitions up one state, the upper chain transitions down one state and vice versa. This is possible since we have N0n=N1nN_0^n=N_1^n and therefore fkn(x)=gkn(1−x)f_k^n(x)=g_k^n(1-x) for all x∈nx ^n. When n is even, r∈nr ^n and both chains meet at r and therefore Tcouplen(Xn,X¯n)=Tentern(r)T_couple^n(X^n, X^n)=T_enter^n(r). When n is odd, let the two adjacent states to r be rL=1/2−1/2n,rU=1/2+1/2n∈nr_L=1/2-1/2n,r_U=1/2+1/2n ^n. It is obvious that if we continue to use the same reflection-symmetric coupling, then the transition of (rL,rU)→(rU,rL)(r_L,r_U)→(r_U,r_L) means that the chains do not meet. We modify the coupling when the reflection symmetric chain reaches the state (rL,rU)(r_L,r_U). Introduce three independent exponential clocks corresponding to the following transitions. First, at rate gkn(rL)=fkn(rU)g_k^n(r_L)=f_k^n(r_U), both chains move away from r. At rate fkn(rL)f_k^n(r_L) the lower chain jumps from rL→rUr_L→ r_U, i.e. (rL,rU)→(rU,rU)(r_L,r_U)→(r_U,r_U) and the chains couple at rUr_U. Finally, at rate gkn(rU)g_k^n(r_U), the upper chains moves from rU→rLr_U→ r_L, i.e. (rL,rU)→(rL,rL)(r_L,r_U)→(r_L,r_L) and the chains meet at rLr_L. The first exponential clock to ring determines which transition occurs. After the chains couple, they evolve together. Hence, we again have Tcouplen(Xn,X¯n)=Tentern(r)T_couple^n(X^n, X^n)=T_enter^n(r). If x≠1−x¯x≠ 1- x is not true, then define the chain YnY^n such that Yn(0)=1−Xn(0)Y^n(0)=1-X^n(0). Now couple XnX^n and YnY^n with the reflection-symmetric coupling described above. By the choice of XnX^n, the initial state of X¯n X^n lies between those of XnX^n and YnY^n. Let X¯n X^n evolve independently of both XnX^n and YnY^n until it first meets one of them after which the chains that meet move together. Since the chains are one dimensional birth-death processes, X¯n X^n cannot leave the interval bounded by XnX^n and YnY^n without first meeting one of them. Thus, under this constructed coupling, we must have Tcouplen(Xn,X¯n)≤Tcouplen(Xn,Yn)=Tentern(r)T^n_couple(X^n, X^n)≤ T^n_couple(X^n,Y^n)=T^n_enter(r). ∎ Hence, using the above lemma and the coupling lemma for Markov chain mixing we obtain dn(t) d^n(t) ≤maxx,x¯ℙx,x¯(Tcouplen(Xn,X¯n)>t) ≤ _x, xP_x, x(T^n_couple(X^n, X^n)>t) ≤maxxℙx(Tentern(r)>t) ≤ _xP_x(T_enter^n(r)>t) ≤maxxx[Tentern(r)]t ≤ _x E_x[T_enter^n(r)]t ≤C′n1/2t. ≤ C n^1/2t. Now choosing t=4C′n1/2t=4C n^1/2, we have that dn(4C′n1/2)≤1/4d^n(4C n^1/2)≤ 1/4. Hence, tmixn=O(n1/2)t_mix^n=O(n^1/2). This concludes the proof of the upper bound. 8.2.2 Lower bound Choose ϕ(x)=(x−r+ϵn)2φ(x)=(x-r+ _n)^2 with ϵn=n−1/4 _n=n^-1/4. Then for x∈[r−ϵn,r]x∈[r- _n,r] and all sufficiently large n we have Xnϕ(x) _X^nφ(x) =Δkn(x)2(x−r+ϵn)+σkn(x)n = _k^n(x)2(x-r+ _n)+ _k^n(x)n ≤(a)−2d(x−r)3(x−r+ϵn)+σmaxn+2C(x−r+ϵn)n (a)≤-2d(x-r)^3(x-r+ _n)+ _ n+ 2C(x-r+ _n)n ≤2dϵn(r−x)3+σmaxn+2Cϵn ≤ 2d _n(r-x)^3+ _ n+ 2C _nn ≤(b)2d+σmaxn+2Cn5/4 (b)≤ 2d+ _ n+ 2Cn^5/4 =2d+σmaxn(1+C¯n1/4) = 2d+ _ n (1+ Cn^1/4 ) ≤C′n, ≤ C n, for a sufficiently large n, where (a) follows since Δkn(x)≤−d(x−r)3+C/n,x≥r−ϵn _k^n(x)≤-d(x-r)^3+C/n,x≥ r- _n, and σkn(x)<σmax _k^n(x)< _ and (b) follows because |x−r|≤n−1/4 x-r ≤ n^-1/4. Similarly, for x≤r−ϵnx≤ r- _n we have Xnϕ(x)=2Δkn(x)(x−r+ϵn)+σkn(x)n≤σmaxn,G_X^nφ(x)=2 _k^n(x)(x-r+ _n)+ _k^n(x)n≤ _ n, where the inequality follows since Δkn(x)>0 _k^n(x)>0 and x−r+ϵn≤0x-r+ _n≤ 0 in the range considered. Thus, combining the above bounds we have Xnϕ(x)≤Cn,∀x≤r,G_X^nφ(x)≤ Cn, ∀ x≤ r, where C is some positive constant. Now, we define τ=inft≥0:|x−r+ϵn|≥1/n1/4τ= \t≥ 0: x-r+ _n ≥ 1/n^1/4\ and τr=inft≥0:x≥r _r= \t≥ 0:x≥ r\. Clearly, for any x<rx<r we have x[τr]≥x[τ]E_x[ _r] _x[τ]. Furthermore, starting from x=r−n−1/4x=r-n^-1/4 and applying Dynkin’s formula we obtain the following: r−ϵn[ϕ(Xn(τ∧δn1/2))] _r- _n[φ(X^n(τ δ n^1/2))] =r−ϵn[ϕ(Xn(0))]+r−ϵn[∫0τ∧δn1/2nϕ(Xn(s))s] =E_r- _n[φ(X^n(0))]+E_r- _n [ _0^τ δ n^1/2G^nφ(X^n(s))ds ] ≤1n2+Cnr−ϵn[τ∧δn1/2] ≤ 1n^2+ CnE_r- _n[τ δ n^1/2] ≤1n2+Cnδ. ≤ 1n^2+ C nδ. But we also have r−ϵn[ϕ(Xn(τ∧δn1/2))]≥r−ϵn[ϕ(Xn(τ))(τ≤δn1/2)]≥ϵn2ℙr−ϵn(τ≤δn1/2). _r- _n[φ(X^n(τ δ n^1/2))] _r- _n [φ(X^n(τ))1_ (τ≤δ n^1/2 ) ]≥ _n^2P_r- _n (τ≤δ n^1/2 ). Hence, we have ℙr−ϵn(τ≤δn1/2)≤Cδ+n−3/2. _r- _n (τ≤δ n^1/2 )≤ Cδ+n^-3/2. Now, we recall that d(t)=maxsupA⊆[γ1,1−γ0]x∈[0,1]|ℙx(Xn(t)∈A)−πn(A)|d(t)= _x∈[0,1] _A [ _1,1- _0] _x(X^n(t)∈ A)-π^n(A) . Hence, choosing x=(r−ϵn)x=(r- _n) and A=[r,1−γ0]A=[r,1- _0] we obtain d(t)≥|ℙr−ϵn(Xn(t)∈[r,1−γ0])−πn([r,1−γ0])|d(t)≥ _r- _n(X^n(t)∈[r,1- _0])-π^n([r,1- _0]) . But, since πn⇒δrπ^n _r as n→∞n→∞, we have for all sufficiently large n that πn([r,1−γ0])≥12π^n([r,1- _0])≥ 12. Hence, d(t) d(t) ≥12−ℙr−ϵn(Xn(t)∈[r,1−γ0]) ≥ 12-P_r- _n(X^n(t)∈[r,1- _0]) ≥12−ℙr−ϵn(τ≤t). ≥ 12-P_r- _n(τ≤ t). Choosing t=δn1/2t=δ n^1/2 with δ=1/8Cδ=1/8C in the above we obtain for all sufficiently large n d(δn1/2) d(δ n^1/2) ≥12−ℙr−ϵn(τ≤δn1/2)≥12−Cδ−n−3/2=12−18−n−3/2≥14. ≥ 12-P_r- _n(τ≤δ n^1/2)≥ 12-Cδ-n^-3/2= 12- 18-n^-3/2≥ 14. This implies that tmixn≥n1/28C=Ω(n1/2)t_mix^n≥ n^1/28C= (n^1/2). To conclude this section, we have shown that tmixn=Ω(n1/2)t_mix^n= (n^1/2) and tmixn=(n1/2)t_mix^n=O(n^1/2). Therefore, it is true that for γ0=γ1 _0= _1, we have tmixn=Θ(n1/2)t_mix^n= (n^1/2). This concludes the proof of Theorem 7. 9 Conclusion and Future Work We studied the 2k2k-choices dynamics in the presence of stubborn agents. We have shown that, as the system size increases, the stationary distribution concentrates on the majority state of the opinion with the larger fraction of stubborn followers. We demonstrate that the convergence to the stationary distribution relies completely on the stubborn fractions. When both fractions are small, the system exhibits metastability, taking an exponentially long time to reach steady-state. When either the stubborn fractions are both large or the difference between them is large, the system converges rapidly to its stationary distribution. When the stubborn fractions lie on the phase transition boundary, convergence to the stationary distribution happens in polynomial time. Future work should aim to study this process on alternative graph families. In our model, the agents are heterogeneous due to stubbornness. Hence, how the stubborn agents are distributed across different neighbourhoods matters, and would render the analysis much more complex. We would expect, however, that similar results will hold when each neighbourhood has a similar distribution of stubborn agents. References [1] D. Acemoğlu, G. Como, F. Fagnani, and A. Ozdaglar (2013) Opinion fluctuations and disagreement in social networks. Mathematics of Operations Research 38 (1), p. 1–27. Cited by: §1. [2] A. Anagnostopoulos, L. Becchetti, E. Cruciani, F. Pasquale, and S. Rizzo (2020) Biased opinion dynamics: when the devil is in the details. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, C. Bessiere (Ed.), p. 53–59. Note: Main track External Links: Document, Link Cited by: §1.1. [3] A. Bovier and F. Den Hollander (2016) Metastability: a potential-theoretic approach. Springer. Cited by: §1. [4] A. Braverman (2021) The prelimit generator comparison approach of stein’s method. arXiv preprint arXiv:2102.12027. Cited by: §1. [5] F. Capannoli, E. Cruciani, H. A. Mimun, and M. Quattropani (2026) A phase transition for opinion dynamics with competing biases. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, p. 29323–29331. Cited by: §1.1. [6] C. Castellano, S. Fortunato, and V. Loreto (2009) Statistical physics of social dynamics. Reviews of Modern Physics 81 (2), p. 591–646. Cited by: §1. [7] P. Clifford and A. Sudbury (1973) A model for spatial conflict. Biometrika 60 (3), p. 581–588. Cited by: §1.1. [8] C. Cooper, R. Elsasser, H. Ono, and T. Radzik (2013) Coalescing random walks and voting on connected graphs. SIAM Journal on Discrete Mathematics 27 (4), p. 1748–1758. Cited by: §1.1. [9] C. Cooper, R. Elsässer, T. Radzik, N. Rivera, and T. Shiraga (2015) Fast consensus for voting on general expander graphs. In International Symposium on Distributed Computing, p. 248–262. Cited by: §1.1. [10] C. Cooper, R. Elsässer, and T. Radzik (2014) The power of two choices in distributed voting. In International Colloquium on Automata, Languages, and Programming, p. 435–446. Cited by: §1.1, §1. [11] J. T. Cox (1989) Coalescing random walks and voter model consensus times on the torus in ℤdZ^d. The Annals of Probability, p. 1333–1366. Cited by: §1.1. [12] E. Cruciani, E. Natale, A. Nusser, and G. Scornavacca (2021) Phase transition of the 2-choices dynamics on core–periphery networks. Distributed Computing 34 (3), p. 207–225. Cited by: §1.1. [13] B. Finkbeiner and L. Tentrup (2015) Detecting unrealizability of distributed fault-tolerant systems. Logical Methods in Computer Science 11. Cited by: §1. [14] B. L. Granovsky and N. Madras (1995) The noisy voter model. Stochastic Processes and their Applications 55 (1), p. 23–43. Cited by: §1.1, §1. [15] R. A. Holley and T. M. Liggett (1975) Ergodic theorems for weakly interacting infinite systems and the voter model. The Annals of Probability, p. 643–663. Cited by: §1.1. [16] O. Kallenberg (2002) Foundations of modern probability. 2 edition, Probability and Its Applications, Springer-Verlag, New York. External Links: ISBN 0-387-95313-2 Cited by: §4.3. [17] P. L. Krapivsky and S. Redner (2003) Dynamics of majority rule in two-state interacting spin systems. Physical Review Letters 90 (23), p. 238701. Cited by: §1.1. [18] L. Lamport, R. Shostak, and M. Pease (1982) The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4 (3), p. 382–401. External Links: ISSN 0164-0925, Link, Document Cited by: §1. [19] D. A. Levin and Y. Peres (2017) Markov chains and mixing times. Vol. 107, American Mathematical Soc.. Cited by: §7. [20] L. Meredith and A. Mukhopadhyay (2026) Robustness of the 2-choices dynamics to node failures. Proceedings of the ACM on Measurement and Analysis of Computing Systems 10 (1), p. 1–33. Cited by: §1.1. [21] M. Mobilia (2003) Does a single zealot affect an infinite group of voters?. Physical Review Letters 91 (2), p. 028701. Cited by: §1. [22] A. Mukhopadhyay, R. R. Mazumdar, and R. Roy (2016) Binary opinion dynamics with biased agents and agents with different degrees of stubbornness. In 2016 28th International Teletraffic Congress (ITC 28), Vol. 1, p. 261–269. Cited by: §1.1. [23] A. Mukhopadhyay, R. R. Mazumdar, and R. Roy (2020) Voter and majority dynamics with biased and stubborn agents. Journal of Statistical Physics 181 (4), p. 1239–1265. Cited by: §1.1, §1.1. [24] M. Pineda, R. Toral, and E. Hernandez-Garcia (2009) Noisy continuous-opinion dynamics. Journal of Statistical Mechanics: Theory and Experiment 2009 (08), p. P08001. Cited by: §1. [25] E. Yildiz, D. Acemoglu, A. E. Ozdaglar, A. Saberi, and A. Scaglione (2011) Discrete opinion dynamics with stubborn agents. Available at SSRN 1744113. Cited by: §1.1, §1. Appendix A Proof of Lemma 1 The function Δk _k can also be written as Δk(x) _k(x) =(1−x−γ0)Ix(k+1,k)−(x−γ1)I1−x(k+1,k), =(1-x- _0)I_x(k+1,k)-(x- _1)I_1-x(k+1,k), where Ix(α,β)=∑r=a+b−1(a+b−1r)xr(1−x)a+b−1−r, I_x(α,β)= _r=a^a+b-1 a+b-1rx^r (1-x )^a+b-1-r, is the regularized incomplete beta function with parameters y∈[0,1]y∈[0,1] and α,β∈ℤ+α,β ^+. This can also be written as Ix(α,β)=B(x,α,β)/B(α,β)I_x(α,β)=B(x;α,β)/B(α,β), where B(x,α,β)=∫0xtα−1(1−t)β−1t, B(x;α,β)= _0^xt^α-1(1-t)^β-1dt, with B(α,β)=B(1,α,β)B(α,β)=B(1;α,β), where B(x,α,β)B(x;α,β) is the incomplete beta function and B(α,β)B(α,β) is the complete beta function. The function Δk _k then has the following derivative properties: 1. The first derivative is dxΔk(x)=(2k)xk−1(1−x)k−1[(2k+1)x(1−x)−k(γ0x+γ1(1−x))]−1. ddx _k(x)= 2kkx^k-1(1-x)^k-1 [(2k+1)x(1-x)-k( _0x+ _1(1-x)) ]-1. 2. The second derivative is d2dx2Δk(x)=k(2k)xk−2(1−x)k−2Pγ0,γ1(x), d^2dx^2 _k(x)=k 2kkx^k-2(1-x)^k-2P_ _0, _1(x), (14) where Pγ0,γ1P_ _0, _1 is a cubic polynomial given by Pγ0,γ1(x)=(1−2x) P_ _0, _1(x)=(1-2x) [(2k+1)x(1−x)−(k−1)(γ0x+γ1(1−x))] [(2k+1)x(1-x)-(k-1)( _0x+ _1(1-x))] −(γ0−γ1)x(1−x). -( _0- _1)x(1-x). To prove the first statement, we need the derivative of the regularized incomplete beta function Ix(a,b)I_x(a,b). It is known that dxIx(a,b)=xa−1(1−x)b−1B(a,b), ddxI_x(a,b)= x^a-1(1-x)^b-1B(a,b), where B(a,b)B(a,b) is the complete beta function. Setting a=k+1a=k+1 and b=kb=k, we get dxIx(k+1,k)=xk(1−x)k−1B(k+1,k), ddxI_x(k+1,k)= x^k(1-x)^k-1B(k+1,k), dxI1−x(k+1,k)=−(1−x)kxk−1B(k+1,k). ddxI_1-x(k+1,k)=- (1-x)^kx^k-1B(k+1,k). Also, note that B(k+1,k)=(k(2k))−1B(k+1,k)=(k 2kk)^-1. Now the derivative of Δk _k is dxΔk(x) ddx _k(x) =−Ix(k+1,k)+(1−x−γ0)dxIx(k+1,k) =-I_x(k+1,k)+(1-x- _0) ddxI_x(k+1,k) −I1−x(k+1,k)−(x−γ1)dxI1−x(k+1,k) -I_1-x(k+1,k)-(x- _1) ddxI_1-x(k+1,k) =−(Ix(k+1,k)+I1−x(k+1,k)) =-(I_x(k+1,k)+I_1-x(k+1,k)) +(2k)[k(1−x−γ0)xk(1−x)k−1+k(x−γ1)xk−1(1−x)k)] + 2kk [k(1-x- _0)x^k(1-x)^k-1+k(x- _1)x^k-1(1-x)^k) ] =−(Ix(k+1,k)+I1−x(k+1,k)) =-(I_x(k+1,k)+I_1-x(k+1,k)) +(2k)xk−1(1−x)k−1[k(1−x−γ0)x+k(x−γ1)(1−x)]. + 2kkx^k-1(1-x)^k-1 [k(1-x- _0)x+k(x- _1)(1-x) ]. It is true that I1−x(k+1,k)=1−Ix(k,k+1)I_1-x(k+1,k)=1-I_x(k,k+1). Now we also need an expression for Ix(k+1,k)+I1−x(k+1,k) I_x(k+1,k)+I_1-x(k+1,k) =1+Ix(k+1,k)−Ix(k,k+1) =1+I_x(k+1,k)-I_x(k,k+1) =1+k(2k)∫0xtk(1−t)k−1−tk−1(1−t)kt =1+k 2kk _0^xt^k(1-t)^k-1-t^k-1(1-t)^kdt =1+k(2k)∫0xtk−1(1−t)k−1(1−2t)t =1+k 2kk _0^xt^k-1(1-t)^k-1(1-2t)dt =1−(2k)xk(1−x)k. =1- 2kkx^k(1-x)^k. Plugging this expression into the derivative equation, we get dxΔk(x) ddx _k(x) =−1+(2k)xk−1(1−x)k−1[k(1−x−γ0)x+k(x−γ1)(1−x)+x(1−x)] =-1+ 2kkx^k-1(1-x)^k-1 [k(1-x- _0)x+k(x- _1)(1-x)+x(1-x) ] =(2k)xk−1(1−x)k−1[(2k+1)x(1−x)−k(γ0x+γ1(1−x))]−1 = 2kkx^k-1(1-x)^k-1 [(2k+1)x(1-x)-k( _0x+ _1(1-x)) ]-1 =(2k)xk−1(1−x)k−1Mγ0,γ1(x)−1. = 2kkx^k-1(1-x)^k-1M_ _0, _1(x)-1. This establishes the first derivative result. We will need the derivative of the function Mγ0,γ1M_ _0, _1: dxMγ0,γ1(x)=(2k+1)(1−2x)+k(γ1−γ0). ddxM_ _0, _1(x)=(2k+1)(1-2x)+k( _1- _0). The second derivative is then as follows d2dx2Δk(x) d^2dx^2 _k(x) =(2k)xk−2(1−x)k−2(k−1)(1−2x)Mγ0,γ1(x) = 2kkx^k-2(1-x)^k-2(k-1)(1-2x)M_ _0, _1(x) +(2k)xk−1(1−x)k−1dxMγ0,γ1(x) 142.26378pt+ 2kkx^k-1(1-x)^k-1 ddxM_ _0, _1(x) =(2k)xk−2(1−x)k−2((k−1)(1−2x)Mγ0,γ1(x)+x(1−x)dxMγ0,γ1(x)) = 2kkx^k-2(1-x)^k-2 ((k-1)(1-2x)M_ _0, _1(x)+x(1-x) ddxM_ _0, _1(x) ) =(2k)xk−2(1−x)k−2[(k−1)(1−2x)((2k+1)x(1−x)−k(γ0x+γ1(1−x))) = 2kkx^k-2(1-x)^k-2 [(k-1)(1-2x) ((2k+1)x(1-x)-k( _0x+ _1(1-x)) ) +x(1−x)((2k+1)(1−2x))+k(γ1−γ0)x(1−x)] 115.00017pt+x(1-x) ((2k+1)(1-2x) )+k( _1- _0)x(1-x) ] =k(2k)xk−2(1−x)k−2[(1−2x)((2k+1)x(1−x) =k 2kkx^k-2(1-x)^k-2 [(1-2x)((2k+1)x(1-x) −(γ0x+γ1(1−x)))+k(γ1−γ0)x(1−x)] 142.26378pt-( _0x+ _1(1-x)))+k( _1- _0)x(1-x) ] =k(2k)xk−2(1−x)k−2Pγ0,γ1(x). =k 2kkx^k-2(1-x)^k-2P_ _0, _1(x). A.1 Proof of the first statement Plugging in γ1 _1 and 1−γ01- _0 into Δk _k gives Δk(γ1)=(1−γ0−γ1)Iγ1(k+1,k)>0 _k( _1)=(1- _0- _1)I_ _1(k+1,k)>0 Δk(1−γ0)=−(1−γ0−γ1)Iγ0(k+1,k)<0, _k(1- _0)=-(1- _0- _1)I_ _0(k+1,k)<0, since γ0+γ1<1 _0+ _1<1 and Ix(k,k+1)I_x(k,k+1) is a strictly positive function for x>0x>0. This also shows that Δk _k must have at least one real root in [γ1,1−γ0][ _1,1- _0]. Below we show that the number of roots of Δk _k in [γ1,1−γ0][ _1,1- _0] is at most three. Note that to prove that Δk _k can have at most three real roots in [γ1,1−γ0][ _1,1- _0], it is sufficient to prove that Δk′ _k has at most one real root in [γ1,1−γ0][ _1,1- _0]. To see this, assume that Δk _k has at least four real roots in [γ1,1−γ0][ _1,1- _0]. This by Rolle’s theorem implies that f2k′f _2k has at least three real roots in [γ1,1−γ0][ _1,1- _0] which again by Rolle’s theorem implies that f2k′f _2k has at least two real roots in [γ1,1−γ0][ _1,1- _0] contradicting the fact f2k′f _2k has only one real root in [γ1,1−γ0][ _1,1- _0]. We now proceed to prove that Δk′ _k has at most one real root in [γ1,1−γ0][ _1,1- _0]. Note from (14) that to prove this result it is sufficient to prove that the cubic polynomial Pγ0,γ1P_ _0, _1 which can be rewritten as Pγ0,γ1(x) P_ _0, _1(x) =(1−2x)[(2k+1)x(1−x)−(k−1)(γ0x+γ1(1−x))]−(γ0−γ1)x(1−x) =(1-2x)[(2k+1)x(1-x)-(k-1)( _0x+ _1(1-x))]-( _0- _1)x(1-x) =2(2k+1)x3+[(2k−1)(γ0−γ1)−3(2k+1)]x2 =2(2k+1)x^3+[(2k-1)( _0- _1)-3(2k+1)]x^2 +((2k+1)−kγ0+(3k−2)γ1)x−(k−1)γ1, +((2k+1)-k _0+(3k-2) _1)x-(k-1) _1, has at most one real root in [γ1,1−γ0][ _1,1- _0]. Note that the coefficient of x3x^3 is strictly positive, i.e. 2(2k+1)>02(2k+1)>0 for every k≥1k≥ 1. Hence, limx→−∞Pγ0,γ1(x)=−∞ _x→-∞P_ _0, _1(x)=-∞ and limx→∞Pγ0,γ1(x)=∞ _x→∞P_ _0, _1(x)=∞. Also note that Pγ0,γ1P_ _0, _1 can be written as Pγ0,γ1(x)=x(1−x)((1−2x)Gγ0,γ1(x)−(γ0−γ1))P_ _0, _1(x)=x(1-x)((1-2x)G_ _0, _1(x)-( _0- _1)) where Gγ0,γ1(x)=(2k+1)−(k−1)(γ01−x+γ1x).G_ _0, _1(x)=(2k+1)-(k-1) ( _01-x+ _1x ). For x∈[γ1,1−γ0]x∈[ _1,1- _0] we have Gγ0,γ1(x)≥(2k+1)−(k−1)(γ0γ0+γ1γ1)=3. G_ _0, _1(x)≥(2k+1)-(k-1) ( _0 _0+ _1 _1 )=3. Consider the case γ0<1/2 _0<1/2. Evaluating Pγ0,γ1P_ _0, _1 at 1−γ01- _0 gives Pγ0,γ1(1−γ0) P_ _0, _1(1- _0) =γ0(1−γ0)(−(1−2γ0)Gγ0,γ1(1−γ0)−(γ0−γ1)) = _0(1- _0)(-(1-2 _0)G_ _0, _1(1- _0)-( _0- _1)) =−γ0(1−γ0)((1−2γ0)Gγ0,γ1(1−γ0)+(γ0−γ1)) =- _0(1- _0)((1-2 _0)G_ _0, _1(1- _0)+( _0- _1)) ≤−γ0(1−γ0)(3(1−2γ0)+γ0−γ1) ≤- _0(1- _0)(3(1-2 _0)+ _0- _1) =−γ0(1−γ0)(3−4γ0−(γ0+γ1)) =- _0(1- _0)(3-4 _0-( _0+ _1)) <−γ0(1−γ0)(2−4γ0) <- _0(1- _0)(2-4 _0) <0. <0. If γ1<1/2 _1<1/2, then Pγ0,γ1(γ1) P_ _0, _1( _1) =γ1(1−γ1)((1−2γ1)Gγ0,γ1(γ1)−(γ0−γ1)) = _1(1- _1)((1-2 _1)G_ _0, _1( _1)-( _0- _1)) ≥γ1(1−γ1)(3(1−2γ1)−(γ0−γ1)) ≥ _1(1- _1)(3(1-2 _1)-( _0- _1)) =γ1(1−γ1)(3−4γ1−(γ0+γ1)) = _1(1- _1)(3-4 _1-( _0+ _1)) >γ1(1−γ1)(2−4γ1) > _1(1- _1)(2-4 _1) >0. >0. Hence, for γ0,γ1<1/2 _0, _1<1/2, there is at least 1 root of the function in the interval [γ1,1−γ0][ _1,1- _0], via the IVT. The IVT can also be applied to conclude there is at least 1 root in (−∞,γ1)(-∞, _1), since limx→−∞Pγ0,γ1(x)=−∞ _x→-∞P_ _0, _1(x)=-∞ and Pγ0,γ1(γ1)>0P_ _0, _1( _1)>0. The same can be concluded between (1−γ0,∞)(1- _0,∞), since limx→∞Pγ0,γ1(x)=∞ _x→∞P_ _0, _1(x)=∞ and Pγ0,γ1(1−γ0)<0P_ _0, _1(1- _0)<0. Since a cubic has at most three roots, we conclude there is exactly one root in [γ1,1−γ0][ _1,1- _0] when γ0,γ1<1/2 _0, _1<1/2. Alternatively, if γ1>1/2 _1>1/2, either Pγ0,γ1(γ1)>0P_ _0, _1( _1)>0, Pγ0,γ1(γ1)=0P_ _0, _1( _1)=0, or Pγ0,γ1(γ1)<0P_ _0, _1( _1)<0. Note, we can show that Pγ0,γ1(1/2) P_ _0, _1(1/2) =14(γ1−γ0) = 14( _1- _0) >0. >0. If Pγ0,γ1(γ1)>0P_ _0, _1( _1)>0, then IVT is used identically as before to conclude the existence of exactly 1 root in [γ1,1−γ0][ _1,1- _0]. If Pγ0,γ1(γ1)=0P_ _0, _1( _1)=0, then γ1 _1 is the root and IVT can be applied in (−∞,1/2)(-∞,1/2) and (1−γ0,∞)(1- _0,∞) to show that it is the only root in [γ1,1−γ0][ _1,1- _0]. Finally, if Pγ0,γ1(γ1)<0P_ _0, _1( _1)<0, then since limx→−∞Pγ0,γ1(x)=−∞ _x→-∞P_ _0, _1(x)=-∞ and Pγ0,γ1(1/2)>0P_ _0, _1(1/2)>0, then there is at least one root in (−∞,0)(-∞,0) by IVT. Since Pγ0,γ1(1/2)>0P_ _0, _1(1/2)>0 and Pγ0,γ1(γ1)<0P_ _0, _1( _1)<0, there is at least one root in (1/2,γ1)(1/2, _1) via IVT. Finally, since Pγ0,γ1(1−γ0)P_ _0, _1(1- _0) and limx→∞Pγ0,γ1(x)=∞ _x→∞P_ _0, _1(x)=∞, then there is at least 1 root in (1−γ0,∞)(1- _0,∞). Hence there cannot be a root in (γ1,1−γ0)( _1,1- _0). The proof for the case of γ1<1/2 _1<1/2 immediately follows since Pγ0,γ1(x)=−Pγ1,γ0(1−x)P_ _0, _1(x)=-P_ _1, _0(1-x). This concludes the proof of the first statement. A.2 Proof of the second statement Define the function D2kD_2k as D2k(h)=Δk(γ1+h)+Δk(1−γ0−h), D_2k(h)= _k( _1+h)+ _k(1- _0-h), (15) From the definition of Δk _k it follows that D2k(h)=(1−γ0CLOSE D_2k(h)=(1- _0 OPEN−γ1−h)Iγ1+h(k+1,k)−hI1−γ1−h(k+1,k) - _1-h)I_ _1+h(k+1,k)-hI_1- _1-h(k+1,k) +hI1−γ0−h(k+1,k)−(1−γ0−γ1−h)Iγ0+h(k+1,k), +hI_1- _0-h(k+1,k)-(1- _0- _1-h)I_ _0+h(k+1,k), which simplifies to D2k(h)=(1−γ0CLOSE D_2k(h)=(1- _0 OPEN−γ1−h)[Iγ1+h(k+1,k)−Iγ0+h(k+1,k)] - _1-h)[I_ _1+h(k+1,k)-I_ _0+h(k+1,k)] +h[I1−γ0−h(k+1,k)−I1−γ1−h(k+1,k)]. +h[I_1- _0-h(k+1,k)-I_1- _1-h(k+1,k)]. Since Ix(a,b)I_x(a,b) is an increasing function of x (the regularized incomplete beta function is just the CDF of a binomial distribution, and hence, is an increasing function of x), we can conclude that D2k(h)>0D_2k(h)>0 for all h∈[0,1−γ0−γ1]h∈[0,1- _0- _1] if γ1>γ0 _1> _0; D2k(h)<0D_2k(h)<0 for all h∈[0,1−γ0−γ1]h∈[0,1- _0- _1] if γ1<γ0 _1< _0; and D2k(h)=0D_2k(h)=0 for all h∈[0,1−γ0−γ1]h∈[0,1- _0- _1] when γ0=γ1 _0= _1. Hence, for γ1>γ0 _1> _0, choosing h=r1−γ1h=r_1- _1 gives 0<D2k(r1−γ1) 0<D_2k(r_1- _1) =Δk(r1)+Δk(1+γ1−γ0−r1)=Δk(1+γ1−γ0−r1). = _k(r_1)+ _k(1+ _1- _0-r_1)= _k(1+ _1- _0-r_1). (16) Now, since Δk(1−γ0)<0 _k(1- _0)<0 and r2r_2 is the maximum root of Δk _k below 1−γ01- _0 we must have Δk(y)<0 _k(y)<0 for all y∈(r2,1−γ0]y∈(r_2,1- _0]. Hence, (16) implies that 1+γ1−γ0−r<r21+ _1- _0-r<r_2. This establishes the result for statement 2 when γ1>γ0 _1> _0. The proof follows similarly for γ1<γ0 _1< _0. For γ1=γ2 _1= _2 since D2k(h)=0D_2k(h)=0 for all h∈[0,1−γ0−γ1]h∈[0,1- _0- _1] it follows that for every root r∈[γ1,1−γ0]r∈[ _1,1- _0] of Δk _k there is a root of Δk _k at 1−r1-r (since D2k(r−γ1)=Δk(1−r)=0D_2k(r- _1)= _k(1-r)=0). Hence, if r1r_1 is the smallest root in this interval then the largest root in the interval must be 1−r1=r21-r_1=r_2. Appendix B Proof of Proposition 3 The phase transition boundary is parameterised by the values of γ0(w) _0(w) and γ1(w) _1(w) such that Δk(w)=0and∂xΔk(x)|x=w=0. _k(w)=0 _x _k(x) |_x=w=0. Doing the above results in two simultaneous equations, linear in γ0 _0 and γ1 _1: (1−γ0−w)Pk(w)−(w−γ1)Pk(1−w)=0 (1- _0-w)P_k(w)-(w- _1)P_k(1-w)=0 (17) −(Pk(w)+Pk(1−w))+(1−γ0−w)Pk′(w)+(w−γ1)Pk′(1−w)=0. -(P_k(w)+P_k(1-w))+(1- _0-w)P_k (w)+(w- _1)P_k (1-w)=0. (18) Rearranging (18) for γ0 _0 and plugging it into (17), we arrive at γ1(w)=w−Pk(w)(Pk(w)+Pk(1−w))Pk′(1−w)Pk(w)+Pk′(w)Pk(1−w). _1(w)=w- P_k(w)(P_k(w)+P_k(1-w))P _k(1-w)P_k(w)+P_k (w)P_k(1-w). Plugging this expression back into (17), we obtain an expression for γ0 _0: γ0(w)=(1−w)−Pk(1−w)(Pk(w)+Pk(1−w))Pk′(1−w)Pk(w)+Pk′(w)Pk(1−w). _0(w)=(1-w)- P_k(1-w)(P_k(w)+P_k(1-w))P _k(1-w)P_k(w)+P_k (w)P_k(1-w). Hence, we have that γ1(w)=γ0(1−w) _1(w)= _0(1-w). It is true that Pk(1−w)>Pk(w)P_k(1-w)>P_k(w) for w∈(0,1/2)w∈(0,1/2). Now consider the derivative of dt[t(1−t)]k−1=(k−1)[t(1−t)]k−2(1−2t). ddt[t(1-t)]^k-1=(k-1)[t(1-t)]^k-2(1-2t). Hence, dt[t(1−t)]k−1>0 ddt[t(1-t)]^k-1>0 for t∈(0,1/2)t∈(0,1/2). Therefore, for t≤wt≤ w, using this increasing property we have [t(1−t)]k−1≤[w(1−w)]k−1, [t(1-t)]^k-1≤[w(1-w)]^k-1, and therefore tk(1−t)k−1≤twwk(1−w)k−1. t^k(1-t)^k-1≤ tww^k(1-w)^k-1. Integrating both sides w.r.t t gives ∫0wtk(1−t)k−1t=w2wk(1−w)k−1. _0^wt^k(1-t)^k-1dt= w2w^k(1-w)^k-1. Therefore, using the definition of the regularised incomplete beta function and its derivative, we have that Pk(w)≤w2Pk′(w), P_k(w)≤ w2P_k (w), for w∈(0,1/2)w∈(0,1/2). Now we can do the following Pk(w)(Pk(w)+Pk(1−w)) P_k(w)(P_k(w)+P_k(1-w)) ≤Pk(w)(Pk(1−w)+Pk(1−w)) ≤ P_k(w)(P_k(1-w)+P_k(1-w)) =2Pk(w)Pk(1−w) =2P_k(w)P_k(1-w) ≤wPk(1−w)Pk′(w) ≤ wP_k(1-w)P_k (w) >w(Pk(1−w)Pk′(w)+Pk(w)Pk′(1−w)CLOSE. >w(P_k(1-w)P_k (w)+P_k(w)P_k (1-w). Hence we can conclude that γ1(w) _1(w) >w−w(Pk(1−w)Pk′(w)+Pk(w)Pk′(1−w)CLOSEPk(1−w)Pk′(w)+Pk(w)Pk′(1−w) >w- w(P_k(1-w)P_k (w)+P_k(w)P_k (1-w)P_k(1-w)P_k (w)+P_k(w)P_k (1-w) =0, =0, for w∈(0,1/2)w∈(0,1/2). Now we consider w→0w→ 0. We have that Pk(1−w)→0P_k(1-w)→ 0, Pk(w)=O(wk+1)P_k(w)=O(w^k+1), and Pk(1−w)Pk′(w)+Pk(w)Pk′(1−w)=O(wk)P_k(1-w)P_k (w)+P_k(w)P_k (1-w)=O(w^k) as w→0w→ 0. Plugging these expressions into γ0(w) _0(w), we have that γ0(w)→−∞ _0(w)→-∞ as w→0w→ 0. Evaluating γ1(1/2) _1(1/2), we will need Pk(12)=12−(2k)22k+1,Pk′(12)=k(2k)22k−1. P_k ( 12 )= 12- 2kk2^2k+1, P_k ( 12 )= k 2kk2^2k-1. Then we have γ1(12) _1 ( 12 ) =12−Pk(1/2)(Pk(1/2)+Pk(1/2))Pk′(1/2)Pk(1/2)+Pk′(1/2)Pk(1/2) = 12- P_k(1/2)(P_k(1/2)+P_k(1/2))P _k(1/2)P_k(1/2)+P_k (1/2)P_k(1/2) =12−Pk(1/2)Pk′(1/2) = 12- P_k(1/2)P _k(1/2) =12−12−(2k)22k+1k(2k)22k−1 = 12- 12- 2kk2^2k+1 k 2kk2^2k-1 =12−14k+22k4k(2k). = 12- 14k+ 2^2k4k 2kk. Therefore, γ0(1/2) _0(1/2) also since γ1(w)=γ0(1−w) _1(w)= _0(1-w). Let γ0(1/2)=γ1(1/2)=γk∗>0 _0(1/2)= _1(1/2)=γ^*_k>0. Therefore, as w moves from 1/21/2 to 00, the boundary eventually leaves the valid region γ0,γ1>0 _0, _1>0. Since γ1>0 _1>0, then it must be that it leaves on the γ0=0 _0=0 line. Hence, there exists a minimum value of w, i.e. wminw_ such that γ0(wmin)=0 _0(w_ )=0. Then, we immediately have that wmax=1−wminw_ =1-w_ , where γ1(wmax)=0 _1(w_ )=0. This completes the proof of the proposition. ∎ Appendix C Proof of Lemma 9 For notional simplicity we define β=α/3,l=n1/3κ1,L=n1/3κ2β=α/3,l=n^1/3 _1,L=n^1/3 _2. Then, it is easy to verify that z↦ψ(z)z ψ(z) defined by ψ(z)=∫zL∫−lvexp(−β(v3−u3))uv,ψ(z)= _z^L _-l^v (-β(v^3-u^3) )dudv, (19) solves (12) with the boundary conditions stated in the lemma. Furthermore, it is easy to see that ψ∈C3[−l,L]ψ∈ C^3[-l,L] and ψ≥0ψ≥ 0. This proves the first property of the lemma. Taking the derivative of (19) w.r.t z on both sides, we obtain ψ′(z)=−∫−lzexp(−β(z3−u3))du.ψ (z)=- _-l^z (-β(z^3-u^3) )du. (20) This immediately shows that ψ′≤0ψ ≤ 0. To prove the third property, it is sufficient to show that ψ(−l)ψ(-l) is bounded above by a constant independent of l and L since by the previous property we know that ψ is non-increasing in the interval [−l,L][-l,L]. Now, by definition we have ψ(−l)=∫−lL∫−lvexp(−β(v3−u3))uv≤∫−∞∫−∞vexp(−β(v3−u3))uv, ψ(-l)= _-l^L _-l^v (-β(v^3-u^3) )dudv≤ _-∞^∞ _-∞^v (-β(v^3-u^3) )dudv, where the inequality follows since the integrand is non-negative throughout the entire range of integration. We now show that the integral I=∫−∞∫−∞vexp(−β(v3−u3))uvI= _-∞^∞ _-∞^v (-β(v^3-u^3) )dudv is finite. Substituting v−u=sv-u=s we obtain I I =∫−∞∫0∞exp(−β(v3−(v−s)3))sv = _-∞^∞ _0^∞ (-β(v^3-(v-s)^3) )dsdv =∫−∞∫0∞exp(−β(3v2s−3vs2+s3))sv = _-∞^∞ _0^∞ (-β(3v^2s-3vs^2+s^3) )dsdv =∫0∞∫−∞exp(−β(3s(v−s2)2+s34))vs = _0^∞ _-∞^∞ (-β (3s (v- s2 )^2+ s^34 ) )dvds =∫0∞exp(−βs34)∫−∞exp(−3βs(v−s2)2)vs = _0^∞ (-β s^34 ) _-∞^∞ (-3β s (v- s2 )^2 )dvds =∫0∞exp(−βs34)π3βss = _0^∞ (-β s^34 ) π3β sds =21/3π33β2/3∫0∞t−5/6exp(−t)dt = 2^1/3 π3 3β^2/3 _0^∞t^-5/6 (-t)dt =21/3π33β2/3Γ(16)<∞. = 2^1/3 π3 3β^2/3 ( 16 )<∞. This establishes the third property. To establish the last property we note that ψ′(z)+2αzψ′(z)+αz2ψ′(z)=0ψ (z)+2α zψ (z)+α z^2ψ (z)=0 and ψ′(z)=−1−αz2ψ′(z)ψ (z)=-1-α z^2ψ (z). Combining the above two, we obtain ψ′(z)=αz2+α2z4ψ′(z)−2αzψ′(z) ψ (z)=α z^2+α^2z^4ψ (z)-2α zψ (z) =αz2+(α2z4−2αz)ψ′(z) =α z^2+(α^2z^4-2α z)ψ (z) =αz2+(2αz−α2z4)|ψ′(z)|. =α z^2+(2α z-α^2z^4) ψ (z) . (21) Thus, to bound |ψ′(z)||ψ (z)| we first need to bound |ψ′(z)||ψ (z)|. Choose a constant c>0c>0 sufficiently large such that α2z4−2αz≥0α^2z^4-2α z≥ 0 whenever z≥cz≥ c. For z<−c<0z<-c<0 using (20) we have |ψ′(z)| ψ (z) =∫−lzexp(−β(z3−u3))u = _-l^z (-β(z^3-u^3) )du ≤∫−∞zexp(−β(z3−u3))u ≤ _-∞^z (-β(z^3-u^3) )du =∫−∞zexp(−β(z−u)(z2+zu+u2))u = _-∞^z (-β(z-u)(z^2+zu+u^2) )du ≤∫−∞zexp(−3βz2(z−u))u ≤ _-∞^z (-3β z^2(z-u) )du =∫0∞exp(−3βz2s)s = _0^∞ (-3β z^2s )ds =13βz2=1αz2, = 13β z^2= 1α z^2, (22) where the second inequality follows since for u≤z≤0u≤ z≤ 0 we have zu+u2≥2z2zu+u^2≥ 2z^2. Similarly, for z∈[−c,c]z∈[-c,c] we have using (20) |ψ′(z)| |ψ (z)| =exp(−βz3)∫−lzexp(βu3)u = (-β z^3) _-l^z (β u^3)du ≤exp(βc3)∫−∞cexp(βu3)u ≤ (β c^3) _-∞^c (β u^3 )du ≤exp(βc3)(∫−∞0exp(βu3)u+∫0cexp(βu3)u) ≤ (β c^3) ( _-∞^0 (β u^3 )du+ _0^c (β u^3 )du ) ≤exp(βc3)3β1/3∫0∞s−2/3exp(−s)ds+cexp(2βc3) ≤ (β c^3)3β^1/3 _0^∞s^-2/3 (-s)ds+c (2β c^3) =K1, =K_1, (23) where K1=exp(βc3)3β1/3Γ(13)+cexp(2βc3)K_1= (β c^3)3β^1/3 ( 13 )+c (2β c^3). For z≥cz≥ c using (20) we have |ψ′(z)| ψ (z) ≤∫−∞zexp(−β(z3−u3))u ≤ _-∞^z (-β(z^3-u^3) )du =exp(−βz3)∫−∞0exp(βu3)u+∫0zexp(−β(z3−u3))u = (-β z^3) _-∞^0 (β u^3 )du+ _0^z (-β(z^3-u^3) )du ≤K2exp(−βz3)+∫0zexp(−β(z3−u3))u ≤ K_2 (-β z^3)+ _0^z (-β(z^3-u^3) )du =(a)K2exp(−βz3)+13βz2∫0βz3(1−tβz3)−2/3e−tdt (a)=K_2 (-β z^3)+ 13β z^2 _0^β z^3 (1- tβ z^3 )^-2/3e^-tdt =(b)K2exp(−βz3)+13βz2∫0m(1−tm)−2/3e−tdt (b)=K_2 (-β z^3)+ 13β z^2 _0^m (1- tm )^-2/3e^-tdt =K2exp(−βz3)+13βz2[∫0m/2(1−tm)−2/3e−tdt+∫m/2m(1−tm)−2/3e−tdt] =K_2 (-β z^3)+ 13β z^2 [ _0^m/2 (1- tm )^-2/3e^-tdt+ _m/2^m (1- tm )^-2/3e^-tdt ] ≤(c)K2exp(−βz3)+13βz2[∫0m/2(1+3tm)e−tdt+∫m/2m(1−tm)−2/3e−tdt] (c)≤K_2 (-β z^3)+ 13β z^2 [ _0^m/2 (1+ 3tm )e^-tdt+ _m/2^m (1- tm )^-2/3e^-tdt ] ≤K2exp(−βz3)+13βz2[(1+3m)+∫m/2m(1−tm)−2/3e−tdt] ≤ K_2 (-β z^3)+ 13β z^2 [ (1+ 3m )+ _m/2^m (1- tm )^-2/3e^-tdt ] ≤K2exp(−βz3)+13βz2[(1+3m)+e−m2∫m/2m(1−tm)−2/3dt] ≤ K_2 (-β z^3)+ 13β z^2 [ (1+ 3m )+e^- m2 _m/2^m (1- tm )^-2/3dt ] =K2exp(−βz3)+13βz2[(1+3m)+3m21/3e−m2] =K_2 (-β z^3)+ 13β z^2 [ (1+ 3m )+ 3m2^1/3e^- m2 ] =K2exp(−βz3)+13βz2+1β2z5+2−1/3ze−βz3/2 =K_2 (-β z^3)+ 13β z^2+ 1β^2z^5+2^-1/3ze^-β z^3/2 =K2exp(−βz3)+1αz2+1β2z5+2−1/3ze−βz3/2, =K_2 (-β z^3)+ 1α z^2+ 1β^2z^5+2^-1/3ze^-β z^3/2, (24) where K2=∫−∞0exp(βu3)u=13β1/3Γ(1/3)K_2= _-∞^0 (β u^3 )du= 13β^1/3 (1/3), (a) follows by substituting β(z3−u3)=tβ(z^3-u^3)=t,(b) follows from the letting m=βz3m=β z^3, and (c) follows from the fact that (1−x)−2/3≤1+3x(1-x)^-2/3≤ 1+3x for 0≤x≤1/20≤ x≤ 1/2. For z≥cz≥ c we also obtain the following lower bound using (20) |ψ′(z)| ψ (z) ≥∫0zexp(−β(z3−u3))u ≥ _0^z (-β(z^3-u^3) )du ≥∫0zexp(−3βz2(z−u))u ≥ _0^z (-3β z^2(z-u) )du =∫0zexp(−3βz2s)s=1−exp(−αz3)αz2, = _0^z (-3β z^2s )ds= 1- (-α z^3)α z^2, where the second inequality follows since z3−u3=(z−u)(z2+zu+u2)≤3z2(z−u)z^3-u^3=(z-u)(z^2+zu+u^2)≤ 3z^2(z-u) for 0≤u≤z0≤ u≤ z. Equipped with the above bounds on |ψ′(z)||ψ (z)| we now bound |ψ′(z)||ψ (z)|. For −l≤z<−c-l≤ z<-c using (21) we have ψ′(z)≤αz2≤n2/3ακ12ψ (z)≤α z^2≤ n^2/3α _1^2 since 2αz−α2z4<02α z-α^2z^4<0 for z<−c<0z<-c<0. For the same region, using (21) and (22) we have ψ′(z)≥2/zψ (z)≥ 2/z implying |ψ′(z)|=maxψ′(z),−ψ′(z)≤maxκ12αn2/3,2/|z|≤maxκ12αn2/3,2/c≤κ12αn2/3 ψ (z) = \ψ (z),-ψ (z)\≤ \ _1^2α n^2/3,2/|z|\≤ \ _1^2α n^2/3,2/c\≤ _1^2α n^2/3 for all sufficiently large n. From (21) and (23) we have supz∈[−c,c]|ψ′(z)|≤supz∈[−c,c]αz2+(2α|z|+α2z4)|ψ′(z)|≤αc2+(2αc+α2c4)K1≤n2/3ακ12, _z∈[-c,c]|ψ (z)|≤ _z∈[-c,c]α z^2+(2α|z|+α^2z^4)|ψ (z)|≤α c^2+(2α c+α^2c^4)K_1≤ n^2/3α _1^2, for all sufficiently large n. Finally, for z>cz>c, using (21) and (24) we have ψ′(z) ψ (z) ≥αz2+(2αz−α2z4)(K2exp(−βz3)+1αz2+1β2z5+2−1/3ze−βz3/2) ≥α z^2+(2α z-α^2z^4) (K_2 (-β z^3)+ 1α z^2+ 1β^2z^5+2^-1/3ze^-β z^3/2 ) =18αz4−7z+αK2z(2−αz3)exp(−αz33)+2−1/3αz2(2−αz3)exp(−αz36) = 18α z^4- 7z+α K_2z(2-α z^3) (- α z^33 )+2^-1/3α z^2 (2-α z^3 ) (- α z^36 ) =18αz4−7z+αz(2−αz3)(K2exp(−αz33)+2−1/3zexp(−αz36)) = 18α z^4- 7z+α z(2-α z^3) (K_2 (- α z^33 )+2^-1/3z (- α z^36 ) ) ≥−7z−(α2z4)(K2exp(−αz33)+2−1/3zexp(−αz36)), ≥- 7z-(α^2z^4) (K_2 (- α z^33 )+2^-1/3z (- α z^36 ) ), and ψ′(z)≤αz2+(2αz−α2z4)1−exp(−αz3)αz2≤2z+αz2exp(−αz3). ψ (z)≤α z^2+(2α z-α^2z^4) 1- (-α z^3)α z^2≤ 2z+α z^2 (-α z^3). Therefore, for suitably large c>0c>0, for all z≥cz≥ c and sufficiently large n we have supz∈[c,κ2n1/3]|ψ′(z)| _z∈[c, _2n^1/3]|ψ (z)| ≤supz∈[c,κ2n1/3]max2z+αz2exp(−αz3), ≤ _z∈[c, _2n^1/3] \ 2z+α z^2 (-α z^3), 7z+(α2z4)(K2exp(−αz33)+2−1/3zexp(−αz36)) 99.58464pt 7z+(α^2z^4) (K_2 (- α z^33 )+2^-1/3z (- α z^36 ) ) \ =max2c+αc2exp(−αc3), = \ 2c+α c^2 (-α c^3), 7c+(α2c4)(K2exp(−αc33)+2−1/3cexp(−αc36)). 99.58464pt 7c+(α^2c^4) (K_2 (- α c^33 )+2^-1/3c (- α c^36 ) ) \. This also concludes the second property of the lemma. Since the RHS of the above is a constant, for all sufficiently large n we have supz∈[c,κ2n1/3]|ψ′(z)|≤κ12αn2/3 _z∈[c, _2n^1/3]|ψ (z)|≤ _1^2α n^2/3. Hence, combining the bounds for all regions we obtain supz∈[−l,L]|ψ′(z)|≤n2/3ακ12 _z∈[-l,L]|ψ (z)|≤ n^2/3α _1^2 for all sufficiently large n. But at z=−lz=-l we have ψ′(−l)=0ψ (-l)=0. Hence, ψ′(−l)=αl2=n2/3ακ12ψ (-l)=α l^2=n^2/3α _1^2. Hence, we have shown that the supremum is achieved and this completes the proof of the last statement.∎ Appendix D Proof of Lemma 10 It is easy to verify that ψ as defined below satisfies (13) with the stated boundary conditions. ψ(z)=∫z0∫−κn1/4vexp(α4(v4−u4))uv. ψ(z)= _z^0 _-κ n^1/4^v ( α4(v^4-u^4) )dudv. Clearly, we have ψ′(z)=−∫−κn1/4zexp(α4(z4−u4))du≤0. ψ (z)=- _-κ n^1/4^z ( α4(z^4-u^4) )du≤ 0. This verifies the second property. The second property also implies that ψ(z)ψ(z) takes its maximum value in the range [−κn1/4,0][-κ n^1/4,0] when z=−κn1/4z=-κ n^1/4. Hence, to prove the third property it is sufficient to show that supnψ(−κn1/4)<∞ _nψ(-κ n^1/4)<∞. Now, we have ψ(−κn1/4) ψ(-κ n^1/4) =∫−κn1/40∫−κn1/4vexp(α4(v4−u4))uv = _-κ n^1/4^0 _-κ n^1/4^v ( α4(v^4-u^4) )dudv =∫−κn1/40∫u0exp(α4(v4−u4))vu = _-κ n^1/4^0 _u^0 ( α4(v^4-u^4) )dvdu ≤(a)∫−∞0∫u0exp(α4(v4−u4))vu (a)≤ _-∞^0 _u^0 ( α4(v^4-u^4) )dvdu =∫−∞0∫u0exp(α4(v−u)(v+u)(v2+u2))vu = _-∞^0 _u^0 ( α4(v-u)(v+u)(v^2+u^2) )dvdu ≤(b)∫−∞0∫u0exp(α4(v−u)u3)vu (b)≤ _-∞^0 _u^0 ( α4(v-u)u^3 )dvdu =∫−∞0∫0−uexp(α4su3)su = _-∞^0 _0^-u ( α4su^3 )dsdu =∫−∞04αu3(exp(−α4u4)−1)u = _-∞^0 4α u^3 ( (- α4u^4 )-1 )du =∫0∞4αu3(1−exp(−α4u4))u = _0^∞ 4α u^3 (1- (- α4u^4 ) )du ≤∫014αu3(1−exp(−α4u4))u+∫1∞4αu3u ≤ _0^1 4α u^3 (1- (- α4u^4 ) )du+ _1^∞ 4α u^3du ≤(c)∫014αu3α4u4u+2α (c)≤ _0^1 4α u^3 α4u^4du+ 2α =12+2α, = 12+ 2α, where (a) follows since the integrand is non-negative throughout the entire range of integration, (b) follows since u+v≤u≤0u+v≤ u≤ 0 and u2+v2≥u2≥0u^2+v^2≥ u^2≥ 0 and v−u≥0v-u≥ 0, and (c) follows since e−x≥1−xe^-x≥ 1-x for all x≥0x≥ 0. This establishes the third property of the lemma. To establish the final property of the lemma, note that ψ′(z)−3αz2ψ′(z)−αz3ψ′(z)=0ψ (z)-3α z^2ψ (z)-α z^3ψ (z)=0 and ψ′(z)=αz3ψ′(z)−1ψ (z)=α z^3ψ (z)-1. Therefore, ψ′(z)=−αz3+(α2z6+3αz2)ψ′(z)=−αz3−(α2z6+3αz2)|ψ′(z)|. ψ (z)=-α z^3+(α^2z^6+3α z^2)ψ (z)=-α z^3-(α^2z^6+3α z^2)|ψ (z)|. It is clear that α2z6+3αz2≥0α^2z^6+3α z^2≥ 0 for any z∈[−κn1/4,0]z∈[-κ n^1/4,0]. Consider |ψ′(z)||ψ (z)| in the region z∈[−κn1/4,−ϵ]z∈[-κ n^1/4,-ε]. Then we have that |ψ′(z)| |ψ (z)| =∫−κn1/4zexp(α4(z4−u4))u = _-κ n^1/4^z ( α4(z^4-u^4) )du ≤∫−∞zexp(α4(z4−u4))u ≤ _-∞^z ( α4(z^4-u^4) )du =∫−∞zexp(α4(z2−u2)(z2+u2))u = _-∞^z ( α4(z^2-u^2)(z^2+u^2) )du ≤∫−∞zexp(α4(z2−u2)(2z2))u ≤ _-∞^z ( α4(z^2-u^2)(2z^2) )du =∫−∞zexp(α2z2(z−u)(z+u))u = _-∞^z ( α2z^2(z-u)(z+u) )du ≤∫−∞zexp(α2z2(z−u)(2z))u ≤ _-∞^z ( α2z^2(z-u)(2z) )du =∫−∞zexp(αz3(z−u))u = _-∞^z (α z^3(z-u) )du =∫0∞exp(αz3s)s = _0^∞ (α z^3s)ds =−1αz3. =- 1α z^3. Therefore, for z∈[−κn1/4,−ϵ]z∈[-κ n^1/4,-ε], we have ψ′(z)≥−αz3−(α2z6+3αz2)(−1αz3)=3z. ψ (z)≥-α z^3-(α^2z^6+3α z^2) ( -1α z^3 )= 3z. We also have ψ′(z)≤−αz3. ψ (z)≤-α z^3. Therefore 3/z≤ψ′(z)≤−αz33/z≤ψ (z)≤-α z^3. Hence, |ψ′(z)|≤maxz∈[−κn1/4,−ϵ]α|z|3,3/|z||ψ (z)|≤ _z∈[-κ n^1/4,-ε]\α|z|^3,3/|z|\. For n, sufficiently large, we can conclude that supz∈[−κn1/4,−ϵ]|ψ′(z)|≤ακ3n3/4 _z∈[-κ n^1/4,-ε]|ψ (z)|≤ακ^3n^3/4. Now we focus on the region z∈(−ϵ,0]z∈(-ε,0]. In this region we have that |ψ′(z)| |ψ (z)| =∫−κn1/4zexp(α4(z4−u4))u = _-κ n^1/4^z ( α4(z^4-u^4) )du =exp(α4z4)∫−κn1/4zexp(−α4u4)u = ( α4z^4 ) _-κ n^1/4^z (- α4u^4 )du ≤exp(α4ϵ4)∫−κn1/4zexp(−α4u4)u ≤ ( α4ε^4 ) _-κ n^1/4^z (- α4u^4 )du ≤exp(α4ϵ4)∫−∞0exp(−α4u4)u ≤ ( α4ε^4 ) _-∞^0 (- α4u^4 )du =Γ(1/4)exp(α4ϵ4)22α1/4 = (1/4) ( α4ε^4 )2 2α^1/4 =Cα,ϵ. =C_α,ε. Then, for z∈(−ϵ,0]z∈(-ε,0], we can write ψ′(z)≤−αz3ψ (z)≤-α z^3 and ψ′(z) ψ (z) ≥−αz3−(α2z6+3αz2)Cα,ϵ ≥-α z^3-(α^2z^6+3α z^2)C_α,ε ≥−(α2ϵ6+3αϵ2)Cα,ϵ ≥-(α^2ε^6+3αε^2)C_α,ε =−(α2ϵ6+3αϵ2)Γ(1/4)exp(α4ϵ4)22α1/4. =-(α^2ε^6+3αε^2) (1/4) ( α4ε^4 )2 2α^1/4. Bringing these 2 bounds together, we can conclude that for every z∈(−ϵ,0]z∈(-ε,0] and sufficiently large n, we have that |ψ′(z)|≤maxαϵ3,(α2ϵ6+3αϵ2)Γ(1/4)exp(α4ϵ4)22α1/4. |ψ (z)|≤ \αε^3,(α^2ε^6+3αε^2) (1/4) ( α4ε^4 )2 2α^1/4 \. Then bringing together both regions we have that for all z∈[−κn1/4,0]z∈[-κ n^1/4,0]: |ψ′(z)|≤maxακ3n3/4,3ϵ,αϵ3,(α2ϵ6+3αϵ2)Γ(1/4)exp(α4ϵ4)22α1/4, |ψ (z)|≤ \ακ^3n^3/4, 3ε,αε^3,(α^2ε^6+3αε^2) (1/4) ( α4ε^4 )2 2α^1/4 \, which for fixed α,κ,ϵ>0α,κ,ε>0 and sufficiently large n, allows us to conclude that |ψ′(z)|≤ακ3n3/4|ψ (z)|≤ακ^3n^3/4. This concludes the final statement of the lemma. ∎