Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton
Simulate cream mixing into coffee, blur the picture, and compress it. Entropy climbs steadily. The compressed size of the blurred picture rises, peaks and falls.
Start here (no maths needed)
Scientists simulated milk mixing into coffee on a grid of pixels and showed that, measured the right way, how complicated it looks rises and then falls.
Think of it like this
Squint at a photo of milky coffee from across the room. You stop seeing every tiny speck, and only see the big shapes: milky parts, dark parts and swirly in-between parts. Now imagine zipping that blurry picture. At the start and the end the blurry picture is boring and zips small. In the middle, with all the swirls, it zips bigger.
How it works
- Make a grid of squares: white (milk) on top, black (coffee) on the bottom.
- Again and again, pick two neighbouring squares at random and swap them if they are different colours.
- Zip the sharp picture to measure how mixed it is. This number keeps going up.
- Blur the picture into three shades (milk, coffee, mixed) and zip that. This number goes up, then comes back down.
- Repeat with bigger grids to see how the peak grows.
Why robots care
Robots build blurry maps of the world, made of little squares marked "free", "blocked" or "not sure". Choosing how big those squares are is the same choice as the blur size here. Too small and the map is full of noise. Too big and a chair leg disappears.
Try it
- Put a drop of food colouring in a glass of still water and watch for a few minutes. Draw it at the start, after one minute and at the end. Which drawing took you the longest?
- In the demo further down, press Play and watch the entropy line (mess) climb while the complexity line rises and falls. Then set the Grain size g slider to 3 and play again. With too little blur, the random specks count as "complexity" and the complexity line stays high.
Words to know
- Simulation
- A computer model that acts out a process step by step.
- Pixel
- One small square of a picture.
- Coarse-graining
- Blurring a picture so only the big shapes are left.
- Compressor
- A program like zip that shrinks files by spotting patterns.
- Entropy
- How mixed-up or random something is.
Going deeper: everything below is the full version, with some maths. On a first read, skim the headings and the "Why it matters for robotics" box, and come back for the rest later.
1. Summary
TL;DR
This is the empirical follow-up to Day 06. The authors build a 2D grid of cream (1) and coffee (0) cells, cream on top, and let particles mix by random local moves. Entropy is estimated as the gzip size of the exact grid. "Apparent complexity" is the gzip size of a smoothed, three-level version of the grid. In the interacting model, apparent complexity rises then falls, and its peak grows linearly with the grid's side length. In a non-interacting model, a refined measurement shows it stays low, which they also prove. It's a careful first experiment, with honest caveats about what a compressor can and can't show.
- Interacting model: one particle per cell. Each step, a random adjacent pair of different cells swaps.
- Non-interacting model: cream particles take independent random walks and can share cells.
- Measures: entropy ≈ compressed size of the fine grid. Complexity ≈ compressed size of the coarse-grained grid.
- Scaling: maximum entropy grows with n² (the number of cells), maximum complexity roughly with n, and time to the complexity peak roughly with n².
- Caveat: compressors give only upper bounds. Showing complexity truly gets large needs a lower bound, which nobody has.
2. The core idea
Pick a smoothing function f that throws away "incidental" detail. Then measure entropy on the raw state and complexity on the smoothed one:
entropy(x) ≈ |gzip(x)|
apparent complexity(x) ≈ |gzip(f(x))|
f(x)[i,j] = threshold( mean of x over the g×g square centred at (i,j) )
→ 3 levels: mostly coffee / mixed / mostly creamx: the n×n grid of 0s and 1s, the microstate.g: grain size. Larger g blurs more. It is chosen experimentally.threshold: buckets the average into three values so tiny fluctuations don't count as structure.|gzip(·)|: compressed file size, a computable upper bound on Kolmogorov complexity.
The paper links this back to theory. The coarse-grained image f(x) defines the set of all microstates that blur to the same picture. That is a model set S in the sense of sophistication, so apparent complexity is a heavily resource-bounded version of it.
3. Deep dive
Run it yourself
Interactive: the coffee automaton
48×48 interacting model, seeded. Each step picks a random cell and a random neighbour and swaps them if they differ, a slight variant of the paper's rule. Left: fine grid. Middle: coarse-grained, 3 levels. Right: entropy (LZ78 size of the fine grid) and apparent complexity (LZ78 size of the coarse grid), each scaled to its own maximum.
Try g = 3: the blur is too fine, random fluctuations survive the threshold, and "complexity" stays high long after mixing. The paper's appendix makes this precise for the non-interacting case: the grain must grow like √(log n) for fluctuations to average out. The choice of blur is not a detail.
Thresholding artefacts and the adjusted measure
With three buckets, a smooth gradient from cream to coffee will always have a row sitting near a bucket boundary. Tiny fluctuations make that row flicker between two levels, and the compressor counts the flicker as structure. The authors' fix: use seven levels, and let each cell move one level towards the majority value of its row. With this adjustment, the interacting model still shows the rise and fall. The non-interacting model's complexity is flattened to a low value, matching their proof that its coarse-grained state is always simple to describe: given n and t, you can compute the expected picture, and with a big enough grain nothing deviates from it.
What they tried and dropped
- OSCR, a two-part-code compressor designed to estimate sophistication directly, gave noisy results with no trend. They suspect it failed because it ignores the 2D layout.
- A diff-based two-part code (coarse picture plus corrections) suffered representation artefacts, so they measured the fine grid directly instead.
- Light-cone complexity (Shalizi and colleagues), the mutual information between a point's past and future, is discussed as future work.
Limits
Every number here is an upper bound. A compressor can prove something is simple, never that it is complex. The blur and the thresholds encode human judgement about what counts as "interesting", which the authors acknowledge. And a cellular automaton is a long way from real fluid dynamics.
4. Why it matters for robotics
- The link is methodological, not direct. No robot needs a complextropy meter. What carries over is how to measure structure in messy state.
- Coarse-graining is a design choice. Occupancy grids, voxel maps and downsampled images all pick a grain size. Too fine and the map is full of noise. Too coarse and obstacles vanish. The demo's grain slider is the same trade-off.
- Compression as a quick signal. Compressed size of a sensor log or a segmented image is a cheap, label-free way to spot where the "interesting" moments are, such as contact events, for data curation.
- Interaction creates structure. The independent-particle model never gets complex. The model where particles block each other does. Robots in clutter, with contacts and constraints, live in the interacting regime, and that's why their state is hard to summarise.
5. How to study it
- Read Sections 1–6 of the paper (about 1 h). Skim Section 2's tour of complexity measures, and read the short appendix proof.
- In the 30u30 Day 7 folder, read
implementation.pyand runtrain_minimal.pyto reproduce the rise-and-fall curves. - Do the exercises: coarse-graining, interacting vs non-interacting models, scaling with grid size, adjusted coarse-graining, and comparing compressors.
- Check the scaling claim yourself: run three grid sizes and plot peak complexity against side length.
- Stretch: replace gzip with a small learned model (for example a PixelCNN-style predictor) and use its log-loss as the code length.
6. Self-check
Why compress the coarse-grained grid rather than the fine one to measure complexity?
The fine grid's compressed size tracks randomness, so it just keeps rising like entropy. Blurring removes the random detail and leaves the large-scale structure, which is what "interesting" means here.
Why does the non-interacting model stay simple?
Each particle walks independently, so the expected density depends only on row and time and can be computed from n and t. With a large enough grain, the actual coarse picture matches that expectation with high probability.
What problem does thresholding cause, and how did they fix it?
Rows near a bucket boundary flicker between levels and look like structure. They used seven levels and let cells move one level towards their row's majority value.
How do maximum entropy and maximum complexity scale with grid side n?
Maximum entropy grows like n² (number of cells). Maximum complexity grows roughly linearly in n, since structure develops along one dimension, the cream–coffee boundary.
Why can't simulation alone prove the system becomes complex?
Compressors give upper bounds on complexity. Proving a state is complex needs a lower bound, which the paper leaves as an open problem.
7. Further reading
- The original paper, and Aaronson's 2011 post that proposed it
- 30u30 Day 7: implementation, notebook, cheatsheet, exercises
- Next: Day 08, ImageNet Classification with Deep CNNs (AlexNet)