We study a Markovian agent-based model (MABM) in this paper. Each agent is endowed with a local state that changes over time as the agent interacts with its neighbours. The neighbourhood structure is given by a graph. Recently, Simon, Taylor, and Kiss [40] used the automorphisms of the underlying graph to generate a lumpable partition of the joint state space, ensuring Markovianness of the lumped process for binary dynamics. However, many large random graphs tend to become asymmetric, rendering the automorphism-based lumping approach ineffective as a tool of model reduction. In order to mitigate this problem, we propose a lumping method based on a notion of local symmetry, which compares only local neighbourhoods of vertices. Since local symmetry only ensures approximate lumpability, we quantify the approximation error by means of the Kullback–Leibler divergence rate between the original Markov chain and a lifted Markov chain. We prove the approximation error decreases monotonically. The connections to fibrations of graphs are also discussed.

Model and parameter uncertainties are common whenever some parametric model is selected to value a derivative instrument. Combining the Monte Carlo method with the Smolyak interpolation algorithm, we propose an accurate efficient numerical procedure to quantify the uncertainty embedded in complex derivatives. Except for the value function being sufficiently smooth with respect to the model parameters, there are no requirements on the payoff or candidate models. Numerical tests carried out quantify the uncertainty of Bermudan put options and down-and-out put options under the Heston model, with each model parameter specified in an interval.

This paper concerns the computation of nonlinear crest distributions for irregular Stokes waves, and a numerical algorithm based on the Fast Fourier Transform (FFT) technique has been developed for carrying out the nonlinear computations. In order to further improve the computational efficiency, a new Transformed Rayleigh procedure is first proposed as another alternative for computing the nonlinear wave crest height distributions, and the corresponding computer code has also been developed. In the proposed Transformed Rayleigh procedure, the transformation model is chosen to be a monotonic exponential function, calibrated such that the first three moments of the transformed model match the moments of the true process. The numerical algorithm based on the FFT technique and the proposed Transformed Rayleigh procedure have been applied for calculating the wave crest distributions of a sea state with a Bretschneider spectrum and a sea statewith the surface elevation datameasured at the Poseidon platform. It is demonstrated in these two cases that the numerical algorithm based on the FFT technique and the proposed Transformed Rayleigh procedure can offer better predictions than those from using the empirical wave crest distribution models. Meanwhile, it is found that our proposed Transformed Rayleigh procedure can compute nonlinear crest distributions more than 25 times faster than the numerical algorithm based on the FFT technique.

For a collection of objects such as socks, which can be matched according to a characteristic such as color, we study the innocent phrase ‘the distribution of the color of a matching pair’ by looking at two methods for selecting socks. One method is memoryless and effectively samples socks with replacement, while the other samples socks sequentially, with memory, until the same color has been seen twice. We prove that these two methods yield the same distribution on colors if and only if the initial distribution of colors is a uniform distribution. We conjecture a nontrivial maximum value for the total variation distance of these distributions in all other cases.

A stochastic approach to conditional simulation of flow in randomly heterogeneous media is proposed with the combination of the Karhunen-Loeve expansion and the probabilistic collocation method (PCM). The conditional log hydraulic conductivity field is represented with the Karhunen-Loeve expansion, in terms of some deterministic functions and a set of independent Gaussian random variables. The propagation of uncertainty in the flow simulations is carried out through the PCM, which relies on the efficient polynomial chaos expansion used to represent the flow responses such as the hydraulic head. With the PCM, existing flow simulators can be employed for uncertainty quantification of flow in heterogeneous porous media when direct measurements of hydraulic conductivity are taken into consideration. With illustration of several numerical examples of groundwater flow, this study reveals that the proposed approach is able to accurately quantify uncertainty of the flow responses conditioning on hydraulic conductivity data, while the computational efforts are significantly reduced in comparison to the Monte Carlo simulations.

