# Método de Montecarlo cinético

El método de Monte-Carlo cinético, KMC (de las siglas en inglés kinetic Monte Carlo) es un tipo de Método de Montecarlo de simulación ideado para simular la evolución temporal de algunos procesos que ocurren en la naturaleza con una frecuencia (tasa de ocurrencia) dada. Es importante hacer notar y comprender que dichas tasas son inputs para el algoritmo KMC, i.e. el algoritmo per se no puede predecir la tasa de ocurrencia del proceso.
El método KMC en esencia es equivalente a los métodos dynamic Monte Carlo method y Gillespie algorithm. La principal diferencia entre ellos, parece ser, es la terminología y las áreas de aplicación: KMC se utiliza principalmente en física mientras que dMC o GSA se suelen utilizar en química.

## Esquema del algoritmo

El algoritmo KMC para simular la evolución temporal de un sistema donde ciertos procesos pueden ocurrir con ciertas (conocidas) tasas, r, puede esquematizarse de la forma que sigue:
* Fijar el instante inicial $t=0$.
* Crear una lista de todas las posibles tasas de transición en el sistema $r_{i}$
* Calcular la función cumulativa $R_{i}=\sum _{j=1}^{i}r_{j}$ para todo $i=1,\ldots ,N$, donde N es el número total de transiciones.
* Generar un número aleatorio en arreglo a una distribución uniforme, $u\in (0,1]$
* Encontrar la transición que se llevará a cabo, $i$, siendo $i$ aquel índice para el cual se cumpla $R_{i-1}<uR_{N}\leq R_{i}$ (esta búsqueda puede realizarse eficientemente mediante el uso de una búsqueda binaria, binary search).
* Llevar a cabo la transición $i$.
* Generar un nuevo número aleatorio de distribución uniforme, $u^{\prime }\in (0,1]$.
* Actualizar el tiempo mediante $t=t+\Delta t$, donde $\Delta t=R_{N}^{-1}\ln(1/u^{\prime })$.
* Recalcular todas las tasas $r_{i}$, dado que éstas pueden haber cambiado debido a la transición ocurrida. Si se diera el caso, eliminar o añadir nuevas transiciones $i$. En consecuencia, actualizar N y la lista de sucesos.
* Volver al paso 2.
(Nota: dado que el valor medio de $\ln(1/u^{\prime })$ es igual a la unidad, se puede obtener la misma escala temporal promedio usando $\Delta t=R_{N}^{-1}$ en el paso 8. En tal caso, sin embargo, el lapso temporal asociado con la transición $i$ no se extraerá de la distribución de Poisson descrita por $r_{i}$, sino que será en su lugar la media de dicha distribución.)
Este algoritmo puede ser mencionado en diferentes y diversas fuentes como algoritmo de tiempo de residencia (residence-time algorithm) o n-fold way o como el algoritmo Bortz-Kalos-Lebowitz (BKL) o simplemente como algoritmo kinetic Monte Carlo (KMC). Es importante hacer notar que el paso de tiempo involucrado es una función de la probabilidad de que no ocurra ninguno de los sucesos $i$.

## Algoritmos con dependencia temporal

