3
$\begingroup$

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).

  • 1
    @Raskolnikov: it is if you remove gods as an assumption; after all in this case your Sisyphus may actually get there.2011-01-14

1 Answers 1

5

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).

  • 0
    Excellent, thank you very much! That solves my problem.2011-01-15