JMP Nameplate
  • Volume/Page
  • Keyword
  • DOI
  • Citation
  • Advanced
   
 
 
 

Flickr Twitter iResearch App Facebook

Search Issue | RSS Feeds RSS
Previous Issue

Dec 2008

Volume 49, Issue 12, Articles (12xxxx)

Issue Cover Spotlight Figure

J. Math. Phys. 49, 125206 (2008); http://dx.doi.org/10.1063/1.2982805 (6 pages)

Mohsen Bayati, Alfredo Braunstein, and Riccardo Zecchina
Enlarge Image | Read More
back to top
RSS Feeds

Introduction to Special Issue: Statistical Mechanics on Random Structures

Pierluigi Contucci and Cristian Giardinà

J. Math. Phys. 49, 125101 (2008); http://dx.doi.org/10.1063/1.3030977 (2 pages)

Online Publication Date: 1 December 2008

Full Text: Read Online (HTML) | Download PDF

Abstract Unavailable
Show PACS
01.60.+q Biographies, tributes, personal notes, and obituaries
01.10.Cr Announcements, news, and awards

The interaction between multioverlaps in the high temperature phase of the Sherrington–Kirkpatrick spin glass

Nicholas Crawford

J. Math. Phys. 49, 125201 (2008); http://dx.doi.org/10.1063/1.2966275 (24 pages)

Online Publication Date: 2 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
In this paper we explore the joint behavior of a finite number of multioverlaps in the high temperature phase of the Sherrington–Kirkpatrick model. Extending the work by Talagrand [Spin Glasses: A Challenge for Mathematicians. Cavity and Mean Field Models, A series of Modern Surveys in Mathematics Vol. 46 (Springer-Verlag, Berlin, 2003)] , we show that, when these objects are scaled to have nontrivial limiting distributions, the joint behavior is described by a Gaussian process with an explicit covariance structure.
Show PACS
75.10.Nr Spin-glass and other random models

Fluctuations of the partition function in the generalized random energy model with external field

Anton Bovier and Anton Klimovsky

J. Math. Phys. 49, 125202 (2008); http://dx.doi.org/10.1063/1.2962982 (27 pages)

Online Publication Date: 3 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We study Derrida’s generalized random energy model (GREM) in the presence of uniform external field. We compute the fluctuations of the ground state and of the partition function in the thermodynamic limit for all admissible values of parameters. We find that the fluctuations are described by a hierarchical structure which is obtained by a certain coarse graining of the initial hierarchical structure of the GREM with external field. We provide an explicit formula for the free energy of the model. We also derive some large deviation results providing an expression for the free energy in a class of models with Gaussian Hamiltonians and external field. Finally, we prove that the coarse-grained parts of the system emerging in the thermodynamic limit tend to have a certain optimal magnetization, as prescribed by the strength of the external field and by parameters of the GREM.
Show PACS
75.10.Nr Spin-glass and other random models
75.60.Ej Magnetization curves, hysteresis, Barkhausen and related effects

Minimal supporting subtrees for the free energy of polymers on disordered trees

Peter Mörters and Marcel Ortgiese

J. Math. Phys. 49, 125203 (2008); http://dx.doi.org/10.1063/1.2962981 (21 pages) | Cited 1 time

Online Publication Date: 4 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We consider a model of directed polymers on a regular tree with a disorder given by independent, identically distributed weights attached to the vertices. For suitable weight distributions this model undergoes a phase transition with respect to its localization behavior. We show that, for high temperatures, the free energy is supported by a random tree of positive exponential growth rate, which is strictly smaller than that of the full tree. The growth rate of the minimal supporting subtree decreases to zero as the temperature decreases to the critical value. At the critical value and all lower temperatures, a single polymer suffices to support the free energy. Our proofs rely on elegant martingale methods adapted from the theory of branching random walks.
Show PACS
64.60.A- Specific approaches applied to studies of phase transitions
65.60.+a Thermal properties of amorphous solids and glasses: heat capacity, thermal expansion, etc.
61.41.+e Polymers, elastomers, and plastics

A remark on the infinite-volume Gibbs measures of spin glasses

Louis-Pierre Arguin

