Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Let ∑ = (V,E) be a finite, d‐regular bipartite graph. For any λ > 0 let π_λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ^|I| (π_λ is the hard‐core measure with activity λ on ∑). We study the Glauber dynamics, or single‐site update Markov chain, whose stationary distribution is π_λ. We show that when λ is large enough (as a function of d and the expansion of subsets of single‐parity of V) then the convergence to stationarity is exponentially slow in |V(∑)|. In particular, if ∑ is the d‐dimensional hypercube {0,1}^d we show that for values of λ tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Subexponential loss rate asymptotics for Lévy processes

We consider a Lévy process reflected in barriers at 0 and K > 0. The loss rate is the mean of the local time at K at time 1 when the process is started in stationarity, and is a natural continuous-time analogue of the stationary expected loss rate for a reflected random walk. We derive asymptotics for the loss rate when K tends to infinity, when the mean of the Lévy process is negative and the positive jumps are subexponential. In the course of this derivation, we achieve a formula, which is a generalization of the celebrated Pollaczeck-Khinchine formula.     

Stationary lower probabilities and unstable averages

Summary This paper explores the possibilities for probability-like models of stationary nondeterministic phenomena that possess divergent but bounded time averages. A random sequence described by a stationary probability measure must have almost surely convergent time averages whenever it has almost surely bounded time averages. Hence, no measure can provide the mathematical model we desire. In turning to lower probability based models we first explore the relationships between divergence, stationarity, and monotone continuity and those between monotone continuity and unicity of extensions. We then construct several examples of stationary lower probabilities for sequences of uniformly bounded random variables such that divergence of time averages occurs with lower probability one. We conclude with some remarks on the problem of estimating lower probability models on the basis of cylinder set observations.     

The Invariant Measures of Markov Chains on Product Spaces and a Measurement of Dependence

For probability measures on product spaces, we define a notion of dependence among each coordinate. We study Markov chains on product spaces in which the time developement of each coordinate corresponds to the movement of a particle in an interacting particle system described by the Markov chain. If there is no interaction among these particles, the dependence of them decreases monotonically. We establish an inequality which states that if the interaction among each particle is small, then, in stationarity, the dependence among each particle is small.     

Performance analysis of a slotted-ALOHA protocol on a capture channel with fading

We consider the slotted ALOHA protocol on a channel with a capture effect. There are M < users each with an infinite buffer. If in a slot, i packets are transmitted, then the probability of a successful reception of a packet is q _i. This model contains the CDMA protocols as special cases. We obtain sufficient rate conditions, which are close to necessary for stability of the system, when the arrival streams are stationary ergodic. Under the same rate conditions, for general regenerative arrival streams, we obtain the rates of convergence to stationarity, finiteness of stationary moments and various functional limit theorems. Our arrival streams contain all the traffic models suggested in the recent literature, including the ones which display long range dependence. We also obtain bounds on the stationary moments of waiting times which can be tight under realistic conditions. Finally, we obtain several results on the transient performance of the system, e.g., first time to overflow and the limits of the overflow process. We also extend the above results to the case of a capture channel exhibiting Markov modulated fading. Most of our results and proofs will be shown to hold also for the slotted ALOHA protocol without capture.     

Asymptotic properties of digit sequences of random numbers

We consider several aspects of the relationship between a [0, 1]‐valued random variable X and the random sequence of digits given by its m‐ary expansion. We present results for three cases: (a) independent and identically distributed digit sequences; (b) random variables X with smooth densities; (c) stationary digit sequences. In the case of i.i.d. an integral limit thorem is proved which applies for example to relative frequencies, yielding asymptotic moment identities. We deal with occurrence probabilities of digit groups in the case that X has an analytic Lebesgue density. In the case of stationary digits we determine the distribution of X in terms of their transition functions. We study an associated [0, 1]‐valued Markov chain, in particular its ergodicity, and give conditions for the existence of stationary digit sequences with prespecified transition functions. It is shown that all probability measures induced on [0, 1] by such sequences are purely singular except for the uniform distribution. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Markov chain models for delinquency: Transition matrix estimation and forecasting

