A spectral theory approach for extreme value analysis in a tandem of fluid queues

Abstract

We consider a model to evaluate performance of streaming media over an unreliable network. Our model consists of a tandem of two fluid queues. The first fluid queue is a Markov modulated fluid queue that models the network congestion, and the second queue represents the play-out buffer. For this model the distribution of the total amount of fluid in the congestion and play-out buffer corresponds to the distribution of the maximum attained level of the first buffer. We show that, under proper scaling and when we let time go to infinity, the distribution of the total amount of fluid converges to a Gumbel extreme value distribution. From this result, we derive a simple closed-form expression for the initial play-out buffer level that provides a probabilistic guarantee for undisturbed play-out.

Appendix 1: Proof of Lemma 2

1.1 a: Preliminaries

Definition 8

Let $A$ be a $n\times m$ matrix:

$$\begin{aligned} A=\begin{pmatrix} a_{1,1}&{}\quad a_{1,2}&{}\quad \cdots &{}\quad a_{1,m}\\ a_{2,1}&{}\quad a_{2,2}&{}\quad \cdots &{}\quad a_{2,m}\\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ a_{n,1}&{}\quad a_{n,2}&{}\quad \cdots &{}\quad a_{n,m}\\ \end{pmatrix}. \end{aligned}$$

Then any order-$p$ minor of $A$ will be denoted as:

$$\begin{aligned} A\begin{pmatrix} i_{1}&{}\quad i_{2}&{}\quad \cdots &{}\quad i_{p}\\ k_{1}&{}\quad k_{2}&{}\quad \cdots &{}\quad k_{p}\\ \end{pmatrix} := \det \left[ \begin{pmatrix} a_{i_{1},k_{1}}&{}a_{i_{1},k_{2}}&{}\cdots &{}a_{i_{1},k_{p}}\\ a_{i_{2},k_{1}}&{}a_{i_{2},k_{2}}&{}\cdots &{}a_{i_{2},k_{p}}\\ \vdots &{}\vdots &{}\ddots &{}\vdots \\ a_{i_{p},k_{p}}&{}a_{i_{p},k_{2}}&{}\cdots &{}a_{i_{p},k_{p}}\\ \end{pmatrix} \right] , \end{aligned}$$

provided that

$$\begin{aligned}&1\le i_{1}<i_{2}<\cdots <i_{p}\le m,\\&1\le k_{1}<k_{2}<\cdots <k_{p}\le n,\\&p\le m,n. \end{aligned}$$

The Binet–Cauchy formula on minors (see Gantmacher [12], page 12):

Let $A$ be an $m\times n$ matrix, $B$ be a $n\times q$ matrix and $C$ be an $m\times q$ matrix and $C=AB$. Then any minor of $C$ of order $p$ is the sum of the products of all possible minors of $A$ with order p and corresponding minors of the same order of $B$:

$$\begin{aligned} C\begin{pmatrix} i_{1}&{}i_{2}&{}\cdots &{}i_{p}\\ j_{1}&{}j_{2}&{}\cdots &{}j_{p} \end{pmatrix} =\sum \limits _{1\le k_{1}<k_{2}<\cdots <k_{m}\le n} A\begin{pmatrix} i_{1}&{}i_{2}&{}\cdots &{}i_{p}\\ k_{1}&{}k_{2}&{}\cdots &{}k_{p} \end{pmatrix} B\begin{pmatrix} k_{1}&{}k_{2}&{}\cdots &{}k_{p}\\ j_{1}&{}j_{2}&{}\cdots &{}j_{p} \end{pmatrix}. \end{aligned}$$

Lemma 9

Let $A$ be a $n\times n$ matrix:

$$\begin{aligned} A=\sum \limits _{k=1}^{m}A_{k} \end{aligned}$$

with:

