Suppose that a stationary random process $S(t)$ can be characterized as the figure below, which for most of the time is a straight line $S(t)=c\cdot t$, but occasionally would "stall" for a period of time $B_i$. The stalling time $B_i$'s are i.i.d. random variables, with the first and second moments known as $\operatorname{E}[B]$ and $\operatorname{E}[B^2]$, respectively. The appearance of $B_i$'s can be modeled as a renewal process. In a fraction of $\rho$ time the system would see a $B_i$. Let $N(t)$ be the number of $B_i$'s in a duration of time $t$. $\lim_{t\rightarrow \infty}\frac{N(t)}{t}=\frac{\rho}{\operatorname{E}[B]}$.

Given the above conditions, is it possible to (approximately) determine an affine envelope for the negative moment generating function of $S(t)$? That is, for $\theta>0$, determine a function $\sigma(\theta)$ such that:

$$\operatorname{E}\left[e^{-\theta S(t)}\right]\leq e^{-\theta(c\cdot t-\sigma(\theta))}.$$

For some background, if we think of $S(t)$ as the service process of a server, this kind of envelope (read dash line) corresponds to a lower bound of $S(t)$ known as the serivce curve of the server in the language of stochastic network calculus. $\sigma(\theta)$ may correspond to the latency incurred by the service and $\theta$ is some decaying rate.

Illustration of <span class=$S(t)$" />

Attempted Solution:

I have attempted the following approach and had some problem. Note that $S(t)$ may be expressed as $S(t)=c\cdot t - B(t)$ where $B(t)$ is a random process depicted in the following figure. Illustration of <span class=$B(t)$" />

Then we have $\operatorname{E}[e^{-\theta S(t)}]=e^{-\theta c t}\operatorname{E}[e^{\theta B(t)}]$. The question then reduces to find a function $\sigma(\theta)$ to bound $\operatorname{E}[e^{\theta B(t)}]$ as $\operatorname{E}[e^{\theta B(t)}]\leq e^{\theta \sigma(\theta)}$, i.e., to find a bound on $B(t)$'s MGF.

It seems that Hoeffding's lemma is relevant here. Given $B_i$'s moments and that $B_i$'s are renewal, I was able to determine $B(t)$'s mean as $$\operatorname{E}[B(t)]=\lim_{t\rightarrow\infty}\frac{\int_{0}^tB(\tau)\mathrm{d}\tau}{t}=\lim_{t\rightarrow\infty}\frac{\sum_{i=1}^{N(t)}\frac{1}{2}cB_i^2}{t}=\lim_{t\rightarrow\infty}\frac{N(t)}{t}\frac{\sum_{i=1}^{N(t)}\frac{1}{2}cB_i^2}{N(t)}=\frac{\rho}{\mathrm{E}[B]}\frac{1}{2}c\operatorname{E}[B^2].$$

To use Hoeffding's lemma, it requires that $B(t)\geq 0$ is upper bounded, which unfortunately is not the case here. I have attempted to pick a upper bound $b$ according to Chebyshev's inequality and then bound the MGF as:

$$\operatorname{E}[e^{\theta B(t)}]\leq \exp\left(\theta\cdot \operatorname{E}[B(t)]+\frac{\theta^2b^2}{8}\right).$$

This results in $\sigma(\theta)=\operatorname{E}[B(t)]+\frac{b^2}{8}\theta$. However, this bound seems quite loose.

Are there any other approaches? Or other conditions, say, higher-order moments of $B_i$ are needed to obtain sharper bounds?

  • $\begingroup$ What do you mean by "occasionally"? How often do these occasions come? In what way -- by themselves and in relation with the $B_i$'s? $\endgroup$ Dec 16, 2021 at 15:00
  • $\begingroup$ @Iosif Pinelis Thanks for reminding this important point. The appearance of $B_i$'s is a renewal process. In a fraction of $\rho$ time the system may see a $B_i$. Let $N(t)$ denote the number of $B_i$'s in a duration of time $t$. Using renewal theory, the appearance frequency of $B_i$'s is approximately $\lim_{t\rightarrow \infty}\frac{N(t)}{t}=\lim_{t\rightarrow\infty}\frac{\rho t/\mathrm{E}[B]}{t}=\frac{\rho}{\mathrm{E}[B]}$. I have updated the question. $\endgroup$
    – leeyee
    Dec 17, 2021 at 1:11
  • $\begingroup$ The setting is still not quite clear to me. Can you define it formally? Say, can we assume that the beginning of the $i$th stalling period is $D_1+B_1+D_2+\cdots+B_{i-1}+D_i$, where the $D_i$'s are iid independent of $B_i$'s? If so, what else do we know about the durations $D_i$? $\endgroup$ Dec 17, 2021 at 1:39
  • $\begingroup$ @IosifPinelis Yes, $D_i$'s are independent of $B_i$'s. We may think of $B_i$'s as the busy period of a queueing system. It occurs when a customer arrives at the empty system. In the current setting, I'm trying to not assume a specific arrival pattern. $\endgroup$
    – leeyee
    Dec 17, 2021 at 4:39
  • $\begingroup$ Are the $D_i$'s iid? $\endgroup$ Dec 17, 2021 at 12:20

