Importance Sampling Simulations of Markovian Reliability Systems Using Cross-Entropy

This paper reports simulation experiments, applying the cross entropy method such as the importance sampling algorithm for efficient estimation of rare event probabilities in Markovian reliability systems. The method is compared to various failure biasing schemes that have been proved to give estimators with bounded relative errors. The results from the experiments indicate a considerable improvement of the performance of the importance sampling estimators, where performance is measured by the relative error of the estimate, by the relative error of the estimator, and by the gain of the importance sampling simulation to the normal simulation.     

Approximating zero-variance importance sampling in a reliability setting

We consider a class of Markov chain models that includes the highly reliable Markovian systems (HRMS) often used to represent the evolution of multicomponent systems in reliability settings. We are interested in the design of efficient importance sampling (IS) schemes to estimate the reliability of such systems by simulation. For these models, there is in fact a zero-variance IS scheme that can be written exactly in terms of a value function that gives the expected cost-to-go (the exact reliability, in our case) from any state of the chain. This IS scheme is impractical to implement exactly, but it can be approximated by approximating this value function. We examine how this can be effectively used to estimate the reliability of a highly-reliable multicomponent system with Markovian behavior. In our implementation, we start with a simple crude approximation of the value function, we use it in a first-order IS scheme to obtain a better approximation at a few selected states, then we interpolate in between and use this interpolation in our final (second-order) IS scheme. In numerical illustrations, our approach outperforms the popular IS heuristics previously proposed for this class of problems. We also perform an asymptotic analysis in which the HRMS model is parameterized in a standard way by a rarity parameter ε, so that the relative error (or relative variance) of the crude Monte Carlo estimator is unbounded when ε→0. We show that with our approximation, the IS estimator has bounded relative error (BRE) under very mild conditions, and vanishing relative error (VRE), which means that the relative error converges to 0 when ε→0, under slightly stronger conditions.     

An estimator for the quadratic covariation of asynchronously observed Itô processes with noise: Asymptotic distribution theory

The article is devoted to the nonparametric estimation of the quadratic covariation of non-synchronously observed Itô processes in an additive microstructure noise model. In a high-frequency setting, we aim at establishing an asymptotic distribution theory for a generalized multiscale estimator including a feasible central limit theorem with optimal convergence rate on convenient regularity assumptions. The inevitably remaining impact of asynchronous deterministic sampling schemes and noise corruption on the asymptotic distribution is precisely elucidated. A case study for various important examples, several generalizations of the model and an algorithm for the implementation warrant the utility of the estimation method in applications.     

Optimal importance sampling for Lévy processes

We develop importance sampling estimators for Monte Carlo pricing of European and path-dependent options in models driven by Lévy processes. Using results from the theory of large deviations for processes with independent increments, we compute an explicit asymptotic approximation for the variance of the pay-off under a time-dependent Esscher-style change of measure. Minimizing this asymptotic variance using convex duality, we then obtain an importance sampling estimator of the option price. We show that our estimator is logarithmically optimal among all importance sampling estimators. Numerical tests in the variance gamma model show consistent variance reduction with a small computational overhead.     

Coupling Importance Sampling and Multilevel Monte Carlo using Sample Average Approximation

In this work, we propose a smart idea to couple importance sampling and Multilevel Monte Carlo (MLMC). We advocate a per level approach with as many importance sampling parameters as the number of levels, which enables us to handle the different levels independently. The search for parameters is carried out using sample average approximation, which basically consists in applying deterministic optimisation techniques to a Monte Carlo approximation rather than resorting to stochastic approximation. Our innovative estimator leads to a robust and efficient procedure reducing both the discretization error (the bias) and the variance for a given computational effort. In the setting of discretized diffusions, we prove that our estimator satisfies a strong law of large numbers and a central limit theorem with optimal limiting variance, in the sense that this is the variance achieved by the best importance sampling measure (among the class of changes we consider), which is however non tractable. Finally, we illustrate the efficiency of our method on several numerical challenges coming from quantitative finance and show that it outperforms the standard MLMC estimator.     

Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform sampling assumption imposed for the widely used nuclear-norm penalized approach, and makes low-rank matrix recovery feasible in more practical settings. Theoretically, we prove that the proposed estimator achieves fast rates of convergence under different settings. Computationally, we propose an alternating direction method of multipliers algorithm to efficiently compute the estimator, which bridges a gap between theory and practice of machine learning methods with max-norm regularization. Further, we provide thorough numerical studies to evaluate the proposed method using both simulated and real datasets.     

Monte Carlo Integration With Acceptance-Rejection

This article considers Monte Carlo integration under rejection sampling or Metropolis-Hastings sampling. Each algorithm involves accepting or rejecting observations from proposal distributions other than a target distribution. While taking a likelihood approach, we basically treat the sampling scheme as a random design, and define a stratified estimator of the baseline measure. We establish that the likelihood estimator has no greater asymptotic variance than the crude Monte Carlo estimator under rejection sampling or independence Metropolis-Hastings sampling. We employ a subsampling technique to reduce the computational cost, and illustrate with three examples the computational effectiveness of the likelihood method under general Metropolis-Hastings sampling.     

