Skip to main content    

An official website of the United States government

Here’s how you know

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

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

https://www.nist.gov/itl/math/acmd-seminar-stochastic-enumeration-importance-sampling

            -  Topics  -  All Topics 
-  Advanced communications 
-  Artificial intelligence 
-  Bioscience 
-  Buildings and construction 
-  Chemistry 
-  Climate 
-  Cybersecurity 
-  Electronics 
-  Energy 
-  Environment 
-  Fire 
-  Forensic science 
-  Health 
-  Information technology 
-  Infrastructure 
-  Manufacturing 
-  Materials 
-  Mathematics and statistics 
-  Metrology 
-  Nanotechnology 
-  Neutron research 
-  Performance excellence 
-  Physics 
-  Public safety 
-  Resilience 
-  Standards 
-  Transportation 
 
            -  Publications 
            -  Labs & Major Programs  -  Laboratories    -  Communications Technology Laboratory 
  -  Engineering Laboratory 
  -  Information Technology Laboratory 
  -  Material Measurement Laboratory 
  -  Physical Measurement Laboratory 
-  User Facilities    -  NIST Center for Neutron Research 
  -  CNST NanoFab 
-  Research Test Beds 
-  Research Projects 
-  Tools & Instruments 
-  Major Programs    -  Baldrige Performance Excellence Program 
  -  CHIPS for America Initiative 
  -  Manufacturing Extension Partnership (MEP) 
  -  Office of Advanced Manufacturing 
  -  Special Programs Office 
  -  Technology Partnerships Office 
 
            -  Services & Resources  -  Standards and Measurements    -  Calibration Services 
  -  Laboratory Accreditation (NVLAP) 
  -  Quality System 
  -  Standard Reference Materials (SRMs) 
  -  Standards.gov 
  -  Time Services 
  -  Office of Weights and Measures 
-  Software 
-  Data    -  Chemistry WebBook 
  -  National Vulnerability Database 
  -  Physical Reference Data 
  -  Standard Reference Data (SRD) 
-  Storefront 
-  License & Patents 
-  Computer Security Resource Center (CSRC) 
-  NIST Research Library 
 
            -  News & Events  -  News 
-  Events 
-  Blogs 
-  Feature Stories 
-  Awards 
-  Video Gallery 
-  Image Gallery 
-  Media Contacts 
 
            -  About NIST  -  About Us    -  Leadership 
  -  Organization Structure 
  -  Budget & Planning 
-  Contact Us 
-  Visit 
-  Careers    -  Student programs 
-  Work with NIST 
-  History    -  NIST Digital Archives 
  -  NIST Museum 
  -  NIST and the Nobel 
-  Educational Resources 
 

Information Technology Laboratory

## Applied and Computational Mathematics Division

-  Projects/Programs 
-  How to Work With Us 
-  NIST Publications Searchable Database 
-  Staff Directory 
-  News & Updates 
-  Resources/Services 

# ACMD Seminar: Stochastic Enumeration with Importance Sampling

## Share

Facebook

Linkedin

Twitter

Email

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	Gaithersburg

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

**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.

Mathematics and statisticsNumerical methods and software

## Contacts

### HEADQUARTERS

301-975-2000

Webmaster | Contact Us | Our Other Offices

TwitterFacebookLinkedInInstagramYouTubeGiphyRSS FeedMailing List

Feedback

            -  Site Privacy 
            -  Accessibility 
            -  Privacy Program 
            -  Copyrights 
            -  Vulnerability Disclosure 
            -  No Fear Act Policy 
            -  FOIA 
            -  Environmental Policy 
            -  Scientific Integrity 
            -  Information Quality Standards 
            -  Commerce.gov 
            -  Science.gov 
            -  USA.gov 
            -  Vote.gov