J. Math. Phys. 49, 125204 (2008); http://dx.doi.org/10.1063/1.2966281 (8 pages) | Cited 1 time

Online Publication Date: 5 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
In this note, we point out that infinite-volume Gibbs measures of spin glass models on the hypercube can be identified as random probability measures on the unit ball of a Hilbert space. This simple observation follows from a result of Dovbysh and Sudakov on weakly exchangeable random matrices. Limiting Gibbs measures can then be studied as single well-defined objects. This approach naturally extends the space of random overlap structures as defined by Aizenman et al. We discuss the Ruelle probability cascades and the stochastic stability within this framework. As an application, we use an idea of Parisi and Talagrand to prove that if a sequence of finite-volume Gibbs measures satisfies the Ghirlanda–Guerra identities, then the infinite-volume measure must be singular as a measure on a Hilbert space.
Show PACS
05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion
02.50.Cw Probability theory
02.50.Ey Stochastic processes

Universal structures in some mean field spin glasses and an application

Erwin Bolthausen and Nicola Kistler

J. Math. Phys. 49, 125205 (2008); http://dx.doi.org/10.1063/1.2973818 (17 pages)

Online Publication Date: 8 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We discuss a spin glass reminiscent of the random energy model (REM), which allows, in particular, to recast the Parisi minimization into a more classical Gibbs variational principle, thereby shedding some light into the physical meaning of the order parameter of the Parisi theory. As an application, we study the impact of an extensive cavity field on Derrida’s REM: Despite its simplicity, this model displays some interesting features such as ultrametricity and chaos in temperature.
Show PACS
75.10.Nr Spin-glass and other random models
05.70.Ce Thermodynamic functions and equations of state
05.45.-a Nonlinear dynamics and chaos
05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion
02.50.-r Probability theory, stochastic processes, and statistics

A rigorous analysis of the cavity equations for the minimum spanning tree

Mohsen Bayati, Alfredo Braunstein, and Riccardo Zecchina

J. Math. Phys. 49, 125206 (2008); http://dx.doi.org/10.1063/1.2982805 (6 pages) | Cited 2 times

Online Publication Date: 9 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We analyze a new general representation for the minimum weight Steiner tree problem that translates the topological connectivity constraint into a set of local conditions, which can be analyzed by the so-called cavity equation techniques. For the limit case of the spanning tree, we prove that the fixed point of the algorithm arising from the cavity equations leads to the global optimum.
Show PACS
02.10.Ox Combinatorics; graph theory
02.40.Re Algebraic topology

Susceptibility in subcritical random graphs

Svante Janson and Malwina J. Luczak

J. Math. Phys. 49, 125207 (2008); http://dx.doi.org/10.1063/1.2982848 (23 pages)

Online Publication Date: 10 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We study the evolution of the susceptibility in the subcritical random graph G(n,p) as n tends to infinity. We obtain precise asymptotics of its expectation and variance and show that it obeys a law of large numbers. We also prove that the scaled fluctuations of the susceptibility around its deterministic limit converge to a Gaussian law. We further extend our results to higher moments of the component size of a random vertex and prove that they are jointly asymptotically normal.
Show PACS
05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion
02.50.-r Probability theory, stochastic processes, and statistics
02.10.Ox Combinatorics; graph theory

Loss and recovery of Gibbsianness for XY models in external fields

A. C. D. van Enter and W. M. Ruszel

J. Math. Phys. 49, 125208 (2008); http://dx.doi.org/10.1063/1.2989145 (8 pages) | Cited 2 times

Online Publication Date: 11 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We consider planar rotors (XY spins) in mathd, starting from an initial Gibbs measure and evolving with infinite-temperature stochastic (diffusive) dynamics. At intermediate times, if the system starts at low temperature, Gibbsianness can be lost. Due to the influence of the external initial field, Gibbsianness can be recovered after large finite times. We prove some results supporting this picture.
Show PACS
75.10.Hk Classical spin models
05.60.-k Transport processes
02.50.Ey Stochastic processes
05.10.Gg Stochastic analysis methods (Fokker-Planck, Langevin, etc.)
05.50.+q Lattice theory and statistics (Ising, Potts, etc.)

Universality for distances in power-law random graphs

Remco van der Hofstad and Gerard Hooghiemstra

