One random path down a search tree

Every earlier essay here on Monte Carlo methods has used random points to estimate an integral: the area under a curve, the share of a square inside a shape, the chance a needle crosses a line. What a jump costs evenly spread points pushed that as far as evenly spread points go. This essay uses the same idea on an object that is not a region at all: a search tree, the branching record of every choice a backtracking program will try.

The question is practical. A program that searches by trying a choice, then the next, and backing up when it reaches a dead end can take a second or a geological age, and the difference is often impossible to judge in advance. Donald Knuth proposed in 1975 a way to find out by running the program for a moment: follow one random path from the root to a dead end, and read the tree’s size off the path. It is a Monte Carlo method in the purest sense — an estimate whose average is exactly right — and it is the cleanest example there is of how far “right on average” can be from “right”.

The estimate #

The tree in the figure is the search for eight queens on a chessboard with no two attacking. The program places a queen in the first row, then one in the second row in a column the first does not attack, and so on; whenever a row has no safe column it backs up. Every partial placement it ever considers is a node of the tree, and the whole tree has 2,057 nodes — counted exactly by visiting every one.

Knuth’s estimate follows a single path. At the root there are 8 safe columns; pick one at random. In the second row there are now 5; pick one. Then 3, then 1, then 2, then 1, and in the seventh row none. Multiply along the way — 8, 40, 120, 120, 240, 240 — and add the products to 1: the estimate is 769.

The reason it works is a single line. A node at depth $k$ is reached by the random path with probability $1/(d_1 d_2 \cdots d_k)$, where the $d_i$ are the numbers of choices along the way to it. The path adds $d_1 d_2 \cdots d_k$ to the estimate when it passes through depth $k$ — the inverse of the probability of the node it passes. So each node contributes, on average, its probability times its inverse probability, which is 1, and the expected estimate is the number of nodes. The estimate is unbiased: averaged over all random paths it is exactly the tree’s size, with no approximation anywhere.

A tree with four nodes shows it at work. Let the root have two children, one a leaf and the other a node with a single leaf below it. A random path chooses the leaf with chance one half and reports $1 + 2 = 3$; or it chooses the other child, finds one choice below, and reports $1 + 2 + 2 \cdot 1 = 5$. The average of 3 and 5 is 4, the number of nodes, and neither path reported 4. The path that went the short way under-counted the branch it skipped, and the path that went the long way counted its own branch twice, as a stand-in for the one it did not see.

That is how every estimate should be read: each path reports the size of an imaginary tree in which every node is like the ones it actually visited, with the branching it met copied across every sibling. Where the real tree is uniform, the imaginary one is close to it. Where siblings differ, the path is wrong in a direction set by luck, and only the average is right.

This is the same move that sampling where the answer lives made for integrals: draw something with a known probability and weight it by the inverse of that probability. Here the drawing is fixed in advance — a uniform choice at each level — and the weight is the product of the branching numbers.

Averaging many paths #

One path is crude, and nobody uses one. The average of many is an unbiased estimate with a smaller spread, and the figure shows it settling. For eight queens, a few hundred paths bring the average within a few per cent; for twelve queens, whose tree has 856,189 nodes, it takes longer, and the curve wanders above the truth for a while before coming back. After twenty thousand paths both are within half a per cent.

The cost is the point. Twenty thousand paths down the twelve-queens tree visit about two hundred thousand nodes in all, a quarter of the tree; for fourteen queens they visit about the same number against a tree of twenty-seven million. A path costs only its own length, which is at most the number of rows, and the estimate improves like the square root of the number of paths whatever the size of the tree. That is why the method is worth having: it measures a tree too large to walk.

What the estimate is used for #

The estimate is not only of the total. The same path estimates the number of nodes at each depth separately — the product $d_1 \cdots d_k$ is an unbiased estimate of the nodes at depth $k$ — and so it estimates the number of complete solutions, which are the nodes at the deepest level. For the queens trees that is the number of ways to place $n$ non-attacking queens, and averaging the products over two hundred thousand paths, counting zero for every path that dies early, gives 91.4 for eight queens against the true 92 and 14,039 for twelve against 14,200 — close, and with a larger spread than the total, since most paths contribute nothing.

That makes it a planning tool for exactly the kind of computation that settles small cases in combinatorics. An exhaustive search like the one behind the fewest entries that fix a Latin square or the clause-by-clause search of a letter the clauses already decide is a backtracking tree, and whether it finishes in an hour or a year is the first thing to know. A few thousand random paths, costing a fraction of a second, give an estimate — and the warnings below say how much to trust it.

The estimate also compares strategies. Two orders of choosing which variable to branch on give two trees for the same problem, and estimating both sizes in advance says which order to run, which is how Knuth used it: to choose between versions of a program without running either to completion.

Most single paths guess too small #

The spread of single estimates has a shape, and the shape is the warning. On the twelve-queens tree the estimates run from about twenty thousand to more than eleven million, and 62 per cent of them fall below the true size. The median single estimate is 684,409 against the true 856,189.

That is what an unbiased estimate with a long right tail looks like. Most paths die early, after a few rows with few choices, and report a small tree. A few survive many rows with many choices open at each, and report a tree several times too large — the largest of the twenty thousand reports more than thirteen times the truth. The average is right because the rare large values exactly pay for the common small ones, and a run that is too short to have seen enough of the rare ones will be too small with high probability, even though its expected value is correct.

The typical answer and the average answer are different numbers, and an experimenter who looks at a handful of estimates and takes the middle one is measuring the median, which here is a fifth too small. The difference is mild on the queens trees and, as the last figure shows, it can be anything at all.

The spread grows with the tree #

