Re: How do I bisect unbounded intervals?
On Jan 12 2012, Ralph Baker Kearfott wrote:
Although this not directly focused on our standardization process,
I find it very interesting. In particular, I am leery of
arguments concerning "happens with probability 1." For example,
in homotopy methods for solving polynomial systems, a popular
topic of research in the 1980's, arguments were used stating
that, if you chose the starting coefficients randomly, the paths
ended at all of the solutions to the desired system "with probability 1."
In fact, most polynomial systems occurring in applications have
some kind of special structure, that, in the spaces originally
set up, occur "with probability 0."
Also, "with probability 1," a random matrix is non-singular. In the
appropriate measure space, a continuous function has non-isolated
minima "with probability 0," but, again, the models people design
are often the exceptional cases. Even with toy problems, it seems
that the "probability 0" cases are hard to avoid. For example,
a simple test problem might be to minimize (x_1 - x_2)^2.
I regret to say that those examples simply demonstrate my point that
almost no computer scientists have a clue about probability. There
are some totally bogus 'standard results' in complexity theory that
use the same erroneous 'logic'. You are absolutely right that those
arguments are complete nonsense, but that doesn't stop them being
used :-(
Nonetheless, the above may not apply when choosing the point
for bisection (or trisection, or whatever).
They don't. The defect of the examples is to prove something
almost everywhere (i.e. on a subset of measure one) on a set, and
then make statements about subsets of measure zero. That misses
the whole point, as even a first-year probabilist would know!
I wasn't talking about that, anyway, but of convergence with probability
one, which is a slightly different concept. It gets a bit hairy if the
convergence is not uniform over the problem set, but that is just a
matter of using two infinite limits in the right order - which isn't
exactly a new problem to numerical analysts :-)
Consider this pair of forms:
For all points within the problem set, step N and a function F decreasing
to zero, the error bound is less than F(N).
For all points within the problem set, step N and a function F decreasing
to zero, the error bound is less than sqrt(F(N)) with probability greater
than 1-sqrt(F(N)).
You can do better than that in the vast majority of cases, but you will
take my point about the equivalence.
Another consideration with probability arguments is predictability of the
algorithm behavior (or "behaviour," as might occur in our P-1788
standard). I grant you that this is a bit of a problem in branch and
bound algorithms for optimization, even without randomization, but the
reasons for excessive computation time can be traced in particular cases
when the algorithm is deterministic, provided one is sufficiently
persistent in examining the execution process.
As they can with randomisation, actually, though I accept that it makes
it rather trickier.
Regards,
Nick Maclaren.