Some characterizations of minimal Markov basis for sampling from discrete conditional distributions

In this paper we given some basic characterizations of minimal Markov basis for a connected Markov chain, which is used for performing exact tests in discrete exponential families given a sufficient statistic. We also give a necessary and sufficient condition for uniqueness of minimal Markov basis. A general algebraic algorithm for constructing a connected Markov chain was given by Diaconis and Sturmfels (1998,The Annals of Statistics,26, 363–397). Their algorithm is based on computing Gröbner basis for a certain ideal in a polynomial ring, which can be carried out by using available computer algebra packages. However structure and interpretation of Gröbner basis produced by the packages are sometimes not clear, due to the lack of symmetry and minimality in Gröbner basis computation. Our approach clarifies partially ordered structure of minimal Markov basis.     

Optimization algorithm with probabilistic estimation

In this paper, we present a stochastic optimization algorithm based on the idea of the gradient method which incorporates a new adaptive-precision technique. Because of this new technique, unlike recent methods, the proposed algorithm adaptively selects the precision without any need for prior knowledge on the speed of convergence of the generated sequence. With this new technique, the algorithm can avoid increasing the estimation precision unnecessarily, yet it retains its favorable convergence properties. In fact, it tries to maintain a nice balance between the requirements for computational accuracy and those for computational expediency. Furthermore, we present two types of convergence results delineating under what assumptions what kinds of convergence can be obtained for the proposed algorithm.The work reported here was supported in part by NSF Grant No. ECS-85-06249 and USAF Grant No. AFOSR-89-0518. The authors wish to thank the anonymous reviewers whose careful reading and criticism have helped them improve the paper considerably.     

Statistical ensemble error bounds for homogenized microheterogeneous solids

Typically, in order to characterize the homogenized effective macroscopic response of new materials possessing random heterogeneous microstructure, a relation between averages is sought, where and where and are the stress and strain tensor fields within a statistically representative volume element (SRVE) of volume ||. The quantity, is known as the effective property, and is the elasticity tensor used in usual macroscale analyses. In order to generate homogenized responses computationally, a series of detailed boundary value representations resolving the heterogeneous microstructure, posed over the SRVEs domain, must be solved. This requires an enormous numerical effort that can overwhelm most computational facilities. A natural way of generating an approximation to the SRVEs response is by first computing the response of smaller (subrepresentative) samples, each with a different random realization of the microstructural type under investigation, and then to ensemble average the results afterwards. Compared to a direct simulation of an SRVE, testing many small samples is a computationally inexpensive process since the number of floating point operations is greatly reduced, as well as the fact that the samples responses can be computed trivially in parallel. However, there is an inherent error in this process. Clearly the populations ensemble average is not the SRVEs response. However, as shown in this work, the moments on the distribution of the population can be used to generate rigorous upper and lower error bounds on the quality of the ensemble-generated response. Two-sided bounds are given on the SRVE response in terms of the ensemble average, its standard deviation and its skewness.Received: December 11, 2001     

Improved Bounds and Simulation Procedures on the Value of the Multivariate Normal Probability Distribution Function

Improved bounds and simulation procedures on the value of the multivariate normal probability distribution function value are given in the paper. The author's variance reduction technique was based on the Bonferroni bounds involving the first two binomial moments only. The new variance reduction technique is adapted to the most refined new bounds developed in the last decade for the estimation the probability of union respectively intersection of events. Numerical test results prove the efficiency of the simulation procedures described in the paper.     

非仿射随机波动率的欧式障碍期权定价

研究非仿射随机波动率模型的欧式障碍期权定价问题时,首先介绍了非仿射随机波动率模型,其次利用投资组合和It^o引理,得到了该模型下扩展的Black-Schole偏微分方程.由于这个方程没有显示解,因此采用对偶蒙特卡罗模拟法计算欧式障碍期权的价格.最后,通过数值实例验证了算法的可行性和准确性.     

有类间距离因素聚类结果的比较分析

