Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
Is this the mathematically revamped Sisyphos mythos? :) –  Raskolnikov Jan 14 '11 at 19:46
1  
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
1  
@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
show 2 more comments

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|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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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