Error term for renewal function

Question

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$?

Answer 1

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.

Answer 2

This is only a comment but too long for the commentbox so I put it here in an answer-box. The given data are meant to suggest some more possibly incidental relations to perhaps generalizations of the OP's uniform-distribution-problem.
[update]: I've just put together my observations in that problem in a small treatize, see here .

---

I'm analyzing a matrix-method for divergent summation using the matrix of (factorially rescaled) Eulerian numbers. Looking at the intermediate sequences $Y(0),Y(-1),\ldots$ of "Eulerian transforms" of the sequences of coefficients of the $\zeta(0),\zeta(-1),\zeta(-2),\zeta(-3),\ldots$ I arrive at the following table $$ \small \begin{array} {r|rrrr} & y_0&y_1&y_2&y_3 & \cdots \\ \hline Y(0)&1e & 1e^2-1e & 1e^3-2e^2+1/2!e & 1e^4-3e^3+2e^2-1/3!e & \cdots\\ Y(-1)&2e & 3e^2-3e & 4e^3-8e^2+4/2!e & 5e^4-15e^3+10e^2-5/3!e & \cdots\\ Y(-2)&5e & 11e^2-10e & 19e^3-36e^2+17/2!e & 29e^4-84e^3+54e^2-13/3!e & \cdots\\ Y(-3)&15e & 47e^2-37e & 103e^3-180e^2+77/2!e & 189e^4-519e^3+314e^2-141/3!e & \cdots\\ \vdots& \vdots& \vdots& \vdots& \vdots& \ddots \end{array} $$ where the sequence $1e,1e^2-1e,\ldots$ occurs in the first row but there exist subsequent rows too.

While the first row gives terms $$ \small{y(0)_k = r(0)_k+2}$$ with rapidly diminuishing $r(0)_k$ (the $\epsilon$ in your formula) we have similar type of compositions however of higher order, for instance for $Y(0),Y(-1),Y(-2),\ldots$ the sequences are $$ \small \begin{array}{} y( 1)_k &= r( 1)_k&+1k^{-1} \\ y( 0)_k &= r( 0)_k&&+2 \\ y(-1)_k &= r(-1)_k&&+2/3 &+ 4k \\ y(-2)_k &= r(-2)_k&&+2/3 &+ 4k&+8k^2 \\ y(-3)_k &= r(-3)_k&&+38/45 &+ 20/3k&+16k^2&+16k^3 \\ \vdots & \vdots \end{array}$$ Note that the subarray $C$ built from the coefficients (except the $r(m)_k$-entries) can be seen as a matrix and can be generated by the inversion of the Carleman-matrix of the function $f(x)=\log( {exp(x)-1\over x} )$. Thus the exponential generating-functions for the columns are with the functional inverse $g(x)=f^{[-1]}(x)$ and $g(x)=2x+2/3x^2/2!+2/3x^3/3!+38/45x^4/4! + \cdots $ simply its powers $g(x)^c$ (where $c$ is the column-number).

The sequences $R(m)$ evaluated taken their sums $\rho(m)$ give the constants $$ \small \begin{array}{rll|rll} \rho( 1) &=\sum_{k=0}^\infty r(1)_k &= \log(2) &\epsilon( 1,n) &=\sum_{k=n}^\infty r(1)_k \\ \rho( 0) &=\sum_{k=0}^\infty r(0)_k &= 2/3&\epsilon( 0,n) &=\sum_{k=n}^\infty r(0)_k \\ \rho(-1) &=\sum_{k=0}^\infty r(-1)_k &= 2/3&\epsilon( -1,n) &=\sum_{k=n}^\infty r(-1)_k \\ \rho(-2) &=\sum_{k=0}^\infty r(-2)_k &= 98/135&\epsilon(-2,n) &=\sum_{k=n}^\infty r(-2)_k \\ \rho(-3) &=\sum_{k=0}^\infty r(-3)_k &= 122/135&\epsilon( -3,n) &=\sum_{k=n}^\infty r(-3)_k \\ \vdots & \vdots \end{array}$$ and, we would write your example-function $m(t)$ as partial sums $$ \small \begin{array} {} m_0(n) &= \sum_{k=0}^{n-1} r(0)_k &+ 2\sum_{k=0}^{n-1} 1 \\&= \rho(0) - \epsilon(0,n) &+ 2n \\ &=- \epsilon(0,n) + \frac 23 &+ 2n \end{array}$$ and for the next example $$\small \begin{array} {} m_{-1}(n) &= \rho(-1) - \epsilon(-1,n) &+ \frac 23\sum_{k=0}^{n-1} 1 &+4\sum_{k=0}^{n-1} (1+k) \\ &= - \epsilon(-1,n)+ \frac 23 &+ \frac 23 n +& 4 \frac{n^2+n}2 \end{array}$$

Perhaps that coefficients of the lower rows of the $Y$-table or that in the other tables can incidentally be brought into relation with some possible generalizations of the uniform distribution composition problem...