No Arabic abstract
Consider the complete graph on $n$ vertices. To each vertex assign an Ising spin that can take the values $-1$ or $+1$. Each spin $i in [n]={1,2,dots, n}$ interacts with a magnetic field $h in [0,infty)$, while each pair of spins $i,j in [n]$ interact with each other at coupling strength $n^{-1} J(i)J(j)$, where $J=(J(i))_{i in [n]}$ are i.i.d. non-negative random variables drawn from a prescribed probability distribution $mathcal{P}$. Spins flip according to a Metropolis dynamics at inverse temperature $beta in (0,infty)$. We show that there are critical thresholds $beta_c$ and $h_c(beta)$ such that, in the limit as $ntoinfty$, the system exhibits metastable behaviour if and only if $beta in (beta_c, infty)$ and $h in [0,h_c(beta))$. Our main result are sharp asymptotics, up to a multiplicative error $1+o_n(1)$, of the average crossover time from any metastable state to the set of states with lower free energy. We use standard techniques of the potential-theoretic approach to metastability. The leading order term in the asymptotics does not depend on the realisation of $J$, while the correction terms do. The leading order of the correction term is $sqrt{n}$ times a centred Gaussian random variable with a complicated variance depending on $beta,h,mathcal{P}$ and on the metastable state. The critical thresholds $beta_c$ and $h_c(beta)$ depend on $mathcal{P}$, and so does the number of metastable states. We derive an explicit formula for $beta_c$ and identify some properties of $beta mapsto h_c(beta)$. Interestingly, the latter is not necessarily monotone, meaning that the metastable crossover may be re-entrant.
Consider random $d$-regular graphs, i.e., random graphs such that there are exactly $d$ edges from each vertex for some $dge 3$. We study both the configuration model version of this graph, which has occasional multi-edges and self-loops, as well as the simple version of it, which is a $d$-regular graph chosen uniformly at random from the collection of all $d$-regular graphs. In this paper, we discuss mixing times of Glauber dynamics for the Ising model with an external magnetic field on a random $d$-regular graph, both in the quenched as well as the annealed settings. Let $beta$ be the inverse temperature, $beta_c$ be the critical temperature and $B$ be the external magnetic field. Concerning the annealed measure, we show that for $beta > beta_c$ there exists $hat{B}_c(beta)in (0,infty)$ such that the model is metastable (i.e., the mixing time is exponential in the graph size $n$) when $beta> beta_c$ and $0 leq B < hat{B}_c(beta)$, whereas it exhibits the cut-off phenomenon at $c_star n log n$ with a window of order $n$ when $beta < beta_c$ or $beta > beta_c$ and $B>hat{B}_c(beta)$. Interestingly, $hat{B}_c(beta)$ coincides with the critical external field of the Ising model on the $d$-ary tree (namely, above which the model has a unique Gibbs measure). Concerning the quenched measure, we show that there exists $B_c(beta)$ with $B_c(beta) leq hat{B}_c(beta)$ such that for $beta> beta_c$, the mixing time is at least exponential along some subsequence $(n_k)_{kgeq 1}$ when $0 leq B < B_c(beta)$, whereas it is less than or equal to $Cnlog n$ when $B>hat{B}_c(beta)$. The quenched results also hold for the model conditioned on simplicity, for the annealed results this is unclear.
We study the Glauber dynamics for the Ising model on the complete graph, also known as the Curie-Weiss Model. For beta < 1, we prove that the dynamics exhibits a cut-off: the distance to stationarity drops from near 1 to near 0 in a window of order n centered at [2(1-beta)]^{-1} n log n. For beta = 1, we prove that the mixing time is of order n^{3/2}. For beta > 1, we study metastability. In particular, we show that the Glauber dynamics restricted to states of non-negative magnetization has mixing time O(n log n).
We consider a model of language development, known as the naming game, in which agents invent, share and then select descriptive words for a single object, in such a way as to promote local consensus. When formulated on a finite and connected graph, a global consensus eventually emerges in which all agents use a common unique word. Previous numerical studies of the model on the complete graph with $n$ agents suggest that when no words initially exist, the time to consensus is of order $n^{1/2}$, assuming each agent speaks at a constant rate. We show rigorously that the time to consensus is at least $n^{1/2-o(1)}$, and that it is at most constant times $log n$ when only two words remain. In order to do so we develop sample path estimates for quasi-left continuous semimartingales with bounded jumps.
Red and blue particles are placed in equal proportion through-out either the complete or star graph and iteratively sampled to take simple random walk steps. Mutual annihilation occurs when particles with different colors meet. We compare the time it takes to extinguish every particle to the analogous time in the (simple to analyze) one-type setting. Additionally, we study the effect of asymmetric particle speeds.
We obtain scaling limit results for asymmetric trap models and their infinite volume counterparts, namely asymmetric K processes. Aging results for the latter processes are derived therefrom.