Monte Carlo methods II

Loading...

Del curso dictado por University of Geneva

Simulation and modeling of natural processes

57 calificaciones

University of Geneva

Simulation and modeling of natural processes

57 calificaciones

This course gives you an introduction to modeling methods and simulation tools for a wide range of natural phenomena. The different methodologies that will be presented here can be applied to very wide range of topics such as fluid motion, stellar dynamics, population evolution, ... This course does not intend to go deeply into any numerical method or process and does not provide any recipe for the resolution of a particular problem. It is rather a basic guideline towards different methodologies that can be applied to solve any kind of problem and help you pick the one best suited for you. The assignments of this course will be made as practical as possible in order to allow you to actually create from scratch short programs that will solve simple problems. Although programming will be used extensively in this course we do not require any advanced programming experience in order to complete it.

De la lección

Introduction and general concepts

This module gives an overview of the course and presents the general ideas about modeling and simulation. An emphasis is given on ways to represent space and time from a conceptual point of view. An insight of modeling of complex systems is given with the simulation of the grothw and thrombosis of giant aneurysms. Finally, a first class of modeling approaches is presented: the Monte-Carlo methods.

Monte Carlo methods I9:24

Monte Carlo methods II15:04

Monte Carlo methods III10:39

Conoce a los instructores

Bastien Chopard
Full Professor
Computer Science
Jean-Luc Falcone
Research Associate
Computer Science
Jonas Latt
Senior Lecturer
Computer Science
Orestis Malaspinas
Research Associate
Computer Science Department

[MUSIC]

So hello.

We continue with our class on simulation modeling of natural processes.

And now I'd like to discuss our second module on Monte-Carlo Method and

this is what some people call the Markov-Chain Monte-Carlo, MCMC.

So the main goal again of the Monte-Carlo method is to sample processes.

And, here we will just study a process,

a stochastic process, which is actually sampling state space.

And we first wanna understand the property of this process and see if we can tune it.

I just needed to actually sample something you want.

Okay so we consider a stochastic process

which will move across state

space which I'm not specifying precisely here but I will give you example.

So what do I mean by exploring?

It means that if I have some position x in this state space I will jump

to position x prime at the next time step and

the probability to pick x prime to jump is given by

transition function which I called here W of x to x prime.

And each time I've done an attempt to jump somewhere,

I advanced the system time by one unit.

So that's the way time is evolving in this, and for

those of you who remember your math class, this is called a Markov-Chain.

So just giving a little example, you may have here

a physical system of particle, for instance, they are somewhere in space.

And basically, you may want to sample the space of the configuration

of this particle according to the physics they obeying to and

the ideas from this black configuration I could do modification so

I can decide to move for instance two particle to the white spot, okay?

And so that's typically a jump in my state space.

And the question is with what probability should I accept this move, okay.

And actually, I have, of course,

a constraint to accept or reject this change, is that I would like to

accept changes which correspond to a natural movement of this particle.

So you know that the gas is of course made of particles.

But that's certainly not drastic as my picture suggests.

They keep moving, but they don't explore all the configuration,

because there typically was a given temperature.

And here is an example where we assume for instance that this molecule,

they are in the system described by the Maxwell–Boltzmann

distribution, which is the energy of the configuration x, which depend on

all the position of the particle and the temperature at which the system is kept.

So the question is, is there a way to choose this transition probability?

So that I can move my system from one configuration to another

by still respecting the probability distribution imposed by physics,

for instance or another one that I know.

Okay, so let's do a little bit of math and the probability that our

exploration process it has position x in the state

space at time t plus 1 is basically probability it was somewhere else,

some x prime, at the time t, and then you jump from x prime to x, so

that's very simple probability theory for Markov processes.

So now I will give you a simple example of that.

So we'll consider one D space which is just a discretization of

the horizontal line, meaning that I may have a particle that can jump from

one cell to the next, left, right, or stay at rest.

Or we say that the discrete space is the symbol, Z, natural number,

and then I want to sample this state.

So I assume that they can only move right,

which probability I call W+ to go to the positive direction.

Or I can move to the left, or negative position as probability W-, or

I can stay at rest with property W0 and of course the sum of this thing should be 1.

So now, my equation here becomes with this reduced set of jump to

simply this one that only three possibility of evolving,

so if I'm position x, I time t + 1, I was prior position x- 1,

and then jump right, or I was at position x and I didn't move,

or I was at position x + 1 and I moved left, okay?

So, now suppose I wanna use this

stochastic process to sample the diffusion equation.

So you will learn more about diffusion equation in the coming weeks.

But, just for now, let me tell you that mathematically is partial differential

equation which is the time directive of the density row is the second spatial

directive of the this density time, some diffusion coefficient.

And you will learn in during week

three that you can discretize such equation and find a difference.

And it says simply that the evolution in time

is a previous value plus some combination of your left and right neighbors.

So there's just math translating this equation into a discreet form.

Okay?

But now, we know that our stochastic process has the following property

that tells us how the density probability increase over time,

and you see it's very similar to this thing.

So basically, you see that this

