[Martin Taylor 950220 18:50]

In a previous message, I reported on the probability that an N-dimensional

e-coli jump would be closer to the optimum than the current e-coli position,

given that the jump was of length no greater than M. Since then, we have done

two more simulation runs, both using jumps of length exactly M. The first

asked the question "What is the probability that the jump will reduce

the distance to the optimum" and the second "What is the probability

that the jump will reduce the distance to the optimum by at least 5%."

The first run gives answers practically identical to the earlier, as follows

(I'll try to write them in a way easier to understand). In all cases,

the step is one unit, and the optimum is M units away. The entries in the

table are 100 x the probability that a step will lead to a position closer

to the optimum by any amount, however small (blank areas not tested, 0 means

less than 0.5%).

Dim M=1.5 2 2.5 3 3.5 4 5 6 8 10 12 14 16 20 24

4 33 38 40 42 43 44

8 23 31 35 37 39 40

16 11 21 27 31 34 36

32 0 9 17 23 27 30

64 0 0 3 11 17 21 27 31 36 39 41 42 43 44 45

128 9 17 23 30 34 36 38 40 42 43

256 0 4 11 21 27 31 34 36 39 40

512 0 0 0 9 17 23 27 30 34 36

1024 0 0 0 0 4 11 17 21 27 31

2048 0 0 0 0 0 0 3 9 17 23

4096 0 0 0 0 0 0 0 0 4 11

8192 0 0 0 0 0 0 0 0 0 0

No matter what the dimensionality, there is a reasonable (>5%) probability

of some improvement with the jump, provided the optimum is far enough away.

The situation is quite different for the probability that the improvement is

at least 5%. For one thing, such a large improvement is impossible if the

optimum is more than 20 units away (or less than 0.95 units). For another,

at high dimensionality, to get within that "small" an angle--the angle of

the cone that is tangent to a hypersphere of radius 0.95 from a point at

distance 1.0--is a very low probability event. So there is an optimum

distance from the target, at which the probability of an improvement of

at least 5% is maximum--and for all tested dimensions, that optimum is

at a distance around 3 units! Here are the results:

Dim M=1 2 3 4 5 6 8 10 12 14 16

4 18 32 35 34 33 31 26 19 12 6 2

8 4 22 25 25 23 12 4 1 0 0 0

16 0 9 14 13 9 5 1 0 0 0 0

24 0 1 5 4 1 0 0 0 0 0 0

32 0 0 1 1 0 0 0 0 0 0 0

So the probability of getting much improvement from a jump gets to be very

small for even fairly low dimensionality. I think we'll try for a 1%

improvement next.

However, do not despair for e-coli in high-dimensional spaces. The real

question is the probability that the direction is within a certain cone

whose surface passes adequately close to the optimum, and we haven't tested

that question yet. The zeros for large values of M will not come into

play for this question. I suspect it has a much easier analytic answer, and

tomorrow I'll ask.

This all has to be finished before March 31, as my mathematical colleague

will be retiring then.