本文对于有类间距离因素聚类结果的比较，提出了类结构的空间描述方法和比较相似度的度量指标──夹角余弦，并推导出它的一些性质．最后，用蒙特卡洛模拟的结果阐明用夹角余弦作为聚类结果的相似性度量指标是合理的．     

基于跳扩散过程的可转换债券的定价

本文标的股票的方程采用跳扩散方程,首先规定一个跳跃的涨跌区间,这样就可以很快的找出跳跃点,我们根据跳跃点将股价聚类,然后把各个类看成是总体中抽取出来的一个样本,我们就可以估计出跳扩散方程中的所有参数.由于我们的标的股票的方程是含跳过程,因此无法找出完全保值的自融资策略,但我们可以根据风险最小化的原理给出可转换债券的价格,最后运用Monte Carlo模拟计算出了南京水运转债在0时刻的价格。     

Monte Carlo EM加速算法

EM算法是近年来常用的求后验众数的估计的一种数据增广算法, 但由于求出其E步中积分的显示表达式有时很困难, 甚至不可能, 限制了其应用的广泛性. 而Monte Carlo EM算法很好地解决了这个问题, 将EM算法中E步的积分用Monte Carlo模拟来有效实现, 使其适用性大大增强. 但无论是EM算法, 还是Monte Carlo EM算法, 其收敛速度都是线性的, 被缺损信息的倒数所控制, 当缺损数据的比例很高时, 收敛速度就非常缓慢. 而Newton-Raphson算法在后验众数的附近具有二次收敛速率. 本文提出Monte Carlo EM加速算法, 将Monte Carlo EM算法与Newton-Raphson算法结合, 既使得EM算法中的E步用Monte Carlo模拟得以实现, 又证明了该算法在后验众数附近具有二次收敛速度. 从而使其保留了Monte Carlo EM算法的优点, 并改进了Monte Carlo EM算法的收敛速度. 本文通过数值例子, 将Monte Carlo EM加速算法的结果与EM算法、Monte Carlo EM算法的结果进行比较, 进一步说明了Monte Carlo EM加速算法的优良性.     

Stopping Rules for the Stochastic Nested Partitions Method

We have recently developed a global optimization methodology for solving combinatorial problems with either deterministic or stochastic performance functions. This method, the Nested Partitions (NP) method has been shown to generate a Markov chain and with probability one to converge to a global optimum. In this paper, we study the rate of convergence of the method through the use of Markov Chain Monte Carlo (MCMC) methods, and use this to derive stopping rules that can be applied during simulation-based optimization. A numerical example serves to illustrate the feasibility of our approach.     

Robustness analysis in Multi-Objective Mathematical Programming using Monte Carlo simulation

In most multi-objective optimization problems we aim at selecting the most preferred among the generated Pareto optimal solutions (a subjective selection among objectively determined solutions). In this paper we consider the robustness of the selected Pareto optimal solution in relation to perturbations within weights of the objective functions. For this task we design an integrated approach that can be used in multi-objective discrete and continuous problems using a combination of Monte Carlo simulation and optimization. In the proposed method we introduce measures of robustness for Pareto optimal solutions. In this way we can compare them according to their robustness, introducing one more characteristic for the Pareto optimal solution quality. In addition, especially in multi-objective discrete problems, we can detect the most robust Pareto optimal solution among neighboring ones. A computational experiment is designed in order to illustrate the method and its advantages. It is noteworthy that the Augmented Weighted Tchebycheff proved to be much more reliable than the conventional weighted sum method in discrete problems, due to the existence of unsupported Pareto optimal solutions.     

基于藤Copula的多资产交换期权模拟定价

传统的多维Copula是用单个参数来度量多变量之间的相依关系,这限制了该类Copula在描述多变量之间相依结构.为了解决这一问题,提出了一种使用藤构造三维Copula的算法,用蒙特卡罗方法分别模拟传统的单参数三维Copula和藤构造的三维Copula,并给三资产的交换期权定价,发现藤构造的Copula在定价上与单参数多维Copula存在明显的差别,使用藤构造的Copula在描述相依结构时有较大弹性.     

