= Solution
Measure $Q_t$ immediately after service in slot $(t-1,t)$, and let $a_t\geq0$ denote work eligible for that slot's service. Writing $x^+=\max(x,0)$, the <Lindley recursion> is
$$
\boxed{Q_t=(Q_{t-1}+a_t-c)^+.}
$$
Start with an empty <queue> at time $-N$. Repeated substitution gives its time-zero <queue workload>
$$
Q_0^{(N)}(a,c)=\max_{0\leq n\leq N}\left\{\sum_{j=0}^{n-1}a_{-j}-cn\right\},
$$
where the empty sum is zero. The increasing limit defines the minimal causal <queue workload>:
$$
\boxed{Q_0(a,c)=\sup_{n\geq0}\{A_n(a)-cn\},\qquad A_n(a)=\sum_{j=0}^{n-1}a_{-j},\quad A_0=0.}
$$
If the mean of the remote past is $\lambda<c$, then $A_n(a)/n\to\lambda$, so $A_n(a)-cn\to-\infty$. The <supremum> is then finite and is attained at a finite window. The same formula with indices shifted gives $Q_t(a,c)$ and satisfies the <Lindley recursion> directly: split the supremum into the zero-window term and all positive-window terms.
Back to article page
