# Error term for renewal function

Consider a sequence of independent uniform $[0,1]$ random variables, and for nonnegative real $t$, let $m(t)$ be the expected number of terms in the first partial sum that exceeds $t$. For instance it's folklore that $m(1)=e$, meaning we need on average $e$ terms to get the sum above 1. It follows from renewal theory that for large $t$, $$m(t) = 2t + 2/3 + o(1),$$ but

How does the error $m(t) - (2t+2/3)$ behave?

In particular,

Can $m(t)$ be expressed as $$m(t) = 2t + \sum_{\gamma_i}C_ie^{\gamma_i t},$$ where $\gamma_i$ are the complex roots of the equation $1-\gamma = e^{-\gamma}$?

I started to think about this as I was trying to come up with a clever answer to the question Random walk with positive uniformly distributed steps.

An expression for $m(t)$ can be derived from the so-called renewal equation, which in this case becomes $$m(t) = 1 + \int_{t-1}^t m(x)\,dx$$ for $t\geq 1$, while $m(t) = e^t$ for $0\leq t\leq 1$. This leads (after differentiation) to $m(t) - m'(t) = m(t-1)$, and one can establish by induction that for nonnegative real $t$, $$m(t) = \sum_{k=0}^{\lfloor t \rfloor} \frac{(-1)^k(t-k)^k}{k!}e^{t-k}.$$ Some numerical computation reveals that $m(t)$ is extremely close to $2t+2/3$ even for moderately large $t$. For instance, $$m(5) = e^5 - 4e^4 + \frac92e^3 - \frac43e^2 + \frac1{24}e \approx 10.66666207.$$

The reason $m(t)$ is close to $2t+2/3$ is that the expected value of the first sum that exceeds $t$ is equal to the expectation of the terms (in this case $1/2$) times $m(t)$ (an instance of Wald's equation). And the first sum that exceeds $t$ will do so by an amount which is close to $1/3$ in expectation (see the "inspection paradox").

The difference $m(t) - (2t+2/3)$ seems to be exponentially small, but what is the easiest way to get a reasonable bound? Is there some clever coupling to a stationary process? Those of you who have Maple available can get a plot with the command

plot((sum((k-t)^k/k!*exp(t-k),k=0..floor(t))-(2*t+2/3))*exp(2*t),t=0..10);

Here I have scaled up the error term by an arbitrary factor $e^{2t}$ just to see it more clearly.

It seems that the error term oscillates with a more or less constant frequency. For instance, it has 59 zeros in the interval $0\leq t \leq 25$, and another 59 in the interval $25\leq t \leq 50$.

We can try to explain this behavior by looking at the equation $m(t)-m'(t) = m(t-1)$ without boundary conditions. The ansatz $m(t) = e^{\gamma t}$ leads to the equation $$1-\gamma = e^{-\gamma},$$ and we can try to express $m(t)$ as $$m(t) = 2t + \sum_i C_ie^{\gamma_i t},$$ where $\gamma_i$ ranges over the complex roots of $1-\gamma = e^{-\gamma}$, or if we prefer real numbers, $$m(t) = 2t + \sum_i e^{\alpha_i t}\left(A_i \cos\beta_i t + B_i \sin\beta_i t\right),$$ where $\alpha\pm \beta i$ are the pairs of conjugate roots of $1-\gamma = e^{-\gamma}$.

There is a "trivial" zero at $\gamma = 0$, and the next (in order of decreasing real part and increasing imaginary part) pair of roots are at approximately $-2.09\pm 7.46i$. The plot of the error term is consistent with a term coming from these roots. The error is decaying a little faster than $e^{-2t}$, and the frequency of the oscillations is about $7.46$, so that we expect around $7.46/\pi \approx 2.37$ sign-changes per unit.

Can we establish that $m(t)$ is a sum of this type, and can we say something about the coefficients $A_i$ and $B_i$?

-
There has to be a sign change in every interval of length $1$ since the error is a weighted average of the errors on any previous unit interval, so if the sign of the error were constant on a unit interval the asymptotic behavior would not be $2t+2/3$. –  Douglas Zare Sep 5 at 19:39
Douglas, good comment, and it made me realize I had written down the renewal equation incorrectly, now edited. –  Johan Wästlund Sep 5 at 20:03
There are many papers proving exponential convergence, for example Stone's "On moment generating functions and renewal theory", where the proof seems to be about one page long. –  Yuval Filmus Sep 9 at 19:13

Given $x$, let $P_n=P_n(x)$ denote the probability that $X_1+\ldots+X_n \le x$ where $X_i$ are independent and uniform in $[0,1]$. You are asking for $P_0+P_1+\ldots$. Now for any $c>0$ the integral $$\frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{y^s}{s} ds$$ equals $1$ if $y>1$ and $0$ if $0\le y<1$. The integral is to be interpreted as $\lim_{T\to \infty} \int_{c-iT}^{c+iT}$. From this we see that $$P_n = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{e^{xs}}{s} {\Bbb E}(e^{-sX})^n ds.$$ Summing this over all $n$ from $0$ to infinity, we find that $$\sum_{n=0}^{\infty} P_n = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{e^{sx}}{e^{-s}-1+s}ds.$$ This contour integral can be evaluated by moving the line to the left. There is a double pole at $s=0$ with residue $2x+2/3$. There are other poles that arise from the zeros of $e^{-s}-1+s$ and the residues here will give the kind of expression you want. Note that $s=-2.09+7.46 i$ is approximately a zero of this function.
If I computed correctly the remainder then looks like $$\sum_{\rho} \frac{e^{x\rho}}{\rho}$$ where $\rho$ runs over the zeros of $e^{-s}-1+s=$ except for the trivial zero at $s=0$. These zeros all lie in the half plane Re$(s)<0$ and therefore the remainder does decrease exponentially.
Regarding the PS: Yes, the similarity to the prime number theorem is striking. For the renewal function, if (as I did) one starts from the differential equation and requires each term of the explicit formula to be a solution, it follows that the points $\rho = \sigma + ti$ must be on the curve $t=\pm \sqrt{e^{-2\sigma}-(1-\sigma)^2}$. What would the prime number equivalent of the renewal equation be? –  Johan Wästlund Sep 9 at 23:56