Construction of a set of <Emphasis Type="Italic">p</Emphasis>-adic distributions

Adapting some methods for real-valued Gibbs measures on Cayley trees to the p-adic case, we construct several p-adic distributions on the set ?_p of p-adic integers. In addition, we give conditions under which these p-adic distributions become p-adic measures (i.e., bounded distributions).     

Computational Bayesian Analysis of Hidden Markov Models

Abstract

Versions of the Gibbs Sampler are derived for the analysis of data from hidden Markov chains and hidden Markov random fields. The principal new development is to use the pseudolikelihood function associated with the underlying Markov process in place of the likelihood, which is intractable in the case of a Markov random field, in the simulation step for the parameters in the Markov process. Theoretical aspects are discussed and a numerical study is reported.     

On the hardness of sampling independent sets beyond the tree threshold

We consider local Markov chain Monte–Carlo algorithms for sampling from the weighted distribution of independent sets with activity λ, where the weight of an independent set I is λ^|I|. A recent result has established that Gibbs sampling is rapidly mixing in sampling the distribution for graphs of maximum degree d and λ < λ _c (d), where λ _c (d) is the critical activity for uniqueness of the Gibbs measure (i.e., for decay of correlations with distance in the weighted distribution over independent sets) on the d-regular infinite tree. We show that for d ≥ 3, λ just above λ _c (d) with high probability over d-regular bipartite graphs, any local Markov chain Monte–Carlo algorithm takes exponential time before getting close to the stationary distribution. Our results provide a rigorous justification for “replica” method heuristics. These heuristics were invented in theoretical physics and are used in order to derive predictions on Gibbs measures on random graphs in terms of Gibbs measures on trees. A major theoretical challenge in recent years is to provide rigorous proofs for the correctness of such predictions. Our results establish such rigorous proofs for the case of hard-core model on bipartite graphs. We conjecture that λ _c is in fact the exact threshold for this computational problem, i.e., that for λ > λ _c it is NP-hard to approximate the above weighted sum over independent sets to within a factor polynomial in the size of the graph.     

Markov random fields,Markov cocycles and the 3-colored chessboard

The well-known Hammersley–Clifford Theorem states (under certain conditions) that any Markov random field is a Gibbs state for a nearest neighbor interaction. In this paper we study Markov random fields for which the proof of the Hammersley–Clifford Theorem does not apply. Following Petersen and Schmidt we utilize the formalism of cocycles for the homoclinic equivalence relation and introduce “Markov cocycles”, reparametrizations of Markov specifications. The main part of this paper exploits this to deduce the conclusion of the Hammersley–Clifford Theorem for a family of Markov random fields which are outside the theorem’s purview where the underlying graph is Z_d. This family includes all Markov random fields whose support is the d-dimensional “3-colored chessboard”. On the other extreme, we construct a family of shift-invariant Markov random fields which are not given by any finite range shift-invariant interaction.     

The p-adic Potts model on the Cayley tree of order three

We study a phase transition problem for the q-state p-adic Potts model on the Cayley tree of order three. We find certain conditions for the existence of p-adic Gibbs measures and then establish the existence of a phase transition.     

Markov fields and their applications in economics

Models of policy of companies on the market with competing technologies are considered. It is shown that the Gibbs random fields can serve as a convenient formalization for the investigation of such models. In this case the highly developed theory of Markov random fields can be used for analysis and choice of optimal strategies. Bibliography: 14 titles. Translated fromObchyslyuval'na ta Prykladna Matematyka, No. 80, 1996, pp. 33–46.     

A note on disagreement percolation

We construct a coupling of two distinct Gibbs measures for Markov random fields with the same specifications, such that the existence of an infinite path of disagreements between the two configurations has probability 0. This shows that the independence assumption in the disagreement percolation method for proving Gibbsian uniqueness cannot be dropped without being replaced by other conditions. A similar counterexample is given for couplings of Markov chains. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 267–278, 2001     

p-Adic Gibbs quasimeasures for the Vannimenus model on a Cayley tree

We study p-adic Gibbs quasimeasures for the Vannimenus model on the order-two Cayley tree. We especially address the problem of the boundedness of translation-invariant p-adic Gibbs quasimeasures. We also study periodic p-adic Gibbs quasimeasures.     

A p-Adic Generalized Gibbs Measure for the Ising Model on a Cayley Tree

Theoretical and Mathematical Physics - We consider a p-adic Ising model on the Cayley tree of order k ≥ 2. We completely describe all p-adic-translation-invariant generalized Gibbs measures...     