p of xt, if I want p to be equal to raw,

I have one contribution here and one contribution here.

So it mean that this coefficient 2 times this plus 1 should be equal to w0.

And the same, I can match this with this and this with this.

So this gives you exactly this condition, so provided that you

choose W+ and W- one as this quantity, and

W0 as basically the complement, so that's everything sums up to one.

You get exactly a process which reproduces the diffusion equation.

So it's a stochastic process, you have to run it many times,

you have to do statistics, but if you do so you will see that your particle which

jumps randomly will just be distributed exactly like as the diffusion equation.

What's also interesting in this approach is that you see this condition

that tells you that actually since you have probability

you have this condition that this quantity should be smaller than one half otherwise

you may create negative probability which of course is not very good.

It's interesting to know that this condition

is also the stability condition of this numerical scheme.

So you see there's a nice consistency between the two approaches.

Okay, so we can actually replace the solution

of the diffusion equation by a stochastic process of random walk.

Okay, maybe it looks to simple to solve the diffusion equation with random walk.

But you should realize in that in your random walk you can easily

add obstacles or aggregation mechanics are all kind of, you know,

other feature that might be difficult to insert in the differential equation.

So maybe the process is actually represented at the level of the particle.

It's easier to do it as a Monte Carlo simulation rather than

trying to solve a complicated diffusion equation.

So now, let me go a little bit more into the general case, and

I wanna take again the equation telling me how the probability of

my explorer evolved in time, so we already saw this equation.

And now, I wanna transform it in a very simple way.

So, basically I will single out the situation when x prime is equal to x so

that this term and of course the rest is everything

result x prime equal x, okay?

And then I just use this term that I replace by the fact that

the sum of all the Ws is 1, so I can really rewrite it this way.

Okay, and now I group these two sums into one, and I get this guy out of it.

So, this here, and so I have this equation which tell me how my probability

of my random explorer evolved in time and

of course again the goal here is to try to find the W so

that this p will be actually identity that you know and you want to sample.

And if you want to impose that p

is equal to some row that is known in a steady state, okay,

it's obvious that you need that all this term is equal to zero, okay, so

basically to have p equals rho you need to find Ws that will satisfy this equation.

So this is not an easy one because there is the sum but

there is a way to, which is more restrictive to say that we can

this element, r0, which is exactly what we see here.

And that condition is called in physics,

detailed balance because it mean that the priority of being at x and jumping to

x prime and jumping to x the same as the probability of being at x and

jumping to x prime, so that's why it is called detailed balance.

And detailed balance will certainly solve this condition.

It's maybe a sufficient condition,

maybe not a necessary condition, but we'll go with it for now.

So the famous metropolis rule, the metropolis is this person who used

the Monte Carlo approach in the Manhattan Project.

He was interested to sample the Maxwell-Boltzmann distribution which

again, I am repeating, so it's the energy of the system divided by its temperature.

And he showed that this transition rule is a good one.

It obeys the detail balance and

it's known, it's well known as the Metropolis rule.

So, say that you go from X to X prime, with probability one,

if the the new energy you have is smaller than the previous one so

system is happy to go to lower energy.

Now if the energy of your new configuration is

higher than the previous one.

You can still go but with some probability which decreases because of this minus,

as the temperature is low, and as the jump of energy is big, okay?

But you'll still have a probability to go in a state of higher energy, and

at just the right way to sample this distribution from the theory we just saw.

So in practice, how would you do that in our system of particle?

You'd select a particle at random.

Let's say this black one here and

you decide to move it by a random quantity to this position here.

Now since you've changed the position of the particle,

you've changed the energy of my gas and I have a new energy E prime.

I will accept this change of the particle if

it corresponds to the metropolis rule, which in practice you can write this way.

You can just take a random number between 0 and 1 and

if it is smaller than the minimum between 1 and

this quantity, you accept the change otherwise you reject the change.

So this expression is just a way to express the equation I had before here.

Okay, and so what's the benefit of doing this if I

can sample my distribution of the gas?

Then I can compute some properties like pressure or

whatever physical property that the gas takes, and of course,

that's what was interesting for the Manhattan Project.

So it's easy to show that Metropolis rule actually obeys the detailed balance.

So I assume just that E prime is bigger than E.

So if I wanna compute this quantity,

so that's my distribution at equilibrium here, okay,

times this transition rate, which his given by the Metropolis rule.

Okay now I can of course combine the two exponential in one and

I get just this, okay.

But this is nothing but what we call the density for

the contribution x prime times one if you want.

But one is exactly now the probability of jumping from X to expand to x

because E prime is bigger than E, so then the jump would be with probability one.

So you see that, of course, you obey detailed balance.

And for those of you a bit more curious, you have another way to satisfy

the detailed balance, which is called The Glauber Rules.

It's simply taking this as an expression.

And in the case of an equivalent system you get this as a transition.

And it's of course, also a base detailed balance.

So with this I would like to close my discussion of

the Monte-Carlo Markov chain approach.

And in the next module, we will discuss what's called as kinetic or

dynamic Monte Carlo method.

Thank you for your attention.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play