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:
branch(n)conceptually generates a uniform random number \(0, \ldots, n - 1\).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.