The Multilevel Splitting algorithm for graph colouring with application to the Potts model

Calculating the partition function of the zero-temperature antiferromagnetic model is an important problem in statistical physics. However, an exact calculation is hard since it is strongly connected to a fundamental combinatorial problem of counting proper vertex colourings in undirected graphs, for which an efficient algorithm is not known to exist. Thus, one has to rely on approximation techniques. In this paper, we formulate the problem of the partition function approximation in terms of rare-event probability estimation and investigate the performance of a particle-based algorithm, called Multilevel Splitting, for handling this setting. The proposed method enjoys a provable probabilistic performance guarantee and our numerical study indicates that this algorithm is capable of delivering accurate results using a relatively modest amount of computational resources.     

A Review of Shannon and Differential Entropy Rate Estimation

In this paper, we present a review of Shannon and differential entropy rate estimation techniques. Entropy rate, which measures the average information gain from a stochastic process, is a measure of uncertainty and complexity of a stochastic process. We discuss the estimation of entropy rate from empirical data, and review both parametric and non-parametric techniques. We look at many different assumptions on properties of the processes for parametric processes, in particular focussing on Markov and Gaussian assumptions. Non-parametric estimation relies on limit theorems which involve the entropy rate from observations, and to discuss these, we introduce some theory and the practical implementations of estimators of this type.     

Martingale Methods for Analysing Single-Server Queues

In this paper we presents a martingale method for analysing queues of M/G/1 type, which have been generalised so that the system passes through a series of phases on which the service behaviour may differ. The analysis uses the process embedded at departures to create a martingale, which makes possible the calculation of the probability generating function of the stationary occupancy distribution. Specific examples are given, for instance, a model of an unreliable queueing system, and an example of a queue-length-threshold overload-control system.