Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

ACMD Seminar: Stochastic Enumeration with Importance Sampling

Alathea Jensen
Doctoral Candidate, George Mason University and Guest Researcher, ACMD, NIST

Monday, December 11, 2017, 15:00 - 16:00
Building 222, Room B-263

Monday, December 11, 2017, 13:00 - 14:00
Room 1-4058

Slides: Adobe PDF

Host: Isabel Beichl

Abstract: A great many varied problems in the computational sciences can be solved by summing a cost function over the nodes of a decision tree, and many approximation algorithms exist to estimate such sums. One of the most recent of these algorithms is Stochastic Enumeration (SE), introduced in 2013 by Rubinstein. In 2015, Vaisman and Kroese provided a rigorous analysis of the variance of SE, and also showed that SE can be extended to a fully polynomial randomized approximation scheme for certain cost functions on random trees. However, no one has yet incorporated an importance function into SE to allow non-uniform selection of tree nodes. This talk will present an algorithm that incorporates an importance function into SE, and will provide theoretical analysis including proof of correctness and bounds on the variance of estimates produced by the algorithm. The talk will also present the results of numerical experiments to measure the variance of applications of the algorithm to practical problems, such as counting linear extensions of a poset.

Bio: Alathea is a doctoral candidate at George Mason University, planning to graduate in the spring. Her adviser is Jim Lawrence, and for the past year and a half she has been working as a guest researcher at NIST, under the guidance of Isabel Beichl, with whom she have been working on sequential importance sampling algorithms.


Created November 21, 2017, Updated November 15, 2019