Functional Compatibility,Markov Chains,and Gibbs Sampling with Improper Posteriors

Abstract

The members of a set of conditional probability density functions are called compatible if there exists a joint probability density function that generates them. We generalize this concept by calling the conditionals functionally compatible if there exists a non-negative function that behaves like a joint density as far as generating the conditionals according to the probability calculus, but whose integral over the whole space is not necessarily finite. A necessary and sufficient condition for functional compatibility is given that provides a method of calculating this function, if it exists. A Markov transition function is then constructed using a set of functionally compatible conditional densities and it is shown, using the compatibility results, that the associated Markov chain is positive recurrent if and only if the conditionals are compatible. A Gibbs Markov chain, constructed via “Gibbs conditionals” from a hierarchical model with an improper posterior, is a special case. Therefore, the results of this article can be used to evaluate the consequences of applying the Gibbs sampler when the posterior's impropriety is unknown to the user. Our results cannot, however, be used to detect improper posteriors. Monte Carlo approximations based on Gibbs chains are shown to have undesirable limiting behavior when the posterior is improper. The results are applied to a Bayesian hierarchical one-way random effects model with an improper posterior distribution. The model is simple, but also quite similar to some models with improper posteriors that have been used in conjunction with the Gibbs sampler in the literature.     

p-adic Gibbs measures for the hard core model with three states on the Cayley tree

We study p-adic hard core models with three states on the Cayley tree. It is known that there are four types of such models. We find conditions that must be imposed on the order k of the Cayley tree and on the prime p for a translation-invariant p-adic Gibbs measure to exist.     

Spatiotemporal Models for Gaussian Areal Data

We introduce a class of spatiotemporal models for Gaussian areal data. These models assume a latent random field process that evolves through time with random field convolutions; the convolving fields follow proper Gaussian Markov random field (PGMRF) processes. At each time, the latent random field process is linearly related to observations through an observational equation with errors that also follow a PGMRF. The use of PGMRF errors brings modeling and computational advantages. With respect to modeling, it allows more flexible model structures such as different but interacting temporal trends for each region, as well as distinct temporal gradients for each region. Computationally, building upon the fact that PGMRF errors have proper density functions, we have developed an efficient Bayesian estimation procedure based on Markov chain Monte Carlo with an embedded forward information filter backward sampler (FIFBS) algorithm. We show that, when compared with the traditional one-at-a-time Gibbs sampler, our novel FIFBS-based algorithm explores the posterior distribution much more efficiently. Finally, we have developed a simulation-based conditional Bayes factor suitable for the comparison of nonnested spatiotemporal models. An analysis of the number of homicides in Rio de Janeiro State illustrates the power of the proposed spatiotemporal framework.

Supplemental materials for this article are available online in the journal’s webpage.     

Generalizing Swendsen–Wang for Image Analysis

Markov chain Monte Carlo (MCMC) methods have been used in many fields (physics, chemistry, biology, and computer science) for simulation, inference, and optimization. In many applications, Markov chains are simulated for sampling from target probabilities π(X) defined on graphs G. The graph vertices represent elements of the system, the edges represent spatial relationships, while X is a vector of variables on the vertices which often take discrete values called labels or colors. Designing efficient Markov chains is a challenging task when the variables are strongly coupled. Because of this, methods such as the single-site Gibbs sampler often experience suboptimal performance. A well-celebrated algorithm, the Swendsen–Wang (SW) method, can address the coupling problem. It clusters the vertices as connected components after turning off some edges probabilistically, and changes the color of one cluster as a whole. It is known to mix rapidly under certain conditions. Unfortunately, the SW method has limited applicability and slows down in the presence of “external fields;” for example, likelihoods in Bayesian inference. In this article, we present a general cluster algorithm that extends the SW algorithm to general Bayesian inference on graphs. We focus on image analysis problems where the graph sizes are in the order of 10³–10⁶ with small connectivity. The edge probabilities for clustering are computed using discriminative probabilities from data. We design versions of the algorithm to work on multi grid and multilevel graphs, and present applications to two typical problems in image analysis, namely image segmentation and motion analysis. In our experiments, the algorithm is at least two orders of magnitude faster (in CPU time) than the single-site Gibbs sampler.     

Random walks and flights over connected graphs and complex networks

Markov chains provide us with a powerful probabilistic tool that allows to study the structure of connected graphs in details. The statistics of events for Markov chains defined on connected graphs can be effectively studied by the method of generalized inverses which we review. The approach is also applicable for directed graphs and interacting networks which share the set of nodes. We discuss a generalization of Lévy flight random walks for large complex networks and study the interplay between the nonlinearity of diffusion process and the topological structure of the network.     

