A universal scaling theory for complexity of analog computation

We discuss the computational complexity of solving linear programming problems by means of an analog computer. The latter is modeled by a dynamical system which converges to the optimal vertex solution. We analyze various probability ensembles of linear programming problems. For each one of these we obtain numerically the probability distribution functions of certain quantities which measure the complexity. Remarkably, in the asymptotic limit of very large problems, each of these probability distribution functions reduces to a universal scaling function, depending on a single scaling variable and independent of the details of its parent probability ensemble. These functions are reminiscent of the scaling functions familiar in the theory of phase transitions. The results reported here extend analytical and numerical results obtained recently for the Gaussian ensemble.     

Computational complexity of impact size estimation for spreading processes on networks

Spreading processes on networks are often analyzed to understand how the outcome of the process (e.g. the number of affected nodes) depends on structural properties of the underlying network. Most available results are ensemble averages over certain interesting graph classes such as random graphs or graphs with a particular degree distributions. In this paper, we focus instead on determining the expected spreading size and the probability of large spreadings for a single (but arbitrary) given network and study the computational complexity of these problems using reductions from well-known network reliability problems. We show that computing both quantities exactly is intractable, but that the expected spreading size can be efficiently approximated with Monte Carlo sampling. When nodes are weighted to reflect their importance, the problem becomes as hard as the s-t reliability problem, which is not known to yield an efficient randomized approximation scheme up to now. Finally, we give a formal complexity-theoretic argument why there is most likely no randomized constant-factor approximation for the probability of large spreadings, even for the unweighted case. A hybrid Monte Carlo sampling algorithm is proposed that resorts to specialized s-t reliability algorithms for accurately estimating the infection probability of those nodes that are rarely affected by the spreading process.     

The Ginibre Ensemble of Real Random Matrices and its Scaling Limits

We give a closed form for the correlation functions of ensembles of a class of asymmetric real matrices in terms of the Pfaffian of an antisymmetric matrix formed from a 2 × 2 matrix kernel associated to the ensemble. We apply this result to the real Ginibre ensemble and compute the bulk and edge scaling limits of its correlation functions as the size of the matrices becomes large.     

Invariant Measures for Passive Scalars in the Small Noise Inviscid Limit

We study the singular values of the product of two coupled rectangular random matrices as a determinantal point process. Each of the two factors is given by a parameter dependent linear combination of two independent, complex Gaussian random matrices, which is equivalent to a coupling of the two factors via an Itzykson-Zuber term. We prove that the squared singular values of such a product form a biorthogonal ensemble and establish its exact solvability. The parameter dependence allows us to interpolate between the singular value statistics of the Laguerre ensemble and that of the product of two independent complex Ginibre ensembles which are both known. We give exact formulae for the correlation kernel in terms of a complex double contour integral, suitable for the subsequent asymptotic analysis. In particular, we derive a Christoffel–Darboux type formula for the correlation kernel, based on a five term recurrence relation for our biorthogonal functions. It enables us to find its scaling limit at the origin representing a hard edge. The resulting limiting kernel coincides with the universal Meijer G-kernel found by several authors in different ensembles. We show that the central limit theorem holds for the linear statistics of the singular values and give the limiting variance explicitly.     

System size resonance in coupled noisy systems and in the Ising model

We consider an ensemble of coupled nonlinear noisy oscillators demonstrating in the thermodynamic limit an Ising-type transition. In the ordered phase and for finite ensembles stochastic flips of the mean field are observed with the rate depending on the ensemble size. When a small periodic force acts on the ensemble, the linear response of the system has a maximum at a certain system size, similar to the stochastic resonance phenomenon. We demonstrate this effect of system size resonance for different types of noisy oscillators and for different ensembles---lattices with nearest neighbors coupling and globally coupled populations. The Ising model is also shown to demonstrate the system size resonance.     

Complexity of hierarchical ensembles

Within the framework of generalized combinatorial approaches, complexity is determined as a disorder measure for hierarchical statistical ensembles related to Cayley trees possessing arbitrary branching and number of levels. With strengthening hierarchical coupling, the complexity is shown to increase monotonically to the limit value that grows with tree branching. In contrast to the temperature dependence of thermodynamic entropy, the complexity is reduced by the variance of hierarchical statistical ensemble if the branching exponent does not exceed the gold mean. Time dependencies are found for both the probability distribution over ensemble states and the related complexity. The latter is found explicitly for self-similar ensemble and generalized for arbitrary hierarchical trees.     

Current Distribution and Random Matrix Ensembles for an Integrable Asymmetric Fragmentation Process

We calculate the time-evolution of a discrete-time fragmentation process in which clusters of particles break up and reassemble and move stochastically with size-dependent rates. In the continuous-time limit the process turns into the totally asymmetric simple exclusion process (only pieces of size 1 break off a given cluster). We express the exact solution of the master equation for the process in terms of a determinant which can be derived using the Bethe ansatz. From this determinant we compute the distribution of the current across an arbitrary bond which after appropriate scaling is given by the distribution of the largest eigenvalue of the Gaussian unitary ensemble of random matrices. This result confirms universality of the scaling form of the current distribution in the KPZ universality class and suggests that there is a link between integrable particle systems and random matrix ensembles.     

