[Martin Taylor 950221 16:00]
It turns out that it is easy to compute the probability that some number
of small steps in a given randomly chosen direction will result in an
improvement of x% in N dimensions. And twice the given value will provide
the probability that x% improvement will eventually happen, given that
the first (infinitesimal) step provided some improvement. Other ratios
are easily found for finite initial steps. Here's the logic (discussed
with my colleague).
If we start from a position M units away from the optimum, we are on the
surface of a (hyper)sphere of radius M. If we take a step of 1 unit that
improves or maintains the distance to the optimum, the step ends on or
inside the hypersphere. The mid-point of that step is the closest we would
come to the optimum by taking infinitesimal steps in that direction. So the
probability that a step of size 1 will result in an improvement of any
magnitude is the same as the probability that a step of size 0.5 will
result in an improvement by the ratio
(original distance)
···
_________________________________________________________________________
(radius to mid-point of step that ends on the surface of the hypersphere)
These values can be interpolated from the numbers I have already posted,
but here's a sample. First, the starting distance (M) with which to enter
the previous tables, for an improvement to at least a factor F of the
original distance (i.e. F=0.99 means that by moving in that direction
the improvement will be at least 1% after enough infinitesimal steps).
F M
0.99 14.2
0.98 10.0
0.95 6.4
0.90 4.6
0.80 3.3
There's no point in going any further, because I can't read the graphs
below M=3, and in any case only the very lowest dimensionality have any
readable values for such small M.
Here are my interpolated percentages (Dave is running tests with to get
the exact values, but these will be close enough for most purposes).
F = ratio of improved to original distance to optimum. Entries are probability
of achieving at least that degree of improvement in one straight run of
steps in a direction chosen initially at random (multiply by two to get
the conditional probability, given that the initial tiny step was in an
"improving" direction).
Dim F=0.99 0.98 0.95 .090 0.80
64 42 39 33 25 14
128 38 34 24 13 1
256 34 27 14 0 0
512 27 17 0 0 0
1024 17 4 0 0 0
2048 3 0 0 0 0
These numbers could be used to make a rough estimate of the number of turns
required to make an improvement of x%. By a "turn" I mean a sequence of
trials that continue until a tiny step makes some improvement. To make
a 50% improvement, for example, our e-coli could make a run that produces
a 10% improvement (to 0.90), and then one that makes a 33% improvement
(to 0.60), and then one that makes a 17% improvement (to 0.50). Each of
these straight runs would probably be preceded by a few attempts that
made matters slightly worse, all of which are included in one "turn."
I'm not going to do the arithmetic, because it's summing a lot of probability
values (more correctly, convolving a lot of probability distributions), but
it is easy enough in principle to figure out the probability that N
straight runs will reduce e-coli's distance to the optimum by x% or
better. It'll work in the end, no matter what the dimensionality, but
the number of turns to get any useful improvement (say more than 10%) becomes
very large when the dimensionality gets into the hundreds. This means
that an e-coli optimization procedure in high dimensionality must require
both rapid and accurate assessment of whether a particular move resulted
in an improvement in the situation--i.e. the measurement of relative
distance to the optimum has increased or decreased has to be both fast
and precise. And the higher the dimensionality, the more difficult is
that measurement in any practical situation (such as reorganization).
A better bet, in most cases, is presumably to try to reduce the dimensionality
of the problem.
Martin