A Markov chain is a natural probability model for accounts receivable. For example, accounts that are ‘current’ this month have a probability of moving next month into ‘current’, ‘delinquent’ or ‘paid‐off’ states. If the transition matrix of the Markov chain were known, forecasts could be formed for future months for each state. This paper applies a Markov chain model to subprime loans that appear neither homogeneous nor stationary. Innovative estimation methods for the transition matrix are proposed. Bayes and empirical Bayes estimators are derived where the population is divided into segments or subpopulations whose transition matrices differ in some, but not all entries. Loan‐level models for key transition matrix entries can be constructed where loan‐level covariates capture the non‐stationarity of the transition matrix. Prediction is illustrated on a $7 billion portfolio of subprime fixed first mortgages and the forecasts show good agreement with actual balances in the delinquency states. Copyright © 2010 John Wiley & Sons, Ltd.     

Nonlinear autoregressive models with heavy-tailed innovation

In this paper, we discuss the relationship between the stationary marginal tail probability and the innovation's tail probability of nonlinear autoregressive models. We show that under certain conditions that ensure the stationarity and ergodicity, one dimension stationary marginal distribution has the heavy-tailed probability property with the same index as that of the innovation's tail probability.     

M x /G/1 Queue with Multiple Vacations

Abstract

In this article, we study a queueing system M ^x /G/1 with multiple vacations. The probability generating function (P.G.F.) of stationary queue length and its expectation expression are deduced by using an embedded Markov chain of the queueing process. The P.G.F. of stationary system busy period and the probability of system in service state and vacation state also are obtained by the same method. At last we deduce the LST and mean of stationary waiting time in the service order FCFS and LCFS, respectively.     

Markov Chains with Positive Transitions Are Not Determined by Any p-Marginals

 We prove that if is a finite valued stationary Markov Chain with strictly positive probability transitions, then for any natural number p, there exists a continuum of finite valued non Markovian processes which have the p-marginal distributions of X and with positive entropy, whereas for an irrational rotation and essentially bounded real measurable function f with no zero Fourier coefficient on the unit circle with normalized Lebesgue measure, the process is uniquely determined by its three-dimensional distributions in the class of ergodic processes. We give also a family of Gaussian non-Markovian dynamical systems for which the symbolic dynamic associated to the time zero partition has the two-dimensional distributions of a reversible mixing Markov Chain. (Received 22 July 1999; in revised form 24 February 2000)     

Variable-Length Coding of Two-sided Asymptotically Mean Stationary Measures

We collect several observations that concern variable-length coding of two-sided infinite sequences in a probabilistic setting. Attention is paid to images and preimages of asymptotically mean stationary measures defined on subsets of these sequences. We point out sufficient conditions under which the variable-length coding and its inverse preserve asymptotic mean stationarity. Moreover, conditions for preservation of shift-invariant σ-fields and the finite-energy property are discussed, and the block entropies for stationary means of coded processes are related in some cases. Subsequently, we apply certain of these results to construct a stationary nonergodic process with a desired linguistic interpretation.     

A semi-Markov model of disease recurrence in insured dogs

We use a semi-Markov model to analyse the stochastic dynamics of disease occurrence of dogs insured in Canada from 1990 to 1999, and the probability pattern of death from illness. After statistically justifying the use of a stochastic model, we demonstrate that a stationary first-order semi-Markov process is appropriate for analysing the available data set. The probability transition function is estimated and its stationarity is tested statistically. Homogeneity of the semi-Markov model with respect to important covariates (such as geographic location, insurance plan, breed and age) is also statistically examined. We conclude with discussions and implications of our results in veterinary contents. Copyright © 2007 John Wiley & Sons, Ltd.     

A generalization of the Erlang formula of traffic engineering

Calls arrive at a switch, where they are assigned to any one of the available idle outgoing links. A call is blocked if all the links are busy. A call assigned to an idle link may be immediately lost with a probability which depends on the link. For exponential holding times and an arbitrary arrival process we show that the conditional distribution of the time to reach the blocked state from any state, given the sequence of arrivals, is independent of the policy used to route the calls. Thus the law of overflow traffic is independent of the assignment policy. An explicit formula for the stationary probability that an arriving call sees the node blocked is given for Poisson arrivals. We also give a simple asymptotic formula in this case.Work on this paper was done while the author was at Bellcore and at Berkeley.     

Kernel estimation for stationary density of Markov chains with general state space

