e-coli with discrete steps

[Martin Taylor 960216 17:50]

Today my retired mathematician friend came in and we started a little
simulation of an e-coli approach to a central target in N-dimensions,
with the new twist that the seeker could move only in steps of exactly
one unit, and if it moved in the wrong direction it would choose a new
direction from the place it reached (i.e. it didn't know how to get back
where it just came from). The rules are as follows.

1. Choose a start point.
2. Choose a direction at random and move one unit in that direction.
3. See if the new place is closer to target than the old. If yes, make
another unit move in same direction, and repeat step 3. If no, go to step 2.
4 (at least today). Stop after several thousand steps, when the
experimenter gets bored with watching the results on the screen.

As we ran it today, it was just a test run, so we looked at a representation
of the mean distance from target and the standard deviation of that distance
averaged over the previous 10,000 executions of step 2 above. We originally
intended to see how quickly the seeker halved the distance to the target,
starting at various start distances, but it turned out that the seeker
actually oscillated around an equilibrium value rather than going to the
target. If the dimensionality was small enough, the fluctuations around
the equilibrium might bring it below threshold, but then it would be likely
to move away again, so we thought this was not a very useful datum.

Results: The seeker found an equilibrium distance from the target, that
distance being very close to 0.6*(log2(D))^2 where log2(D) is the log
of the dimensionality to base 2. (For example, log2(64) = 6, and the
equilibrium distance at 64 dimensions was near 0.6*36. This holds from
about D=4 to D=256, to judge from by-eye averaging of the 10,000 point
averages.

The standard deviation of the seeker's position was equal to 1+epsilon times
the mean, where epsilon ranged from (by memory) 0.06 at D=4 to .006 at D=64
(the only two conditions except the uninteresting D=1 that we tried before
the mathematician went home). I find this a most intriguing result, but at
the moment I don't know what to make of it.

Conclusion. If e-coli cannot "go home" to where things were better, but
must go from wherever he arrived, and if it takes a finite distance before
he can determine whether things have improved, then he will not reach an
optimum but will reach some reasonably stable equilibrium distance from
the optimum. This clearly applies to reorganization by flipping the sign
of a connecting link. It probably does not apply to smooth alteration of
connection weights.

Probably we'll look some more at the problem next week.

Martin