7
$\begingroup$

I am working on an algorithm for which the running time is a random variable $X$ that has finite expected value, but infinite variance. Are there examples of other algorithms for which this is the case?

Are any such algorithm used in practice, or does the infinite variance make the running time too unpredictable?

Improve this question
$\endgroup$
10
  • 6
    $\begingroup$ What is the probability space? Random coin tosses? Input? In the former case, you can always get rid of the large variance; in the latter, how can you get anything to be infinite unless you have infinitely many inputs? $\endgroup$
    – Noam
    Jun 27, 2012 at 19:09
  • $\begingroup$ Actually it is a quantum algorithm so randomness in the algorithm comes from measuring a state in a superposition of basis states. The infinite variance comes from the fact that you let the algorithm run until a good solution is obtained. What I am looking for here is not so much how to reduce the variance, I have some ideas for that, just to have other examples of algorithms to compare to and gain some intuition. $\endgroup$
    – lamontap
    Jun 27, 2012 at 19:14
  • 1
    $\begingroup$ @PhilippeLamontagne: Do you have a simple example of such an algorithm? A quantum algorithm is fine too. I'm interested to see what such an algorithm would look like. $\endgroup$
    – Robin Kothari
    Jun 28, 2012 at 0:00
  • 2
    $\begingroup$ I don't follow how "letting the algorithm run until a good solution is obtained" implies "infinite variance". $\endgroup$
    – Suresh Venkat
    Jun 28, 2012 at 5:21
  • 2
    $\begingroup$ @JoeFitzsimons, in this context I take "infinite variance in runtimes" to mean "diverging second moment in runtimes". For example, for any finite instance of 3-SAT a (complete) algorithm will always be guaranteed to halt in finite time, but the run time might diverge in it's second moment as instance size gets larger. Power law tailed distributions, and the more general Levy-Stable distributions, can have infinite second moment but finite expected value. Though finite mean but infinite varianced distributions may be counter intuitive, they exist and are actually fairly common. $\endgroup$
    – user834
    Jun 28, 2012 at 18:20

3 Answers 3

Reset to default
7
$\begingroup$

Though I'm having trouble finding the exact exponent of the power laws they purport to exist, Kroc, Sabharwal and Selman have a paper called "An Empirical Study of Optimal Noise and Runtime Distributions in Local Search" where they show WalkSat (a local solver for SAT) has power law tails in the runtime. If the power law does not fall within the range of $(2,3]$, then obviously this isn't quite what you're looking for, but maybe it's still of some use.

It looks like Gomes, Selman, Crato and Klautz also have a paper called "Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems" though from a quick spot check it looks like they're reporting the exponent in the power law in the range of $(1,2)$ which would violate your finite first moment condition.

Also Gomes, Selman and Crato published a paper called "Heavy-Tailed Distributions in Combinatorial Search" which might be of some relevance.

From what I understand, the sporadic nature of runtimes (for example, because of a power law behavior in running time) gives one a good reason to use random restarts and might even inform you as to when a restart should occur. Figure 8a in the paper "Heavy-Tailed Distributions in Combinatorial Search" gives two run time plots, one without restarts and one with, where the algorithm with random restart clearly wins out.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The Gomes, Selman and Crato paper looks very interesting; I will have a look at it. Thank you! $\endgroup$
    – lamontap
    Jun 28, 2012 at 16:26
5
$\begingroup$

I don't know whether such algorithms are used in practice, but it seems that Markov's inequality should give you a sufficiently good bound on the probability of running for too long time, right?

Improve this answer
$\endgroup$
4
$\begingroup$

Your algorithm's runtime distribution is "heavy-tailed" i.e. the tail of the survival function (1-F(t)) of the runtime distribution follows a power law. This is a well known phenomenon which has been observed in complete solvers for SAT (see the above ref. to Gomes et al., and other papers by the same authors). If your algorithm is randomized, i.e. you get different runtimes with different random seeds on the same problem instance, it turns out you can remove the heavy tails by running several copies of the algorithm in parallel, with different random seeds, in what is called an "algorithm portfolio", aborting all runs as the first one arrives to the solution. Alternatively you may want to implement a "restart strategy", restarting the algorithm with a different seed if no solution found for a certain time.

Main refs (search "algorithm portfolios", "restart strategies" for more)

  • Heavy-tailed phenomenon in satisfiability and constraint satisfaction problems by: C. P. Gomes, B. Selman, N. Crato, H. Kautz Journal of Automated Reasoning, Vol. 24, No. 1-2. (2000), pp. 67-100 doi:10.1023/A:1006314320276
  • Algorithm portfolios by: Carla P. Gomes, Bart Selman Artificial Intelligence, Vol. 126, No. 1-2. (February 2001), pp. 43-62, doi:10.1016/S0004-3702(00)00081-3

On restarts:

  • Optimal speedup of Las Vegas algorithms Information Processing Letters, Vol. 47, No. 4. (1993), pp. 173-180, doi:10.1016/0020-0190(93)90029-9 by M. Luby, A. Sinclair, D. Zuckerman

On the mechanisms behind heavy tails: most runs are short, some runs get "stuck" in a very deep tree search:

  • On the Connections between Heavy-tails, Backdoors, and Restarts in Combinatorial search. Ryan Williams, Carla Gomes, and Bart Selman. In Proc. SAT 2003
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.