Separation of coloured particles
Particles of two colours, following a local stochastic rule, must cluster by colour (or mix).
Problem statement and measurescollapse
Each particle has one of two colours. Particles run a local Markov chain with a bias \(\lambda\) towards more neighbours and a bias \(\gamma\) towards neighbours of the same colour. The system should be compressed and separated (few pairs of neighbours of different colours), or integrated (colours mixed), with high probability in the stationary distribution.
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
A first look
the basic problem, a simple algorithm and why some things cannot be done, for a newcomer
Think of a mixed crowd of red and blue marbles in a tray that, when shaken, sorts itself into a red patch and a blue patch, or stays mixed, depending on how 'sticky' same-coloured marbles are. The floor is the triangular lattice: the endless graph whose nodes are the corners of a tiling of the plane by equal triangles; each node is joined by an edge to six others, its neighbours. A particle occupies one node and moves in two actions: an expansion into an empty neighbouring node, after which it occupies both, then a contraction into one of the two; so one expansion and one contraction move it by one node. The system of \(n\) particles starts connected; each particle carries a fixed colour, one of two, has constant memory and no compass, and one randomly chosen particle acts at a time. The system should become compressed (its perimeter, the length of the walk around its outside, is at most a constant times the smallest possible, as in compression) and either separated (each colour mostly in one region, with few pairs of neighbours of different colours) or integrated (colours mixed), whichever is asked for. As for compression, the question is what the system looks like after running for a long time, with high probability.
There are two biases: \(\lambda\) rewards neighbours of any colour, and \(\gamma\) rewards neighbours of one's own colour. A randomly chosen particle does one of two things.
- Step. As in compression: pick a random empty neighbouring node; check locally that moving there neither splits the system nor encloses a hole (a region of empty nodes surrounded by particles); then move with probability \(\lambda^{\text{(gain in neighbours)}}\cdot\gamma^{\text{(gain in same-coloured neighbours)}}\) (certainly, if this number exceeds 1).
- Swap. Pick a neighbour of the other colour and exchange nodes with it, with probability \(\gamma^{\text{(gain in same-coloured neighbours of the two)}}\) (certainly, if above 1). Swaps let colours move through the middle of the system.
Why it matters. It showed that the biased-rule recipe extends from shape to internal organisation, here the arrangement of types.
One might expect any preference \(\gamma > 1\) for same-coloured neighbours to separate the colours eventually. It does not. There are vastly more mixed arrangements of the colours inside a compressed system than separated ones: separation means fixing a short border between the colours, while mixing leaves almost every particle free to be either colour. A slight preference gives each separated arrangement only a slightly larger weight, which cannot make up for the huge number of mixed ones.
Why it matters. It is the colour version of the compression lesson: a preference must be strong enough to beat the number of disordered states.
What is known
The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.
Open questions 1
Markov chain, sequential
- Bounds on the convergence (mixing) time.
What the community started looking at
Separation extended the stochastic approach of compression to heterogeneous systems; the question is which bias parameters give which emergent behaviour Cannon et al. 2019.
Generalisation of Compression
Separation adds two colours to compression; the same local chain compresses and, depending on a second bias, separates or integrates the colours Cannon et al. 2019.
Related problems
Separation: Robots in the plane separate by hidden colours with deterministic algorithms; here a stochastic local rule separates two visible colours.
Perspectives
- From robots to particles Programmable matter re-asks the questions of robots in the plane on a lattice, with particles that touch, remember a little and stay connected; SILBOT takes memory and messages away again, and the stochastic approach replaces algorithms by a biased local rule.
All settings
The assumption tree (1 settings, 1 branch points)
The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Moves); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Memory › Scheduler › Orientation › Randomness › Initial shape › Connectivity during execution.
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.