Exact simulation approaches for a class of diffusion bridges have recently been proposed based on rejection sampling techniques. The existing rejection sampling methods may not be practical owing to small acceptance probabilities. In this paper we propose an adaptive approach that improves the existing methods significantly under certain scenarios. The idea of the new method is based on a layered process, which can be simulated from a layered Brownian motion with reweighted layer probabilities. We will show that the new exact simulation method is more efficient than existing methods theoretically and via simulation.

We consider the problem of efficient simulation estimation of the density function at the tails, and the probability of large deviations for a sum of independent, identically distributed (i.i.d.), light-tailed, and nonlattice random vectors. The latter problem besides being of independent interest, also forms a building block for more complex rare event problems that arise, for instance, in queueing and financial credit risk modeling. It has been extensively studied in the literature where state-independent, exponential-twisting-based importance sampling has been shown to be asymptotically efficient and a more nuanced state-dependent exponential twisting has been shown to have a stronger bounded relative error property. We exploit the saddle-point-based representations that exist for these rare quantities, which rely on inverting the characteristic functions of the underlying random vectors. These representations reduce the rare event estimation problem to evaluating certain integrals, which may via importance sampling be represented as expectations. Furthermore, it is easy to identify and approximate the zero-variance importance sampling distribution to estimate these integrals. We identify such importance sampling measures and show that they possess the asymptotically vanishing relative error property that is stronger than the bounded relative error property. To illustrate the broader applicability of the proposed methodology, we extend it to develop an asymptotically vanishing relative error estimator for the practically important expected overshoot of sums of i.i.d. random variables.

Many applications in genetic analyses utilize sampling distributions, which describe the probability of observing a sample of DNA sequences randomly drawn from a population. In the one-locus case with special models of mutation, such as the infinite-alleles model or the finite-alleles parent-independent mutation model, closed-form sampling distributions under the coalescent have been known for many decades. However, no exact formula is currently known for more general models of mutation that are of biological interest. In this paper, models with finitely-many alleles are considered, and an urn construction related to the coalescent is used to derive approximate closed-form sampling formulae for an arbitrary irreducible recurrent mutation model or for a reversible recurrent mutation model, depending on whether the number of distinct observed allele types is at most three or four, respectively. It is demonstrated empirically that the formulae derived here are highly accurate when the per-base mutation rate is low, which holds for many biological organisms.

Obtaining a closed-form sampling distribution for the coalescent with recombination is a challenging problem. In the case of two loci, a new framework based on an asymptotic series has recently been developed to derive closed-form results when the recombination rate is moderate to large. In this paper, an arbitrary number of loci is considered and combinatorial approaches are employed to find closed-form expressions for the first couple of terms in an asymptotic expansion of the multi-locus sampling distribution. These expressions are universal in the sense that their functional form in terms of the marginal one-locus distributions applies to all finite- and infinite-alleles models of mutation.

In a fork-join network each incoming job is split into K tasks and the K tasks are simultaneously assigned to K parallel service stations for processing. For the distributions of response times and queue lengths of fork-join networks, no explicit formulae are available. Existing methods provide only analytic approximations for the response time and the queue length distributions. The accuracy of such approximations may be difficult to justify for some complicated fork-join networks. In this paper we propose a perfect simulation method based on coupling from the past to generate exact realisations from the equilibrium of fork-join networks. Using the simulated realisations, Monte Carlo estimates for the distributions of response times and queue lengths of fork-join networks are obtained. Comparisons of Monte Carlo estimates and theoretical approximations are also provided. The efficiency of the sampling algorithm is shown theoretically and via simulation.

Max-stable random fields play a central role in modeling extreme value phenomena. We obtain an explicit formula for the conditional probability in general max-linear models, which include a large class of max-stable random fields. As a consequence, we develop an algorithm for efficient and exact sampling from the conditional distributions. Our method provides a computational solution to the prediction problem for spectrally discrete max-stable random fields. This work offers new tools and a new perspective to many statistical inference problems for spatial extremes, arising, for example, in meteorology, geology, and environmental applications.

