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 $\mathrm{E}[B]$ and $\mathrm{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}{\mathrm{E}[B]}$.

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

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

For some background, if think of $S(t)$ as the service process of a server, this kind of envelop (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.

Then we have $\mathrm{E}[e^{-\theta S(t)}]=e^{-\theta c t}\mathrm{E}[e^{\theta B(t)}]$. The question then reduces to find a function $\sigma(\theta)$ to bound $\mathrm{E}[e^{\theta B(t)}]$ as $\mathrm{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 $$\mathrm{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\mathrm{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:

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

This results in $\sigma(\theta)=\mathrm{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?