J. Math. Phys. 49, 125209 (2008); http://dx.doi.org/10.1063/1.2982927 (14 pages)

Online Publication Date: 12 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We survey the recent work on phase transition and distances in various random graph models with general degree sequences. We focus on inhomogeneous random graphs, the configuration model, and affine preferential attachment models, and pay special attention to the setting where these random graphs have a power-law degree sequence. This means that the proportion of vertices with degree k in large graphs is approximately proportional to k−τ for some τ>1. Since many real networks have been empirically shown to have power-law degree sequences, these random graphs can be seen as more realistic models for real complex networks than classical random graphs such as the Erdős–Rényi random graph. It is often suggested that the behavior of random graphs should have a large amount of universality, meaning, in this case, that random graphs with similar degree sequences share similar behavior. We survey the available results on graph distances in power-law random graphs that are consistent with this prediction.
Show PACS
05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion
02.50.-r Probability theory, stochastic processes, and statistics
02.10.Ox Combinatorics; graph theory
05.70.Fh Phase transitions: general studies

Mathematical foundation of quantum annealing

Satoshi Morita and Hidetoshi Nishimori

J. Math. Phys. 49, 125210 (2008); http://dx.doi.org/10.1063/1.2995837 (47 pages) | Cited 10 times

Online Publication Date: 15 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
Quantum annealing is a generic name of quantum algorithms that use quantum-mechanical fluctuations to search for the solution of an optimization problem. It shares the basic idea with quantum adiabatic evolution studied actively in quantum computation. The present paper reviews the mathematical and theoretical foundations of quantum annealing. In particular, theorems are presented for convergence conditions of quantum annealing to the target optimal state after an infinite-time evolution following the Schrödinger or stochastic (Monte Carlo) dynamics. It is proved that the same asymptotic behavior of the control parameter guarantees convergence for both the Schrödinger dynamics and the stochastic dynamics in spite of the essential difference of these two types of dynamics. Also described are the prescriptions to reduce errors in the final approximate solution obtained after a long but finite dynamical evolution of quantum annealing. It is shown there that we can reduce errors significantly by an ingenious choice of annealing schedule (time dependence of the control parameter) without compromising computational complexity qualitatively. A review is given on the derivation of the convergence condition for classical simulated annealing from the view point of quantum adiabaticity using a classical-quantum mapping.
Show PACS
03.67.Ac Quantum algorithms, protocols, and simulations
03.65.Ge Solutions of wave equations: bound states
05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion
03.65.Ta Foundations of quantum mechanics; measurement theory
03.67.Lx Quantum computation architectures and implementations

An example of mathematical authorship attribution

Chiara Basile, Dario Benedetto, Emanuele Caglioti, and Mirko Degli Esposti

J. Math. Phys. 49, 125211 (2008); http://dx.doi.org/10.1063/1.2996507 (20 pages) | Cited 1 time

Online Publication Date: 16 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
In this paper we discuss a novel mathematical approach to authorship attribution which we implemented recently to face a concrete problem of author recognition. The fundamental ideas for our methods came from statistical mechanics and information theory. We combine two approaches. Both of them use similarity measures between couples of texts as indicators of stylistic closeness: the first one is based on the comparison of frequencies of fixed length substrings (n-grams) throughout the texts; the second one relies on a suitable use of compression algorithms as relative entropy approximators, in the spirit of the so-called Ziv–Merhav theorem. The two methods were separately developed and then combined, together with a suitable and theoretically founded ranking analysis, to produce an original authorship attribution procedure that yielded very successful results on the specific problem to which it was applied. This ranking analysis could be of interest also in other application fields.
Show PACS
05.70.Ce Thermodynamic functions and equations of state
89.70.Cf Entropy and other measures of information

A mean field model for spin glasses based on a 2-level perceptron

Michel Talagrand

J. Math. Phys. 49, 125212 (2008); http://dx.doi.org/10.1063/1.2992583 (23 pages)

Online Publication Date: 17 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We introduce a mean field model for spin glasses that is obtained by “iterating” the definition of the perceptron model of [SG] and we prove the validity of the replica-symmetric solution under a condition of the type “high temperature.” The replica-symmetric equations involve six different parameters. This model illustrates, on one hand, that we now have efficient tools to deal with such systems, and on the other hand, that it is probably unreasonable to hope for abstract theorems independent of the specific type of the system.
Show PACS
75.10.Nr Spin-glass and other random models

