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.