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

  • 0
    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.2011-01-14
  • 0
    Yes, I need the expected time to completion. Editing for clarity.2011-01-14
  • 0
    @redtuna: This looks like a one-dimensional random walk problem with a reflection barrier at $y$.2011-01-14
  • 0
    @Trevor: perhaps it does; I'm afraid I know nothing about reflection barriers. Is there a closed-form solution to this sort of problem?2011-01-14
  • 1
    Is this the mathematically revamped Sisyphos mythos? :)2011-01-14
  • 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.2011-01-14
  • 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
    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] ?2011-01-14
  • 0
    Just compute the expectation of $R$ over the restricted range $[0,X]$ and divide by the probability of $R$ being in that range.2011-01-14
  • 0
    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?2011-01-14
  • 0
    There is a better way - give it to Maple or Mathematica instead of solving it by hand.2011-01-14
  • 0
    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.2011-01-15
  • 0
    This corresponds to a geometric distribution (q.v.), which can plugged in the new formula. The two resulting series can actually be computed (try Wolfram alpha if you get stuck).2011-01-15
  • 0
    Excellent, thank you very much! That solves my problem.2011-01-15