The Cross-Entropy Method for Continuous Multi-Extremal Optimization

In recent years, the cross-entropy method has been successfully applied to a wide range of discrete optimization tasks. In this paper we consider the cross-entropy method in the context of continuous optimization. We demonstrate the effectiveness of the cross-entropy method for solving difficult continuous multi-extremal optimization problems, including those with non-linear constraints.      

A Generalized Markov Sampler

A recent development of the Markov chain Monte Carlo (MCMC) technique is the emergence of MCMC samplers that allow transitions between different models. Such samplers make possible a range of computational tasks involving models, including model selection, model evaluation, model averaging and hypothesis testing. An example of this type of sampler is the reversible jump MCMC sampler, which is a generalization of the Metropolis–Hastings algorithm. Here, we present a new MCMC sampler of this type. The new sampler is a generalization of the Gibbs sampler, but somewhat surprisingly, it also turns out to encompass as particular cases all of the well-known MCMC samplers, including those of Metropolis, Barker, and Hastings. Moreover, the new sampler generalizes the reversible jump MCMC. It therefore appears to be a very general framework for MCMC sampling. This paper describes the new sampler and illustrates its use in three applications in Computational Biology, specifically determination of consensus sequences, phylogenetic inference and delineation of isochores via multiple change-point analysis.     

Single-server queues with spatially distributed arrivals

Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.     

Rare Events in Random Geometric Graphs

This work introduces and compares approaches for estimating rare-event probabilities related to the number of edges in the random geometric graph on a Poisson point process. In the one-dimensional setting, we derive closed-form expressions for a variety of conditional probabilities related to the number of edges in the random geometric graph and develop conditional Monte Carlo algorithms for estimating rare-event probabilities on this basis. We prove rigorously a reduction in variance when compared to the crude Monte Carlo estimators and illustrate the magnitude of the improvements in a simulation study. In higher dimensions, we use conditional Monte Carlo to remove the fluctuations in the estimator coming from the randomness in the Poisson number of nodes. Finally, building on conceptual insights from large-deviations theory, we illustrate that importance sampling using a Gibbsian point process can further substantially reduce the estimation variance.

     

Estimating change-points in biological sequences via the cross-entropy method

The genomes of complex organisms, including the human genome, are known to vary in GC content along their length. That is, they vary in the local proportion of the nucleotides G and C, as opposed to the nucleotides A and T. Changes in GC content are often abrupt, producing well-defined regions.     

The Generalized Cross Entropy Method, with Applications to Probability Density Estimation

Nonparametric density estimation aims to determine the sparsest model that explains a given set of empirical data and which uses as few assumptions as possible. Many of the currently existing methods do not provide a sparse solution to the problem and rely on asymptotic approximations. In this paper we describe a framework for density estimation which uses information-theoretic measures of model complexity with the aim of constructing a sparse density estimator that does not rely on large sample approximations. The effectiveness of the approach is demonstrated through an application to some well-known density estimation test cases.     

The relation between the high-temperature and room-temperature structure of CsCuCl3

The room-temperature structure of CsCuCl₃, spacegroup P6₁22, is described as the superposition of the high-temperature structure, spacegroup P6₃/mmc, and a softening vibration mode transforming as the degenerate irreducible representation τ5 (k = (0,0,2Π/3c)] of P6₃/mmc. It is argued that the presence of a third order invariant for k = (0,0,2Π/3c) in a power series expansion of the free energy in normal coordinates is the reason for a phase transition to occur at k = (0,0,2Π/3c). The connections with a cooperative Jahn-Teller effec: are indicated.     

On the Decay Rates of Buffers in Continuous Flow Lines

Consider a tandem system of machines separated by infinitely large buffers. The machines process a continuous flow of products, possibly at different speeds. The life and repair times of the machines are assumed to be exponential. We claim that the overflow probability of each buffer has an exponential decay, and provide an algorithm to determine the exact decay rates in terms of the speeds and the failure and repair rates of the machines. These decay rates provide useful qualitative insight into the behavior of the flow line. In the derivation of the algorithm we use the theory of Large Deviations.     

Second-order asymptotics in level crossing for differences of renewal processes

We consider level crossing for the difference of independent renewal processes. Second-order expansions for the distribution function of the crossing time of level n are found, as n → ∞. As a by-product several other results on the difference process are found. The expected minimum of the difference process appears to play an important role in the analysis. This makes this problem essentially harder than the level crossing for the sum process which was studied earlier.