A different construction of Gaussian fields from Markov chains: Dirichlet covariances

We study a class of Gaussian random fields with negative correlations. These fields are easy to simulate. They are defined in a natural way from a Markov chain that has the index space of the Gaussian field as its state space. In parallel with Dynkin's investigation of Gaussian fields having covariance given by the Green's function of a Markov process, we develop connections between the occupation times of the Markov chain and the prediction properties of the Gaussian field. Our interest in such fields was initiated by their appearance in random matrix theory.     

Efficient Bayesian Inference for Generalized Bradley–Terry Models

The Bradley–Terry model is a popular approach to describe probabilities of the possible outcomes when elements of a set are repeatedly compared with one another in pairs. It has found many applications including animal behavior, chess ranking, and multiclass classification. Numerous extensions of the basic model have also been proposed in the literature including models with ties, multiple comparisons, group comparisons, and random graphs. From a computational point of view, Hunter has proposed efficient iterative minorization-maximization (MM) algorithms to perform maximum likelihood estimation for these generalized Bradley–Terry models whereas Bayesian inference is typically performed using Markov chain Monte Carlo algorithms based on tailored Metropolis–Hastings proposals. We show here that these MM algorithms can be reinterpreted as special instances of expectation-maximization algorithms associated with suitable sets of latent variables and propose some original extensions. These latent variables allow us to derive simple Gibbs samplers for Bayesian inference. We demonstrate experimentally the efficiency of these algorithms on a variety of applications.     

Metastability in stochastic dynamics of disordered mean-field models

We study a class of Markov chains that describe reversible stochastic dynamics of a large class of disordered mean field models at low temperatures. Our main purpose is to give a precise relation between the metastable time scales in the problem to the properties of the rate functions of the corresponding Gibbs measures. We derive the analog of the Wentzell-Freidlin theory in this case, showing that any transition can be decomposed, with probability exponentially close to one, into a deterministic sequence of “admissible transitions”. For these admissible transitions we give upper and lower bounds on the expected transition times that differ only by a constant factor. The distributions of the rescaled transition times are shown to converge to the exponential distribution. We exemplify our results in the context of the random field Curie-Weiss model. Received: 26 November 1998 / Revised version: 21 March 2000 / Published online: 14 December 2000     

The Construction of Multivariate Distributions from Markov Random Fields

We address the problem of constructing and identifying a valid joint probability density function from a set of specified conditional densities. The approach taken is based on the development of relations between the joint and the conditional densities using Markov random fields (MRFs). We give a necessary and sufficient condition on the support sets of the random variables to allow these relations to be developed. This condition, which we call the Markov random field support condition, supercedes a common assumption known generally as the positivity condition. We show how these relations may be used in reverse order to construct a valid model from specification of conditional densities alone. The constructive process and the role of conditions needed for its application are illustrated with several examples, including MRFs with multiway dependence and a spatial beta process.     

Markov Property and Cokernels of Local Operators

We discuss Gaussian generalized random fields indexed by smoothsections of vector bundles with respect to Markov properties.We propose a new set-up which is suitable for the present questionand within which new phenomena are detected naturally. In particular,we give a counterexample to the belief that locality in theRKHS implies the germ Markov property. We also prove the closeconnection between the Markov property and cokernels of localoperators. Furthermore, we prove the Markov property for a verydegenerate Gaussian random field.     

Optimizing random scan Gibbs samplers

The Gibbs sampler is a popular Markov chain Monte Carlo routine for generating random variates from distributions otherwise difficult to sample. A number of implementations are available for running a Gibbs sampler varying in the order through which the full conditional distributions used by the Gibbs sampler are cycled or visited. A common, and in fact the original, implementation is the random scan strategy, whereby the full conditional distributions are updated in a randomly selected order each iteration. In this paper, we introduce a random scan Gibbs sampler which adaptively updates the selection probabilities or “learns” from all previous random variates generated during the Gibbs sampling. In the process, we outline a number of variations on the random scan Gibbs sampler which allows the practitioner many choices for setting the selection probabilities and prove convergence of the induced (Markov) chain to the stationary distribution of interest. Though we emphasize flexibility in user choice and specification of these random scan algorithms, we present a minimax random scan which determines the selection probabilities through decision theoretic considerations on the precision of estimators of interest. We illustrate and apply the results presented by using the adaptive random scan Gibbs sampler developed to sample from multivariate Gaussian target distributions, to automate samplers for posterior simulation under Dirichlet process mixture models, and to fit mixtures of distributions.