Running the method on boards of every size from 6 to 14 shows the spread rising steadily. A single estimate’s standard deviation is a third of the true size for six queens, half for eight, nearly the whole of it for fourteen. The means are within a few tenths of a per cent of the exact counts at every size, which is the unbiasedness checked nine times over; the spreads are the price.

The number of paths needed for a given accuracy grows as the square of that relative spread. At fourteen queens it is still modest: a thousand paths give an estimate good to about three per cent, at a cost of fourteen thousand node visits against a tree of twenty-seven million. But the trend is upward, and it is upward for a reason that generalises. A larger tree has more room for unevenness — subtrees of very different sizes hanging from the same node — and the uniform choice at each node treats a vast subtree and a tiny one alike.

A tree built to defeat it #

Push that unevenness to the limit and the method breaks while remaining, formally, perfect. The tree in the figure is a spine twelve nodes long, each node having two children: a leaf, and the next node of the spine. At the foot of the spine sits a full binary tree sixteen levels deep. Almost all of the 131,095 nodes are in that bush, and a random path reaches it only by choosing the spine twelve times running, with chance one in 4,096.

Of twenty thousand paths, two got there. The other 19,998 reported trees of a few dozen nodes, and the median estimate is 7. The two that reached the bush reported half a billion each, and the average of all twenty thousand comes to 0.41 of the truth — the right order of magnitude only because of two paths, and short of the truth because the expected number of such paths was nearly five and only two arrived.

This is the general failure of the estimator, not a curiosity. Its variance is governed by how unequal the subtrees are, and nothing in a short run reveals it: a thousand paths would usually see no path reach the bush and would report a tree of about twenty nodes, with a small standard error, because every one of the thousand agreed. Knuth’s paper made the point with real backtracking programs, where a handful of probes can miss the part of the tree where the work is.

Why the queens trees are kind to it #

The queens trees are a fair test and a forgiving one, and it is worth saying why. Their unevenness is real but bounded: the number of safe columns in a row falls fairly steadily as queens are placed, and no single early choice hides a large fraction of the tree. Siblings in the tree are similar because the board looks similar from most partial placements — a queen in column three rather than column four changes which later columns are attacked, but not by much how many.

That similarity is exactly what the estimator relies on. Each path reports the size of the imaginary uniform tree built from its own branching numbers, and when real siblings resemble each other the imaginary trees resemble the real one. The spread grows with the board because the resemblance weakens as the tree deepens: placements that differ in an early row lead, ten rows later, to boards with quite different numbers of safe squares, and the products of many slightly different factors spread out multiplicatively.

That multiplicative spreading is why the histogram of single estimates, drawn on a logarithmic scale, looks like a bell: on a straight scale it would be lopsided. A product of many independent-looking factors has a logarithm that is a sum, and sums settle into a bell shape; the estimates themselves are therefore spread like the exponential of a bell, with a long right tail that holds much of the mean. The queens trees sit in the mild part of that family, and the spine-and-bush tree in the extreme part, but the mechanism is the same.

Choosing the branches better #

The remedy is the one importance sampling offers for integrals: choose the branches with unequal probabilities, favouring the larger subtrees, and weight by the inverse of whatever probability was used. Any choice of probabilities keeps the estimate unbiased, provided every branch has some chance, and the variance falls to zero when each branch is chosen in proportion to the size of the subtree below it — which would require knowing the answer already.

In practice the probabilities are guessed from cheap information. Paul Purdom suggested in 1978 exploring a few branches at each node rather than one, so that a path is less likely to commit early to a small subtree; Pang Chen proposed in 1992 grouping nodes into strata by some feature believed to predict subtree size and sampling within each. Both keep the estimate unbiased and reduce the spread on trees like the queens trees. Neither helps on the spine-and-bush tree unless the feature they use happens to see the bush coming, and that is the general situation: the estimate is as good as the information used to steer it.

A different family of methods avoids following paths altogether: a walk that samples a distribution can be run on the nodes of a tree to sample them in proportion to any weight, and from such samples the tree’s size can be estimated too. Those methods mix slowly on exactly the trees where Knuth’s estimate fails — a walk has to find the bush to sample it — so they move the difficulty rather than remove it.

There is a kinship here with counting a population by its repeats, where the size of a population is read from how often samples come back. Both estimate something too large to count by sampling a little of it, both are exact on average, and both are blind to a part of the population that is rarely sampled — the hidden subpopulation there, the hidden bush here.

What the figures can be trusted for #

Every true tree size in the figures is an exact count, made by a backtracking search that visits every node, and the twelve- and fourteen-queens counts agree with the published numbers of solutions at their last level, 14,200 and 365,596. The random paths use a seeded generator, so every figure can be reproduced exactly, and the unbiasedness is checked on nine boards by comparing the average of twenty thousand estimates with the exact size.

The spreads are estimated from the same samples and carry their own sampling error, which for a long-tailed distribution is larger than the usual formulas suggest; they are reliable for the queens trees, where the tail is moderate. For the spine-and-bush tree they would not be, which is the figure’s whole point.

Still open: knowing when the estimate is wrong #

Is there a way to tell, from the paths alone, that a run has missed most of the tree? For the spine-and-bush tree the answer is no: a run that never reached the bush contains no trace of it. In general the question is whether a cheap diagnostic can flag the trees where the estimator’s variance is large before the estimate is trusted, and the answers are partial — heuristics based on how much the estimates of different depths disagree, or on how unevenly the branching numbers vary along a path.

A related question is how good an estimate any method can give from a limited number of paths. The spine-and-bush tree shows that no method that sees only a few paths can succeed on every tree, since a tree can hide almost all its nodes behind a single unlikely sequence of choices. Which natural families — the search trees of satisfiability solvers, or of exact cover — are easy to estimate, and by which choice of branch probabilities, is where the practical work continues.