# Estimating run time in the absence of knowledge

I’ve always wondered how to make a best guess in the absence of any knowledge.

Let’s say you have a computation running, and you don’t know when it will complete (just that it will). Can you make any estimate when it will be finished just based on the elapsed time without any further knowledge? For example after 10 minutes I cannot tell how much longer it will take, it might take 10 more minutes, or less, or a lot more. But after 4 hours I’m quite sure it will not finish in the next 10 minutes (that would be a big coincidence). So a guess might be "probably a few hours more". After 4 days I’d be quite certain that it will take a lot longer.

Can you somehow quantify this certainty / uncertainty?

• I'm not sure this is a computer science question. – Yuval Filmus Jul 7 '17 at 17:36
• Me neither, but not sure where it fits better. – Julian Jul 8 '17 at 8:20
• – David Richerby Jul 8 '17 at 12:35
• Do you have a prior? In other words, before you start the computation, suppose I asked you for your guess at the probability distribution of what the total computation time will be. What probability distribution would you choose? – D.W. Jul 8 '17 at 16:13
• Great question. Once again shows me how important it is to think about the prior. I guess I'll have to write down my experiences and come up with my own best guess for the prior. – Julian Jul 10 '17 at 17:28

No, you can't make any well-justified estimate, if you truly have no knowledge.

In practice, it's rarely that case that we have zero knowledge. Instead, we might have some idea what the distribution of total computation time will look like. That gives you a prior. In other words, before you start the computation, suppose I asked you for your guess at the probability distribution of what the total computation time will be. What probability distribution would you choose? The result is a prior.

If you have a prior, then you can compute an estimate for the remaining run time and quantify the uncertainty, using Bayesian analysis. Let $p(x)$ denote the prior probability that the total computation time is $x$; in other words, before you start running it and before you make any observation, $p(x)$ is your estimate of the probability that it will take $x$ seconds to terminate.

Now we make an observation, and we want to update our estimate of the probability. We observe that the computation has run for $y$ seconds without terminating yet. This implies that, whatever the true value of $x$ will turn out to be, it will be at least $y$. Using Bayes' theorem we obtain

\begin{align*} p(x|y) &= {p(y|x) p(x) \over p(y)}\\ &= {p(y|x) p(x) \over \int_0^\infty p(y|x) p(x) \; dx} \end{align*}

We notice that we're going to need to know the distribution $p(y|x)$. This helps us realize that the problem isn't well-stated yet: you haven't told us how you would decide when to make the observation.

Suppose that we decide in advance, before starting the computation, that we're going to wait $y_0$ seconds and then check whether it has halted or not. Thus there are two possible outcomes of the observation: "already halted" (finished in $\le y_0$ seconds) or "hasn't halted yet" (will take a total of $>y_0$ seconds to finish). Let's denote those by the outcomes "A" vs "H", so we'll say $y=A$ in the former and $y=H$ in the latter. Then we find that $p(y|x)$ has the following form: $p(A|x) = 1$ if $x \le y_0$, else $p(A|x)=0$; and the reverse for $p(H|x)$. Plugging into the formulas above, we obtain

\begin{align*} p(x|A) &= {p(A|x) p(x) \over \int_0^{y_0} p(x) \; dx}\\ p(x|H) &= {p(H|x) p(x) \over \int_{y_0}^\infty p(x) \; dx} \end{align*}

When $x \le y_0$, we have $p(x|H)=0$ (naturally). When $y_0 < x < \infty$, we see that $p(x|H) = p(x)/q$, where $q = \int_{y_0}^\infty p(x) \; dx$ is the prior probability that $x$ falls in the range $y_0 < x < \infty$. Here $q$ is a constant that depends on the prior probability; you can think of it as a normalization constant to ensure that $p(x|H)$ is a probability distribution (it integrates to one).

