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

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.