Efficient Simulation for Branching Processes

分支过程的高效模拟

• 批准号: 1654544
• 负责人: Mariana Olvera-Cravioto
• 金额: $ 11万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2018-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1654544&HistoricalAwards=false
• 关键词: Efficient; Simulation; Branching; Processes

The analysis of a variety of problems in science and engineering, ranging from population and statistical physics models to the analysis of queueing systems, computer networks and the internet, leads to mathematical structures known as distributional equations. In most instances, these distributional equations cannot be solved analytically, and their solutions need to be computed numerically, e.g., via stochastic simulation. However, in many cases, traditional simulation methods require such an extraordinary number of computations that they become intractable, and therefore there is a need to develop more efficient alternatives. The work that will be funded through this award focuses in a particular type of distributional equations, known as branching stochastic fixed-point equations (BSFPEs). These equations appear naturally in the study of locally tree-like graphs, and are related to the analysis of weighted branching processes. The proposed work consists in developing and analyzing new stochastic simulation methods to compute the solutions to a large class of BSFPEs. In particular, the principal investigator will provide convergence guarantees and mechanisms to compute confidence intervals for iterative bootstrap-type algorithms, as well as develop new importance sampling algorithms for the estimation of rare events. The new algorithms will be easy to implement by scientists and engineers working on a wide range of problems.

从人口和统计物理模型到排队系统，计算机网络和互联网的分析，对各种科学和工程问题的分析都导致了数学结构称为分布方程。 在大多数情况下，这些分布方程无法分析求解，并且需要通过数值计算它们的解决方案，例如，通过随机仿真来计算。 但是，在许多情况下，传统的仿真方法需要大量的计算，以使它们变得棘手，因此有必要开发更有效的替代方法。将通过该奖项资助的工作重点是特定类型的分布方程，称为分支随机定点方程（BSFP）。 这些方程在本地树状图的研究中自然出现，并且与加权分支过程的分析有关。 提出的工作包括开发和分析新的随机仿真方法，以计算大量BSFP的解决方案。 特别是，首席研究者将提供收敛的保证和机制，以计算迭代引导型算法的置信区间，并为估计罕见事件的估计而开发新的重要性采样算法。 从事各种问题的科学家和工程师将易于实施新的算法。