Imagine flipping coins two at time. If the first coin is Heads, we step to the right, otherwise we step to the left. If the second coin is Heads we step forwards; otherwise we step back. This is the basic move, a kind of two-step random dance. If we make a little red dot to record our position at each step, we get an image somewhat like the one on the left — in this case a record of 15,097 steps, with a new step taken every 50 milliseconds.
This sort of dance is called random walk or Brownian motion. The Wikipedia article on the subject is excellent. Historically, the term refers to the odd dance that pollen grains suspended in water make when observed under the microscope. The phenomenon was noted by botanist Robert Brown in 1827. Einstein’s 1905 paper gave a mathematical treatment of the phenomenon, showing that it was the result of random bombardment of pollen grains by water molecules. Because the paper gave quantitative predictions (diffusion rates), it played a leading role in convincing scientists of the time that the atomic hypothesis was true. The road from Democritus to Einstein was a long one! (Yes folks, universal acceptance of the atomic theory of matter is surprisingly recent.)
For this little simulation, I used the Elm — part of my effort to learn the language by doing a series of small, fun projects. The code is on GitHub if you are interested. If you do run the code, you have the option (History Off) to display the red dot at 50 millisecond intervals, but not to display prior positions. The History On option displays all prior positions, as in the image. As far as I can tell, keeping track of 15,000 circles and displaying them every 50 ms is not a problem, although with this many circles to display, the “clock” which calls out the moves seems to slow down. This is an informal observation, and so needs to be checked more scientifically, with some actual measurements. In any case, no crashes!
The program is not long — 248 lines of code in the main file, and 184 in the
Graphlibrary, only part of which is used. The basic move used is slightly more complex than described above — the distance moved vertically or horizontally at each step, not just the direction, is chosen at random, varying uniformly in steps of 0.2 from -1.0 to +1.0. This results in better esthetics, since the circles plotted do not all lie on an observable grid. One can also argue that it is a slightly more realistic model of true Brownian motion.
Related posts: A Billiards Simulator in Elm
Notes on the Code
The heart of the program is the snippet below, which causes a pair of random integers in the range
0..10 to be created on each tick of the clock.
Tick newTime ->
if model.simulatorState == Running then
( model, Random.generate MakeMove randomMove )
( model, Cmd.none )
randomMove function is defined like this:
randomMove : Random.Generator ( Int, Int )
Random.pair (Random.int 0 10) (Random.int 0 10)
As mentioned in the official documentation on the
Random module, the theory for constructing and using complex random number generators like
randomMove from simple ones like
Random.int is very much like that of constructing and using JSON decoders. See this tutorial for some useful information on
Random , and see this post for some remarks on JSON decoders.
Notes on using Elm. (i) I am really enjoying this! (ii) Elm is different — a pure functional language with its own opinions on how a web app is made. Accept this, understand it, and move on! (iii) Understanding the type system is of great help. You will come to love it. (iv) There are some tricky notions, e.g., JSON decoders and complex random generators. (Complex meaning only that they are built from simple generators, not that they huge and complicated). (v) The compiler is your friend.