BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Efficient simulation for weighted branching trees Olvera Cravioto, Mariana


Motivated by recent results for the analysis of information ranking algorithms on complex networks and parallel queueing networks with synchronization, we propose an efficient algorithm for simu- lating the endogenous solution to max-plus branching stochastic fixed-point equations. The aforementioned solutions can be constructed on a weighted branching process, but closed-form expressions for their distri- butions are in general unavailable. Unlike for the Galton-Watson process, Laplace transform methods in this context are also problematic. Hence, a stochastic simulation approach seems to be the most natural way of numerically approximating the distributions and moments of these solutions. Naive Monte Carlo techniques, however, are extremely inefficient due to the geometric growth of the underlying trees. We describe in this talk an algorithm based on iterative bootstrap whose complexity grows linearly (as opposed to exponentially) in the number of generations of the weighted branching process being simulated. We also show the consistency of a wide class of estimators based on our algorithm.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivs 2.5 Canada