# DKW type inequality for renewal processes

Let $$X_1, X_2, \ldots$$ be a sequence of positive iid random variables with mean $$\mu$$ whose distribution admits a moment generating function in a neighborhood of zero.

Let $$N_t$$ be the associated renewal process given by $$N_t = \sup \left\{ m \geq 0: \sum_{i=1}^m X_i \leq t \right\}.$$

I am looking for DKW type inequalities that would give an exponentially decreasing upper bound to the following probability:

$$P \left( \sup_{0 \leq t \leq T} \left| \dfrac{N_{nt}}{n} - \dfrac{t}{\mu} \right| \geq \epsilon \right).$$

Are there any results which give an upper bound which is up to a constant equal to $$\exp(-n\epsilon^2)$$?

$$\newcommand{\si}{\sigma} \newcommand{\ep}{\varepsilon}$$ Without loss of generality, $$\ep\ge4/n$$, because otherwise the bound $$Ke^{-n\ep^2}$$ on a probability (with an unspecified constant $$K$$) is trivial. Let $$S_m:=\sum_1^m X_i$$. Then for $$t\ge0$$ $$$$S_{N_{nt}}\le nt If the event $$\sup_{0\le t\le T}|\frac{N_{nt}}n-\frac t\mu|>\ep$$ occurs, then for some $$t\in[0,T]$$ we have $$$$\text{ either (i) N_{nt}>k:=\lfloor n(\tfrac t\mu+\ep)\rfloor or (ii) N_{nt}+1 whence either $$S_k\le S_{N_{nt}}\le nt\le(k+1-n\ep)\mu\le(k-n\ep/2)\mu$$ or $$S_l\ge S_{N_{nt}+1}\ge nt\ge(l-2+n\ep)\mu\ge(l+n\ep/2)\mu;$$ note also that here $$$$k\le N:=\lfloor n(\tfrac T\mu+\ep)\rfloor, \quad l\le\lfloor n(\tfrac T\mu-\ep)+2\rfloor\le\lfloor n\tfrac T\mu\rfloor\le N.$$$$
So, $$$$P \left( \sup_{0 \leq t \leq T} \left| \dfrac{N_{nt}}{n} - \dfrac{t}{\mu} \right| \geq \ep \right) \le Q_1+Q_2,$$$$ where $$$$Q_1:=P(\min_{k\le N}T_k\le-n\ep\mu/2),\quad Q_2:=P(\max_{l\le N}T_l\ge n\ep\mu/2),$$$$ $$$$T_k:=\sum_1^k Y_i,\quad Y_i:=X_i-\mu,$$$$ so that $$EY_i=0$$. For positive $$h$$ close enough to $$0$$, we have $$Ee^{h|Y_i|}<2$$, whence $$$$Ee^{hY_i}\le E(1+hY_i+h^2Y_i^2e^{h|Y_i|}/2)\le1+h^2\si^2\le e^{h^2\si^2},$$$$ where $$\si^2:=EY_i^2=Var\,X_i$$. Using now Doob's maximal inequality for the submartingale $$(e^{hT_k})_{k\ge1}$$, with small enough $$\ep$$ and $$$$h=\frac nN\,\frac{\ep\mu}{4\si^2}$$$$ we have $$\begin{multline} Q_2\le\exp\{-hn\ep\mu/2\}Ee^{hT_N} \\ \le\exp\{-hn\ep\mu/2+Nh^2\si^2\} =\exp\Big\{-\frac{n^2\ep^2\mu^2}{16\si^2 N}\Big\} \\ \le\exp\Big\{-\frac{n\ep^2\mu^2}{16\si^2(T/\mu+\ep)}\Big\} \le e^{-cn\ep^2}, \end{multline}$$ where $$c:=\mu^3/(32\si^2 T)$$. Similarly, $$Q_1\le e^{-cn\ep^2}$$. So, the probability in question is upper-bounded by $$2e^{-cn\ep^2}$$, for small enough $$\ep$$ (depending on the distribution of $$X_1$$ and $$T$$). This bound is similar to what you wanted, $$Ke^{-n\ep^2}$$, except that the factor in the exponent has the extra constant factor $$c$$, depending on $$\mu,\si,T$$ -- as it of course should be.