En el caso en el que las tasas de transición dependan del tiempo, i.e. $r_{i}(t)$, como resulta evidente el paso 8 en el esquema anterior tiene que modificarse por (Prados 1997):
    $\int _{0}^{\Delta t}R_{i}(t')dt'=\ln(1/u^{\prime })$.
En cuyo caso, la transición que tendrá lugar (paso 5) ha de ser elegida después de esto mediante
    $R_{i-1}(\Delta t)<uR_{N}(\Delta t)\leq R_{i}(\Delta t)$
Otro algoritmo muy similar a este es el también conocido como el método de primera reacción (First Reaction Method (FRM)), consistente en elegir la primera reacción, lo que significa elegir el menor tiempo $\Delta t_{i}$, y el correspondiente índice de reacción $i$, a partir de la siguiente ecuación
    $\int _{0}^{\Delta t_{i}}r_{i}(t')dt'=\ln(1/u_{i})$,
donde $u_{i}\in (0,1]$ son N números aleatorios.

## Comentarios sobre el algoritmo

La principal y más importante característica del método KMC (también del método FRM) es que en caso de que las tasas sean correctas, si los procesos considerados son de tipo proceso de Poisson y si los diferentes procesos son estadísticamente independientes ( i.e. no están correlacionados), entonces el algoritmo KMC (o FRM) devuelve una escala temporal realista y correcta para la evolución del sistema simulado.
Si además las transiciones siguen una relación de balance detallado, el algoritmo se puede utilizar para simular el equilibrio termodinámico. Sin embargo, el método KMC normalmente se utiliza para simular procesos de no equilibrio (Meng 1994), en cuyo caso las relaciones de balance detallado no serán satisfechas.
El algoritmo KMC es eficiente en el sentido que cada iteración garantiza una transición. No obstante, en el esquema presentado anteriormente ello requiere $N$ operaciones para cada transición, lo cual no es muy eficiente desde el punto de vista computacional. En muchas ocasiones ésta puede ser mejorada notablemente mediante el agrupamiento de transiciones del mismo tipo en contenedores (bins), y/o formando estructura de datos en árbol de los sucesos. Un algoritmo de este tipo ha sido recientemente publicado y probado en (Slepoy 2008).
La mayor desventaja de los métodos KMC es que para reproducir con fidelidad el sistema bajo consideración se tienen que conocer todas y cada una de las reacciones (transiciones) y sus respectivas tasas de ocurrencia. El método por sí mismo no puede hacer predicciones en este respecto.

## Historia

La primera publicación que describió las características básicas del modelo KMC (e.g. usar una función cumulativa para seleccionar una transición y un cálculo de la escala temporal del tipo 1/R) data de 1966 y sus autores Young and Elcock (Young 1966). El algoritmo de tiempo de residencia también se publicó por esa fecha, (Cox 1965).
De forma independiente al trabajo de Young y Elcock, al parecer, Bortz, Kalos and Lebowitz (Bortz 1975) desarrollaron un algoritmo KMC para simular el Modelo de Ising, el cual llamaron n-fold way. Las bases de su algoritmo son las mismas que en el caso de (Young 1996), aunque ellos proporcionaron muchos más detalles sobre el método.
En los años sucesivos, Dan Gillespie publicó lo que hoy en día es conocido como el método de Gillespie para describir sistemas de reacciones químicas (Gillespie, 1976). El algoritmo es muy similar y la técnica de avance temporal es esencialmente la misma que en el KMC.
Desde la fecha de este documento (junio de 2006) no hay un tratado definitivo de la teoría del KMC, aunque Fichthorn y Weinberg han tratado en gran detalle la teoría para simulaciones KMC en equilibrio termodinámico en (Fichthorn 1991). También existe una muy buena introducción al método escrita por Art Voter (Voter 2005), y por A.P.J. Jansen (Jansen 2003),. Por último (Chatterjee 2007) or (Chotia 2008) es un review del tema relativamente reciente.
En marzo de 2006, el primer software comercial que hace uso de KMC para simular la difusión y la activación/desactivación de dopantes en Silicio y materiales tipo Silicio fue liberado por Synopsys, notificado por Martin-Bragado et al. (Martin-Bragado 06).

## Variedades de KMC

El método KMC puede ser categorizado por cómo los objetos se mueven o las reacciones tienen lugar. Las siguientes subdivisiones son las más utilizadas:
* Lattice KMC (LKMC) que significa que el método KMC se lleva a cabo en una red atómica. En ocasiones esta variedad también se puede encontrar designada como atomistic KMC (AKMC).
* Object KMC (OKMC) donde KMC se lleva a cabo con defectos or impurezas, las cuales se encuentran saltando bien aleatoriamente, bien en direcciones preferenciales. Tan sólo se incluyen las posiciones de los objetos en movimiento en la simulación, a diferencia de aquellos que forman parte de la red de fondo.
* Event KMC (EKMC) o First-passage KMC (FPKMC) que es una variedad de OKMC donde la siguiente reacción entre objetos (e.g. agrupación de dos, aniquilación por pares, etc.) se elige con un algoritmo KMC, teniendo en cuenta la posición de los objetos (Dalla Torre 2005, Oppelstrup 2006).