Δ-wavy probability distributions and Potts model

Udrea Păun

Abstract


We define the wavy probability distributions on a subset and Δ-wavy probability distributions - two generalizations of the wavy probability distributions. A classification on the Δ-waviness is given. For the Δ-wavy probability distributions having normalization constant, we give a formula for this constant, to compute this constant. We show that the Potts model is a Δ-wavy probability distribution, where Δ is a partition which will be specified. For the normalization constant of Potts model, we give formulas and bounds. As to the formulas for this constant, we give two general formulas, one of them is simple while the other is more complicated, and based on independent sets, a formula for the Potts model on connected separable graphs - closed-form expressions are then obtained in several cases -, and a formula for the Potts model on graphs with a vertex of degree 2 - a recurrence relation is then obtained for the normalization constant of Potts model on Cn; the cycle graph with n vertices; the normalization constant of Ising model on Cn is computed using this relation. As to the bounds for the normalization constant, we present two ways to obtain such bounds; we illustrate these ways giving a general lower bound, and a lower bound and an upper one when the model is the Potts model on Gn,n, the square grid graph, n = 6k, k ≥ 1 - two upper bounds for the free energy per site of this model are then obtained, one of them being in the limit. A sampling method for the Δ-wavy probability distributions is given and, as a result, a sampling method for the Potts is given. This method - that for the Potts model too - has two steps, Step 1 and Step 2, when |Δ| > 1 and one step, Step 2 only, when |Δ| = 1. For the Potts model, Step 1 is, in general, difficult. As to Step 2, for the Potts model too, using the Gibbs sampler in a generalized sense, we obtain an exact (not approximate) sampling method having p + 1 steps (p + 1 substeps of Step 2), where p = |I|; I is an independent set, best, a maximum independent set, best, a maximum independent set - for the Potts model on Gn1,n2,…,nd , the d-dimensional grid graph, d ≥ 1, n1, n2,…, nd ≥ 1, n1n2·…·nd ≥ 2; we obtain an exact sampling method for half or half+1 vertices.


Full Text:

PDF

References


A.S. Asratian, T.M.J. Denley, and R. Häggkvist, Bipartite Graphs and Their Applications, Cambridge University Press, Cambridge, 1998.

D. Avis, A. Hertz, and O. Marcotte (Eds.), Graph Theory and Combinatorial Optimization, Springer, New York, 2005.

J. Beck, Inevitable Randomness in Discrete Mathematics, AMS, Providence, Rhode Island, 2009.

A. Benjamin, G. Chartrand, and P. Zhang, The Fascinating World of Graph Theory, Princeton University Press, Princeton, 2015.

J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, North-Holland, New York, 1979.

G. Chartrand and P. Zhang, Chromatic Graph Theory, CRC Press, Boca Raton, 2008.

J.A. De Loera, X. Goaoc, F. Meunier, and N.H. Mustafa, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Bull. Amer. Math. Soc. (N.S.) 56 (2019), 415-511.

M. Iosifescu, Finite Markov Processes and Their Applications, Wiley, Chichester & Ed. Tehnică, Bucharest, 1980; corrected republication by Dover, Mineola, N.Y., 2007.

E. Ising, Beitrag zur Theorie des Ferromagnetismus, Z. Physik 31 (1925), 253-258.

N. Madras, Lectures on Monte Carlo Methods, AMS, Providence, Rhode Island, 2002.

P. Martin, Potts Models and Related Problems in Statistical Mechanics, World Scientific, Singapore, 1991.

B.M. McCoy and T.T. Wu, The Two-Dimensional Ising Model, 2nd Edition, Dover, Mineola, N.Y., 2014.

U. Păun, GΔ1,Δ2 in action, Rev. Roumaine Math. Pures Appl. 55 (2010), 387-406.

U. Păun, A hybrid Metropolis-Hastings chain, Rev. Roumaine Math. Pures Appl. 56 (2011), 207-228.

U. Păun, G method in action: from exact sampling to approximate one, Rev. Roumaine Math. Pures Appl. 62 (2017), 413-452.

U. Păun, G method in action: normalization constant, important probabilities, and fast exact sampling for Potts model on trees, Rev. Roumaine Math. Pures Appl. 65 (2020), 103-130.

U. Păun, A Gibbs sampler in a generalized sense, An. Univ. Craiova Ser. Mat. Inform. 43 (2016), 62-71.

U. Păun, A Gibbs sampler in a generalized sense, II, An. Univ. Craiova Ser. Mat. Inform. 45 (2018), 103-121.

U. Păun, Ewens distribution on Sn is a wavy probability distribution with respect to n partitions, An. Univ. Craiova Ser. Mat. Inform. 47 (2020), 1-24.

R.B. Potts, Some generalized order-disorder transitions, Proc. Cambridge Philos. Soc. 48 (1952), 106-109.

E. Seneta, Non-negative Matrices and Markov Chains, 2nd Edition, Springer-Verlag, Berlin, 1981; revised printing, 2006.

W.T. Tutte, Graph Theory, Cambridge University Press, Cambridge, 2001.

F.Y. Wu, The Potts model, Rev. Mod. Phys. 54 (1982), 235-268.




DOI: https://doi.org/10.52846/ami.v49i2.1494