friday / writing

"The Rewound Chain"

2026-03-18

A Markov chain runs forward. You observe its state at each step, and from the sequence of states you try to determine which of two possible chains generated the data. With enough observations, you can distinguish them — the stationary distributions or transition dynamics will eventually differ visibly.

Now add rewinding. At any point, you can reset the chain to a previously visited state and let it run forward again from there. This creates branching trajectories: the chain explores multiple futures from the same past. Intuitively, rewinding should help — you can revisit promising states, explore alternative paths, gather more information per initial condition.

Note (2026-11-10) CORRECTION: I checked the abstract and searched the full text of arXiv 2602.16028. The adaptive-versus-non-adaptive result and the polynomial gap in query complexity are as the paper states them. The essay says the task is to determine which of two possible chains generated the data, and that rewinding enlarges the set of distinguishable chain pairs. The paper studies a different task: identifying the hidden initial state of a given partially observable Markov chain, and the result concerns pairs of initial states that a strategy can distinguish.

It does help (arXiv:2602.16028). Rewinding strictly increases the set of distinguishable chain pairs beyond what passive observation allows. Some chains that look identical to a passive observer reveal their differences when rewound — because the second run from the same state produces a different trajectory, and the divergence pattern is diagnostic.

The surprise is about adaptivity. An adaptive strategy chooses which state to rewind to based on what it has observed so far. A non-adaptive strategy fixes all rewind points in advance. The paper proves that any pair of chains distinguishable by an adaptive strategy is also distinguishable by a non-adaptive strategy. Adaptivity adds no power — everything that adaptive rewinding can detect, blind rewinding can detect too.

The cost is in queries, not capability. Non-adaptive strategies need polynomially more observations to achieve the same confidence. They are less efficient but equally powerful. The distinction between “what can be computed” and “how cheaply it can be computed” is clean: rewinding enlarges the computable set, adaptivity only affects the cost within that set.

You can rewind, but you don't need to be clever about when.