Computing probability one program is faster than another So I often have the situation where I want to compare the runtime of two computer processes. Even when measuring only user+system time (as opposed to wall clock time) there is a random element in the measured time. I'm going to suppose that this randomness is poisson distributed (task switches and interrupts from random events on the computer system). 
My hypothesis is that a single program with identical input will run in some amount of time which is composed of a constant amount of time to execute the instructions and some random amount of time generated by one or more poisson process. 
So let's simplify for the moment and assume that there's one poisson process and each time it happens it accounts for the same amount of time. We don't know lambda, nor t(lambda), the time associated with it. I can, however, run the same program on the same input many many times. 
How can I estimate what the constant part of the run time is?
How can I estimate lambda and t(lambda)?
The deeper issue is...
If I have two programs that do the same thing and I want to estimate the probability that one runs faster than the other how would I do this? It seems that blindly applying the normal distribution could be problematic. The random part is (I believe) poisson; but before applying the poisson distribution I'd have to factor out the constant portion. 
 A: You may model the running times $X_1,\dots,X_n$ of the program  as conditionally independent and identically distributed, given $M=\mu$ and $\Lambda=\lambda$, with density
$$
  f_{X_1\mid M,\Lambda}(x_1\mid \mu,\lambda) = \lambda\,e^{-\lambda(x_1-\mu)} I_{(\mu,\infty)}(x_1) \, .
$$
The likelihood of this translated exponential model is
$$
  L_x(\mu,\lambda)=\lambda^n \, e^{-\lambda\left(\left(\sum_{i=1}^n x_i\right) - n\mu\right)} I_{(0,x_{(1)})}(\mu) \, .
$$
As a first attempt, I would try a Bayesian analysis with a Jeffreys-like prior $f_{M,\Lambda}(\mu,\lambda)\propto 1/\lambda$. One goal is to estimate $M$ by $\mathbb{E}[M\mid X=x]$. To sample from the posterior, I would try a Metropolis-Hastings algorithm proposing the next $M$ as $\mathrm{U}[0,x_{(1)}]$, and the next $\Lambda$ from a gamma distribution with expectation equal to the previous value and a tiny variance. With a working sampler, it is easy to compute the estimate and a posterior credible interval for $M$. It is not difficult to extend this analysis to a second program; with the necessary additions to the notation, the natural way to compare both programs is to compute
$P(M<M'\mid X=x,X'=x')$. If this probability is near zero or near one, you can claim that one of the programs is faster.