We present a method for computing the probability density function (PDF) and the cumulative distribution function (CDF) of a nonnegative infinitely divisible random variable X. Our method uses the Lévy-Khintchine representation of the Laplace transform Ee-λX = e-ϕ(λ), where ϕ is the Laplace exponent. We apply the Post-Widder method for Laplace transform inversion combined with a sequence convergence accelerator to obtain accurate results. We demonstrate this technique on several examples, including the stable distribution, mixtures thereof, and integrals with respect to nonnegative Lévy processes.

In this paper we prove that the stationary distribution of populations in genetic algorithms focuses on the uniform population with the highest fitness value as the selective pressure goes to ∞ and the mutation probability goes to 0. The obtained sufficient condition is based on the work of Albuquerque and Mazza (2000), who, following Cerf (1998), applied the large deviation principle approach (Freidlin-Wentzell theory) to the Markov chain of genetic algorithms. The sufficient condition is more general than that of Albuquerque and Mazza, and covers a set of parameters which were not found by Cerf.

A weighted graph G is a pair (V, ℰ) containing vertex set V and edge set ℰ, where each edge e ∈ ℰ is associated with a weight We. A subgraph of G is a forest if it has no cycles. All forests on the graph G form a probability space, where the probability of each forest is proportional to the product of the weights of its edges. This paper aims to simulate forests exactly from the target distribution. Methods based on coupling from the past (CFTP) and rejection sampling are presented. Comparisons of these methods are given theoretically and via simulation.

In this paper we develop a constructive approach to studying continuously and discretely sampled functionals of Lévy processes. Estimates for the rate of convergence of the discretely sampled functionals to the continuously sampled functionals are derived, reducing the study of the latter to that of the former. Laguerre reduction series for the discretely sampled functionals are developed, reducing their study to that of the moment generating function of the pertinent Lévy processes and to that of the moments of these processes in particular. The results are applied to questions of contingent claim valuation, such as the explicit valuation of Asian options, and illustrated in the case of generalized inverse Gaussian Lévy processes.

In this paper we develop a constructive structure theory for a class of exponential functionals of Brownian motion which includes Asian option values. This is done in two stages of differing natures. As a first step, the functionals are represented as Laguerre reduction series obtained from main results of Schröder (2006), this paper's companion paper. These reduction series are new and given in terms of the negative moments of the integral of geometric Brownian motion, whose structure theory is developed in a second step. Providing a new angle on these processes, this is done by establishing connections with theta functions. Integral representations and computable formulae for the negative moments are thus derived and then shown to furnish highly efficient ways for computing the negative moments. Application of this paper's Laguerre reduction series in numerical examples suggests that one of the most efficient methods for the explicit valuation of Asian options is obtained. The paper also provides mathematical background results referred to in Schröder (2005c).

In this paper we develop methods for reducing the study, the computation, and the construction of stochastic functionals to those of standard concepts such as the moments of the pertinent random variables. Principally, our methods are based on the notion of ladder height densities and their Laguerre expansions, and our results provide a unifying framework for the distinct approaches of Dufresne (2000) and Schröder (2005).

Particle filters are Monte Carlo methods that aim to approximate the optimal filter of a partially observed Markov chain. In this paper, we study the case in which the transition kernel of the Markov chain depends on unknown parameters: we construct a particle filter for the simultaneous estimation of the parameter and the partially observed Markov chain (adaptive estimation) and we prove the convergence of this filter to the correct optimal filter, as time and the number of particles go to infinity. The filter presented here generalizes Del Moral's Monte Carlo particle filter.

We give explicit upper bounds for convergence rates when approximating both one- and two-sided general curvilinear boundary crossing probabilities for the Wiener process by similar probabilities for close boundaries of simpler form, for which computation of the boundary crossing probabilities is feasible. In particular, we partially generalize and improve results obtained by Pötzelberger and Wang in the case when the approximating boundaries are piecewise linear. Applications to barrier option pricing are also discussed.

One approach to the computation of the price of an Asian option involves the Hartman–Watson distribution. However, numerical problems for its density occur for small values. This motivates the asymptotic study of its distribution function.