.. _chap-randomness-disorder:

=======================
Randomness and Disorder
=======================

[status: content-mostly-written]

Purpose: to drive home the notion of disorder (and order) and how that
relates to the probabilities of various situations.

Prerequisites:

a. The basic Python course.

b. Familiarity with simple plotting.


Experiment: burn a match
========================

NOTE: this experiment should be carried out under adult supervision.

1. Have a flat piece of metal, or a tile, or a very flat rock.  Lay it
   down in a stable place.

2. Light a match and *before* the flame reaches your finger, lay it
   gently on the flat metal or tile or rock.

3. Watch it until it finishes burning and let it cool down.

4. If possible, take the dark stick that is left and remake it into
   the original match.


Experiment: ink in water
========================

1. Find an ink-like substance.

2. Fill a discardable plastic cup with water.

3. Drop a single drop of the ink into the water.

4. Observe the ink in the water the instant it falls in.

5. Observe the ink in the water after thirty seconds.

6. If possible, make the water return the drop of ink to where it was
   the instant it fell in.


Discussion on "ink in water" experiment
=======================================

Discuss the meaning of the "ink in water" experiment with your
partners.  In particular discuss the meaning of the last step and
whether it was possible.


Flipping a single coin
======================

Take a coin and flip it 16 times.  Tabulate the results like this:

::

  H T T H H H T H T T H H T H T H ...

and so forth.  Count how many times you get heads and how many times
you get tails.

If you use 1 for heads and 0 for tails, calculate the average of all
the tosses.  In the few flips shown above it will be 0.5625: just a
bit more than half of the tosses were heads.


Review: random numbers in Pythyon
=================================

To review random numbers, open the python interpreter with

.. code-block:: console

  $ python3
  >>> import random
  >>> random.random()
  ## repeat that many times
  >>> random.randint(-3, 12)
  >>> random.randint(-3, 12)
  ## repeat that many times
  >>> random.randint(0, 1)
  ## repeat that many times

..


Experiment: flipping a single virtual coin
==========================================

Just the flips
--------------

Flipping coins just a few times can give inconsistent results.  Let us
explore how long it takes for the average number of heads and tails to
become consistent.

In this experiment we will write a computer program to flip a single
virtual coin and look at the results. Then we will update the program
to keep track of the average between heads and tails.  We will count
heads as 1, tails as 0, and print the average as we keep flipping.
First enter (or paste) the program in
:numref:`listing-single-coin-average-py`.

.. _listing-single-coin-average-py:

.. literalinclude:: single_coin_average.py
   :language: python
   :caption: single_coin_average.py

Run this program with:

.. code-block:: console

   $ python3 single_coin_average.py
   [... there will be output here ...]
   $ python3 single_coin_average.py > coin_avg.dat

Then plot the results with:

.. code-block:: console

   $ gnuplot
   # and at the gnuplot> prompt:
   plot 'coin_avg.dat' using 1:2 with linespoints
   plot [] [0:1] 'coin_avg.dat' using 1:2 with linespoints

Then change n_runs to be 100 and re-run the program and re-plot the
results.  Then plot 1000 runs.


Long-running average of single coin flips
-----------------------------------------

Write the program in :numref:`listing-single-coin-flip-py` in a file
called ``single_coin_flip.py``

.. _listing-single-coin-flip-py:

.. literalinclude:: single_coin_flip.py
   :language: python
   :caption: single_coin_flip.py

then run it with with:

.. code-block:: console

  $ python3 single_coin_flip.py
  [... there will be output here ...]
  $ python3 single_coin_average.py > coin_avg.dat

Then plot the results with:

.. code-block:: console

   $ gnuplot
   # and at the gnuplot> prompt:
   plot 'coin_avg.dat' using 1:2 with linespoints pt 7 ps 1

Then change n_runs to be 100 and re-run the program and re-plot the
results.  Then plot 1000 runs.



Flipping multiple coins
=======================

Take two different coins and flip them 16 times.  Tabulate the results
like this:

::

  H T
  T H
  T T
  H H
  ...

and so forth.  Count how many times you get all heads and how many
times you get all tails.

Do the same thing with three coins.


Experiment: flipping virtual coins
==================================

Since the purpose of computers is to *automate repetitive tasks*, we
should not go beyond flipping three coins.  Rather, we will write a
computer program to do so.  Enter the program in
:numref:`listing-many-coins-py` as ``many_coins.py``:

.. _listing-many-coins-py:

.. literalinclude:: many_coins.py
   :language: python
   :caption: many_coins.py


The variables at the top, ``n_runs`` and ``n_coins``, set how many
runs you do and how many coins you flip in each run.