Variational principle for regular and random Ising models on the cactus tree or on the usual lattice in the “cactus approximation”

The distribution functions and the free energy are expressed in terms of the effective fields for the regular and random Ising models of an arbitrary spin S on the generalized cactus tree. The same expressions apply to systems on the usual lattice in the “cactus approximation” in the cluster variation method. For an ensemble of random Ising models of an arbitrary spin S on the generalized cactus tree, the equation for the probability distribution function of the effective fields is set up and the averaged free energy is expressed in terms of the probability distribution. The same expressions apply to the system on the usual lattice in the “cactus approximation”. We discuss the quantities on the usual lattice when the system or the ensemble of random systems has the translational symmetry. Variational properties of the free energy for a system and of the averaged free energy for an ensemble of random systems are noted. The “cactus approximations” are applicable to the Heisenberg model as well as to the Ising model of an arbitrary spin, and to ensembles of random systems of these models.     

A new analytic solution for the Zwanzig-Lauritzen model of polymer chain folding

A two-dimensional model of polymer chain folding invented by Zwanzig and Lauritzen is here studied using a grand ensemble and transfer matrix method. Due to the character of the model, there are no extensive parameters in the grand ensemble and the dispersion in system size is large, raising doubts about the validity and usefulness of the ensemble. We find it possible to define a thermodynamic limit such that it leads to near equivalence between the canonical and grand ensembles in the limit of large systems. The transfer matrix in this case is a nonlocal operator on a space of L₂ functions, and the eigenvalue equation is a homogeneous Fredholm integral equation of the second kind which can be completely solved in terms of Bessel functions. The grand partition function can then be expressed as a sum of powers of the known eigenvalues. It is an easy matter to reproduce the second-order phase transition in the canonical ensemble found in the original work on the model. The investigation is extended to yield the probability densities describing the length of a segment and the correlations among segments. The concept of a local width of the folded chain is found to break down at higher temperatures, while critical correlations are characterized by infinite range, as expected. Apart from physical and methodological implications, the new solution provides striking illustrations of some basic ideas concerning phase transitions.     

Spectral Properties of the k-Body Embedded Gaussian Ensembles of Random Matrices for Bosons

We consider m spinless Bosons distributed over l degenerate single-particle states and interacting through a k-body random interaction with Gaussian probability distribution (the Bosonic embedded k-body ensembles). We address the cases of orthogonal and unitary symmetry in the limit of infinite matrix dimension, attained either as l→∞ or as m→∞. We derive an eigenvalue expansion for the second moment of the many-body matrix elements of these ensembles. Using properties of this expansion, the supersymmetry technique, and the binary correlation method, we show that in the limit l→∞ the ensembles have nearly the same spectral properties as the corresponding Fermionic embedded ensembles. Novel features specific for Bosons arise in the dense limit defined as m→∞ with both k and l fixed. Here we show that the ensemble is not ergodic and that the spectral fluctuations are not of Wigner-Dyson type. We present numerical results for the dense limit using both ensemble unfolding and spectral unfolding. These differ strongly, demonstrating the lack of ergodicity of the ensemble. Spectral unfolding shows a strong tendency toward picket-fence-type spectra. Certain eigenfunctions of individual realizations of the ensemble display Fock-space localization.     

Applications of the Dotsenko-Fateev integral in random-matrix models

The characteristic multi-dimensional integrals that represent physical quantities in random-matrix models, when calculated within the supersymmetry method, can be related to a class of integrals introduced in the context of two-dimensional conformal field theories by Dotsenko and Fateev. Known results on these Dotsenko-Fateev integrals provide a means by which to perform explicit calculations (otherwise difficult) in random-matrix theory. We illustrate this by (i) an evaluation of the mean squared S-matrix elements for the Gaussian orthogonal ensemble coupled with M external channels, and (ii) a direct derivation of the asymptotic behaviour of the dynamical density-density cotrelator in the limit of large spatial and temporal separation for the Calogero-Sutherland model which, at certain couplings, is known to map onto the parameter-dependent random-matrix ensembles.     

Hydrodynamic Limit for an Evolutional Model of Two-Dimensional Young Diagrams

We construct dynamics of two-dimensional Young diagrams, which are naturally associated with their grandcanonical ensembles, by allowing the creation and annihilation of unit squares located at the boundary of the diagrams. The grandcanonical ensembles, which were introduced by Vershik [17], are uniform measures under conditioning on their size (or equivalently, area). We then show that, as the averaged size of the diagrams diverges, the corresponding height variable converges to a solution of a certain non-linear partial differential equation under a proper hydrodynamic scaling. Furthermore, the stationary solution of the limit equation is identified with the so-called Vershik curve. We discuss both uniform and restricted uniform statistics for the Young diagrams.     

