<p>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?</p>

CC BY-SA 3.0
2012-06-27T23:55:16.153Z
2012-06-27T23:55:16.153Z
Or Meir
<p>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. </p>

<p>Main refs (search "algorithm portfolios", "restart strategies" for more)</p>

<ul>
<li>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 </li>
<li>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 </li>
</ul>

<p>On restarts:</p>

<ul>
<li>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</li>
</ul>

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

<ul>
<li>On the Connections between Heavy-tails, Backdoors, and Restarts in
Combinatorial search.  Ryan Williams,  Carla Gomes, and Bart Selman. 
In Proc. SAT 2003 </li>
</ul>

CC BY-SA 3.0
2012-07-04T13:37:53.587Z
2012-07-04T13:37:53.587Z
ggll
<p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.186.188&amp;rep=rep1&amp;type=pdf">"An Empirical Study of Optimal Noise and Runtime Distributions in Local Search"</a> where they show <a href="http://en.wikipedia.org/wiki/WalkSAT">WalkSat</a> (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.</p>

<p>It looks like Gomes, Selman, Crato and Klautz also have a paper called <a href="http://www.cs.rochester.edu/u/kautz/papers/jar.pdf">"Heavy-Tailed Phenomena in Satisﬁability and Constraint Satisfaction Problems"</a> 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.</p>

<p>Also Gomes, Selman and Crato published a paper called <a href="http://pascal.iseg.utl.pt/~ncrato/papers/CP97.pdf">"Heavy-Tailed Distributions in Combinatorial Search"</a> which might be of some relevance.</p>

<p>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.</p>

CC BY-SA 3.0
2012-06-28T16:26:20.497Z
The Gomes, Selman and Crato paper looks very interesting; I will have a look at it. Thank you!
lamontap
CC BY-SA 3.0
2012-06-28T07:18:42.693Z
2012-06-28T07:18:42.693Z
user834
<p>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?</p>

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

CC BY-SA 3.0
2012-06-27T19:09:04.400Z
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
CC BY-SA 3.0
2012-06-27T19:14:37.407Z
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.
lamontap
CC BY-SA 3.0
2012-06-28T00:00:18.500Z
@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
CC BY-SA 3.0
2012-06-28T04:59:50.183Z
If it's a quantum algorithm, then you shouldn't worry about its usability in practice!
Mahdi Cheraghchi
CC BY-SA 3.0
2012-06-28T05:21:53.133Z
I don't follow how "letting the algorithm run until a good solution is obtained" implies "infinite variance".
Suresh Venkat
CC BY-SA 3.0
2012-06-28T07:32:31.790Z
I'm also having trouble in seeing how it is possible to have finite exected time put infinite variance. If there are finitely many inputs and finitely many computational paths, then surely an infinite variance in run time implies an infinite expected run time. Even in the case of quantum systems, where there exists a continuum of states, linearity means that there are only finitely many independent input states and computational paths.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-28T10:14:33.727Z
@RickyDemer: Indeed. Perhaps I'm wrong in assuming it has finitely many computational paths.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-28T16:36:38.937Z
@SureshVenkat: It doesn't, but the probability density function of the running time has a long tail. This makes it impossible to upper bound the variance.
lamontap
CC BY-SA 3.0
2012-06-28T18:20:43.557Z
@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
<ds.algorithms><time-complexity><randomized-algorithms>
Algorithms with finite expected running time and infinite variance
lamontap
# Algorithms with finite expected running time and infinite variance

(Asked by: username_0 on 2012-06-27)

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?

**Tags:** ds.algorithms, time-complexity, randomized-algorithms
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: @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.  
> **username_3**: If it's a quantum algorithm, then you shouldn't worry about its usability in practice!  
> **username_4**: I don't follow how "letting the algorithm run until a good solution is obtained" implies "infinite variance".  
> **username_5**: I'm also having trouble in seeing how it is possible to have finite exected time put infinite variance. If there are finitely many inputs and finitely many computational paths, then surely an infinite variance in run time implies an infinite expected run time. Even in the case of quantum systems, where there exists a continuum of states, linearity means that there are only finitely many independent input states and computational paths.  
> **username_5**: @RickyDemer: Indeed. Perhaps I'm wrong in assuming it has finitely many computational paths.  
> **username_0**: @SureshVenkat: It doesn't, but the probability density function of the running time has a long tail. This makes it impossible to upper bound the variance.  
> **username_6**: @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.  

---

## 3 answers

### Answer by username_6 on 2012-06-28. Score: 7 | Accepted answer

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"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.186.188&rep=rep1&type=pdf) where they show [WalkSat](http://en.wikipedia.org/wiki/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"](http://www.cs.rochester.edu/u/kautz/papers/jar.pdf) 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"](http://pascal.iseg.utl.pt/~ncrato/papers/CP97.pdf) 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.

> **Comments:**
> **username_0**: The Gomes, Selman and Crato paper looks very interesting; I will have a look at it. Thank you!  

---

### Answer by username_7 on 2012-06-27. Score: 5

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?


---

### Answer by username_8 on 2012-07-04. Score: 4

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


---