2 Answers 2


$\newcommand{\ep}{\varepsilon}$A bound similar to, and at least in some cases more accurate than, the bound presented in my previous answer on this page, can be obtained, a bit more easily, using formula (15) by Lorden: for real $u\ge0$ and $z\ge0$, \begin{equation*} P(Z_u\ge z)\le\frac1\mu\,E(2B-z)1(B\ge z), \end{equation*} where $B:=B_1$, $\mu:=EB\in(0,\infty)$, and, as in the previous answer, $Z_u$ is the backward recurrence time.

Indeed, by formula (4) in the previous answer and the just cited result by Lorden, for any real $h>0$, \begin{equation*} \begin{aligned} Ee^{hZ_u}-1&=\int_0^\infty he^{hz}P(Z_u>z)\,dz \\ &\le\frac1\mu\,E\int_0^\infty he^{hz}(2B-z)1(B\ge z)\,dz \\ &=\frac1\mu\,E\int_0^B he^{hz}(2B-z)\,dz \\ &=\frac1{h\mu}\,E(e^{hB}+hBe^{hB}-1-2hB), \end{aligned} \end{equation*} whence \begin{equation*} Ee^{hZ_u}\le-1+\frac1{h\mu}\,(Ee^{hB}-1+hEBe^{hB}). \tag{*} \end{equation*}

The upper bound on $Ee^{hZ_u}$ given by (*) can be compared with the upper bound given by the inequality \begin{equation*} Ee^{hZ_u} \le Ee^{2hB}\Big(1+\frac1{2 h^2 \mu}+\frac{EB^2}{2h\mu^2}\Big) \end{equation*} at the end of the previous answer, as well as with the lower bound \begin{equation*} \begin{aligned} \sup_{u>0}Ee^{hZ_u}&\ge-1+\frac1{h\mu}\,E(e^{hB}-1), \end{aligned} \end{equation*} which follows immediately from formula (6) in the previous answer.

One may also note that $e^{hB}-1\le hBe^{hB}\le h\dfrac{e^{(h+\ep)B}-e^{hB}}\ep$ for positive real $h$ and $\ep$, and hence (*) implies \begin{equation*} Ee^{hZ_u}\le-1+\frac2\mu\,EBe^{hB}\le-1+\frac2\mu\,\dfrac{Ee^{(h+\ep)B}-Ee^{hB}}\ep. \end{equation*}

  • $\begingroup$ The bound of (*) seems to be slightly tighter in my application. As all I need is a lower envelope of $S(t)$, I wonder is that possible to directly derive an upper bound of $\lim_{n\rightarrow\infty}P(\max_{i=1,\ldots,n}B_i>x)$, if I know $B$'s MGF exactly? As an example, suppose that $B$ is the busy period of a M/M/1 queue, for which the Laplace transform of its pdf is known to be $G^*(s)=\frac{\mu+\lambda+s-[(\mu+\lambda+s)^2-4\lambda\mu]^{1/2}}{2\lambda}$, where $\lambda$ and $\mu$ are arrival and service rates. respectively [Eqn.(5.144) of Kleinrock "Queueing Systems, Vol. 1"]. $\endgroup$
    – leeyee
    Dec 23, 2021 at 10:25
  • $\begingroup$ This limit is just $1$ for all $x$ such that $P(B_1\le x)<1$. However, the questions in your latter comment are in addition to your posted question. You may want to post such additional questions separately (not necessarily on MathOverflow). Generally, asking multiple questions in one post is discouraged on MathOverflow. Anyway, are you satisfied with the answers to your originally posted question? $\endgroup$ Dec 23, 2021 at 14:42
  • $\begingroup$ Your solutions to my original question are very useful. And thanks for reminding me the policy. I have posted the further question as a separate one on MSE: math.stackexchange.com/questions/4340872/…. $\endgroup$
    – leeyee
    Dec 24, 2021 at 1:12

