Models for evolving structures

How do you model a structure that evolves over time?

How do you keep track of an approximately sorted order with few probes, when the true underlying order evolves over time? Agnastopoulos, Kumar, Mahdian and Upfal designed an algorithm assuming the following model for an evolving order: at any time, there is a ground truth order, and the next change will consist in a swap of an adjacent pair, where the choice of the pair to swap is made uniformly at random.

How do you keep track of the minimum spanning tree of a weighted graph that evolves over time? Agnastopoulos, Kumar, Mahdian, Upfal and Vandin designed an algorithm assuming the above model for the evolving set of edge weights.

How do you keep track of an unweighted graph that evolves over time? Agnastopoulos, Kumar, Mahdian, Upfal and Vandin designed an algorithm assuming the following model for an evolving graph: at any time, there is a ground truth, and the next change will consist of swapping out an edge and swapping in a non-edge, where the choice of the edge to swap out and the edge to swap in are made uniformly at random.

Those models that are simple enough to be amenable to analysis. They are combinatorial, independent of the distribution of the numbers themselves. That makes them quite elegant.

More generally, if one has a static distribution of structures, a local operation to modify the structure such that the set of structures is connected under that operation, and an associated Markov chain such that the asymptotic distribution is the desired status distribution, then that naturally suggests a model for the evolving structure: simply run the Markov chain.

Other examples that fall into that category: random binary trees evolving by rotations; random planar triangulations evolving by edge flips; etc.