previous up next SYLLABUS  Previous: 5.2 Stochastic theory  Up: 5 MONTE-CARLO METHOD  Next: 5.4 A scheme for


5.3 Particle orbits


Slide : [ deterministic - Taylor - stochastic - Feynman-Kac || VIDEO login]

In the Monte Carlo method, the initial condition or indeed any function is discretized using quasi-particles; differential operators are therefore reformulated in terms of particle motions. Remember that a quasi-particle is defined in (1.4.7#eq.1) by a weight $ w_i$ , a position $ x_i$ and a shape function $ S_i$ ; for simplicity, we assume here unit weights $ w_i=1$ and point shaped particles in the form of Dirac pulses $ S_i(x)=\delta(x_i)$ . The solution can then be calculated from the particles density obtained from the positions $ \{x_i(t)\}$ called particle orbits. By construction, the lowest order moment is perfectly conserved, since no particle is lost.

To show the contrast between the Taylor and the Feynman-Kac theorems, which provide a rigorous foundation for the Monte Carlo method, the deterministic and the stochastic motion are first considered separately.

* Deterministic orbits
satisfy an ordinary differential equation for the position $ X(t)$ as a function of time $ t$

$\displaystyle \frac{d X(t)}{dt}=v(X(t),t)$ (1)

or

$\displaystyle d X(t)=v(X(t),t)dt$ (2)

This is solved numerically using the methods discussed in section 1.2.1, using an explicit or implicit discretization of time
\begin{subequations}\begin{alignat}{2} {X}(t+\Delta t)&={X}(t) + {v}({X}(t),t)\D...
...a t\right)\Delta t\quad && \textrm{\lq\lq implicit''} \end{alignat}\end{subequations}

For an ensemble of $ N$ particles with orbits $ {x}_i(t)$ , the particle density distribution function $ f({x},t)$ is obtained by superposition

$\displaystyle f(x,t)=\sum_{i=0}^N\delta (x-x_i(t))$ (4)

and is plotted in the applet below using the projection (1.4.7#eq.3) from section 1.4.
JBONE applet:  press Start/Stop to simulate the deterministic motion of a particle or random walker (red dot). The contribution to the density distribution (black line) is obtained from a linear assignment of the position on a coarse grid.



Numerical experiments: deterministic orbits
  1. Study in slow motion how the density function is obtained from a linear assignment on the coarse grid.
  2. Increase the number of Walkers=100, press Initialize and Start/Stop to verify that the lowest order moment is exactly conserved for all times. Increase the number of MeshPoints=64 and discuss whether the solution gets more precise.
  3. Increase to TimeStep=1 or any signed integer; verify that the deterministic motion of a cloud of particles provides in fact an exact description of advection once the initial condition has been discretized.

If a large number of particles approximate a smooth density function and each individual orbit $ X(t)$ evolves in a deterministic manner

$\displaystyle dX(t)=v({X}(t),t)dt.$ (5)

then the Taylor's transport theorem states that the evolution of the particle density distribution function $ f({x},t)$ satisfies the advection equation

$\displaystyle \frac{\partial f}{\partial t}+\frac{\partial}{\partial x}\left( {v}f \right)=0$ (6)

The theorem makes it possible to study a PDE instead of an $ N$ -particle system; the reverse is also true and will be used to solve the advection equation with particles.

* Stochastic particle orbits
are defined as an ensemble of possible orbits with different probabilities. Imagine a snowflake falling slowly from the sky: the motion is unpredictable and each evolution can be described with an orbit $ {X(t)}$ following the stochastic differential equation

$\displaystyle d{X}(t)={v}({X}(t),t)dt + b({X}(t),t) \circ d{W}_t$ (7)

where $ {W}_t$  is a Wiener processes (Brownian motion). Averaging over a large number of orbits, the average velocity and the broadening of possible orbits are readily obtained (exercise 5.02) as


Stochastic orbits can therefore be parametrized with statistical averages

$\displaystyle d{X}_{t}= \frac{\partial }{\partial t}\mathcal{E}\left[{X}_t \rig...
...\frac{\partial }{\partial t} \mathcal{V}\left[{X}_t \right]({x}) } \circ d{W}_t$ (10)

and lead to a different result each time the JBONE applet is executed.
JBONE applet:  press Start/Stop to simulate the random motion of a particle (red dot). The contribution to the density distribution (black line) is obtained from a linear assignment of the position on a grid.



Numerical experiments: stochastic orbits
  1. Take a few single Step 1 and convince yourself that the direction where the particle moves does not depend on the past. Re-Initialize and verify that the same stochastic differential equation each time produces a different orbit.
  2. Increase the number of Walkers=100 and observe how the cloud of independent particles diffuses in time.
  3. Vary the Velocity and Diffusion parameters, which are linked to the average velocity $ v(x,t)$ and the broadening $ b(x,t)$ of the orbits.

In the same spirit as in Taylor's transport theorem, it is possible to relate the evolution of a large number of stochastic particle orbits to a PDE; the so-called Feynman-Kac theorem tells that a smooth density distribution function $ f({x},t)$ in which individual particles move according to

$\displaystyle d{X}(t)={v}({X}(t),t)dt + b({X}(t),t) \circ d{W}_t$ (11)

evolves according to the Fokker-Planck equation

$\displaystyle \frac{\partial f}{\partial t}= -\frac{\partial }{\partial x}\left( {v}f\right) + \frac{\partial^2}{\partial x^2}\left( \frac{b^2}{2}f \right)$ (12)

which is in fact an advection-diffusion equation.

For example, let $ X(t)$ be a stochastic process with an evolution of the probability density distribution $ f(x,t)$ following the advection-diffusion equation

$\displaystyle \frac{\partial f(x,t)}{\partial t}+ \frac{\partial }{\partial x}\...
... x}\left(D(x) \frac{\partial f}{\partial x}\right), \quad x\in(-\infty, \infty)$ (13)

From the Feynman-Kac theorem, it is easy to show (exercise 5.01) that $ X(t)$ satisfies the stochastic differential equation
\begin{subequations}\begin{alignat}{2} \frac{\partial }{\partial t}\mathcal{E}[X...
...}{\partial t}\mathcal{V}[X(t)](x) & = 2D(X(t)) & \end{alignat}\end{subequations}

showing exactly what evolution is required to reproduce statistically the properties desired at the macroscopic scale.

SYLLABUS  Previous: 5.2 Stochastic theory  Up: 5 MONTE-CARLO METHOD  Next: 5.4 A scheme for

      
back up next contents bibliography Copyright © Lifelong-learners at 15:47:01, November 22nd, 2017