Central limit theorem and recurrence for random walks in bistochastic random environments

Marco Lenci

J. Math. Phys. 49, 125213 (2008); http://dx.doi.org/10.1063/1.3005226 (9 pages) | Cited 2 times

Online Publication Date: 18 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We prove the annealed central limit theorem for random walks in bistochastic random environments on mathd with zero-local drift. The proof is based on a “dynamicist’s interpretation” of the system and requires a much weaker condition than the customary uniform ellipticity. Moreover, recurrence is derived for d ≤ 2.
Show PACS
05.40.Fb Random walks and Levy flights
02.50.Ey Stochastic processes

Coupling, concentration inequalities, and stochastic dynamics

Jean-René Chazottes, Pierre Collet, and Frank Redig

J. Math. Phys. 49, 125214 (2008); http://dx.doi.org/10.1063/1.2995833 (22 pages) | Cited 1 time

Online Publication Date: 19 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
In the context of interacting particle systems, we study the influence of the action of the semigroup on the concentration property of Lipschitz functions. As an application, this gives a new approach to estimate the relaxation speed to equilibrium of interacting particle systems. We illustrate our approach in a variety of examples for which we obtain several new results with short and nontechnical proofs. These examples include the symmetric and asymmetric exclusion processes and high-temperature spin-flip dynamics (“Glauber dynamics”). We also give a new proof of the Poincaré inequality, based on coupling, in the context of one-dimensional Gibbs measures. In particular, we cover the case of polynomially decaying potentials, where the log-Sobolev inequality does not hold.
Show PACS
05.40.Fb Random walks and Levy flights
05.50.+q Lattice theory and statistics (Ising, Potts, etc.)
02.50.Ey Stochastic processes
02.20.-a Group theory

Continuous spin mean-field models: Limiting kernels and Gibbs properties of local transforms

Christof Külske and Alex A. Opoku

J. Math. Phys. 49, 125215 (2008); http://dx.doi.org/10.1063/1.3021285 (31 pages) | Cited 2 times

Online Publication Date: 22 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We extend the notion of Gibbsianness for mean-field systems to the setup of general (possibly continuous) local state spaces. We investigate the Gibbs properties of systems arising from an initial mean-field Gibbs measure by application of given local transition kernels. This generalizes previous case studies made for spins taking finitely many values to the first step in the direction to a general theory containing the following parts: (1) A formula for the limiting conditional probability distributions of the transformed system (it holds both in the Gibbs and in the non-Gibbs regime and invokes a minimization problem for a “constrained rate function”), (2) a criterion for Gibbsianness of the transformed system for initial Lipschitz–Hamiltonians involving concentration properties of the transition kernels, and (3) a continuity estimate for the single-site conditional distributions of the transformed system. While (2) and (3) have provable lattice counterparts, the characterization of (1) is stronger in mean field. As applications we show short-time Gibbsianness of rotator mean-field models on the (q−1)-dimensional sphere under diffusive time evolution and the preservation of Gibbsianness under local coarse graining of the initial local spin space.
Show PACS
05.50.+q Lattice theory and statistics (Ising, Potts, etc.)
05.70.Fh Phase transitions: general studies

On the survey-propagation equations in random constraint satisfiability problems

Giorgio Parisi

J. Math. Phys. 49, 125216 (2008); http://dx.doi.org/10.1063/1.3030862 (16 pages)

Online Publication Date: 23 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
In this paper we study the existence of a solution of the survey-propagation equations for a given instance of a random problem in the framework of constraint satisfiability. We consider the concrete examples of K-satisfiability and coloring. We conjecture that when the number of variables goes to infinity, the solution of the survey-propagation equations for a given instance can be obtained by finding the (supposed unique) solution of the corresponding equations on an infinite tree. We conjecture that the survey-propagation equations on a random infinite tree have a unique solution in the suitable range of parameters. We also present analytic arguments that indicate that the survey-propagation equations do have solutions in the satisfiable phase. For simplicity of notation the argument is presented in the case of the coloring problem. The same results extend to other optimization problems where exist configurations that have cost zero, i.e., in the satisfiable phase. On a random graph the solutions of the belief-propagation equations are associated with the existence of many well separated clusters of configurations (clustering states). We argue that on a random graph the belief-propagation equations have solutions almost everywhere: the statement may be sharpened by introducing the concept of quasisolution of the belief-propagation equations.
Show PACS
05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion
02.50.-r Probability theory, stochastic processes, and statistics
02.10.Ox Combinatorics; graph theory