This gives you the posterior distribution for $x$, after running the experiment (starting up the computation and after $y_0$ seconds checking to see whether it has finished yet) and making the observation (that it hasn't finished yet). From the posterior distribution, you can make estimates for the total running time. For instance, one reasonable way to make an estimate is to compute the expected value of this posterior distribution. In this way we obtain

$$\mathbb{E}(x|H) = \int_0^\infty x p(x|H) \; dx = {\int_{y_0}^\infty x p(x) \; dx \over \int_{y_0}^\infty p(x) \; dx}.$$

You can also summarize the uncertainty in your estimate using a 95% credible interval.

As you can see, all of this machinery requires that we have a prior for the total running time. Selection of the prior isn't something math can give you; instead, it needs to reflect your domain knowledge and expectations. Probably you have some ideas for how likely it is that the computation will take a certain amount of time. For instance, maybe it's common for computations to take anywhere from 1ms to 1 day, but it's rare to run across computations that take (say) 10000 hours -- usually they'll either complete much earlier, or (occasionally) they'll take much longer, but 10000 hours is a lot less likely outcome than 1 hour. So, constructing a prior is the (subjective) process of quantifying that knowledge you already have. Alternatively, the choice of prior might be informed by data, if you collect a data set of how long other computations have taken to complete and use that to fit some kind of distribution to them.

Once you've chosen a prior, then you can use the mathematics shown above to estimate how long the running time will turn out to be, in a methodologically sound way.

• It is Bayesin inference which requires prior knowledge, even distribution. I am curious how to come up with a prior distribution in case similar to asker's. But Bayesian inference is a process requiring intial prior and then updating it to obtain poterior distribution. Then again and again based on fresh data. So it turns it into a sequence of experiments. In fact I suggested similar idea with collecting statistics on running times but was objected that that approach is not suitable. – fade2black Jul 8 '17 at 17:34
• @fade2black, Yup. The next-to-last paragraph of my answer suggests two alternative ways to come up with a prior distribution: use subjective knowledge (based on personal experience, knowledge about the domain, etc.), or collect data. Bayesian analysis tells you what to do once you have a prior, not how to choose a prior. In other words, Bayesian analysis tells you how to draw sound inferences from the knowledge you already have, but doesn't tell you how to obtain that knowledge in the first place. I suspect we're on the same page here. – D.W. Jul 8 '17 at 17:40
• Right. I agree.)) – fade2black Jul 8 '17 at 17:52
• Thanks, this is a great explanation. So let's see if I understand. My best guess right now is that 50% of the computations I observe are below 5 minutes, 30% are between 5 and 30 minutes, 15% between 30m and 2h and the remaining 5% between 2h and 24h. With these numbers, after waiting 5 minutes, I get (25m*0.3+90m*0.15+1320m*0.05)/0.5 = 174m or around 3h for the expected value*. If I wait for 30 minutes, this increases to 344m or around 6h. Perhaps a bit much and I'll have to improve my priors, but sounds legitimate. (* using a simplified step function) – Julian Jul 10 '17 at 17:22

What you are talking about is probably related to exponential distribution and Poisson processes.

In probability theory and statistics, the exponential distribution (also known as negative exponential distribution) is the probability distribution that describes the time between events in a Poisson process, i.e. a process in which events occur continuously and independently at a constant average rate.

The key property of geometric and exponential distributions is memoryless.

It is the continuous analogue of the geometric distribution, and it has the key property of being memoryless.

If we discretize time then the process will be similar to tossing a coin ( given probabilities for $Heads$ and $Tails$) and waiting until the first $Heads$. Memoryless property says that the probability of $Heads$ is the same after the first $Tails$, after 10 $Tails$, or after 1000 $Tails$ in a row.

In your statement you don't provide any information implying that the termination of process somehow depends on the elapsed time. So I assume that the process is memoryless.

The exponential distribution may be applied as following. Suppose that you run your computation anew every time it terminates. And suppose that the rate $\lambda$ is taken as the number of terminations per unit of time (you may guess this quantity or you may collect statistical data). For example if $\lambda$ is measured as number of terminations per minute, then the probability that the computation will terminate in $t$ minutes is equal to $1 − e^{−λt}$.

• But the process isn't memoryless. Any reasonable computation depends on its past state. – David Richerby Jul 8 '17 at 12:20
• @DavidRicherby Process itself is not memoryless, but computation of a new process does not depend on the state of the previous processes, does it? This is what we call memoryless. Exactly as with two incoming telephone calls in a call center. – fade2black Jul 8 '17 at 12:26
• I agree that it's reasonable to assume that different processes are independent -- it won't always be the case, but it's a plausible common case. But we're not talking about different processes, here: we're talking about trying to estimate the time at which a single currently executing process will terminate, based on our knowledge of the running time so far. – David Richerby Jul 8 '17 at 12:33
• @DavidRicherby I agree. But the asker writes "...how to make a best guess in the ABSENCE OF ANY KNOWLEDGE". Then he asks "Can you make any estimate when it will be finished just based on the elapsed time without any further knowledge?" In other words, absolutely no knowledge and no information. In that case we have all rights to make any assumption. Any distribution would be right. – fade2black Jul 8 '17 at 13:40
• @DavidRicherby As for me, if the estimation is so vital and I have NO access to the internals of the computation then I would collect statistical data (durations of each computations) and estimate $\lamda$. And then would choose a model for estimation. – fade2black Jul 8 '17 at 13:43