# Algorithms with finite expected running time and infinite variance

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?

• 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? – Noam Jun 27 '12 at 19:09
• 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. – Philippe Lamontagne Jun 27 '12 at 19:14
• @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. – Robin Kothari Jun 28 '12 at 0:00
• I don't follow how "letting the algorithm run until a good solution is obtained" implies "infinite variance". – Suresh Venkat Jun 28 '12 at 5:21
• @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. – user834 Jun 28 '12 at 18:20

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 Satisﬁability 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.

• The Gomes, Selman and Crato paper looks very interesting; I will have a look at it. Thank you! – Philippe Lamontagne Jun 28 '12 at 16:26

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?

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