About the ergodic regime in the analogical Hopfield neural networks: Moments of the partition function

Adriano Barra and Francesco Guerra

J. Math. Phys. 49, 125217 (2008); http://dx.doi.org/10.1063/1.3039083 (18 pages) | Cited 8 times

Online Publication Date: 24 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
In this paper we introduce and exploit the real replica approach for a minimal generalization of the Hopfield model by assuming the learned patterns to be distributed according to a standard unit Gaussian. We consider the high storage case, when the number of patterns linearly diverges with the number of neurons. We study the infinite volume behavior of the normalized momenta of the partition function. We find a region in the parameter space where the free energy density in the infinite volume limit self-averages around its annealed approximation, as well as the entropy and the internal energy density. Moreover, we evaluate the corrections to their extensive counterparts with respect to their annealed expressions. The fluctuations of properly introduced overlaps, which act as order parameters, are also discussed.
Show PACS
05.70.Ce Thermodynamic functions and equations of state
05.45.-a Nonlinear dynamics and chaos
89.70.Cf Entropy and other measures of information
89.75.Kd Patterns
05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion

First passage percolation on locally treelike networks. I. Dense random graphs

Shankar Bhamidi

J. Math. Phys. 49, 125218 (2008); http://dx.doi.org/10.1063/1.3039876 (27 pages) | Cited 3 times

Online Publication Date: 29 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
We study various properties of least cost paths under independent and identically distributed (iid) disorder for the complete graph and dense Erdős–Rényi random graphs in the connected phase, with iid exponential and uniform weights on edges. Using a simple heuristic, we compute explicitly limiting distributions for (properly recentered) lengths of shortest paths between typical nodes as well as multiple source destination pairs; we also derive asymptotics for the number of edges on the shortest path, namely, the hopcount, and find that the addition of edge weights converts these graphs from ultrasmall world networks to small world networks. Finally we study the Vickrey–Clarke–Groves measure of overpayment for the complete graph with exponential edge weights and show that the complete graph is far from monopolistic for large n.
Show PACS
02.10.Ox Combinatorics; graph theory
02.50.Cw Probability theory

The peculiar phase structure of random graph bisection

Allon G. Percus, Gabriel Istrate, Bruno Gonçalves, Robert Z. Sumi, and Stefan Boettcher

J. Math. Phys. 49, 125219 (2008); http://dx.doi.org/10.1063/1.3043666 (13 pages) | Cited 3 times

Online Publication Date: 31 December 2008

Full Text: Read Online (HTML) | Download PDF

Show Abstract
The mincut graph bisection problem involves partitioning the n vertices of a graph into disjoint subsets, each containing exactly n/2 vertices, while minimizing the number of “cut” edges with an endpoint in each subset. When considered over sparse random graphs, the phase structure of the graph bisection problem displays not only certain familiar properties but also some surprises. It is known that when the mean degree is below the critical value of 2 log 2, the cutsize is zero with high probability. We study how the minimum cutsize increases with mean degree above this critical threshold, finding a new analytical upper bound that improves considerably upon previous bounds. Combined with recent results on expander graphs, our bound suggests the unusual scenario that random graph bisection is replica symmetric up to and beyond the critical threshold, with a replica symmetry breaking transition possibly taking place above the threshold. An intriguing algorithmic consequence is that although the problem is NP-hard, we can conceivably find near-optimal cutsizes (whose ratio to the optimal value approaches 1 asymptotically) in polynomial time for typical instances near the phase transition.
Show PACS
05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion
02.50.-r Probability theory, stochastic processes, and statistics
02.10.Ox Combinatorics; graph theory
Close

Google Calendar

ADVERTISEMENT

Go to AIP Home   © AIP Publishing LLC
close