For each natural $i$, let $S_i$ and $T_i$ denote, respectively, the starting and terminal (ending) time moments of the $i$th stalling period. Let $D_i:=S_i-T_{i-1}$, the duration of the time between the end $T_{i-1}$ of the $(i-1)$th stalling period and the start $S_i$ of the $i$th stalling period, with $T_0:=0$.

So, for each natural $i$, \begin{equation*} S_i=D_1+B_1+D_2+\dots+B_{i-1}+D_i=R_i+U_i \end{equation*} and \begin{equation*} T_i=S_i+B_i, \end{equation*} where \begin{equation*} R_i:=D_1+\dots+D_i,\quad U_i:=B_1+\dots+B_{i-1}. \end{equation*} It is assumed that the $B_i$'s are iid and the $D_i$'s are independent of $B_i$'s.

Take any real $c>0$. For real $t\ge0$, we have \begin{equation*} \begin{aligned} ct-S(t)&=c\sum_{i=1}^\infty (t-S_i)\,1(S_i\le t<S_i+B_i) \\ &=c\sum_{i=1}^\infty (u-U_i)\,1(U_i\le u<U_i+B_i) \\ &=cZ_u, \end{aligned} \tag{1} \end{equation*} where \begin{equation*} u:=t-R_i, \end{equation*} \begin{equation*} Z_u:=u-U_{N(u)}, \end{equation*} and \begin{equation*} N(u):=\max\{i\ge1\colon U_i\le u)\}, \end{equation*} so that $Z_u$ is the backward recurrence time for the jump times $U_i$.

We want to upper-bound \begin{equation} Ee^{\theta(ct-S(t))}=Ee^{hZ_u}, \tag{*} \end{equation} where $h:=\theta c>0$.

The distribution of the backward recurrence time is well known; see e.g. Theorem 6.13 in Stochastic Processes by J. Medhi, 3rd ed.; notice the typos there, though: one has to replace there conditions $x\le t$ and $x>t$ by $x<t$ and $x\ge t$, respectively. Recall also that the $D_i$'s are independent of $B_i$'s. So, given $u=t-R_i$, the distribution of $Z_u$ does not depend on the $D_i$'s. So, by the mentioned Theorem 6.13, for real $x\ge0$, \begin{equation*} P(Z_u>x)=\Big(\bar F(u)+\int_0^{u-x}\bar F(t-y)\,dM(y)\Big)1(x<u), \tag{2} \end{equation*} where $\bar F:=1-F$, $F$ is the cdf of $B_1$, and $M$ is the renewal function given by \begin{equation*} M(y):=EN(y)=\sum_{i=1}^\infty P(U_i\le y). \tag{3} \end{equation*}

For any real $h$ and any nonnegative random variable $Y$, \begin{equation*} \begin{aligned} Ee^{hY}&=1+E\int_0^Y he^{hx}\,dx \\ &=1+E\int_0^\infty he^{hx}1(x<Y)\,dx \\ &=1+\int_0^\infty he^{hx}P(Y>x)\,dx. \end{aligned} \tag{4} \end{equation*}

So, by (2), \begin{equation*} \begin{aligned} Ee^{hZ_u}&=1+\int_0^u dx\, he^{hx}\Big(\bar F(u)+\int_0^{u-x}\bar F(u-y)\,dM(y)\Big) \\ &=(e^{hu}-1)\bar F(u)+\int_0^u dM(y)\,\bar F(u-y)\,\int_0^{u-y} dx\, he^{hx} \\ &=(e^{hu}-1)\bar F(u)+\int_0^u dM(y)\,\bar F(u-y)\,(e^{h(u-y)}-1). \end{aligned} \tag{5} \end{equation*} Therefore and by Smith's theorem (Theorem 6.9 in the mentioned book by Medhi), with \begin{equation*} \mu:=EB_1\in(0,\infty), \end{equation*} we have \begin{equation*} \begin{aligned} Ee^{hZ_u}&\ge\int_0^u dM(y)\,\bar F(u-y)\,(e^{h(u-y)}-1) \\ &\underset{u\to\infty}\longrightarrow\frac1\mu\,\int_0^\infty dy\,\bar F(y)\,(e^{hy}-1) \\ &=-1+\frac1{h\mu}\,E(e^{hB_1}-1); \end{aligned} \tag{6} \end{equation*} the latter equality holds by (4). So, if the expectation in (*) has a finite upper bound not depending on $u$, then we must have $Ee^{hB_1}<\infty$.

