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.
Let M be the number of possible MC events (or state transitions), and let r_{i} be the rate at which
the i^{th} event should occur. The total rate is
R = ∑^{M}_{i=1} r_{i}.
For an accurate simulation, event i should occur with probability
r_{i}/R. (For equilibrium MC done according to BKL, the calculations are the same, but the {r_{i}}
are transition probabilities, not rates.) If the
rates are updated in the obvious, naive way, the
cost per step is O(M) which could be prohibitive for a large M. We
explain how to use a dynamic binary tree to reduce this cost to O(log_{2} M) per step. There is a onetime cost for
establishing the dynamic tree. However, for all but very small values of M, this cost is easily recouped in the perstep
savings.
[PRESENTATION SLIDES]
