Efficient simulation for branching linear recursions

Ningyuan Chen; Mariana Olvera-Cravioto

doi:10.1109/WSC.2015.7408378

Efficient simulation for branching linear recursions

Ningyuan Chen, Mariana Olvera-Cravioto

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

2 Citations (Scopus)

Abstract

We provide an algorithm for simulating the unique attracting fixed-point of linear branching distributional equations. Such equations appear in the analysis of information ranking algorithms, e.g., PageRank, and in the complexity analysis of divide and conquer algorithms, e.g., Quicksort. The naive simulation approach would be to simulate exactly a suitable number of generations of a weighted branching process, which has exponential complexity in the number of generations being sampled. Instead, we propose an iterative bootstrap algorithm that has linear complexity; we prove its convergence and the consistency of a family of estimators based on our approach.

Original language	English
Title of host publication	2015 Winter Simulation Conference, WSC 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2716-2727
Number of pages	12
ISBN (Electronic)	9781467397438
DOIs	https://doi.org/10.1109/WSC.2015.7408378
Publication status	Published - 16 Feb 2016
Externally published	Yes
Event	Winter Simulation Conference, WSC 2015 - Huntington Beach, United States Duration: 6 Dec 2015 → 9 Dec 2015

Publication series

Name	Proceedings - Winter Simulation Conference
Volume	2016-February
ISSN (Print)	0891-7736

Conference

Conference	Winter Simulation Conference, WSC 2015
Country/Territory	United States
City	Huntington Beach
Period	6/12/15 → 9/12/15

Bibliographical note

Publisher Copyright:
© 2015 IEEE.

Access to Document

10.1109/WSC.2015.7408378

Cite this

@inproceedings{28d1e2577b5a4adab73f7e330d204084,

title = "Efficient simulation for branching linear recursions",

abstract = "We provide an algorithm for simulating the unique attracting fixed-point of linear branching distributional equations. Such equations appear in the analysis of information ranking algorithms, e.g., PageRank, and in the complexity analysis of divide and conquer algorithms, e.g., Quicksort. The naive simulation approach would be to simulate exactly a suitable number of generations of a weighted branching process, which has exponential complexity in the number of generations being sampled. Instead, we propose an iterative bootstrap algorithm that has linear complexity; we prove its convergence and the consistency of a family of estimators based on our approach.",

author = "Ningyuan Chen and Mariana Olvera-Cravioto",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; Winter Simulation Conference, WSC 2015 ; Conference date: 06-12-2015 Through 09-12-2015",

year = "2016",

month = feb,

day = "16",

doi = "10.1109/WSC.2015.7408378",

language = "English",

series = "Proceedings - Winter Simulation Conference",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2716--2727",

booktitle = "2015 Winter Simulation Conference, WSC 2015",

}

Chen, N & Olvera-Cravioto, M 2016, Efficient simulation for branching linear recursions. in 2015 Winter Simulation Conference, WSC 2015., 7408378, Proceedings - Winter Simulation Conference, vol. 2016-February, Institute of Electrical and Electronics Engineers Inc., pp. 2716-2727, Winter Simulation Conference, WSC 2015, Huntington Beach, United States, 6/12/15. https://doi.org/10.1109/WSC.2015.7408378

Efficient simulation for branching linear recursions. / Chen, Ningyuan; Olvera-Cravioto, Mariana.
2015 Winter Simulation Conference, WSC 2015. Institute of Electrical and Electronics Engineers Inc., 2016. p. 2716-2727 7408378 (Proceedings - Winter Simulation Conference; Vol. 2016-February).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Efficient simulation for branching linear recursions

AU - Chen, Ningyuan

AU - Olvera-Cravioto, Mariana

PY - 2016/2/16

Y1 - 2016/2/16

N2 - We provide an algorithm for simulating the unique attracting fixed-point of linear branching distributional equations. Such equations appear in the analysis of information ranking algorithms, e.g., PageRank, and in the complexity analysis of divide and conquer algorithms, e.g., Quicksort. The naive simulation approach would be to simulate exactly a suitable number of generations of a weighted branching process, which has exponential complexity in the number of generations being sampled. Instead, we propose an iterative bootstrap algorithm that has linear complexity; we prove its convergence and the consistency of a family of estimators based on our approach.

AB - We provide an algorithm for simulating the unique attracting fixed-point of linear branching distributional equations. Such equations appear in the analysis of information ranking algorithms, e.g., PageRank, and in the complexity analysis of divide and conquer algorithms, e.g., Quicksort. The naive simulation approach would be to simulate exactly a suitable number of generations of a weighted branching process, which has exponential complexity in the number of generations being sampled. Instead, we propose an iterative bootstrap algorithm that has linear complexity; we prove its convergence and the consistency of a family of estimators based on our approach.

UR - https://www.scopus.com/pages/publications/84962846995

U2 - 10.1109/WSC.2015.7408378

DO - 10.1109/WSC.2015.7408378

M3 - Conference Paper published in a book

AN - SCOPUS:84962846995

T3 - Proceedings - Winter Simulation Conference

SP - 2716

EP - 2727

BT - 2015 Winter Simulation Conference, WSC 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - Winter Simulation Conference, WSC 2015

Y2 - 6 December 2015 through 9 December 2015

ER -

Efficient simulation for branching linear recursions

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this