A polynomial-time perfect sampler for the <Emphasis Type="Italic">Q</Emphasis>-Ising with a vertex-independent noise

We present a polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise. The Q-Ising, one of the generalized models of the Ising, arose in the context of Bayesian image restoration in statistical mechanics. We study the distribution of Q-Ising on a two-dimensional square lattice over n vertices, that is, we deal with a discrete state space {1,…,Q} ⁿ for a positive integer Q. Employing the Q-Ising (having a parameter β) as a prior distribution, and assuming a Gaussian noise (having another parameter α), a posterior is obtained from the Bayes’ formula. Furthermore, we generalize it: the distribution of noise is not necessarily a Gaussian, but any vertex-independent noise. We first present a Gibbs sampler from our posterior, and also present a perfect sampler by defining a coupling via a monotone update function. Then, we show O(nlog n) mixing time of the Gibbs sampler for the generalized model under a condition that β is sufficiently small (whatever the distribution of noise is). In case of a Gaussian, we obtain another more natural condition for rapid mixing that α is sufficiently larger than β. Thereby, we show that the expected running time of our sampler is O(nlog n).     

Some Results for Uniformizable Semi-Markov Processes

It is well known that finite Markov chains (M.C.s) in continuous time are uniformizable. That is, a finite M. C. in continuous time can be treated as an M. C. in discrete time with random Poisson transition epochs. In this paper, we see to what extent generalization of the uniformization to a class of semi-Markov Processes (S.M.P.s) is possible. A necessary condition under which S.M.P.s are uniformizable is provided. It is shown that, an S.M.P. with dwell-time distributions depending only on the current state is uniformizable if and only if the distributions are compound geometric distributions having the same base distribution. It is also shown that if the distributions are of generalized phase type then an S.M.P. being uniformizable implies that it is an M.C. in continuous time. Some properties that are shared by a uniformizable S.M.P. and the associated M.C. in discrete time are also discussed.     

ON THE UNIMODALITY OF TRANSITION PROBABILITIES IN MARKOV CHAINS

Consider a discrete time Markov chain X(n) denned on {0,1,…} and let P be the transition probability matrix governing X(n). This paper shows that, if a transformed matrix of P is totally positive of order 2, then poj(n) and pio(n) are unimodal with respect to n, where pij(n) = Pr[X(n) = j |X(0) = i]. Furthermore, the modes of poj(n) and pio(n) are non-increasing in j and I, respectively, when additionally P itself is totally positive of order 2. These results are transferred to a class of semi-Markov processes via a uniformization.     

ON TRANSITION PROBABILITIES OF SKIP-FREE MARKOV CHAINS

Consider an ergodic Markov chain X(t) in continuous time with an infinitesimal matrix Q = (q_ij) defined on a finite state space {0, 1,…, N}. In this note, we prove that if X(t) is skip-free positive (negative, respectively), i.e., q_ij, = 0 for j > i+ 1 (i > j+ 1), then the transition probability p_ij(t) = Pr[X(t)=j | X(0) =i] can be represented as a linear combination of p_0N(t) (p^(m)_(N0)(t)), 0 ≤ m ≤N, where f^(m)(t) denotes the mth derivative of a function f(t) with f⁽⁰⁾(t) =f(t). If X(t) is a birth-death process, then p_ij(t) is represented as a linear combination of p_0N^(m)(t), 0 ≤m≤N - |i-j|.