Efficient Simulation for 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.