# yet more e-coli

**URL:** <http://discourse.iapct.org/t/yet-more-e-coli/15447>\
**Category:** CSG1995\
**Created:** [February 21, 1995, 10:03pm UTC](http://discourse.iapct.org/t/yet-more-e-coli/15447 "1995-02-21T22:03:25Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![\_Martin\_Taylor](http://discourse.iapct.org/letter_avatar_proxy/v4/letter/_/a9adbd/32.png) [@\_Martin\_Taylor](http://discourse.iapct.org/u/_Martin_Taylor)\
**Post date:** [February 21, 1995, 10:03pm UTC](http://discourse.iapct.org/t/yet-more-e-coli/15447/1 "1995-02-21T22:03:25Z")

</div>

[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

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(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).
> 
> &nbsp;&nbsp;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