$$\begin{aligned} A_{k}= \begin{bmatrix} a_{k,1,1}&\cdots&a_{k,1,n}\\ \vdots&\ddots&\vdots \\ a_{k,n,1}&\cdots&a_{k,n,n} \end{bmatrix}. \end{aligned}$$

Define $\mathbf{A}$ as a $n\times mn$ matrix with:

$$\begin{aligned} \mathbf{A}= \begin{bmatrix}A_{1}&A_{2}&\cdots&A_{k}\end{bmatrix}, \end{aligned}$$

and $\mathbf{I}$ is a $mn\times n$ matrix (consisting of $m$ $n\times n$ identity matrices $I_{n}$) defined by:

$$\begin{aligned} \mathbf{I}= {\begin{bmatrix}I_{n}&I_{n}&\cdots&I_{n}\end{bmatrix}}^\mathrm{T}. \end{aligned}$$

Let $\mathcal {V}$ be the set of subsets with exactly $n-1$ elements from the set $\{1,2,\ldots ,mn\}$ which is defined by:

$$\begin{aligned} \mathcal {V}=\{(k_{1},k_{2},\ldots ,k_{n-1}):1\le k_{1}<k_{2}<\cdots <k_{n-1}\le mn\}. \end{aligned}$$

Then the following holds:

$$\begin{aligned} {{\mathrm{{adj}}}}(A)=\sum \limits _{v\in \mathcal {V}}{{\mathrm{{adj}}}}\Big (F_{C}(\mathbf{A},v)F_{R}(\mathbf{I},v)\Big ), \end{aligned}$$

with operators:

$$\begin{aligned} F_{C}(\mathbf{A},v)=\begin{bmatrix} \mathbf{a}_{1,v_{1}}&\cdots&\mathbf{a}_{1,v_{n-1}}\\ \vdots&\ddots&\vdots \\ \mathbf{a}_{n,v_{1}}&\cdots&\mathbf{a}_{n,v_{n-1}} \end{bmatrix}, \end{aligned}$$

$$\begin{aligned} F_{R}(\mathbf{I},v)=\begin{bmatrix} \mathbf{i}_{v_{1},1}&\cdots&\mathbf{i}_{v_{1},n}\\ \vdots&\ddots&\vdots \\ \mathbf{i}_{v_{n-1},1}&\cdots&\mathbf{i}_{v_{n-1},n} \end{bmatrix}, \end{aligned}$$

Operator $F_{C}(\mathbf{A},v)$ selects the columns from $\mathbf{A}$ according to vector $v$, while operator $F_{R}(\mathbf{I},v)$ selects rows from $\mathbf{I}$ according to vector $v$.

Proof

We write $\sum \limits _{k=1}^{m}A_{k}=\mathbf{A}\mathbf{I}=\begin{bmatrix}A_{1}&A_{2}&\cdots&A_{k}\end{bmatrix}{\begin{bmatrix}I_{n}&I_{n}&\cdots&I_{n}\end{bmatrix}}^\mathrm{T}$. Using the Binet–Cauchy formula on minors, this can be rewritten to:

