Determine the affine envelope of a random process's MGF

Question

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.

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

Answer 1

$\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*}

Answer 2

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