Experiment with ``n_coins`` = 2 and try to let ``n_runs`` go through
16, 50, and then try 1000.  Run the program several times with each
value of ``n_runs`` and pay close attention to the output lines
``fraction_all_heads`` and ``fraction_all_tails`` -- are they more
consistent when ``n_runs`` is larger?

Do the same with ``n_coins`` set to 3, 4, 5, and then to 20, keeping
``n_runs`` at 1000.

Discuss what you see happen to ``fraction_all_heads`` and
``fraction_all_tails``.


Experiment: back to physical coins - disorder
=============================================

1. Take 10 coins, set them up to be all heads and near each other on
   the ground.

2. Take a spatula, slide it under the 10 coins, toss them high up in
   the air.

3. Watch the debris and count heads and tails.

4. Take the spatula again and use a single movement of the spatula to
   put all the 10 coins back into their original state (all near each
   other and all heads).  If you cannot do this with a single movement
   of the spatula, give yourself 10 spatula moves.

5. Repeat this experiment with the 10 coins stacked up instead "near
   each other".

6. Now do what you have to do to restore the 10 coins to the pile
   where they are all "heads up" using the spatula.  I that fails, do
   so with your fingers.


The drunk fencer
================

Let us now start talking about random walks.  I want to move toward
discussing random walks in 2 dimensions, but it is easier to program a
one-dimensional random lurching back and forth - the way a drunk
fencer might move back and forth randomly rather than according to the
needs of the bout.

Let us type in the program in :numref:`listing-walk-1d-py`:

.. _listing-walk-1d-py:

.. literalinclude:: walk-1d.py
   :language: python
   :caption: walk-1d.py -- simulates a drunken fencer

and run it and plot the results like this:

.. code-block:: console

   $ python3 walk-1d.py
   $ python3 walk-1d.py > walk-1d.dat
   $ gnuplot
   # and at the gnuplot> prompt:
   set grid
   set size square
   plot 'walk-1d.dat' using 1:2 with lines

By changing the number of steps to 100, 1000 and 10000 you should see
the plots in :numref:`fig-walk-path-1d`.

.. command-output:: /bin/sh randomness-disorder/do-walk-1d.sh

.. _fig-walk-path-1d:

.. figure:: walk-path-1d.*

   The path of a drunken fencer 100, 1000, 10000 and 100000 steps.


.. _sec-the-drunkards-walk:

The drunkard's walk
===================

Now we move on to the more gratifying 2-dimensional random walk, also
called the drunkard's walk.

First introduce the notion with pictures and possibly an acting out of
drunk behavior.  Then type in the program in :numref:`listing-walk-py`

.. _listing-walk-py:

.. literalinclude:: walk.py
   :language: python
   :caption: walk.py

Examples of running this program:

.. code-block:: console

   $ python3 walk.py
   $ python3 walk.py 20
   $ python3 walk.py 100

Now we want to do a big run and save the data to a file:

.. code-block:: console

   $ python3 walk.py 1000000 > walk-1000000.dat

Now we plot it.  Note the tricks with the ``tail`` command which let
you plot just the first few lines rather than the whole file:

.. code-block:: console

   $ gnuplot
   # and at the gnuplot> prompt:
   set grid
   set size square
   plot '<tail -100 walk-1000000.dat' using 2:3 with lines
   plot '<tail -1000 walk-1000000.dat' using 2:3 with lines
   plot '<tail -10000 walk-1000000.dat' using 2:3 with lines
   plot '<tail -100000 walk-1000000.dat' using 2:3 with lines
   plot '<tail -1000000 walk-1000000.dat' using 2:3 with lines

By changing the number of steps to 100, 1000 and 10000 you should see
the plots in :numref:`fig-random-walk-path`

.. command-output:: /bin/sh randomness-disorder/do-walk.sh


.. _fig-random-walk-path:

.. figure:: walk-path.*

   The path walked by a drunkard for 100, 1000, 10000 and 100000
   steps.  Note that for long walks the figure starts looking like a
   *fractal*.


.. _sec-matplotlib-animation-of-random-walk:

Matplotlib animation of a random walk
=====================================

Using matplotlib we can animate rather smoothly in real time.  Try
this program in :numref:`listing-walk_matplotlib-py`:

.. _listing-walk_matplotlib-py:

.. literalinclude:: walk_matplotlib.py
   :language: python
   :caption: walk_matplotlib.py

There are many things you might find notable in this program.  The one
I will comment on here is that there is a particular way in which we
update the line in the plot (the key animation step).

Instead of using drawing commands to draw a new line, we use the
:code:`line.set_data()`.  This is for speed: redrawing would be very
slow, while updating the internal plot data will write to screen much
faster.