$$\begin{aligned} {{\mathrm{{adj}}}}\left[ A \right] = {{\mathrm{{adj}}}}\left[ \mathbf AI \right]&= \begin{pmatrix} \sum \limits _{v\in \mathcal {V}}\overline{\mathbf{a }}_{1,1}(v) &{}\quad \sum \limits _{v\in \mathcal {V}}\overline{\mathbf{a }}_{1,2}(v) &{}\quad \cdots &{}\quad \sum \limits _{v\in \mathcal {V}}\overline{\mathbf{a }}_{1,n}(v)\\ \sum \limits _{v\in \mathcal {V}}\overline{\mathbf{a }}_{2,1}(v) &{}\quad \sum \limits _{v\in \mathcal {V}}\overline{\mathbf{a }}_{2,2}(v) &{}\quad \cdots &{}\quad \sum \limits _{v\in \mathcal {V}}\overline{\mathbf{a }}_{2,n}(v)\\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ \sum \limits _{v\in \mathcal {V}}\overline{\mathbf{a }}_{n,1}(v) &{}\quad \sum \limits _{v\in \mathcal {V}}\overline{\mathbf{a }}_{n,2}(v) &{}\quad \cdots &{}\quad \sum \limits _{v\in \mathcal {V}}\overline{\mathbf{a }}_{n,n}(v) \end{pmatrix}\\&= \sum \limits _{v\in \mathcal {V}}\begin{pmatrix} \overline{\mathbf{a }}_{1,1}(v) &{}\quad \overline{\mathbf{a }}_{1,2}(v) &{}\quad \cdots &{}\quad \overline{\mathbf{a }}_{1,n}(v)\\ \overline{\mathbf{a }}_{2,1}(v) &{}\quad \overline{\mathbf{a }}_{2,2}(v) &{}\quad \cdots &{}\quad \overline{\mathbf{a }}_{2,n}(v)\\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ \overline{\mathbf{a }}_{n,1}(v) &{}\quad \overline{\mathbf{a }}_{n,2}(v) &{}\quad \cdots &{}\quad \overline{\mathbf{a }}_{n,n}(v) \end{pmatrix}\\&=\sum \limits _{v\in \mathcal {V}}{{\mathrm{{adj}}}}\Big (F_{C}(\mathbf{A},v)F_{R}(\mathbf{I},v)\Big ), \end{aligned}$$

with:

$$\begin{aligned} \overline{\mathbf{a }}_{i,j}(v)=\mathbf{A} \begin{pmatrix} 1&{}\cdots &{}i-1&{}i+1&{}\cdots &{}n\\ v_{1}&{}\cdots &{}v_{i-1}&{}v_{i}&{}\cdots &{}v_{n-1} \end{pmatrix} \mathbf{I} \begin{pmatrix} v_{1}&{}\cdots &{}v_{j-1}&{}v_{j}&{}\cdots &{}v_{n-1}\\ 1&{}\cdots &{}j-1&{}j+1&{}\cdots &{}n. \end{pmatrix}. \end{aligned}$$

$\square$

1.2 b: Proof of Lemma 2

Proof

Let $\mathcal {V}$ be the set of subsets with exactly $n-1$ elements from the set $\{1,2,\ldots ,mn\}$ which is defined by:

$$\begin{aligned} \mathcal {V}=\{(k_{1},k_{2},\ldots ,k_{n-1}):1\le k_{1}<k_{2}<\cdots <k_{n-1}\le mn\}. \end{aligned}$$

We define $\mathcal {P}$ as the set containing all k-permutations of $n-1$ elements from the set $\{1,\ldots ,n\}$. Furthermore we define $\mathcal {C}$ as the set with all combinations of $n-1$ elements from the set $\{1,\ldots ,m\}$. For each combination $c\in \mathcal {C}$ we define:

$$\begin{aligned} \mathbf{A}_{c}&= \begin{bmatrix}A_{c_{1}}A_{c_{2}}\cdots&A_{c_{n-1}}\end{bmatrix},\\ \mathbf{I}_{c}&= {\begin{bmatrix}I_{n} I_{n} \cdots I_{n}\end{bmatrix}}^\mathrm{T}, \end{aligned}$$

and thus:

$$\begin{aligned} \mathbf {A}_{c}\mathbf {I}_{c}=\sum \limits _{k\in c}A_{k}. \end{aligned}$$

Next we apply Lemma 9:

$$\begin{aligned} {{\mathrm{{adj}}}}[A]&=\sum \limits _{v\in \mathcal {V}}\left( \prod \limits _{k\in v}b_{\lceil k / n \rceil }\right) {{\mathrm{{adj}}}}\Big (F_{C}(\mathbf{A},v)F_{R}(\mathbf{I},v)\Big ), \end{aligned}$$

