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](https://mathoverflow.net/questions/140912/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$?



Error term for renewal function
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.


P.S. It may be worth pointing out that the argument above parallels the usual "explicit formula" in prime number theory where the error term in the prime number theorem is described in terms of zeros of the Riemann zeta-function. The expression for the renewal time given above is entirely analogous to that explicit formula.


