Search

Logit dynamics is a form of randomized game dynamics in which players have a bias toward strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converge to the so-called Gibbs distribution over the set of all strategy profiles when interpreted as a Markov chain. In general, logit dynamics can converge slowly to the Gibbs distribution, but beyond that, not much is known about its algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: (i) Is there an efficient algorithm for sampling from the Gibbs distribution? (ii) If yes, does there also exist natural randomized dynamics that converge quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics that converges quickly to the Gibbs distribution in such games. We also address the first question for the class of so-called capacitated uniform congestion games and the second question for max cut games played on a complete graph. To prove our results, we rely on the recent breakthrough work of Anari et al. (2019) regarding the approximate sampling of a base of a matroid according to a strongly log-concave probability distribution. [ABSTRACT FROM AUTHOR] more...

The authors consider an algorithm for estimating the unknown parameters of the infection spread model based on the Markov field tools using the maximum likelihood method. It is assumed that each state of the Markov chain represents some configuration of a finite random Markov field, and the probability distribution of the chain states is the same as general probability distribution of the states of elements of the Gibbs random field. [ABSTRACT FROM AUTHOR] more...

Abstract Most real world combinatorial optimization problems are affected by noise in the input data, thus behaving in the high noise limit like large disordered particle systems, e.g. spin glasses or random networks. Due to uncertainty in the input, optimization of such disordered instances should infer stable posterior distributions of solutions conditioned on the noisy input instance. The maximum entropy principle states that the most stable distribution given the noise influence is defined by the Gibbs distribution and it is characterized by the free energy. In this paper, we first provide rigorous asymptotics of the difficult problem to compute the free energy for two combinatorial optimization problems, namely the sparse Minimum Bisection Problem (sMBP) and Lawler's Quadratic Assignment Problem (LQAP). We prove that both problems exhibit phase transitions equivalent to the discontinuous behavior of Derrida's Random Energy Model (REM). Furthermore, the derived free energy asymptotics lead to a theoretical justification of a recently introduced concept [3] of Gibbs posterior agreement that measures stability of the Gibbs distributions when the cost function fluctuates due to randomness in the input. This relatively new stability concept may potentially provide a new method to select robust solutions for a large class of optimization problems. [ABSTRACT FROM AUTHOR] more...

What are the face-probabilities of a cuboidal die, i.e. a die with different side-lengths? This paper introduces a model for these probabilities based on a Gibbs distribution. Experimental data produced in this work and drawn from the literature support the Gibbs model. The experiments also reveal that the physical conditions, such as the quality of the surface onto which the dice are dropped, can affect the face-probabilities. In the Gibbs model, those variations are condensed in a single parameter, adjustable to the physical conditions. [ABSTRACT FROM AUTHOR] more...

Segmentation is one of the most complicated procedures in the image processing that has important role in the image analysis. In this paper, an improved pixon-based method for image segmentation is proposed. In proposed algorithm, complex partial differential equations (PDEs) is used as a kernel function to make pixonal image. Using this kernel function causes noise on images to reduce and an image not to be over-segment when the pixon-based method is used. Utilising the PDE-based method leads to elimination of some unnecessary details and results in a fewer pixon number, faster performance and more robustness against unwanted environmental noises. As the next step, the appropriate pixons are extracted and eventually, we segment the image with the use of a Markov random field. The experimental results indicate that the proposed pixon-based approach has a reduced computational load and a better accuracy compared to the other existing pixon-image segmentation techniques. To evaluate the proposed algorithm and compare it with the last best algorithms, many experiments on standard images were performed. The results indicate that the proposed algorithm is faster than other methods, with the most segmentation accuracy. [ABSTRACT FROM AUTHOR] more...

We prove that a stochastic process of pure coagulation has at any time t ≥ 0 a time-dependent Gibbs distribution if and only if the rates ψ(i, j) of single coagulations are of the form ψ(i; j) = if(j) + jf(i), where f is an arbitrary nonnegative function on the set of positive integers. We also obtain a recurrence relation for weights of these Gibbs distributions that allow us to derive the general form of the solution and the explicit solutions in three particular cases of the function f. For the three corresponding models, we study the probability of coagulation into one giant cluster by time t > 0. [ABSTRACT FROM AUTHOR] more...

