Efficient Simulation for Branching Processes

对各种科学和工程问题的分析，从人口和统计物理模型到排队系统、计算机网络和互联网的分析，导致了被称为分布方程的数学结构。在大多数情况下，这些分布方程不能解析解，它们的解需要数值计算，例如，通过随机模拟。然而，在许多情况下，传统的模拟方法需要如此大量的计算，以至于它们变得难以处理，因此需要开发更有效的替代方案。通过该奖项资助的工作将集中于一种特殊类型的分布方程，即分支随机不动点方程（BSFPEs）。这些方程在局部树状图的研究中很自然地出现，并且与加权分支过程的分析有关。提出的工作包括开发和分析新的随机模拟方法来计算一类大的bsfpe的解。特别是，首席研究员将提供收敛保证和机制来计算迭代自举型算法的置信区间，以及开发用于估计罕见事件的新的重要采样算法。新的算法将很容易被科学家和工程师用于解决各种各样的问题。

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.