Sign up ×

I hope this is the right place for help on this question! I expect this should be easy for this audience (and, no, this isn't homework).

I have a task that takes $X$ seconds to complete (say, moving a rock up a hill). However, sometimes the task is restarted from the beginning (say, an earthquake rolls the rock back to the bottom of the hill). I know that these restart events happen on average every $Y$ seconds ($Y$ less than $X$). I need to find out how long it will take in total to reach the top of the hill.

To be perfectly clear, suppose I start the task at time $t=0$ and, every time a "restart event" happens, I immediately restart. When I complete the task I record $f$, the final value of $t$. What is the expected value of $f$?

In my attempt to solve this, I model the restart as a Poisson event with average $\lambda=Y$. However, I'm not sure how to proceed.

p.s. the restart events are random, of course, not on a schedule happening every Y seconds (otherwise I would never be able to reach the top of the hill).

share|cite|improve this question
What do you want to know? I'm guessing you're asking about the time to completion -- either the average time to completion or some more specific information about the distribution -- but I think a sentence or two is missing here. – Michael Lugo Jan 14 '11 at 19:28
Yes, I need the expected time to completion. Editing for clarity. – redtuna Jan 14 '11 at 19:31
Is this the mathematically revamped Sisyphos mythos? :) – Raskolnikov Jan 14 '11 at 19:46
Also, if you want to model the restart so that it happens every $Y$ seconds on average, you probably want the Poisson event with average $\lambda = Y^{-1}$. The mean should reflect the number of events per unit time expected. – Willie Wong Jan 14 '11 at 19:47
@Raskolnikov: it is if you remove gods as an assumption; after all in this case your Sisyphus may actually get there. – Willie Wong Jan 14 '11 at 19:49

1 Answer 1

up vote 5 down vote accepted

Let $T$ be the requested time, and $R$ a random variable measuring the time until the next restart. We have $$\mathbb{E}[T] = \Pr[R > X] \cdot X + \Pr[R \leq X]( \mathbb{E}[T] + \mathbb{E}[R|R\leq X]).$$ Simplifying, we get $$\mathbb{E}[T] = X + \frac{\Pr[R \leq X]}{\Pr[R > X]} \mathbb{E}[R|R\leq X].$$

Edit: Here's a more explicit formula, assuming that $R$ is a continuous random variable with density $f$: $$ \mathbb{E}[T] = X + \frac{\int_0^X rf(r)\, dr}{1 - \int_0^X f(r)\, dr}. $$

Edit: Here's another formula, for a discrete random variable with integer values (assuming a restart is valid if it happens at time $X$): $$ \mathbb{E}[T] = X + \frac{\sum_{t=0}^X t\Pr[R=t]}{1 - \sum_{t=0}^X \Pr[R=t]}.$$

Edit: plugging a geometric distribution with expectation $\lambda$, Wolfram alpha gets this. Note that a geometric distribution has a non-zero probability to be $0$ (in that case the restart occurs immediately).

share|cite|improve this answer
Ah, this looks good. And with a Poisson distribution for R, Pr[R \leq X] is the CDF at X (using lambda=1/X), yes? But how do I compute E[R|R \leq X] ? – redtuna Jan 14 '11 at 19:53
Just compute the expectation of $R$ over the restricted range $[0,X]$ and divide by the probability of $R$ being in that range. – Raskolnikov Jan 14 '11 at 19:58
I apologize for needing handholding. So I apply Bayes, and I use the CDF for Pr[R in the range] (that's the same as the PR[R \leq X] above, it seems). But how do I compute the expected-time-to-failure-under-constraint-that-it's-less-than-X? A weighted sum of each time for 0..X, multiplied by the probability that it's in that interval (based on the CDF)? There ought to be a better way, no? – redtuna Jan 14 '11 at 21:52
There is a better way - give it to Maple or Mathematica instead of solving it by hand. – Yuval Filmus Jan 14 '11 at 23:18
ok, if the "restart events" are iid, such that during any second there is the same probability of a restart as during any other second, and I know the average time between restart, does the equation simplify to something more mundane? I don't have Maple or Mathematica on hand, now do I have any experience with them. – redtuna Jan 15 '11 at 0:10

Your Answer