Stochastic Langevin molecular dynamics for nuclei is derived from the Ehrenfest Hamiltonian system (also called quantum classical molecular dynamics) in a Kac-Zwanzig setting, with the initial data for the electrons stochastically perturbed from the ground state and the ratio M of nuclei and electron mass tending to infinity. The Ehrenfest nuclei dynamics is approximated by the Langevin dynamics with accuracy o(M-1/2) on bounded time intervals and by o(1) on unbounded time intervals, which makes the small $\mathcal{O}(M^{-1/2})$ friction and o(M-1/2) diffusion terms visible. The initial electron probability distribution is a Gibbs density at low temperature, motivated by a stability and consistency argument. The diffusion and friction coefficients in the Langevin equation satisfy the Einstein's fluctuation-dissipation relation. [ABSTRACT FROM AUTHOR] more...

We construct an integrated probabilistic model to capture interactions between atoms of a nanocomponent. We then use this model to assess reliabilities of nanocomponents with different structures. Several properties of our proposed model are also described under a sparseness condition. The model is an extension of our previous model based on Markovian random field theory. The proposed integrated model is flexible in that pairwise relationship information among atoms as well as features of individual atoms can be easily incorporated. An important feature that distinguishes the integrated probabilistic model from our previous model is that the integrated approach uses all available sources of information with different weights for different types of interaction. In this paper we consider the nanocomponent at a fixed moment of time, say the present moment, and we assume that the present state of the nanocomponent depends only on the present states of its atoms. [ABSTRACT FROM AUTHOR] more...

In this paper, we adopt an agent-based approach to model collective market dynamics when interactions between the agents in a market are significant. Our model has two special features. First, social groups are formed in a random cluster process which, we believe, mimics the actual formation of social circles. Second, the process is shown to have an equilibrium distribution which gives the highest probability to the market configurations with the maximum total likelihood. With this model we are able to catch some key characteristics of collective dynamics emerged from agent interactions. These characteristics include, for example, a heavy-tailed distribution for the market returns. [ABSTRACT FROM AUTHOR] more...

The article deals with the new distributions in classical physics. It considers a sufficiently general classical Hamilton function and makes three assumptions concerning it. It presents theorems how the three equations given related to each other. Further, it considers a rigid constraint, which is related to the fact that although the volume is large, it is bounded. Therefore, the impact parameter cannot tend to infinity. For two particles, it is limited by the volume. more...

Abstract: This paper describes how a visual system can automatically define features of interest from the observation of a large enough number of natural images. The principle complements the low-level feature extractors provided by PCA filters by analyzing their spatial interactions. This is achieved by modeling an internal representation in the system, composed with ternary variables obtained by thresholding the filters, using a Markov Random Field model. A stochastic gradient algorithm, based on statistics computed from an image database, is used to train this model. The result is a probability distribution on the internal state of the system which adjusts with its environment, under what is referred to as a principle of homeostasis. When new images enter the system, they are confronted to this internal distribution, and images which appear as salient in this regard are detected as visually relevant. A classification of these relevant images is provided, as an illustration of the model. [Copyright &y& Elsevier] more...

A rigorous derivation of the Gibbs and Bose-Einstein distributions on a finite set of energies is stated, in essence, as a theorem in number theory. If there are not very many particles, then the discussion of this question reduces to an exact theorem. [ABSTRACT FROM AUTHOR] more...

The notion of density of a finite set is introduced. We prove a general theorem of set theory which refines the Gibbs, Bose-Einstein, and Pareto distributions as well as the Zipf law. [ABSTRACT FROM AUTHOR] more...

Motivated by the autologistic model for the analysis of spatial binary data on the two–dimensional lattice, we develop efficient computational methods for calculating the normalizing constant for models for discrete data defined on the cylinder and lattice. Because the normalizing constant is generally unknown analytically, statisticians have developed various ad hoc methods to overcome this difficulty. Our aim is to provide computationally and statistically efficient methods for calculating the normalizing constant so that efficient likelihood–based statistical methods are then available for inference. We extend the so–called transition method to find a feasible computational method of obtaining the normalizing constant for the cylinder boundary condition. To extend the result to the free–boundary condition on the lattice we use an efficient path sampling Markov chain Monte Carlo scheme. The methods are generally applicable to association patterns other than spatial, such as clustered binary data, and to variables taking three or more values described by, for example, Potts models. [ABSTRACT FROM AUTHOR] more...