New Techniques and Analyses for Random Sampling

Stanford University, Stanford CA

Investigators

Abstract

Every part of modern life is studied using computer simulation. This includes -medicine: computer studies of protein folding for designing new drugs; -physics: basic estimates of mass and charge are most accurately obtained via lattice gauge theory; -business: the number of bank tellers or grocery checkers that will optimize customer traffic flows; -and virtually every area of the social sciences. In the face of huge, sophisticated data sets, new algorithms are required to efficiently and accurately carry out such simulations. At the same time, in this "anything goes" world, questions of how long an algorithm should be run in order to do its job must be studied-and answered. A very simple example would be, "How many times do we shuffle a deck of cards to completely mix it?" The research supported by this award suggests a host of such algorithms using sequential importance sampling which are broadly applicable. It also incorporates new proof techniques from the geometric theory of Markov chains to rigorously pin down running times. This work addresses those instances when researchers are sometimes too "fast and loose", which can yield misleading results. The proposed algorithms can help detect and fix these issues. The project provides research training opportunities for graduate students. The proposed new research is to design new algorithms, and analyze widely used existing algorithms for simulation. This is centered around four main themes: importance sampling where new criteria for required sample size are developed and tried out in problems of missing data and contingency tables; developing analytic and geometric techniques adapted from partial differential equations and geometry (Whitney covers, John domains, Carlesson estimates) to develop geometric theory of Markov chains; exploring connections between the generators of Markov processes and algebraic complexes (Hodge theory) developed by combinatorialists and topologists; the study of mathematics of shuffling cards. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.