Three-term asymptotic expansions for the moments of the random walk with triangular distributed interference of chance

In this study, a semi-Markovian random walk with a discrete interference of chance (X(t)) is considered and under some weak assumptions the ergodicity of this process is discussed. The exact formulas for the first four moments of ergodic distribution of the process X(t) are obtained when the random variable ζ₁, which is describing a discrete interference of chance, has a triangular distribution in the interval [s, S] with center (S + s)/2. Based on these results, the asymptotic expansions with three-term are obtained for the first four moments of the ergodic distribution of X(t), as a ≡ (S − s)/2 → ∞. Furthermore, the asymptotic expansions for the variance, skewness and kurtosis of the ergodic distribution of the process X(t) are established. Finally, by using Monte Carlo experiments it is shown that the given approximating formulas provide high accuracy even for small values of parameter a.     

多层线性模型参数估计的MCEM算法

应用Monte Carlo EM(MCEM)算法给出了多层线性模型参数估计的新方法,解决了EM算法用于模型时积分计算困难的问题,并通过数值模拟将方法的估计结果与EM算法的进行比较,验证了方法的有效性和可行性.     

Importance Sampling for Backward SDEs

In this article, we explain how the importance sampling technique can be generalized from simulating expectations to computing the initial value of backward stochastic differential equations (SDEs) with Lipschitz continuous driver. By means of a measure transformation we introduce a variance reduced version of the forward approximation scheme by Bender and Denk [4 Bender , C. , and Denk , R. 2007 . A forward scheme for backward SDEs . Stochastic Processes and their Applications 117 ( 12 ): 1793 – 1812 . [Google Scholar]] for simulating backward SDEs. A fully implementable algorithm using the least-squares Monte Carlo approach is developed and its convergence is proved. The success of the generalized importance sampling is illustrated by numerical examples in the context of Asian option pricing under different interest rates for borrowing and lending.     

有偏总体的极差控制图

根据加权标准差方法建立有偏总体的极差控制图,它基于有偏总体来计算对应于正态分布的控制图常数,根据样本数据的偏度来计算上下控制限,对于总体是对称分布,该控制图退化为标准的休哈特控制图.最后,用蒙特卡洛方法给出了改进的控制图常数.     

基于顾客评价变化的两种CSI计算方法的比较

不同背景下因调查量表和评价标准的影响而导致的顾客评价的变化分为三类:量表变化、基准变化和结构变化。合理的CSI计算方法需要准确地反映结构变化,不反映量表变化和基准变化。本文采用蒙特卡罗模拟方法比较了两种计算方法在三种变化下的CSI结果。模拟结果表明:通用方法不会反映量表变化,能灵敏地反映基准变化,同时准确地反映结构变化;改进方法不会反映量表变化和基准变化,而是能够准确地反映出结构变化。因此,改进方法优于通用方法。同时,当不同品牌的CSI分值较接近时,CSI的排序不稳定;而当不同品牌CSI分值差异较大时,排序具有稳定性。     

Multilevel sequential Monte Carlo: Mean square error bounds under verifiable conditions

In this article, we consider the multilevel sequential Monte Carlo (MLSMC) method of Beskos et al. (Stoch. Proc. Appl. [to appear]). This is a technique designed to approximate expectations w.r.t. probability laws associated to a discretization. For instance, in the context of inverse problems, where one discretizes the solution of a partial differential equation. The MLSMC approach is especially useful when independent, coupled sampling is not possible. Beskos et al. show that for MLSMC the computational effort to achieve a given error, can be less than independent sampling. In this article we significantly weaken the assumptions of Beskos et al., extending the proofs to non-compact state-spaces. The assumptions are based upon multiplicative drift conditions as in Kontoyiannis and Meyn (Electron. J. Probab. 10 [2005]: 61–123). The assumptions are verified for an example.