2. THE MODEL

We consider a storage system, or fluid queue, which can be modeled as a piecewise deterministic Markov process

with state space [0,∞) × {0,1}. When in state (x,1), the process decreases at rate r₁(x) or switches to state (x,0) with rate λ₁(x). When in state (x,0), the process increases at rate r₀(x) or switches to state (x,1) with rate λ₀(x). We assume that r₁(x) and λ₁(x) are left-continuous and that r₀(x) and λ₀(x) are right-continuous. To avoid an infinite number of switches, we assume that both λ₀(·) and λ₁(·) are bounded. We further assume that r₀(x) > 0 for all x ≥ 0 and that r₁(x) > 0 for all x > 0 and r₁(0) = 0 and that λ₁(0) > 0 (so that the process does not get stuck in state (0,1) forever). With these assumptions, the extended generator of this process can be written as follows:

for differentiable f (x,i), where f′(x,i) is the derivative with respect to x. For background regarding piecewise deterministic Markov processes, the reader is referred to [5].

3. THE STATIONARY DISTRIBUTION

In this section, we will compute the unique stationary distribution for the Markov process

. To this end, we notice that the process sampled at exponential times is Feller; that is, x → U¹f (x,j), where U¹ is the transition function of the process sampled at exp(1) distributed times (independent of our process), is continuous in x for all f (x,j) that are continuous in x. When all states communicate, which will be the case under some natural conditions that are discussed in Section 4,

is an irreducible T-chain and the existence of a finite invariant measure for it will make it automatically Harris recurrent [12]. Furthermore, the equation

implies that a measure μ that satisfies

is invariant for U¹, and by the results of [3], it is also invariant for the original process. If the measure μ is finite,

is immediately positive Harris recurrent. With that in mind, we are now set to compute an invariant distribution for

. Let us assume that a stationary distribution π exists and is of the form

where g_i(·) are densities (integrate to 1) and c₀ + c₁ + p = 1. In particular, for every Borel set A and with 1_A(0) denoting the indicator function of the event {0 ∈ A}, the stationary distribution π is given by

Theorem 1: Assume that a stationary distribution π exists and is of the form (2).

(i) If

is finite for some ε > 0, then

where

, and

Proof: From the form of the generator, we have that

Taking f (x,1) ≡ f (x,0), we obtain

Since (11) should hold for all differentiable functions f (·,0) for which the integrals are well defined, this yields the expected level crossings identity (rate up = rate down):

Taking either f (x,0) ≡ 0 and f (x,1) ≡ 1, or f (x,0) ≡ 1 and f (x,1) ≡ 0 gives

which is also expected, as it implies that the stationary rate at which the second coordinate of the process moves from state 0 to state 1 is equal to the rate at which it moves from state 1 to state 0. This is also a type of level crossings identity.

We now substitute (13) in (10) to obtain

With

and a change of the order of integration, (14) becomes

Since (15) should hold for all differentiable functions for which the integrals are well defined, we obtain that necessarily

as well as

Due to (12), the last two equations are identical.

Let D_i(x) be such that D_i′(x) = λ_i(x)/r_i(x). Then, with h(x) = c₀ r₀(x)g₀(x) = c₁ r₁(x)g₁(x), we have that

and, thus,

This implies that

Since the g_i(x) are densities, (4) follows. It remains to compute the constants c₀, c₁, and p. First, recall that c₀ + c₁ + p = 1. Second, (12) implies that c₁ /c₀ = α₁ /α₀. Finally, letting x → 0 in (16) and using (13), one obtains that pλ₁(0) = c₀ r₀(0)g₀(0). If D₀(x) − D₁(x) → ∞ as x → 0 or λ₁(0) = ∞, then necessarily p = 0. Otherwise, (4) with x = 0 yields

The theorem follows. █

Remark 1: Several special cases of this result are contained in the literature; for example, (i) the case λ_i(x) ≡ λ_i, μ_i(x) ≡ μ_i gives a classical two-state fluid queue with exponential buffer content densities g₀(·) and g₁(·) and (ii) if λ₀(x) and r₀(x) go to infinity with λ₀(x)/r₀(x) ≡ μ, one obtains an M/M/1 queue with exp(μ) service time distribution and with state-dependent service rate r₁(x) and state-dependent arrival rate λ₁(x). The stationary workload distribution of that model has already been derived in [4, Sect.4].

Remark 2: It should be noted that g_i(x)r_i(x) depends on λ_j(x) and r_j(x), j = 0,1, only via their ratio. Similar observations for related models have been made in [4] and have been explained there via a rescaling of time.

It is evident that a necessary condition for the results of the theorem to be valid is that α₀ and α₁ are both finite. In the next section, we study the conditions for the existence of a stationary distribution of

in detail.

4. CONDITIONS FOR IRREDUCIBILITY

Since we showed that whenever λ₁(0) > 0, α₀ < ∞, and α₁ < ∞, there is a stationary distribution, in order to show that it is unique, it suffices to prove that the process

is irreducible and nonexplosive. This will also imply that the process is positive Harris recurrent. We will show that the following set of conditions implies that

is indeed irreducible and nonexplosive:

Remark 3: Note that Conditions 1 and 4 together imply that

for any given x.

Condition 1 states that α₀ < ∞ and α₁ < ∞. Note that the lower limit of the integral in the exponent is 1 and not 0. This is not a mistake, since we want to allow for the case where D₀(x) − D₁(x) → ∞ as x → 0. When

, as usual.