Let {X _n } _n ≥0 be a Markov chain with stationary distributionf(x)ν(dx), ν being a σ-finite measure onE⊂R ^d . Under strict stationarity and mixing conditions we obtain the consistency and asymptotic normality for a general class of kernel estimates off(·). When the assumption of stationarity is dropped these results are extended to geometrically ergodic chains. Partially supported by CAPES. Partially supported by CNPq, PROCAD/CAPES, PRONEX/FAPDF and FINATEC/UnB.     

Markov Chains with Positive Transitions Are Not Determined by Any p -Marginals

 We prove that if is a finite valued stationary Markov Chain with strictly positive probability transitions, then for any natural number p, there exists a continuum of finite valued non Markovian processes which have the p-marginal distributions of X and with positive entropy, whereas for an irrational rotation and essentially bounded real measurable function f with no zero Fourier coefficient on the unit circle with normalized Lebesgue measure, the process is uniquely determined by its three-dimensional distributions in the class of ergodic processes. We give also a family of Gaussian non-Markovian dynamical systems for which the symbolic dynamic associated to the time zero partition has the two-dimensional distributions of a reversible mixing Markov Chain.     

A character formula for a family of simple modular representations of $ GL_n $

Let K be an algebraically closed field of finite characteristic p, and let be an integer. In the paper, we give a character formula for all simple rational representations of with highest weight any multiple of any fundamental weight. Our formula is slightly more general: say that a dominant weight λ is special if there are integers such that and . Indeed, we compute the character of any simple module whose highest weight λ can be written as with all are special. By stabilization, we get a character formula for a family of irreducible rational -modules. Received: June 30, 1997.     

The conjugate gradient method for computing all the extremal stationary probability vectors of a stochastic matrix

Summary The conjugate gradient method is developed for computing stationary probability vectors of a large sparse stochastic matrixP, which often arises in the analysis of queueing system. When unit vectors are chosen as the initial vectors, the iterative method generates all the extremal probability vectors of the convex set formed by all the stationary probability vectors ofP, which are expressed in terms of the Moore-Penrose inverse of the matrix (P−I). A numerical method is given also for classifying the states of the Markov chain defined byP. One particular advantage of this method is to handle a very large scale problem without resorting to any special form ofP. The Institute of Statistical Mathematics     

A preferential attachment model with Poisson growth for scale-free networks

We propose a scale-free network model with a tunable power-law exponent. The Poisson growth model, as we call it, is an offshoot of the celebrated model of Barabási and Albert where a network is generated iteratively from a small seed network; at each step a node is added together with a number of incident edges preferentially attached to nodes already in the network. A key feature of our model is that the number of edges added at each step is a random variable with Poisson distribution, and, unlike the Barabási–Albert model where this quantity is fixed, it can generate any network. Our model is motivated by an application in Bayesian inference implemented as Markov chain Monte Carlo to estimate a network; for this purpose, we also give a formula for the probability of a network under our model.     

Strong stationary duality for continuous-time Markov chains. Part I: Theory

LetX(t), 0t<, be an ergodic continuous-time Markov chain with finite or countably infinite state space. We construct astrong stationary dual chainX ^* whose first hitting times yield bounds on the convergence to stationarity forX. The development follows closely the discrete-time theory of Diaconis and Fill.^(2,3) However, for applicability it is important that we formulate our results in terms of infinitesimal rates, and this raises new issues.     

Markov Chain Analysis for One-Dimensional Asynchronous Cellular Automata

We consider the finite homogeneous Markov chain induced by a class of one-dimensional asynchronous cellular automata—automata that are allowed to change only one cell per iteration. Furthermore, we confine to totalistic automata, where transitions depend only on the number of 1s in the neighborhood of the current cell. We consider three different cases: (i) size of neighborhood equals length of the automaton; (ii) size of neighborhood two, length of automaton arbitrary; and (iii) size of neighborhood three, length of automaton arbitrary. For each case, the associated Markov chain proves to be ergodic. We derive simple-form stationary distributions, in case (i) by lumping states with respect to the number of 1s in the automaton, and in cases (ii) and (iii) by considering the number of 0–1 borders within the automaton configuration. For the three-neighborhood automaton, we analyze also the Markov chain at the boundary of the parameter domain, and the symmetry of the entropy. Finally, we show that if the local transition rule is exponential, the stationary probability is the Boltzmann distribution of the Ising model.