Vice versa, assuming that, say, \begin{equation*} C:=Ee^{2hB_1}<\infty, \tag{7} \end{equation*} we can get a finite upper bound not depending on $u$ on the expectation in (*). (The factor $2$ here can be replaced by any real number $>1$.)

Indeed, (7) implies $\bar F(t)\le Ce^{-2ht}$ for all real $t$. So, recalling (5) and then integrating by parts, we get \begin{equation*} \begin{aligned} Ee^{hZ_u}&\le C+C\int_0^u dM(y)\,(e^{-h(u-y)}-e^{-2h(u-y)}) \\ &=C+C\int_0^u dy\,M(y)\,(-e^{-h(u-y)}+2e^{-2h(u-y)}). \end{aligned} \tag{8} \end{equation*}

Next, by the last equality in (6.2) and Proposition 6.2 (Lorden's inequality) in Applied Probability and Queues by Asmussen, Second Ed., for all real $y>0$, \begin{equation*} \Big|M(y)-\frac y\mu\Big|\le\frac{EB_1^2}{\mu^2}. \tag{9} \end{equation*} So, by (8), \begin{equation*} \begin{aligned} Ee^{hZ_u}&\le C+C\int_0^u dy\,\frac y\mu\,(-e^{-h(u-y)}+2e^{-2h(u-y)}) \\ &+C\frac{EB_1^2}{\mu^2}\,\int_0^u dy\,|-e^{-h(u-y)}+2e^{-2h(u-y)}|. \end{aligned} \tag{10} \end{equation*} Next, \begin{equation*} \int_0^u dy\,\frac y\mu\,(-e^{-h(u-y)}+2e^{-2h(u-y)}) =\frac{\left(1-e^{-h u}\right)^2}{2 h^2 \mu }\le\frac1{2 h^2 \mu } \end{equation*} and \begin{equation*} \begin{aligned} &\int_0^u dy\,|-e^{-h(u-y)}+2e^{-2h(u-y)}| \\ &=\int_0^u dv\,|-e^{-hv}+2e^{-2hv}| \\ &\le\int_0^\infty dv\,|-e^{-hv}+2e^{-2hv}|=\frac1{2h}. \end{aligned} \end{equation*} Thus, by (*) and (7), for all real $t\ge0$, \begin{equation*} Ee^{\theta(ct-S(t))}=Ee^{hZ_u} \le Ee^{2hB_1}\Big(1+\frac1{2 h^2 \mu}+\frac{EB_1^2}{2h\mu^2}\Big), \end{equation*} where $h:=\theta c>0$.

  • $\begingroup$ Thanks for this inspiring answer! As the bound depends on $B_1$'s MGF, i.e., $Ee^{2hB_1}$, may I know what if $B_1$'s MGF is not known? Is it possible to approximate it (say, using moments)? $\endgroup$
    – leeyee
    Dec 22, 2021 at 12:55
  • $\begingroup$ @leeyee : As (6) shows, for the mgf of the backward recurrence time $Z_u$ to be bounded in a neighborhood of $0$, we need the mgf of $B_1$ to be finite (and hence bounded) in a neighborhood of $0$. On the other hand, by (say) expanding the mgf of any positive random variable $X$ in terms of the moments of $X$, it is clear that no information whatsoever about any finite number of moments of $X$ can guarantee that the mgf of $X$ be finite in a neighborhood of $0$. $\endgroup$ Dec 22, 2021 at 13:09
  • $\begingroup$ Previous comment continued: So, no, no information whatsoever about any finite number of moments of $B_1$ can guarantee even the finiteness (let alone the boundedness) of the mgf of the backward recurrence time $Z_u$ in any neighborhood of $0$. E.g., if $B_1$ has a log-normal distribution (en.wikipedia.org/wiki/Log-normal_distribution), then all the moments of $B_1$ are finite, whereas the mgf of $B_1$ is infinite in any right neighborhhod of $0$, and hence the only upper bound here on the mgf of the backward recurrence time $Z_u$ in any right neighborhhod of $0$ is $\infty$. $\endgroup$ Dec 22, 2021 at 13:18

You must log in to answer this question.

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