with

$$\begin{aligned} \mathbf{A}= \begin{bmatrix}A_{1}&A_{2}&\cdots&A_{k}\end{bmatrix}, \end{aligned}$$

and

$$\begin{aligned} \mathbf{I}= {\begin{bmatrix}I_{n}&I_{n}&\cdots&I_{n}\end{bmatrix}}^\mathrm{T}. \end{aligned}$$

Because all matrices $A_{k}$ have rank 1 the only adjugates that remain are those where there are $n-1$ columns, at $n-1$ different positions, from $n-1$ different $A_{k}$ matrices. All other combinations of columns result in a matrix with rank $<n-1$ for which the minors of order $n-1$ are zero. Thus the only elements from $\mathcal {V}$ that contribute are those that correspond to any k-permutation of $n-1$ columns from the set $\{1,\ldots n\}$ where each column is selected from a distinct matrix $A_{k},~k=1,\ldots ,m$. Note that each selected column remains exactly on its originating column position in the $A_{k}$ matrix. As the only combinations consisting of $n-1$ columns at unique positions from $n-1$ unique matrices contribute to non-zero minors it holds that:

$$\begin{aligned}&\sum \limits _{v\in \mathcal {V}}\left( \prod \limits _{k\in v}b_{\lceil k / n \rceil }\right) {{\mathrm{{adj}}}}\Big (F_{C}(\mathbf{A},v)F_{R}(\mathbf{I},v)\Big )\\ =&\sum \limits _{c\in \mathcal {C}}\sum \limits _{p\in \mathcal {P}}\left( \prod \limits _{k\in c}b_{k}\right) {{\mathrm{{adj}}}}\Big (F_{C}(\mathbf{A}_{c},v_{p})F_{R}(\mathbf{I}_{p},v_{p})\Big ), \end{aligned}$$

where $v_{p}$ is the vector that selects the $p_{i}$th column from matrix $A_{c_{i}}$:

$$\begin{aligned}&(v_{p})_{i}:=n(i-1)+p_{i}, \quad i\in \{1,\ldots ,n-1\},~p\in \mathcal {P}. \end{aligned}$$

We now define $\mathcal {V}_{c}$ as be the set of subsets with exactly $n-1$ elements from the set $\{1,2,\ldots ,n(n-1)\}$ which is defined by:

$$\begin{aligned} \mathcal {V}_{c}=\{(k_{1},k_{2},\ldots ,k_{n-1}):1\le k_{1}<k_{2}<\cdots <k_{n-1}\le n(n-1)\}. \end{aligned}$$

For each combination $c\in \mathcal {C}$ we can do the opposite: add again the terms (corresponding to zero valued minors) from the set $\mathcal {V}_{c}$ corresponding to columns of $\mathbf{A}_{c}=\begin{bmatrix}A_{c_{1}}&\cdots&A_{c_{n-1}}\end{bmatrix}$:

$$\begin{aligned}&\sum \limits _{c\in \mathcal {C}}\sum \limits _{p\in \mathcal {P}}\left( \prod \limits _{k\in c}b_{k}\right) {{\mathrm{{adj}}}}\Big (F_{C}(\mathbf{A}_{c},v_{p})F_{R}(\mathbf{I}_{p},v_{p})\Big ),\\&=\sum \limits _{c\in \mathcal {C}}\left( \prod \limits _{k\in c}b_{k}\right) \sum \limits _{v\in \mathcal {V}_{c}}{{\mathrm{{adj}}}}\Big (F_{C}(\mathbf{A}_{c},v)F_{R}(\mathbf{I}_{c},v)\Big ),\\&=\sum \limits _{c\in \mathcal {C}}\left( \prod \limits _{k\in c}b_{k}\right) {{\mathrm{{adj}}}}\left[ \sum \limits _{k\in c}A_{k}\right] . \end{aligned}$$

$\square$