Open Collections

Efficient simulation for weighted branching trees

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Probability theory and stochastic processes; Statistics; Operation research

video/mp4

Author affiliation: Columbia University

2016-01-04

Attribution-NonCommercial-NoDerivs 2.5 Canada

http://hdl.handle.net/2429/56151

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/2.5/ca/