多面體均勻分配之產生及其在蒙地卡羅模擬之應用

Abstract

本計畫介紹如何利用迪氏分配來生成各種多面體區域(包括凸面與非凸面多面體)之均勻分配。此結果可用來估計具有線性限制之最佳化問題的解，並可以應用在許多抽樣及蒙地卡羅模擬的問題上，例如估計隨機變數總和的尾端機率、多變數的適合度檢定等。利用現有文獻中產生迪氏分配之最高效率演算法，我們驗証本計畫所提之方法比現有文獻中的方法表現更佳。

In this project, we propose a method for generating the uniform distribution over a general polyhedron (including the convex and non-convex polyhedron) by utilizing the Dirichlet generating algorithm. The result is quite useful for solving some constrained optimization problems and has many applications in sampling and Monte Carlo simulations, such as estimation of tail probabilities for the sum of random variables, multivariate KS tests, etc. We show that by using state-of-the-art Dirichlet generation algorithms, our proposed method are superior to the existing methods in terms of computational efficiency.