Abstract:
This pair of talks will cover some basic algorithms for accelerating
dynamic Monte Carlo, meaning Monte Carlo for cases in which the
probability distribution sampled changes as a consequence of sampling.
We explain how to use a slightly more elaborate tree and a more
sophisticated strategy for grouping of the r_{i} to reduce the cost per
step to O(log_{2}^{*} M). Here log^{*} X denotes the number of
iterations of X=log X required before X becomes negative. As a
point of reference, if D denotes the US national debt in dollars,
then log_{10}^{*} D = 3.
In this case, the onetime costs are slightly greater and the cost per
step is greatly reduced.
[PRESENTATION SLIDES]
