Post date: 22-Feb-2012 06:27:30
the story thus far....
You have made (and mostly lost) a small fortune predicting the color of the moon in a small feudal town. A hermit named Shalizi underpinned your success, and your downfall was at the hands of your (former) assistant Grunt. Shalizi's method involved observing the color of the moon (for many nights) and recording the probability that a given color will follow a particular sequence of colors.
Fortunately it was not necessary to maintain records for every possible sequence of colors (every possible sequence of 8 moon colors over 20 nights is a lot of data). At times a long sequence of colors was required to make a good prediction, while at other times a shorter sequence sufficed. Also, some sequences simply never occurred at all. Finally, some sequences could be grouped together, as the probabilities for the subsequent moon color were indistinguishable. This last efficiency did however contain a trap for young players. Moving from one such group of color sequences to the next group was not always deterministic. Careful management was required to avoid this disaster.
back to the story .....
You re-establish your moon prediction business in a distant and much larger town. However, your transported system seems not to work quite so well in these distant parts but you can think of no way of updating it other that starting again.
Fortunately, records of the moons colors have been kept going back many years. Many pundits have attempted to analyse these records but with limited success so you pick up a cheap copy of the almanac at a garage sale. You set up your field again complete with paths, colored stones, and flags.
You keep the new set of menhirs safely indoors with their paths mapped out. However, it is always a huge job every time one of the menhirs changes due to changes out in the field. The homogeneity and determinism of every menhir in every group needs to be checked each time.
You realise after a while that the paths between the menhir groups are actually determined out in the field. If you take a truncated route string which just leads out to a flagged fork and then add a new bead at the knotted end, it will guide you to a fork one step further out from the starting point. Sometimes you pass a flagged fork on the way out but on other occasions the flagged fork is further out and you do not have enough information to determine which of the more distant flagged forks will be next. If you had the whole route string then you would have enough information but you only have the truncated route string. Furthermore, if those more distant flags are not all in the same group then you will be equally unable to determine which group will come next.
To fix this problem you go back to the original flagged fork and move the flag out one step. Of course you will need a number of flags, one for each path from the fork. This time you make it one more step out the subsequent route and one step closer to determining the next flagged fork. So if you move the flags on the first path out far enough you will be able to determine the next flagged fork (and consequently the next group) reliably.
This time however you have no intention of upskilling Grunt's replacement (Bob) and putting your intellectual property at risk. When Bob reports that he has moved a flag further out then you take personal responsibility for the next step. You take the route string and ignore both the bead closest to the knot, and those further out than Bob's newly positioned flag. You follow this route out into the field and if you pass a flagged fork then you move the flag out with you to its new position, one step less distant than Bob's flag.
However, you have not finished yet. You have thought this one thru to avoid being caught making assumptions (as you have before). You realise that you have just moved a flag in the field and that this needs to be treated similarly. So you proceed back to the starting point, ignore the next closest bead to the knot and set out again. And you repeat this until you walk one of these ever more truncated routes without needing to move a flag out. It sometimes requires walking quite a few routes but you are always going to a particular fork and never just searching blindly.
Now you return to your cosy workshop with sometimes a whole stack of new menhirs to be assigned to groups.
And there is a relatively easy way to do this, but the paths and stones analogy is already overstretched. Tip, it involves a very little bit of searching but in a very constrained search space.
This paper attempts to explain the technique in more modern terms.