1
$\begingroup$

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

$\endgroup$

1 Answer 1

3
$\begingroup$

$\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.

$\endgroup$
1
  • $\begingroup$ Thank you for your detailed answer. $\endgroup$ Commented Mar 27, 2019 at 15:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .