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$ \begin{equation} S_{N_{nt}}\le nt<S_{N_{nt}+1}. \end{equation} 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 \begin{equation} \text{ either (i) $N_{nt}>k:=\lfloor n(\tfrac t\mu+\ep)\rfloor$ or (ii) $N_{nt}+1<l:=\lceil n(\tfrac t\mu-\ep)\rceil+1$ }, \end{equation} 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 \begin{equation} 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. \end{equation}

So, \begin{equation} 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, \end{equation} where \begin{equation} 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), \end{equation} \begin{equation} T_k:=\sum_1^k Y_i,\quad Y_i:=X_i-\mu, \end{equation} so that $EY_i=0$. For positive $h$ close enough to $0$, we have $Ee^{h|Y_i|}<2$, whence \begin{equation} 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}, \end{equation} 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 \begin{equation} h=\frac nN\,\frac{\ep\mu}{4\si^2} \end{equation} 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.

  • $\begingroup$ Thank you for your detailed answer. $\endgroup$ – Roling Wheel Mar 27 '19 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.