Next, assume that given we are in state 0 (1), the time to get from x to y (y to x), where 0 < x < y < ∞, is finite. The condition for this is Condition 2. Two types of explosion may be possible in such a process. One is where the content reaches ∞ in a finite time and the other is where there may be an infinite number of switches between 0 and 1 in a finite time. To prevent the first, it suffices to assume that the first part of Condition 4 holds. In order to prevent the second, we have assumed that λ_i(·) are bounded. To make sure that all states are reachable, it suffices to assume that starting from any state (x,0) ((x,1)), the time until a switch is made is greater than the time to reach any level y > x (y < x) and is a.s. finite. Starting from (x,0), the time to reach y > x (provided there is no switch) is

. Denoting T to be the switching time and w_x,0(t) the unique solution of

, we have that

Therefore, it is immediate that in order for P_x,0 [T > θ(x,y)] to be positive for every finite y > x, we need to assume that Condition 3 holds for i = 0. Since the first part of Condition 4 implies that θ(x,y) → ∞ as y → ∞, the second part assures us that T is a.s. finite.

Similar reasoning applies to the switching time from 1 to 0, with the possible exception when state (0,1) is not reachable, in which case it can be removed from the state space in order to maintain irreducibility. This happens when

. In the latter case, the condition that the switching time is a.s. finite is the necessary condition in Condition 5.

5. EXPECTED EXCURSION TIMES

In this section, we compute the expected time ER(y) that it takes for the buffer content to return to a given level y after an instant where it crossed it from below.

Theorem 2:

where

If the conditions for p > 0 are satisfied, then it also holds for y = 0.

Proof: For y = 0, when p > 0, if μ_C is the expected regenerative epoch (cycle time), then it is clear that

where p is given by (6). So, μ_C = α₀ + α₁ + [1/λ₁(0)] . Hence, the expected return time to zero must be α₀ + α₁, which, indeed, equals α₀(0) + α₁(0). By reflecting the process at some positive level y instead of zero (i.e., by setting r₁(y) = 0 and starting the process at (y,0)), the result for any y > 0 is easily concluded. █

The following intuitive argument also leads to the same formula for μ_C. The fraction of time that the buffer content spends just above level 0 in a given cycle can be thought of as the density at zero c₀ g₀(0+) + c₁ g₁(0+). During a single cycle, the buffer content spends the infinitesimal time [1/r₀(0+)] + [1/r₁(0+)] just above level 0. Therefore,

Applying Theorem 1, we see that this is consistent with μ_C = α₀ + α₁ + [1/λ₁(0)].

6. THE PROCESS RESTRICTED TO DOWN OR UP INTERVALS

The process restricted to down intervals (the off state) decreases at a rate r₁(x) when at level x > 0 and has jumps up, which are state dependent. Standard regenerative arguments imply that for the case p > 0, the stationary distribution function of this restricted content process is given by

When λ₁(x) = λ, r₁(x) = 1 for x > 0, λ₀(x)/r₀(x) = μ for x ≥ 0, and λ < μ, it is easy to check that 1 − F(w) = (λ/μ)e^{−(μ−λ)w}. For this case, the restricted process is the workload process of an M/M/1 queue for which this formula is well known.

As for the process restricted to the up intervals (the on state), the stationary distribution of the content level has the density g₀(·).

7. THE STATIONARY DISTRIBUTION OF PEAKS AND VALLEYS

In this section, we want to compute the distribution of local minima and maxima of

. Each forms a discrete-time Markov process. We call the local maxima peaks and the local minima valleys. Beginning with valleys and assuming that p > 0, Theorem 5.1 and the resulting Eq. (20) of [4] cover the model considered here, when we restrict

to down intervals. Therefore, if we denote by V_D a random variable that has the stationary distribution of the process restricted to down intervals and by W_D the stationary distribution of the discrete-time process of valleys (which in the restricted process are the states right before jumps up), then for a given bounded Borel measurable function f,

Since, by (24), for a given bounded Borel measurable function h, we have that

it follows that for a given bounded f,

Taking f (u) = 1_[0,x](u), this implies that the stationary distribution function of the valleys is given by

When p = 0, W_D has density

Similarly, it can be shown by identical methods that if W_U denotes a random variable having the stationary distribution of the discrete-time peak process, then it has the following density:

Remark 4: Equations (28)–(30) show that the densities of valleys and peaks are proportional to λ₀(x)g₀(x) and λ₁(x)g₁(x), respectively. A similar result, which may be viewed as a PASTA generalization, was derived in [4] for an M/G/1 queue with state-dependent arrival rate and service speed. It should also be noted that (cf. Remark 2), the densities of valleys and peaks depend on λ_j(x) and r_j(x), j = 0,1, only via their ratio.

8. EXPONENTIAL ERGODICITY

In this section, we impose the following restrictions on the process parameters, which will ensure that the convergence to the stationary distribution π is at some exponential rate (i.e., that

is f-exponentially ergodic for some function f > 1):

We will show that under those conditions, the process

is f-exponentially ergodic as defined in [13], with f = V + 1 (V defined below):

We do this by verifying that

for some k₁ > 0 and k₂ < ∞, thus verifying Condition (CD3) of [13]. The verification for

is easy:

Now, consider

. With

for x ≥ 1, we have

It is easy to see that for x < 1,

is bounded as a product of a continuous function and a bounded function λ₁(x). For x ≥ 1,

Using the Taylor expansion

it follows that

But by Condition A1 and Condition 4, for x ≥ x₀,

As for the second term in the expression for

, we use the inequality x² ≤ 2Δ⁻²e^Δx with Δ = c*/2 and c < Δ to show that

and according to Condition A2,

It thus follows that with c as above and x > 1,

We now choose c < εΔ²/2B and for x ≥ x₀, we obtain

and it is bounded for x < x₀. It follows that the functions V(x,i),i = 0,1, satisfy condition (CD3) of [13] and, thus, Theorem 6.1 of [13] implies that

is exponentially ergodic.