Program you way out of a paper bag – Fran Buontempo

This talk is about Monte Carlo simulations. Sometimes, you cannot make a model upfront, so you can have randomness help you. Suppose you need to estimate a bloblike area. You can try to come up for a formula to describe the boundaries, or you could shoot darts at it and see how many hit the area. This is the basic idea of Monte Carlo, simulate a system in many different conditions and see what happens. It is used commonly in finance modeling, but also used for finding pi (Buffon’s needle) or simulating the spread of infectious diseases.

So what is diffusion? Literally, it is the process of liquids or gasses (or even solids) mixing, but more generic it is about stuff spreading, or brownian motion. This is a stochastic process, whose increments are:

  • Independent
  • Stationary (they don’t vary with time)
  • Normally distributed
  • Continuous (you can draw without lifting your pen from the paper)

Cue the paper bag that we are programming ourselves out of: Imagine we have a 2D paper bag, with a particle on (x,y), and we want to simulate random motion in the bag, such that all particles move out.

2015-04-23 16.22.12

The normal rand() function might not be random enough for a real random walk, see this talk, or the Ferrenberg affair.

How do we get a number in [0,100}

x = rand() % 100 -> no good, because we can never get 100

x = (rand() * 1.0/RAND_MAX) * 100 -> a bit better, but we can only get 100 in 1 way

while (value > 100)
x = rand() -> will work but not in a very efficient way (this is called rejection sampling)

Better is to use a Mersenne Twister, which is a quite complicated thing, I do not know how it exactly works but apparently it needs 623 dimensions to work. Luckily many modern programming languages support it in a library so you don’t have to build it to use it.

Stock market

Let’s take our simulation efforts to a more serious domain: stock prices. Let’s predict them with Monte Carlo, using geometric Brownian motion. This is when the logarithm of the varying quantity follows a Brownian motion, creating a ‘drift’ in a certain direction.

2015-04-23 16.52.21

Code for the stock price simulation

Would it not be even nicer if the particles could learn from each other? For this, Fran made the ABC (artificial bee colony). The artificial bees do a little wiggle dance to communicate to other bees where the food is. I had never heard of this phenomenon before, but apparently there is a whole scientific community around it, see Wikipedia.