- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Efficient simulation for weighted branching trees
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Efficient simulation for weighted branching trees Olvera Cravioto, Mariana
Description
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 Metadata
Title |
Efficient simulation for weighted branching trees
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2015-06-04T11:01
|
Description |
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.
|
Extent |
59 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Columbia University
|
Series | |
Date Available |
2016-01-04
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivs 2.5 Canada
|
DOI |
10.14288/1.0221667
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Faculty
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivs 2.5 Canada