Complete Equivalence of the Gibbs Ensembles for One-Dimensional Markov Systems

We show the equivalence of the Gibbs ensembles at the level of measures for one-dimensional Markov-Systems with arbitrary boundary conditions. That is, the limit of the microcanonical Gibbs ensemble is a Gibbs measure with an interaction depending on the microcanonical constraint. In fact the usual microcanonical condition is replaced by the sharper constraint that all type frequencies of neighboring spins (including the boundary spins) are fixed. When conditioning on a set of different frequencies of neighboring spins compatible with physical quantities like energy density we get the usual microcanonical ensemble. We show that the limit is a Gibbs measure for a nearest neighbor potential depending on the pair measure which maximizes the entropy on the given set of pair measures. For this we show the large deviation property of the pair empirical measure for arbitrary boundary conditions. We establish analogous results for finite range potentials.     

Characteristic Polynomials of Random Matrices

Number theorists have studied extensively the connections between the distribution of zeros of the Riemann ζ-function, and of some generalizations, with the statistics of the eigenvalues of large random matrices. It is interesting to compare the average moments of these functions in an interval to their counterpart in random matrices, which are the expectation values of the characteristic polynomials of the matrix. It turns out that these expectation values are quite interesting. For instance, the moments of order 2K scale, for unitary invariant ensembles, as the density of eigenvalues raised to the power K ²; the prefactor turns out to be a universal number, i.e. it is independent of the specific probability distribution. An equivalent behaviour and prefactor had been found, as a conjecture, within number theory. The moments of the characteristic determinants of random matrices are computed here as limits, at coinciding points, of multi-point correlators of determinants. These correlators are in fact universal in Dyson's scaling limit in which the difference between the points goes to zero, the size of the matrix goes to infinity, and their product remains finite. Received: 1 October 1999 / Accepted: 18 May 2000     

Biorthogonal ensembles

One object of interest in random matrix theory is a family of point ensembles (ramdom point configurations) related to various systems of classical orthogonal polynomials. The paper deals with a one-parametric deformation of these ensembles, which is defined in terms of the biorthogonal polynomials of Jacobi, Laguerre and Hermite type.Our main result is a series of explicit expressions for the correlation functions in the scaling limit (as the number of points goes to infinity). As in the classical case, the correlation functions have determinatal form. They are given by certain new kernels which are described in terms of Wright's generalized Bessel function and can be viewed as a generalization of the well-known sine and Bessel kernels.In contrast to the conventional kernels, the new kernels are non-symmetric. However, they possess other, rather surprising, symmetry properties.Our approach to finding the limit kernel also differs from the conventional one, because of lack of a simple explicit Christoffel-Darboux formula for the biorthogonal polynomials.     

Statistics of mesoscopic ensembles of bosons and fermions

Equilibrium distribution functions are obtained for boson and fermion ensembles with a limited number of particles. It is shown that the number-of-particle distribution functions in different quantum states are statistically dependent; this dependence disappears only for a large number of particles in the ensemble. The distributions are transformed into the Boltzmann distribution at a high temperature and into the Bose-Einstein and Fermi-Dirac distributions for a large number of particles in the ensemble.     

Discrete-time quantum walks on one-dimensional lattices

In this paper, we study discrete-time quantum walks on one-dimensional lattices. We find that the coherent dynamics depends on the initial states and coin parameters. For infinite size of lattices, we derive an explicit expression for the return probability, which shows scaling behavior P(0, t) ~ t ^-1 and does not depends on the initial states of the walk. In the long-time limit, the probability distribution shows various patterns, depending on the initial states, coin parameters and the lattice size. The time-averaged probability mixes to the limiting probability distribution in linear time, i.e., the mixing time M _ε is a linear function of N (size of the lattices) for large values of thresholds ϵ. Finally, we introduce another kind of quantum walk on infinite or even-numbered size of lattices, and show that by the method of mathematical induction, the walk is equivalent to the traditional quantum walk with symmetrical initial state and coin parameter.     

Scaling exponents and probability distributions of DNA end-to-end distance

The scaling of the average gyration radius of polymers as a function of their length can be experimentally determined from ensemble measurements, such as light scattering, and agrees with analytical estimates. Ensemble techniques, yet, do not give access to the full probability distributions. Single molecule techniques, instead, can deliver information on both average quantities and distribution functions. Here we exploit the high resolution of atomic force microscopy over long DNA molecules adsorbed on a surface to measure the average end-to-end distance as a function of the DNA length, and its full distribution function. We find that all the scaling exponents are close to the predicted 3D values (upsilon=0.589+/-0.006 and delta=2.58+/-0.77). These results suggest that the adsorption process is akin to a geometric projection from 3D to 2D, known to preserve the scaling properties of fractal objects of dimension df<2.