An efficient sampling scheme for dynamic generalized models

A multimove sampling scheme for the state parameters of non-Gaussian and nonlinear dynamic models for univariate time series is proposed. This procedure follows the Bayesian framework, within a Gibbs sampling algorithm with steps of the Metropolis–Hastings algorithm. This sampling scheme combines the conjugate updating approach for generalized dynamic linear models, with the backward sampling of the state parameters used in normal dynamic linear models. A quite extensive Monte Carlo study is conducted in order to compare the results obtained using our proposed method, conjugate updating backward sampling (CUBS), with those obtained using some algorithms previously proposed in the Bayesian literature. We compare the performance of CUBS with other sampling schemes using two real datasets. Then we apply our algorithm in a stochastic volatility model. CUBS significantly reduces the computing time needed to attain convergence of the chains, and is relatively simple to implement.     

Post-Processing Accept-Reject Samples: Recycling and Rescaling

Abstract

This article proposes alternative methods for constructing estimators from accept-reject samples by incorporating the variables rejected by the algorithm. The resulting estimators are quick to compute, and turn out to be variations of importance sampling estimators, although their derivations are quite different. We show that these estimators are superior asymptotically to the classical accept-reject estimator, which ignores the rejected variables. In addition, we consider the issue of rescaling of estimators, a topic that has implications beyond accept-reject and importance sampling. We show how rescaling can improve an estimator and illustrate the domination of the standard importance sampling techniques in different setups.     

Two noniterative algorithms for computing posteriors

In this paper, we first propose a noniterative sampling method to obtain an i.i.d. sample approximately from posteriors by combining the inverse Bayes formula, sampling/importance resampling and posterior mode estimates. We then propose a new exact algorithm to compute posteriors by improving the PMDA-Exact using the sampling-wise IBF. If the posterior mode is available from the EM algorithm, then these two algorithms compute posteriors well and eliminate the convergence problem of Markov Chain Monte Carlo methods. We show good performances of our methods by some examples.     

Modelling and analysis of Markovian continuous flow systems with a finite buffer

In this study, a Markovian fluid flow system with two stages separated by a finite buffer is considered. Fluid flow models have been analyzed extensively to evaluate the performance of production, computer, and telecommunication systems. Recently, we developed a methodology to analyze general Markovian continuous flow systems with a finite buffer. The flexibility of this methodology allows us to analyze a wide range of systems by specifying the transition rates and the flow rates associated with each state of each stage. In this study, in order to demonstrate the applicability of our methodology, we model and analyze a range of models studied in the literature. The examples we analyze as special cases of our general model include systems with phase-type failure and repair-time distributions, systems with machines that have multiple up and down states, and systems with multiple unreliable machines in series or parallel in each stage. For each case, the Markovian model is developed, the transition and flow rates are determined, and representative numerical results are obtained by using our methodology.     

Weighted frames of exponentials and stable recovery of multidimensional functions from nonuniform Fourier samples

In this paper, we consider the problem of recovering a compactly supported multivariate function from a collection of pointwise samples of its Fourier transform taken nonuniformly. We do this by using the concept of weighted Fourier frames. A seminal result of Beurling shows that sampling points give rise to a classical Fourier frame provided they are relatively separated and of sufficient density. However, this result does not allow for arbitrary clustering of sampling points, as is often the case in practice. Whilst keeping the density condition sharp and dimension independent, our first result removes the separation condition and shows that density alone suffices. However, this result does not lead to estimates for the frame bounds. A known result of Gröchenig provides explicit estimates, but only subject to a density condition that deteriorates linearly with dimension. In our second result we improve these bounds by reducing the dimension dependence. In particular, we provide explicit frame bounds which are dimensionless for functions having compact support contained in a sphere. Next, we demonstrate how our two main results give new insight into a reconstruction algorithm—based on the existing generalized sampling framework—that allows for stable and quasi-optimal reconstruction in any particular basis from a finite collection of samples. Finally, we construct sufficiently dense sampling schemes that are often used in practice—jittered, radial and spiral sampling schemes—and provide several examples illustrating the effectiveness of our approach when tested on these schemes.     

An Efficient Algorithm for Rare-event Probability Estimation,Combinatorial Optimization,and Counting

Although importance sampling is an established and effective sampling and estimation technique, it becomes unstable and unreliable for high-dimensional problems. The main reason is that the likelihood ratio in the importance sampling estimator degenerates when the dimension of the problem becomes large. Various remedies to this problem have been suggested, including heuristics such as resampling. Even so, the consensus is that for large-dimensional problems, likelihood ratios (and hence importance sampling) should be avoided. In this paper we introduce a new adaptive simulation approach that does away with likelihood ratios, while retaining the multi-level approach of the cross-entropy method. Like the latter, the method can be used for rare-event probability estimation, optimization, and counting. Moreover, the method allows one to sample exactly from the target distribution rather than asymptotically as in Markov chain Monte Carlo. Numerical examples demonstrate the effectiveness of the method for a variety of applications.      