Another thing to note is that in this example we don't use
matplotlib's animation approach.  We could probably change this
program over, but it might be good to first see how to program it
directly.

There is a tutorial on matplotlib animations here:

https://jakevdp.github.io/blog/2012/08/18/matplotlib-animation-tutorial/

archived at:

https://web.archive.org/web/20220601192231/https://jakevdp.github.io/blog/2012/08/18/matplotlib-animation-tutorial/


.. _sec-making-a-movie-animation-of-the-walk:

Making a movie from walk frames
===============================

Reviewing graphics and animation
--------------------------------

In this session I will start with a discussion of graphical and video
file formats: mention png (portable network graphics), jpeg (joint
picture expert group), and mpeg (motion picture expert group).

We can use either ``ffmpeg`` or ``convert`` or ``mencoder`` to convert
the sequence of frames into a movie.

In other mini courses, for example :numref:`introduce_imagemagick`, we
have used the same idea of generating several individual frames and
then using ffmpeg to make a movie out of them.  We can go to that
section and try those examples, and then return here.

It basically boils down to this.  Find an image to work with, for
example a Hubble Space Telescope image of the Pillars of Creation in
the Eagle nebula:

.. code-block:: console

   wget https://ia902307.us.archive.org/7/items/pillars-of-creation-2014-hst-wfc-3-uvis-full-res-denoised/Pillars_of_creation_2014_HST_WFC3-UVIS_full-res_denoised.jpg
   # rename it something simpler
   mv Pillars_of_creation_2014_HST_WFC3-UVIS_full-res_denoised.jpg pillars_of_creation_hubble_big.jpg
   # make it smaller
   convert -resize 1000x pillars_of_creation_hubble_big.jpg pillars_of_creation_hubble.jpg

Then, to experiment with making animations, try this sequence:

.. code-block:: console

   for i in `seq -w 0 360`
   do
       echo "rotating by $i degrees"
       convert pillars_of_creation_hubble.jpg -rotate $i pillars_of_creation_hubble-rotate${i}.jpg
   done

   ffmpeg -framerate 20 -i pillars_of_creation_hubble-rotate%03d.jpg rotate-movie-fr20.mp4

Then you can view ``rotate-movie-fr20.mp4`` with your favorite movie plyer.


Making individual frames of the random walk
-------------------------------------------

We will use gnuplot to generate a sequence of images in png format.

Start with a file with a million lines of random walk output.  You can
do this as shown above with:

.. code-block:: console

   $ python3 walk.py 1000000 > walk-1000000.dat


gnuplot usually draws its output to the screen, but we can change that
behavior and have it generate a ``.png`` file.  To do so we add a
couple of lines at the top:

.. code-block:: console

   $ gnuplot
   # and at the gnuplot> prompt:
   set grid
   set size square
   set terminal png
   set output 'walk-100.png'
   plot '<tail -100 walk-1000000.dat' using 2:3 with lines
   set terminal png
   set output 'walk-1000.png'
   plot '<tail -1000 walk-1000000.dat' using 2:3 with lines
   quit
   # at the shell, possibly in another window, you can type:
   $ ls

After running this last example you should find that there are a
couple of new files in this directory: ``walk-100.png`` and
``walk-1000.png``.  If you view them with your favorite image viewer
(you might want to consider the viewer ``geeqie``) you will see that
they are indeed the plots you wanted to make.

Our first task is to *automate* this process to generate hundreds or
thousands of individual static images.  The program
:download:`walk_movie.py` in :numref:`listing-walk-movie-py` does so.

.. _listing-walk-movie-py:

.. literalinclude:: walk_movie.py
   :language: python
   :caption: walk_movie.py

If you run this program it will generate ``n_frames`` different frames
(the default in the program is 1000).  To make a more satisfying movie
we should increase this, but let us start with 1000 to make the
program run more quickly.

``walk_movie.py`` will pick out the random walk steps jumping 100 every
time (see the line that says ``n_steps = i*100``).  It then generates a
sequence of gnuplot commands like the one we saw above to generate
file names that look something like ``walk_frame-000023.png``.

If we run the program and the list the directory:

.. code-block:: console

   $ python3 walk_movie.py
   $ ls

we see that the program has generated a bunch of ``walk_frame-*.png``
files (initially 1000 of them).  Your favorite graphic viewer might
allow you to press the space bar and almost see an animation of them.

Now let us talk about making a movie.  There are several programs
which *encode* a sequence of static image files into an mpeg movie.  I
mention three such programs: ``ffmpeg``, ``convert`` and ``mencoder``.
The ``walk_movie.py`` program gave us a tip on how to run those
programs to encode all the frames into the movie file
``walk-movie.mp4``:

.. code-block:: console

   $ ffmpeg -framerate 24 -i walk_frame-%06d.png walk-movie.mp4

or

.. code-block:: console

   $ convert walk_frame*.png walk-movie.mp4

or

.. code-block:: console

   $ mencoder "mf://walk_frame*.png" -o walk-movie.mp4 -ovc lavc

or, to make a movie in reverse:

.. code-block:: console

   $ ffmpeg -framerate 24 -start_number -999999 -i walk_frame-%06d.png walk-movie.mp4
   ## FIXME: the reverse order with a negative start number needs to
   ## be ironed out.  Maybe ffmpeg can take an `ls -r ...` on the
   command line.

or

.. code-block:: console

   $ ls -1 -r walk_frame*.png > reverse_filelist
   $ mencoder "mf://@reverse_filelist" -o walk-movie-reverse.mp4 -ovc lavc

Note that the simplest and fastest approach is to use ``ffmpeg`` (the
"Swiss army knife" of video and audio formats) so I will continue with
``ffmpeg`` for my examples.

You can now play these movies with your favorite movie player - I
recommend ``vlc``, though your system might come with ``totem`` already
installed:

.. code-block:: console

   $ vlc walk-movie.mp4
   $ vlc walk-movie-reverse.mp4

I wrote ``walk_movie.py`` to only generate 500 frames so that it can
run quickly when I give examples or when I build this book, but you
should increase that number a lot so you can see a longer movie with
more detail.

Playing the movie shows you the growth of a fractal.  It is
interesting to watch how sometimes it adds paths in a clump, while
sometimes it darts off into another sector of the plane, creating some
filaments that connect the thicker bushes.

.. raw:: html 

   <video controls src="../_static/walk-movie.ogg"></video> 


Discussion
==========

Discuss the result of these experiments with your partners.  Ask each
other the following questions and write slides to present your
answers.  You might write one slide for each few related questions.
You may include any of the plots you made in this course into your
slides.

* Look at the first two plots we made.  In the first one (single coin
  flips) note that a new point in the plot is completely independent
  of the previous ones.  In the second one (running average of single
  coin flips) is each new point on the plot related to previous ones?
  Are there two types of random events - those that are fresh and new,
  and those that add a small random change to a previous state?  The
  former is called a *Poisson process*, the latter is called a *Markov
  process* or a *Markov chain*.

* Look at the plot of averages from the single coin experiment and
  tell a story of what is going on in that plot, addressing the fact
  that initially it fluctuates quite a bit and later it seems to
  converge to 0.5.

* Is this related to how many more ways you can create 10 disordered
  coins than 10 ordered coins?

* Was it more work to restore the 10 coins to "heads up" or was it
  more work to toss them with the spatula.

* Why it easier to restore 10 coins to their initial "heads up" state
  than to restore the drop of ink to its inital state?

* Is it easier to go from order to disorder or from disorder to order?

* Have you heard of *Entropy*?  If not, now you have.  Entropy is
  related to the idea of *disorder*.  One of the deepest laws in
  physics is the *Second Law of Thermodynamics*.  One of the ways of
  stating the second law is that *the entropy of the universe is
  always increasing*.

* Referring back to the *Emergent Behavior* short course, remember how
  in that situation we examined systems that go from chaos to order: a
  random first row in a cellular automaton becomes a pattern of
  triangles, and a random initial state in John Conway's game of life
  can produce ordered patterns as well as gliders.  Discuss how
  emergent behavior seems to produce order out of chaos - does this
  violate the second law of thermodynamics?

* Discuss the cycle that brings to living creatures: trees, flowers,
  cats, dogs, horses, humans...  Is each living creature more or less
  ordered than the molecules in the earth and air from which that
  creature is made?


Further reading and videos
==========================

A cartoon video for kids on entropy:

https://www.youtube.com/watch?v=Tay3-2WKQ5Y

Jeff Phillips's TED-ed video "What is entropy?":

https://www.youtube.com/watch?v=YM-uykVfq_E

The "What is Entropy?" video from "The Good Stuff":

https://www.youtube.com/watch?v=gS_C7dM25pc

A discussion of how information in the demon's brain makes it respect
the second law is here:

https://www.youtube.com/watch?v=ULbHW5yiDwk

Science asylum video on entropy:

https://www.youtube.com/watch?v=ykUmibZHEZk

Try this:

https://www.youtube.com/watch?v=lj5tqM5GZnQ

starting at minute 14:10

Feynman's lecture on "The Distinction of Past and Future":

https://www.youtube.com/watch?v=_Kab9dkDZJY