Determine the affine envelope of a random process's MGF 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?
 A: 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$.
A: $\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*}
