Toss and test: improved random searches with outcome testing. (Try this!) Edward H. Carlson.

Toss and test: Improved random searches with outcome testing

What do a stock speculator, a hungry bacterium, a code breaker, and a typing monkey have in common? Answer: All of them use "toss and test' to get ahead in the world. This article demonstrates toss and test with two programs.

Ok. I confess that I made up the "toss and test' name myself. "Toss' as in tossing a coin, "test' as in looking to see whether it is heads or tails. The toss and test process is a repeated set of random events sandwiched with tests of the results. It sounds commonplace enough, but it has surprising consequences.

Drowing in a Sea of Facts

Toss and test is a way of grabbing at a goal while drowning in a sea of facts. Your grandpa's "By guess and by gosh' and grandma's "If at first you don't succeed, try, try again' are beginning points for the method.

In biology, it is called "mutation followed by natural selection.' It also guides bacteria in their search for the sweet spots in their environments. The disgusted stock speculator, picking stocks by tossing darts at the financial page of his newspaper, may be surprised by his success when he sandwiches dart tosses with careful market timing. It is valuable anyswhere else that decisions must be made with confusing or insufficient data as input.

The Sandwich and the Amplifier

The toss and test process is a set of random trials sandwiched between tests or evaluations of the results. Anyone who builds complex systems uses an analogous method: "build a part, test, build, test, assemble into a bigger unit, test . . .' We can call this brother of toss and test the "build and test' method. Both are important for computer users.

Before trying out toss and test simulations on our computer, let's compare the computer as simulator with some of its other uses. We were promised that the computer would be our mind amplifier, doing all sorts of important thinking for us. But nowadays the computer--as a mental servant--helps us primarily with such menial tasks as mailing list preparation, sorting, world processing, and so forth.

What went wrong? The computer is a mind amplifier true enough, but remember that an amplifier must start with music on a tape before it can thunder a tune through the speakers. Likewise you must have a kit of concepts in your mind before the mind amplifier can do great works for you. Toss and test is just one of a set of integrated concepts that I explain in my recent book The Thinking Tree.

In this article we explore the toss and test idea, letting the computer teach you how it works. Toss and test is fun, and it holds surprises in both of the cases we examine.

A Barrel of Monkeys

Sit a monkey down at a typewriter and let it poke the keys at random. People have claimed that eventually it will type every sentence that has ever been written in English. The big surprise is how long "eventually' can be. Try the sentence:

OFF WITH HER HEAD

which the queen of hearts screeched at Alice and just about everyone else in Alice's Adventures in Wonderland. It has 17 characters counting the spaces. Start the monkey typing 17 character sentences, letting him pick the characters at random from among 27 characters on the keyboard--the 26 letters and a space.

Here goes. The monkey is typing the first sentence. There is one chance in 27 that the first character will be an O. There is another chance in 27 that the second letter will be an F. So there is one chance in 27 times 27 (equals 729) that the first two letters will be correct. Not such a good start on getting all 17 letters right.

But it gets worse very fast. Continuing the multiplications, we find the chance of getting all 17 characters right is 1 over 27 to the 17th power, or about 1 chance in 2 E+24 (using the scientific notation that our computers employ for very large numbers).

Well, let the monkey type fast, day and night for as long as it takes. Assuming 10 characters per second (a very fast typist) and knowing there are about 3 E+7 seconds in a year (60 X 60 X 24 X 365) we must give the monkey a lot of time. So let's suppose the monkey started his work 10 billion years ago (when our galaxy was first formed). In that time the monkey can try 1.8 E + 17 sentences (3 e+17 seconds times 10 characters/ second, then divided by 17 characters in a sentence) but is very unlikely to type the queen's favorite sentence.

He needs help! If we set 12 million more monkeys to typing, with a little luck they may produce OFF WITH HER HEAD once in 10 billion years.

So our first surprise is that random poking, which did not look like a very good method to start with, is really much, much worse than we feared.

Hire a Proofreader

The second surprise will be that toss and test, while still half random, is quite practical.

Twelve million monkey typists are more than our budget can spring for. Let's cut our workforce back: hiring just one monkey and also one proofreader, saving vast sums of money. The proofreader stands behind the monkey and every time the monkey types a letter, the proofreader checks to see if it is correct (that is, if it matches the corresponding letter in OFF WITH HER HEAD). If the letter is wrong, the helper erases it and back spaces the typewriter. This is the toss (random letter) and test (erase if wrong) procedure.

Before running the Toss and Test program (Listing 1), make a guess how long it will take to type OFF WITH HER HEAD by toss and test. The program first tries five sentences by the random all-17-letters-at-once-before-testing method, just to give an idea of what the random sentences look like. They are gibberish, of course. Then the program shows the toss and test method. No trouble at all in deciding which is better. (Toss and Test was written in Microsoft Basic on an IBM PC, but should run on other computers with few or no changes required.)

The Hungry Bug

Now I know you are a practical person, and talk of monkeys does not put bread on the table. I am half practical and will now demonstrate a model of a recent scientific discovery. Here is the experiment.

Take a shallow dish and pour a weak broth containing bacteria into it. When the solution settles down, put a lump of sugar in the dish. The sugar begins to dissolve, providing a high sugar concentration near the lump and a lower concentration farther away.

After a while you will observe that most of the bacteria have congregated near the sugar lump. Sensible, you say. Sure. But bacteria are the world's simplest living organisms, just one cell and, of course, no brain. How do they figure out which direction to swim to get to the goodies? (Of course, the bacteria do not actually need to reach the sugar to eat; they absorb the nourishment in the sugar water through their cell walls.)

Let's watch a single bug and see what happens. The first observation is that the bug swims in a zig-zag path. Each short straight zig is followed by a random "twiddle' to a new heading before the bug sets off on the next zag. The new heading is not completely random however. It is preferentially in a direction similar to the zig it just finished-- that is, within about 45 degrees of the old heading. This kind of motion is called a "random walk,' and there is no way to predict where it will end. The bacterium has as much chance of swimming toward the sugar lump as away from it. Indeed, as we watch, the bug seems to be getting nowhere fast.

But wait. In all his wandering, he seems to be slowly getting closer to the sugar lump. Observe! Not all the zigs and zags are the same length. If the straight path he finished took him close to the sugar (so he tastes more sugar in the water at the end of the run than at the beginning), the next straight line run, while random in direction, is longer. If he tastes less sugar after the zig, the next zag is short again. This is the toss (twiddle to a random direction) and test (taste and decide on a long or short next zag) method again.

Well, I see you are underwhelmed. Such an adjustment in path length would seem to be of little help to a bug that is determined to zig-zag crazily around. Can it really be the secret of success in the bug world?

Run the Bug program (Listing 2) to see the answer. The bug is in a rectangular tank which has its right side wall coated with sugar. Score is kept on how long the bug spends on the left side and how long on the right. (The program runs as written on an IBM PC, but I took care to use standard commands as far as possible, and you can probably adapt it to other computers with only a little rewriting.)

That takes care of the bug and the monkeys. I leave the stock speculator, the code breaker, and many other applications of toss and test to your own modeling efforts.

Table: Listing 1.

Table: Listing 2.