Penalized empirical likelihood estimation of semiparametric models

We propose an empirical likelihood-based estimation method for conditional estimating equations containing unknown functions, which can be applied for various semiparametric models. The proposed method is based on the methods of conditional empirical likelihood and penalization. Thus, our estimator is called the penalized empirical likelihood (PEL) estimator. For the whole parameter including infinite-dimensional unknown functions, we derive the consistency and a convergence rate of the PEL estimator. Furthermore, for the finite-dimensional parametric component, we show the asymptotic normality and efficiency of the PEL estimator. We illustrate the theory by three examples. Simulation results show reasonable finite sample properties of our estimator.     

Efficient algorithms for basket default swap pricing with multivariate Archimedean copulas

We introduce a new importance sampling method for pricing basket default swaps employing exchangeable Archimedean copulas and nested Gumbel copulas. We establish more realistic dependence structures than existing copula models for credit risks in the underlying portfolio, and propose an appropriate density for importance sampling by analyzing multivariate Archimedean copulas. To justify efficiency and accuracy of the proposed algorithms, we present numerical examples and compare them with the crude Monte Carlo simulation, and finally show that our proposed estimators produce considerably smaller variances.     

An adaptive refinement method for convection‐diffusion problems

An adaptive finite difference method for singularly perturbed convection‐diffusion problems is presented. The method is introduced using a first‐order upwind scheme and a suitable error estimator based on the first derivatives. To obtain the grid structure needed for the cross stencil a special refinement strategy is considered. To avoid the slave points we change the stencil at the interface points from a cross to a skew one. After the convergence of the refinement algorithm we use a combination of a first order upwind and a second order central schemes to achieve higher order of convergence. Several numerical examples show the efficiency of our treatment. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Improved Estimation and Uncertainty Quantification Using Monte Carlo-Based Optimization Algorithms

In this article, we present a novel method to obtain both improved estimates and reliable stopping rules for stochastic optimization algorithms such as the Monte Carlo EM (MCEM) algorithm. By characterizing a stationary point, θ*, of the algorithm as the solution to a fixed point equation, we provide a parameter estimation procedure by solving for the fixed point of the update mapping. We investigate various ways to model the update mapping, including the use of a local linear (regression) smoother. This simple approach allows increased stability in estimating the value of θ* as well as providing a natural quantification of the estimation uncertainty. These uncertainty measures can then also be used to construct convergence criteria that reflect the inherent randomness in the algorithm. We establish convergence properties of our modified estimator. In contrast to existing literature, our convergence results do not require the Monte Carlo sample size to go to infinity. Simulation studies are provided to illustrate the improved stability and reliability of our estimator.     

Super optimal rates for nonparametric density estimation via projection estimators

In this paper, we study the problem of the nonparametric estimation of the marginal density f of a class of continuous time processes. To this aim, we use a projection estimator and deal with the integrated mean square risk. Under Castellana and Leadbetter's condition (Stoch. Proc. Appl. 21 (1986) 179), we show that our estimator reaches a parametric rate of convergence and coincides with the projection of the local time estimator. Discussions about the optimality of this condition are provided. We also deal with sampling schemes and the corresponding discretized processes.     

Lyapunov direct method for investigating stability of nonstandard finite difference schemes for metapopulation models

In this paper nonstandard finite difference (NSFD) schemes of two metapopulation models are constructed. The stability properties of the discrete models are investigated by the use of the Lyapunov stability theorem. As a result of this we have proved that the NSFD schemes preserve essential properties of the metapopulation models (positivity, boundedness and monotone convergence of the solutions, equilibria and their stability properties). Especially, the basic reproduction number of the continuous models is also preserved. Numerical examples confirm the obtained theoretical results of the properties of the constructed difference schemes. The method of Lyapunov functions proves to be much simpler than the standard method for studying stability of the discrete metapopulation model in our very recent paper.     

State-dependent importance sampling schemes via minimum cross-entropy

We present a method to obtain state- and time-dependent importance sampling estimators by repeatedly solving a minimum cross-entropy (MCE) program as the simulation progresses. This MCE-based approach lends a foundation to the natural notion to stop changing the measure when it is no longer needed. We use this method to obtain a state- and time-dependent estimator for the one-tailed probability of a light-tailed i.i.d. sum that is logarithmically efficient in general and strongly efficient when the jumps are Gaussian. We go on to construct an estimator for the two-tailed problem which is shown to be similarly efficient. We consider minor variants of the algorithm obtained via MCE, and present some numerical comparisons between our algorithms and others from the literature.