STA 290 Seminar: Mariana Olvera-Cravioto

STA 290 Seminar Series

Tuesday, January 12th, 4:10pm, MSB 1147 (Colloquium Room)

Refreshments at 3:30pm in MSB 4110 (Statistics Lounge)

Speaker:          Mariana Olvera-Cravioto (Columbia University)

Title:                “Efficient simulation for weighted branching trees”

Abstract:          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 simulating 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 distributions are in general unavailable. Unlike for the Galton-Watson process, Laplace transform methods in this context are problematic beyond a few special cases. 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 this algorithm.