Kinetic Monte Carlo - Algorithm

Algorithm

The KMC algorithm for simulating the time evolution of a system where some processes can occur with known rates r can be written for instance as follows:

1. Set the time .
2. Form a list of all possible rates in the system
3. Calculate the cumulative function for, where N is the total number of transitions.
4. Get a uniform random number
5. Find the event to carry out i by finding the i for which (this can be achieved efficiently using binary search).
6. Carry out event i.
7. Get a new uniform random number .
8. Update the time with, where
9. Recalculate all rates which may have changed due to the transition. If appropriate, remove or add new transitions i. Update N and the list of events accordingly.
10. Return to step 2.

(Note: because the average value of is equal to unity, the same average time scale can be obtained by instead using in step 8. In this case, however, the delay associated with transition i will not be drawn from the Poisson distribution described by, but will instead be the mean of that distribution.)

This algorithm is known in different sources variously as the residence-time algorithm or the n-fold way or the Bortz-Kalos-Lebowitz (BKL) algorithm or just the kinetic Monte Carlo (KMC) algorithm. It is important to note that the timestep involved is a function of the probability that all events i, did not occur.