DRMacIver's Notebook

Branch and Consolidate

Branch and Consolidate

Attention conservation notice: This note is even more note to self than then normally are, so may not make much sense.

The following implementation strategy has just occurred to me, for writing code that can be both a randomized algorithm and a dynamic programming solution for giving you the full distribution (you can also achieve this by just writing it abstracted by a suitable monad implementation of course).

Add two primitives:

  1. branch(n) conceptually generates a uniform random number \(0, \ldots, n - 1\).
  2. consolidate(data) says “the rest of the computation is uniquely determined by this value”.

In random generation, branch has the obvious implementation and consolidate does nothing.

When doing the dynamic programming, we use the standard trick for exhaustively enumerating a tree of unknown shape: Explore based on prefixes, filling with infinitely many zeroes for branches drawn past the prefix, and increment it lexicographically until we can’t any more. The difference is that whenever we call consolidate with a value we have already seen, we raise an exception to terminate the process and add an entry that says to use the final value. Conceptually this is the same as just exhaustively enumerating all the possibilities, but with shortcuts.

At the end we just solve the obvious dynamic programming problem to calculate the probabilities.