2. Main results and discussion

2.2. Ergodicity is a critical phenomenon for the Data Collection Process

For a given Data Collection Process on a network modeled by an undirected graph $G=(V,E,w)$ , there is an associated $(\lvert V \rvert - 1)$ -dimensional vector $Q^{\boldsymbol{{J}},\beta}_t$ , where each $Q^{\boldsymbol{{J}},\beta}_t(u)$ represents the queue size at a given node $u \in V\setminus \{u_{{\scriptsize s}}\}$ given a data rate $\beta$ . Since the Data Collection Process is a queueing system, the question of stability arises; i.e., we need to understand whether the system is able to successfully transfer data at a given value of $\beta$ , which is the controlling parameter for the rate at which packets appear in the system. For this, following Loynes [Reference Loynes22] and Szpankowski [Reference Szpankowski31], we formally define the notion of a stable data rate as follows.

Definition 1. (Stable rate.) Given a weighted undirected graph $G = (V,E,w)$ and a relative rate vector $\boldsymbol{{J}}$ with $\boldsymbol{{J}}(v) \lt 0$ for exactly one $v \in V$ , the process $Q^{\boldsymbol{{J}}, \beta}_t$ is said to be stable, and a value $\beta \geq 0$ of the rate parameter is said to be a stable rate, if

(1) \begin{equation}\lim_{t \rightarrow \infty} \mathbb{P}\left[ {\Big|\Big| Q^{\boldsymbol{{J}}, \beta}_t \Big|\Big|_{\infty} <x} \right] = F(x) \quad \mbox{ and } \quad \lim_{x \rightarrow \infty} F(x) = 1,\end{equation}

where F(x) is the limiting distribution function.

However, if a weaker condition holds, i.e.,

(2) \begin{equation}\lim_{x \rightarrow \infty}\liminf_{t \rightarrow \infty} \mathbb{P}\left[ {\Big|\Big| Q^{\boldsymbol{{J}}, \beta}_t \Big|\Big|_{\infty} <x} \right] = 1,\end{equation}

then the process is said to be substable, and otherwise it is unstable. So, a stable process is necessarily substable, and for a substable process to be stable, its distribution function should tend to a limit.

Thus, for the Data Collection Process, by stability we mean the distribution of $Q^{\boldsymbol{{J}}, \beta}_t$ as $t\rightarrow\infty$ exists. In particular, we show that the given process has two distinct regimes, one ergodic and one non-ergodic, as we vary $\beta$ , and there is a sharp transition between them. We find that there is a nontrivial $\beta^* > 0$ such that the chain $\left\{Q^{\boldsymbol{{J}},\beta}_t \right\}_{t\geq 0}$ is ergodic for $\beta$ below this value and converges to a stationary distribution. Above $\beta^*$ the queue sizes grow unboundedly as $t \rightarrow \infty$ . Specifically we prove the following theorem.

Theorem 1. Consider a weighted undirected graph $G = (V,E,w)$ and a relative rate vector $\boldsymbol{{J}}$ with $\boldsymbol{{J}}(v) \lt 0$ for exactly one $v \in V$ . If the random walk on G with transition matrix $P_w$ , where $P_w[ {u,v} ] = w_{uv}/\mbox{deg}({u})$ , is irreducible and aperiodic, then there exists a $\beta^*>0$ such that the resulting multidimensional Markov chain $\left\{Q^{\boldsymbol{{J}},\beta}_t \right\}_{t\geq 0}$ is ergodic for all $\beta \lt \beta^*$ and non-ergodic for all $\beta\geq\beta^*$ .

There are multiple ways of proving this theorem. In Section 3 we prove it using the induction-based technique developed by Georgiadis and Szpankowski [Reference Georgiadis and Szpankowski7], and later summarized by Szpankowski in his study of slotted ALOHA [Reference Szpankowski31]. This technique gives nice insights into the workings of the Data Collection Process.

2.3. A lower bound on the critical rate

When $\beta \lt \beta^*$ the Data Collection Process is ergodic and has a stationary distribution, so we can define ${\boldsymbol{\eta}}^{\beta}(v) = \lim_{t \rightarrow \infty} \mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta}_t(v) > 0} \right]$ for all $v \in V \setminus \{u_{{\scriptsize s}}\}$ . We will show in Section 4 that at stationarity, the vector ${\boldsymbol{\eta}}$ extended to $u_{{\scriptsize s}}$ by setting ${\boldsymbol{\eta}}(u_{{\scriptsize s}}) =0$ is a solution to a linear system

\begin{equation*} {\boldsymbol{\eta}}^T(I-P_w)= \beta \boldsymbol{{J}}^T,\end{equation*}

where $P_w$ is the transition matrix of the random walk defined on G by the weight function w. In Section 4.1 we discuss the relationship of this system to the Laplacian of G and the implications of this relationship. For now, we state one important consequence of this relationship: a lower bound on $\beta^*$ .

Theorem 2. Suppose we have a Data Collection Process with relative rate vector $\boldsymbol{{J}}$ such that $\boldsymbol{{J}}(v) > 0$ for $v \in V_s$ and $\boldsymbol{{J}}(v) < 0$ only for $v = u_{{\scriptsize s}}$ , defined on a graph $G=(V,E,w)$ that satisfies the conditions of Theorem 1 and has critical rate $\beta^*$ . Then if $P_w$ is the transition matrix of the random walk defined by w on G and $\lambda_2^w$ is the second largest eigenvalue of $P_w$ , we have

(3) \begin{equation}\beta^* \geq \frac{(1 - \lambda_2^w)}{\sum_{i\in V_s} \boldsymbol{{J}}(i)}~\frac{\sqrt{d_{\min}\mbox{deg}({u_{{\scriptsize s}}})}}{\left(d_{\max}+\mbox{deg}({u_{{\scriptsize s}}}) \right)}.\end{equation}

We also prove an upper bound on the critical data rate for the special case where $V_s=V \setminus \{u_{{\scriptsize s}}\}$ . In order to present this bound, we need to define some terms. For any vertex $u \in V$ , we define its measure as

\begin{equation*}\rho(u)\,:\!=\,\sum\limits_{v\in V}P_w[ {u,v} ].\end{equation*}

Similarly, for any $U \subset V$ we define the measure

\begin{equation*}\rho(U)=\sum\limits_{u\in U}\rho(u).\end{equation*}

We also define the edge boundary as $\partial U\,:\!=\,\{(u,v)\,:\, u \in U ,v \notin U\}$ , so that

\begin{equation*}\rho(\partial U)= \sum\limits_{u \in U ,v \notin U}P_w[ {u,v} ].\end{equation*}

We have the following upper bound result.

Proposition 1. Consider a graph $G=(V,E,w)$ with $|V|=n$ nodes which include one sink $u_{{\scriptsize s}}$ , and let $V_s = V \setminus \{u_{{\scriptsize s}}\}$ be the set of source nodes running a Data Collection Process having critical data rate $\beta^*$ as defined by Theorem 1. To achieve stable queues, $\beta^*$ must satisfy

(4) \begin{equation}\beta^* \leq \min\Big\{\hat{h}(G), \sum\limits_{u\,:\,u\sim u_{{\scriptsize s}}}\frac{P_w[ {u,u_{{\scriptsize s}}} ]}{n-1}\Big\},\end{equation}

where $P_w$ is the transition matrix of the random walk defined by w,

\begin{equation*}\hat{h}(G)=\min\limits_{U \subset V,u_{{\scriptsize s}}\notin U}\frac{\rho(\partial U)}{\rho(U)}\end{equation*}

is a constant, and $\hat{h}(G)$ is at most h(G), the edge expansion of graph G.

In Tables 1 and 2, we present lower bounds on the critical data rate for the stochastic Data Collection Process on various graphs for the cases where the source set sizes is $|V_s|= S$ or $|V_s|= 1$ , respectively. We also present the exact values of the data rate, which are easy to calculate using elementary algebra for these topologies. In all these cases, we assume that all edges have unit weight $w\,:\,E\rightarrow \textbf{1}$ , i.e., the random walk defined by $P_w$ is a simple random walk.

If we consider the complete graph topology, it is easy to see that the exact rate is $n/(S+1)(n-1)$ . As the spectral gap of the simple random walk on the complete graph of n nodes is $n/(n-1)$ , we note that for this case our lower bound is tight, i.e., both the exact value and the lower bound have order $\Theta(1/S)$ , where $|V_s|=S$ . Similarly, for the star graph with sink at outer node, our lower bound is tight and is of order $\Theta(1/Sn)$ . Hence it is clear that our lower bound cannot admit any asymptotic improvement in general. On the other hand, consider the cycle topology, which shows that for specific cases a better lower bound may be possible. We note that our spectral-gap-based lower bound is $\Theta(1/n)$ lower than the exact value for this case. Similarly, for other topologies, such as the wheel graph, complete binary tree, and k-times star of star graph ( $n^{1/k}$ -regular tree defined on k levels), a better lower bound is possible.

Table 1.

Rate lower bounds for various graphs with $w\,:\,E\rightarrow \textbf{1}$ and $|V_s|=S$ .

Regarding the upper bound, we achieve a tight upper bound in the cases of the complete graph and the star graph with the sink at either the center or an outer node. However, for the cycle graph our upper bound is $\Theta(1/n)$ higher than the exact rate for this setup.

Table 2.

Rate lower bounds for various graphs with $w\,:\,E\rightarrow \textbf{1}$ and $|V_s|=1$ .

Table 3.

Rate upper bounds for various graphs with $w\,:\,E\rightarrow \textbf{1}$ and $V_s=V \setminus \{u_{{\scriptsize s}}\}$ .

2.4. Geometric ergodicity

We show that when $\beta < \beta^*$ the Data Collection Process converges to its stationary distribution at a geometric rate, i.e., the process is geometrically ergodic. Following Meyn and Tweedie [Reference Meyn and Tweedie25], we define geometric ergodicity formally as follows.

Definition 2. (Geometric ergodicity.) Given an irreducible and aperiodic Markov chain $\Phi$ defined on state space $\mathcal{X}$ with transition probability $\mathcal{P}[\cdot,\cdot]$ and stationary distribution $\pi$ , the chain is said to be geometrically ergodic if there exist constants $\rho < 1$ , $R > 0$ , and for every state $\boldsymbol{{x}} \in \mathcal{X}$ there exists a $C_{\boldsymbol{{x}}} < \infty$ , such that for all $t > 0$ ,

(5) \begin{equation}\| \mathcal{P}^t[ {\boldsymbol{{x}},\cdot} ] - \pi \| \leq R C_{\boldsymbol{{x}}} \rho^t.\end{equation}

We use the coupling method to prove that convergence happens at a geometric rate. The convergence rate is in terms of the hitting time, $t_{{\scriptsize hit}}$ , of the random walk $P_w$ defined on G, which has been widely studied for a long time; see [Reference Brightwell and Winkler3, Reference Kanade, Mallmann-Trenn and Sauerwald13, Reference Palacios27]. Specifically, it is defined as follows. If $\{X_t\}_{t \geq 0}$ is a random walk on G and $\tau_v = \min \{t\,:\, X_t = v\}$ , then $t_{{\scriptsize hit}} = \max_{u,v \in V} {\mathbb{E}\left[{\tau_v \mid X_0 = u}\right]},$ i.e., the maximum over all pairs (u,v) of vertices of the expected time taken for a random walk begun at u to first reach the vertex v. We prove the following convergence theorem.

Theorem 3. Consider $\left\{ Q_t^{\boldsymbol{{J}}, \beta}\right\}_{t\geq 0}$ defined on $G = (V,E,w)$ such that there is a critical $\beta^*$ as described in Theorem 1. Let $\beta = \beta^*(1-\delta)$ for $\delta \in (0,1)$ and denote by $\mathcal{P}$ the transition matrix for the resulting multidimensional Markov chain. Suppose we have $\boldsymbol{{x}},\boldsymbol{{y}} \in (\mathbb{N} \cup \{0\})^{|V|-1}$ with

\begin{equation*}\sum_{i=1}^{|V|-1} \boldsymbol{{x}}_i = N^{(\boldsymbol{{x}})}, \qquad \sum_{i=1}^{|V|-1} \boldsymbol{{y}}_i = N^{(\boldsymbol{{y}})}.\end{equation*}

Then

(6) \begin{equation}||\mathcal{P}^t[ {\boldsymbol{{x}},\cdot} ]-\mathcal{P}^t[ {\boldsymbol{{y}},\cdot} ]||_{TV}\leq 2^{\left(1+\frac{\left(\max\big\{N^{(\boldsymbol{{x}})},N^{(\boldsymbol{{y}})}\big\}-1\right)\delta}{2t_{{\scriptsize hit}}}\right)}\cdot \left(\frac{1}{2}\right)^{\frac{\delta}{2t_{{\scriptsize hit}}}\cdot t }.\end{equation}

Convergence to stationarity can be derived as a special case of Theorem 3 by choosing $\boldsymbol{{y}} \in (\mathbb{N} \cup \{0\})^{|V|-1}$ according to $\pi$ , the stationary distribution of the chain $\left\{ Q_t^{\boldsymbol{{J}}, \beta}\right\}_{t\geq 0}$ . This establishes the geometric ergodicity of the Data Collection Process in the subcritical regime.

Corollary 1. Consider the multidimensional Markov chain $\left\{ Q_t^{\boldsymbol{{J}}, \beta}\right\}_{t\geq 0}$ with $\beta = \beta^*(1-\delta)$ for $\delta \in (0,1)$ as defined in Theorem 3, and denote its stationary distribution by $\pi$ . For $\boldsymbol{{x}} \in (\mathbb{N} \cup \{0\})^{|V|-1}$ such that

\begin{equation*}\sum_{i=1}^{|V|-1} \boldsymbol{{x}}_i = N^{(\boldsymbol{{x}})},\end{equation*}

we have

(7) \begin{equation}||\mathcal{P}^t[ {\boldsymbol{{x}},\cdot} ]-\pi||_{TV}\leq 2^{\left(1+\frac{N^{(\boldsymbol{{x}})}\delta}{2t_{{\scriptsize hit}}}\right)}\cdot \left(\frac{1}{2}\right)^{\frac{\delta}{t_{{\scriptsize hit}}((1 - \delta)\beta^* + 2)} \cdot t}.\end{equation}

Moreover, for the special case that $\boldsymbol{{x}} = \textbf{0}$ (i.e. the system begins with empty queues), the Markov chain mixes to within $1/M$ of its stationary distribution in terms of total variation distance for any parameter $M > 0$ in time t that is

\begin{equation*}\Theta\left(\frac{t_{{\scriptsize hit}} \log M}{\delta}\right).\end{equation*}

3. Ergodicity as a critical phenomenon

In this section, we prove Theorem 1; i.e., we show the existence of a nontrivial critical data rate $\beta^*$ for the multidimensional Markov chain $\left\{ Q_t^{\boldsymbol{{J}}, \beta}\right\}_{t\geq 0}$ associated with the Data Collection Process such that the chain is ergodic for all values below $\beta^*$ and non-ergodic above it.

We first state two lemmas that we will need: Szpankowski’s ‘isolation lemma’ (Lemma 1) and Loynes’s scheme [Reference Loynes22] as adapted to our situation (Lemma 2).

We will also need the following property of the Markov chain $Q^{\boldsymbol{{J}},\beta}_t$ associated with the Data Collection Process: the queue occupancy probability of a node $\mathbb{P}\big[ {Q^{\boldsymbol{{J}},\beta}_t(u)>0} \big]$ is an increasing function of $\beta$ for all $u \in V\setminus \{u_{{\scriptsize s}}\}$ , and it is continuous for all $\beta<\beta^*$ , where $\beta^*$ is the critical rate above which the queues are unstable and below which they are stable.

Proof of Part (1). To prove this property, we will first establish that the multidimensional Markov chain $Q^{\boldsymbol{{J}},\beta}_t$ is stochastically ordered; i.e., stochastically larger initial states will produce stochastically larger chains at all times. For this, let us consider a coupling as used by Szpankowski of two trajectories of this chain, $\{Q^{\boldsymbol{{J}},\beta}_t\}$ and $\{\bar{Q}_t^{\boldsymbol{{J}},\beta}\}$ , such that $\bar{Q}_0^{\boldsymbol{{J}},\beta} \preceq_{\small \text{SD}} Q_0^{\boldsymbol{{J}},\beta}$ . Now, assume the stochastic dominance relation between the two holds at time t, i.e., $\bar{Q}_t^{\boldsymbol{{J}},\beta} \preceq_{\small \text{SD}} Q^{\boldsymbol{{J}},\beta}_t$ . Then, at time step $t+1$ , for both $Q^{\boldsymbol{{J}},\beta}_t$ and $\bar{Q}_t^{\boldsymbol{{J}},\beta}$ , from the one-step basic queue evolution equation at all nodes $u\in V \setminus \{u_{{\scriptsize s}}\}$ , we have

(8) \begin{align}{\mathbb{E}\Big[{Q_{t+1}^{\boldsymbol{{J}},\beta}(u) \Big| Q^{\boldsymbol{{J}},\beta}_t(u)}\Big]} = & Q^{\boldsymbol{{J}},\beta}_t(u) - {\boldsymbol{1}_{\{{Q^{\boldsymbol{{J}},\beta}_t(u) > 0}\}}} \sum_{v\,:\,v \sim u} P_w[ {u,v} ] \nonumber\\ &+ \sum_{v\,:\,v \sim u} P_w[ {v,u} ] {\boldsymbol{1}_{\{{Q^{\boldsymbol{{J}},\beta}_t(v) > 0}\}}}+A_t(u),\end{align}

where $A_t(u)$ is the number of packets generated at u, which is 0 if $u \notin V_s$ and is 1 with probability $\beta \mathbf{J}(v)$ if $v \in V_s$ , so ${\mathbb{E}\left[{A_t(u)}\right]}=\beta \mathbf{J}(u)$ . Now consider any node u at time $t+1$ . From the induction hypothesis, queues at the node u as well as its neighbors in $Q^{\boldsymbol{{J}},\beta}_t$ will dominate the ones in $\bar{Q}^{\boldsymbol{{J}},\beta}_t$ , so the first three terms on the right of (8) in $Q^{\boldsymbol{{J}},\beta}_t(u)$ will dominate the ones for $\bar{Q}^{\boldsymbol{{J}},\beta}_t(u)$ , and since $\beta$ is the same, the last term is the same for both cases. So we have $\bar{Q}_{t+1}^{\boldsymbol{{J}},\beta}(u) \preceq_{\small \text{SD}} Q_{t+1}^{\boldsymbol{{J}},\beta}(u)$ . This is true for all nodes $u\in V \setminus \{u_{{\scriptsize s}}\}$ , so we have, at time $t+1$ , $\bar{Q}_{t+1}^{\boldsymbol{{J}},\beta} \preceq_{\small \text{SD}} Q_{t+1}^{\boldsymbol{{J}},\beta}$ . Hence, by induction, the Markov chain $Q^{\boldsymbol{{J}},\beta}_t$ is stochastically ordered.

Now, to prove monotonicity, for $\beta<\beta'$ let us consider a coupling similar to the one used before of two stochastically ordered Markov chains $Q^{\boldsymbol{{J}},\beta}_t$ and $Q_t^{{\boldsymbol{{J}},\beta'}}$ such that $Q_0^{\boldsymbol{{J}},\beta} \preceq_{\small \text{SD}} Q_0^{{\boldsymbol{{J}},\beta'}}$ . We know that for all $u\in V \setminus \{u_{{\scriptsize s}}\}$ , $\beta \boldsymbol{{J}}(u)<{\boldsymbol{{J}},\beta'} \boldsymbol{{J}}(u)$ , so by using induction and evolving queues using the one-step queue evolution equation (8), we can show that $Q^{\boldsymbol{{J}},\beta}_t \preceq_{\small \text{SD}} Q_t^{{\boldsymbol{{J}},\beta'}}$ for all t. Hence, by induction we have that $\mathbb{P}\big[ {Q^{\boldsymbol{{J}},\beta}_t(u)>0} \big]$ is an increasing function of $\beta$ for all $u\in V \setminus \{u_{{\scriptsize s}}\}$ .

Proof of Part (2). To prove the continuity of the given function for $\beta<\beta^*$ , we will consider a similar coupling, but this time between two stochastically ordered Markov chains $Q^{\boldsymbol{{J}},\beta}_t$ and $Q_t^{\boldsymbol{{J}},\beta-d\beta}$ with infinitesimal $d\beta$ . For the data generation rule in the two chains, we have that whenever a new data packet is generated at any node in the chain $Q^{\boldsymbol{{J}},\beta-d\beta}_t$ , it is definitely generated at the corresponding node in the chain $Q^{\boldsymbol{{J}},\beta}_t$ , but not vice versa. To understand the difference between the two chains, let $N^{\beta-d\beta}_t$ and $N^\beta_t$ denote the total number of packets in the respective chains till time t, and let $\Lambda_t^{\beta}=N^\beta_t-N^{\beta-d\beta}_t$ . Now, consider $g\,:\,[0,1]\rightarrow\mathbb{R}$ to be a function dependent on $\beta$ such that $g(\beta)={\mathbb{E}\big[{Q_{t+1}^{\boldsymbol{{J}},\beta}(u)-Q^{\boldsymbol{{J}},\beta}_t(u)}\big]}$ , which is bounded by definition. If we look at the derivative of this function, the term where $\Lambda_t^{\beta}=0$ will be zero by definition of coupling, as the two chains behave differently only when there is an extra generated packet. Similarly, terms with $\Lambda_t^{\beta}\geq 2$ will have higher powers of $d\beta$ , which will become zero as $d\beta\rightarrow 0$ . Hence, the derivative $g'(\beta)$ depends only on the $\Lambda_t^\beta= 1$ term; i.e.,

\begin{equation*}g'(\beta)=\lim_{d\beta\rightarrow 0}\big(g(\beta)-g(\beta-d\beta)\Big|\Lambda_t^\beta=1\big) \big(|V_s|t (1-d\beta)^{|V_s|t-1}\big),\end{equation*}

where $V_s\subset V$ is the set of data sources. So the total numbers of data packets generated in the two Markov chains up to time t differ by one, and hence the queues at nodes in the two chains differ by at most one data packet at any time step. Now, for the given coupled chains, let t ^′ be the time by which an extra packet is generated in chain $Q^{\boldsymbol{{J}},\beta}_t$ . We have

(9) \begin{equation}\mathbb{P}\Big[ {Q^{\boldsymbol{{J}},\beta}_t(u)>0\Big|Q^{\boldsymbol{{J}},\beta-d\beta}_t(u)=0}\Big]=\dfrac{\mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta}_t(u)>0\cap Q^{\boldsymbol{{J}},\beta-d\beta}_t(u)=0} \right]}{\mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta-d\beta}_t(u)=0} \right]} = \sum_{t'=1}^t d\beta P_{t'},\end{equation}

where $P_{t'}$ is the probability that the extra packet generated in the chain $Q^{\boldsymbol{{J}},\beta}_t$ is present at node $u\in V\setminus\{u_{{\scriptsize s}}\}$ . This means

(10) \begin{equation}\mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta}_t(u)>0} \right]-\mathbb{P}\left[ {Q_t^{\boldsymbol{{J}},\beta-d\beta}(u)>0} \right]\leq\sum_{t'=1}^t d\beta P_{t'}.\end{equation}

So, if

\begin{equation*}\mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta}_t(u)>0\Big|Q^{\boldsymbol{{J}},\beta-d\beta}_t(u)=0} \right]\end{equation*}

is defined, as $d\beta\rightarrow 0$ , from the above equation we have

\begin{equation*}\mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta}_t(u)>0} \right]-\mathbb{P}\left[ {Q_t^{\boldsymbol{{J}},\beta-d\beta}(u)>0} \right]\rightarrow 0.\end{equation*}

Similarly, for the other side, if

\begin{equation*}\mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta+d\beta}_t(v)>0\Big|Q_t^{\boldsymbol{{J}},\beta}(u)=0} \right]\end{equation*}

is defined, then as $d\beta\rightarrow 0$ , similarly to (10), we have

\begin{equation*}\mathbb{P}\left[ {Q_t^{\boldsymbol{{J}},\beta+d\beta}(u)>0} \right]-\mathbb{P}\left[ {Q_t^{{\boldsymbol{{J}},\beta}}(u)>0} \right]\rightarrow 0.\end{equation*}

Now, if both these conditions are true, then the function is continuous, as it has both left and right continuity.

Now, consider all data rates $\beta<\beta^*$ , where $\beta^*$ is the critical rate below which all rates are stable and above which all are unstable. For such rates, both the probabilities

\begin{equation*}\mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta}_t(u)>0\Big|Q^{\boldsymbol{{J}},\beta-d\beta}_t(u)=0} \right], \qquad \mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta+d\beta}_t(v)>0\Big|Q_t^{\boldsymbol{{J}},\beta}(u)=0} \right]\end{equation*}

are defined, so as discussed above the function is continuous on both sides for all $\beta<\beta^*$ . Now consider the case of data rates $\beta\geq\beta^*$ . At $\beta^*$ , we know

\begin{equation*}\mathbb{P}\left[ {Q_t^{\boldsymbol{{J}},\beta^*}(u)>0} \right]-\mathbb{P}\left[ {Q_t^{\boldsymbol{{J}},\beta^*-d\beta}(u)>0} \right]\end{equation*}

is defined (see Equation (9)), as the rate $\beta^*-d\beta$ is stable by definition; hence the function is left continuous for this rate. However, for the other side, we know $\beta^*$ is not stable, i.e.,

\begin{equation*}\lim_{t\rightarrow\infty}\mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta^*}_t(v)=0} \right]=0;\end{equation*}

hence,

\begin{equation*}\mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta^*+d\beta}_t(v)>0\Big|Q_t^{\boldsymbol{{J}},\beta^*}(u)=0} \right]\end{equation*}

is not defined, and the function is not right continuous. So for $\beta\geq\beta^*$ the function is left continuous but not right continuous. However, for all $u \in V\setminus \{u_{{\scriptsize s}}\}$ , $\mathbb{P}\big[ {Q^{\boldsymbol{{J}},\beta}_t(u)>0} \big]$ is a continuous function (both limits exist) for all $\beta<\beta^*$ .

Proof of Theorem 1. We prove first sufficiency, i.e., the existence of a nontrivial $\beta^*>0$ such that the multidimensional Markov chain is ergodic for all $\beta<\beta^*$ , and then necessity, i.e., that for all $\beta\geq\beta^*$ the chain is non-ergodic.

Sufficiency. Given a partition (P,U) of $V \setminus \{u_{{\scriptsize s}}\}$ queues, we define a modification $\bar{Q}_t^{\beta,U}$ of the $(|V|-1)$ -dimensional chain $Q^{\boldsymbol{{J}},\beta}_t$ . In this modification, all nodes in U have the same behavior as in $Q^{\boldsymbol{{J}},\beta}_t$ , but the nodes in $V \setminus \{u_{{\scriptsize s}}\} \setminus U$ are not allowed to have empty queues. Let us now first set $U = \emptyset$ (we call these nodes ‘non-persistent’) and $P = V \setminus \{u_{{\scriptsize s}}\}$ (we call these nodes ‘persistent’). For any $\beta \in (0,1)$ , we know the one-step basic queue evolution equation under the Data Collection Process for any u is as follows:

\begin{align*}{\mathbb{E}\left[{Q_{t+1}^{\boldsymbol{{J}},\beta}(u) \Big| Q^{\boldsymbol{{J}},\beta}_t(u)}\right]} &= Q^{\boldsymbol{{J}},\beta}_t(u) - {\boldsymbol{1}_{\{{Q^{\boldsymbol{{J}},\beta}_t(u) > 0} \}}}\sum_{v\,:\,v \sim u} P_w[ {u,v} ] \\&+ \sum_{v\,:\,v \sim u} P_w[ {v,u} ] {\boldsymbol{1}_{\{{Q^{\boldsymbol{{J}},\beta}_t(v) > 0}\}}} +\beta \boldsymbol{{J}}(u).\end{align*}

So at each node u we have an arrival from v with probability $P_w[ {v,u} ]$ in $\bar{Q}_t^{\beta, \emptyset}$ , since the queue of v is always non-empty and the departure is the usual $\sum_{v\,:\,v \sim u} P_w[ {u,v} ]$ .

Now, since we know $P_w[ {u_{{\scriptsize s}},v} ]= 0$ for all $v \in V \setminus \{u_{{\scriptsize s}}\}$ , the sum of the outgoing probabilities from $V \setminus \{u_{{\scriptsize s}}\}$ is greater than the sum of the incoming probabilities; i.e.,

\begin{equation*}\sum_{u \in V \setminus \{u_{{\scriptsize s}}\}}\sum_{v\,:\,v \sim u} P_w[ {u,v} ] > \sum_{u\in V \setminus \{u_{{\scriptsize s}}\}} \sum_{v\,:\,v \sim u, v \in V \setminus \{u_{{\scriptsize s}}\}} P_w[ {v,u} ].\end{equation*}

Therefore, there must be a vertex $u^* \in V \setminus \{u_{{\scriptsize s}}\}$ for which

\begin{equation*}\sum_{v\,:\,u^* \sim v} P_w[ {u^*,v} ] > \sum_{v\,:\,u^* \sim v, v \in V \setminus \{u_{{\scriptsize s}}\}} P_w[ {v,u^*} ].\end{equation*}

From (8) for this $u^*$ we note that the expected drift is

\begin{equation*}-\sum_{v\,:\,u^* \sim v} P_w[ {u^*,v} ] + \sum_{v\,:\,u^* \sim v, v \in V \setminus \{u_{{\scriptsize s}}\}} P_w[ {v,u^*} ] + \beta \boldsymbol{{J}}(u^*),\end{equation*}

which is negative for an appropriately small but nonzero value of $\beta$ ; let us call it $\beta_{u^*}$ .

Now, to apply Loynes’s scheme to the vertex $u^*$ , we need to ensure that the sequence $(I_t(u^*), O_t(u^*))$ is strictly stationary, where $I_t(u^*)$ is the number of incoming packets to $u^*$ at time t and $O_t(u^*)$ is the number of outgoing packets from $u^*$ . Since all nodes $u \in P$ , both $u^*$ and its neighbors always have a packet in the queue, so both $O_t(u^*)$ and $I_t(u^*)$ are sequences of independent Bernoulli random variables and hence are stationary and ergodic. We can therefore apply Loynes’s scheme (Lemma 2) to claim that the one-dimensional process $\bar{Q}^{\beta_{u^*}, \emptyset}_t(u^*)$ is stable, and hence $Q^{\beta_{u^*}}_t(u^*)$ is stable.

Now we assume there is a non-empty set U of non-persistent users and a $\beta_U > 0$ such that $\bar{Q}_t^{\beta_U,U}(U)$ is stable and has a stationary distribution. To apply Loynes’s scheme to a vertex $u \in P = V \setminus \{u_{{\scriptsize s}}\} \setminus U$ , we need to ensure that the sequence $(I_t(u), O_t(u))$ is strictly stationary. Since $u \in P$ there is always a packet in the queue at u, and so $O_t(u)$ is a sequence of independent Bernoulli random variables which takes value 1 with probability $\sum_{v\,:\,v\sim u} P_w[ {u,v} ]$ and value 0 otherwise. We decompose $I_t(u)$ as the sum of 0–1 random variables $A^{uv}_t$ , where $A^{uv}_t = 1$ if u receives a packet from v at time t. Then

\begin{equation*}I_t(u) = \sum_{v \in U} A^{uv}_t + \sum_{v \in P} A^{uv}_t.\end{equation*}

Since all $v \in P$ have a packet in their queue at all $t \geq 0$ , each $\sum_{v \in P} A^{uv}_t$ is the sum of Bernoulli random variables and hence is taken from a strongly stationary sequence. We start the $\bar{Q}_t^{\beta_U,U}$ from an initial state picked according to its stationary distribution, which ensures that the process stays in the stationary state for all $t \geq 0$ . In particular, this implies that for any $v \in P$ , the number of incoming packets from v at time $t \geq 0$ is a sequence of random variables that is strongly stationary. Therefore $(I_t(u), O_t(u))$ is a strongly stationary sequence and we can apply Loynes’s scheme. The expected drift at time $t \geq 0$ at any $u \in P$ for any $\beta \leq \beta_U$ is given by

(11) \begin{equation}-\sum_{v\,:\,u\sim v} P_w[ {u,v} ] + \sum_{u \sim v, v\in P} P_w[ {v,u} ] + \sum_{u \sim v, v\in U} P_w[ {v,u} ]P_w[ {\bar{Q}^{\beta,U}_t(u) >0} ] + \beta \boldsymbol{{J}}(u).\end{equation}

Since the graph is connected and so there is at least one pair $(w_1,w_2)$ such that $w_1 \in U, w_2 \in P$ and $P_w[ {w_1, w_2} ] >0$ , we know that

\begin{equation*}\sum_{u \in P}\sum_{v \sim u} P_w[ {u,v} ] > \sum_{u\in P, v \in U} \sum_{v \sim u} P_w[ {v,u} ].\end{equation*}

This means that there is a $u^* \in P$ such that

\begin{equation*}\sum_{u^* \sim v} P_w[ {u^*,v} ] > \sum_{u^* \sim v, v \in P} P_w[ {v,u^*} ].\end{equation*}

For this $u^*$ the first two terms in (11) add up to a value which is negative. Further from Lemma 3 we note that the third term is continuous and increasing in $\beta$ and tends to 0 as $\beta \downarrow 0$ . Hence it is possible to find a value $\beta_{U \cup \{u^*\}}$ which lies in $(0,\beta_U)$ such that the expected drift is negative. From Loynes’s scheme (Lemma 2) this implies that $\bar{Q}^{\beta, U}_t(U \cup \{u^*\})$ is stable for $\beta < \beta_{U \cup \{u^*\}}$ . Moreover, from Lemma 1, the stability of all the one-dimensional Markov chains associated with the vertices in $U \cup \{u^*\}$ implies the stability of the overall multidimensional chain. Consequently, the same holds for $Q^{\boldsymbol{{J}},\beta}_t(U \cup \{u^*\})$ . Therefore, by induction, there is a $\beta^*$ such that for $\beta<\beta^*$ , $Q^{\boldsymbol{{J}},\beta}_t$ is stable.

Necessity. Corresponding to the sequence by which the stability region is expanded to include all the vertices of $V \setminus \{u_{{\scriptsize s}}\}$ , there is a sequence $\beta_{u_1}, \beta_{u_2},\ldots, \beta_{u_{|V \setminus \{u_{{\scriptsize s}}\}|}}$ such that $\beta^{*} = \min \{\beta_{u_1}, \beta_{u_2},\ldots, \beta_{u_{|V \setminus \{u_{{\scriptsize s}}\}|}}\}.$ Let w be the vertex for which $\beta_w = \beta^*$ . Assume for the sake of simplicity of presentation that $\beta_w < \min \{\beta_u \,:\, u \in V \setminus \{u_{{\scriptsize s}}\} \setminus \{w\} \}.$ Hence we can choose any $\beta$ such that $\beta_w < \beta < \min \{\beta_u \,:\, u \in V \setminus \{u_{{\scriptsize s}}\} \setminus \{w\} \}.$ For this $\beta$ we know that $Q_t^{\beta, V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\}}(V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\})$ is stable. If we start this chain from its stationary distribution, then the number of packets that are transmitted from $V \setminus \{u_{{\scriptsize s}}\} \setminus \{w\}$ to w form a strongly stationary sequence. Since w is persistent in this setting, the packets leaving it are also strongly stationary. Hence Loynes’s scheme (Lemma 2) can be applied. By the choice of $\beta$ we know that the expected drift at w is strictly positive and so $\bar{Q}_t^{\beta, V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\}}(w)$ is unstable; hence, by Lemma 1, $\bar{Q}_t^{\beta, V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\}}$ is unstable.

In order to show that $Q^{\boldsymbol{{J}},\beta}_t$ is also unstable for this choice of $\beta$ , we will show that there is a coupling of $Q^{\boldsymbol{{J}},\beta}_t$ and $\bar{Q}_t^{\beta, V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\}}$ with an appropriately chosen initial condition such that the two models behave exactly the same. We know that on the set of sample paths (of positive probability) on which the queue at w remains strictly positive, the two coupled models behave exactly the same, because a difference arises only if the queue at w becomes 0 at time t, in which case $\bar{Q}_{t+1}^{\beta, V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\}}(w)$ is automatically set to 1 since w is persistent and $Q^{\boldsymbol{{J}},\beta}_{t+1}(w)$ remains 0. Now, we know that $\bar{Q}_t^{\beta, V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\}}(w)$ is unstable, so when we start $\bar{Q}_t^{\beta, V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\}}(V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\})$ according to its stationary distribution and we set the queue at w to 1, there is a positive probability that this queue never reaches 0. For those cases, $Q^{\boldsymbol{{J}},\beta}_t(w)$ behaves the same as $\bar{Q}_t^{\beta, V \setminus \{u_{{\scriptsize s}}\} \setminus\{w\}}(w)$ ; i.e., it is unstable. Therefore, with these initial conditions, $Q^{\boldsymbol{{J}},\beta}_t(w)$ is not substable, since with positive probability $\lim_{t\rightarrow \infty} \mathbb{P}\left[ {Q^{\boldsymbol{{J}},\beta}_t(w) > m} \right]$ for all finite m. Hence, $Q^{\boldsymbol{{J}},\beta}_t(w)$ is unstable, and by Lemma 1, $Q^{\boldsymbol{{J}},\beta}_t$ is unstable for our choice of $\beta$ . By the monotonicity of the process (see Lemma 3), it is therefore unstable for all choices of $\beta \geq \beta^*$ .

Discussion of proof technique. Our proof of Theorem 1 follows a general method for proving the existence of a ‘stability region’ which is similar to the induction-based technique used by Georgiadis and Szpankowski to characterize the stability region of the multi-queue system described by token passing rings [Reference Georgiadis and Szpankowski7]. Szpankowski showed that this technique applies to a class of multi-queueing systems with certain properties [Reference Szpankowski31], and the Data Collection Process falls in this class.

A more direct approach to proving Theorem 1 would involve taking the sum of all queues as a Lyapunov function and then proving that the one-step drift of this Lyapunov function is negative when the sum of queues is greater than some $N> 0$ . There are some challenges in this method. We want to show that

\begin{equation*}{\mathbb{E}\left[{\sum_{v \in V \setminus \{u_{{\scriptsize s}}\}} Q_{t+1}^{\boldsymbol{{J}},\beta}(v) - \sum_{v \in V \setminus \{u_{{\scriptsize s}}\}} Q_{t}^{\boldsymbol{{J}},\beta}(v) \left| \sum_{v \in V \setminus \{u_{{\scriptsize s}}\}}\right. Q_{t}^{\boldsymbol{{J}},\beta}(v) > N }\right]}<0,\end{equation*}

but in general this drift need not be negative. If none of the N packets currently in the system are in a queue adjacent to the sink, then this drift cannot be negative, and in fact it is strictly positive. Instead we may try to find an $\ell > 1$ such that

\begin{equation*}{\mathbb{E}\left[{\sum_{v \in V \setminus \{u_{{\scriptsize s}}\}} Q_{t+\ell}^{\boldsymbol{{J}},\beta}(v) - \sum_{v \in V \setminus \{u_{{\scriptsize s}}\}} Q_{t}^{\boldsymbol{{J}},\beta}(v) \left| \sum_{v \in V \setminus \{u_{{\scriptsize s}}\}}\right. Q_{t}^{\boldsymbol{{J}},\beta}(v) > N }\right]} < 0.\end{equation*}

However, even determining this $\ell$ would involve making nontrivial arguments.

This was one reason why we chose to use Szpankowski’s technique to prove Theorem 1. The other reason was that the induction on the graph is a pleasing technique which extends stability one vertex at a time to the entire graph.

4. Characterizing the critical rate

In Section 3 we proved the ergodicity of the Markov chain associated with the Data Collection Process and showed that its stationary distribution exists. In this section we will show that at the steady state, the Data Collection Process satisfies a special class of linear equations that we call ‘one-sink’ Laplacian systems. Using this equivalence we will derive a lower bound on the critical rate. Lastly, we will also present an upper bound on the critical rate.

4.1. Equivalence to one-sink Laplacian systems

The one-step basic queue evolution equation under the Data Collection Process for any node $u\in V$ is as follows:

(12) \begin{align}{\mathbb{E}\left[{Q_{t+1}^{\boldsymbol{{J}},\beta}(u) \Big| Q^{\boldsymbol{{J}},\beta}_t(u)}\right]} = & Q^{\boldsymbol{{J}},\beta}_t(u) - {\boldsymbol{1}_{\{{Q^{\boldsymbol{{J}},\beta}_t(u) > 0}\}}} \sum_{v\,:\,v \sim u} P_w[ {u,v} ] \nonumber\\&+ \sum_{v\,:\,v \sim u} P_w[ {v,u} ] {\boldsymbol{1}_{\{{Q^{\boldsymbol{{J}},\beta}_t(v) > 0}\}}} + A_t(u).\end{align}

The second and third terms on the right-hand side of the above equation represent the transmissions sent to and received from the neighbors, respectively, and $A_t(u)$ is the number of packets generated at u, which is 1 with probability $\beta \boldsymbol{{J}}(u)$ if $u \in V_s$ , for the sink $\beta \boldsymbol{{J}}(u_{{\scriptsize s}})=-\beta \sum_{v \in V_s}\mathbf{J}(v)$ , and for all other nodes $\boldsymbol{{J}}(u)=0$ , where $u\notin \{V_s\cup\{u_{{\scriptsize s}}\}\}$ . Now, taking expectations on both sides of (12), letting ${\boldsymbol{\eta}}^\beta_t(u) = \mathbb{P}\big[ {Q^{\boldsymbol{{J}},\beta}_t(u) > 0} \big]$ be the queue occupancy probability of node u, and observing that ${\mathbb{E}\left[{A_t(u)}\right]}=\beta \mathbf{J}(u)$ , where $\boldsymbol{{J}}$ is the relative rate vector, we have

(13) \begin{equation}{\mathbb{E}\left[{Q_{t+1}^{\boldsymbol{{J}},\beta} (u)}\right]} = {\mathbb{E}\left[{Q^{\boldsymbol{{J}},\beta}_t (u)}\right]} - {\boldsymbol{\eta}}_t^\beta(u) \sum_{v\,:\,v\sim u}P_w[ {u,v} ] + \sum_{v\,:\,v\sim u}P_w[ {v,u} ]{\boldsymbol{\eta}}_t^\beta(v)+\beta \mathbf{J}(u).\end{equation}

From Theorem 1, we know that for an appropriately chosen value of $\beta$ the Data Collection Process has a steady state. Moreover, at the steady state ${\mathbb{E}\big[{Q^{\boldsymbol{{J}},\beta}_t(u)}\big]}$ is a constant, so if we let ${\boldsymbol{\eta}}^{\beta}(u) = \lim_{t \rightarrow \infty} \mathbb{P}\big[ {Q^{\boldsymbol{{J}},\beta}_t(u) > 0} \big]$ be the queue occupancy probability of the node u at the stationarity, then we have the steady-state equation for the given node as

(14) \begin{equation}- {\boldsymbol{\eta}}^\beta(u) \sum_{v\,:\,v\sim u}P_w[ {u,v} ] + \sum_{v\,:\,v\sim u}P_w[ {v,u} ]{\boldsymbol{\eta}}^\beta(v)+\beta \mathbf{J}(u)= 0.\end{equation}

We can also represent the steady-state equations of all $|V|=n$ nodes in matrix form. For this, let us first order the nodes so that the nth node represents the sink. Let ${\boldsymbol{\eta}}$ be an n-element column vector representing the steady-state queue occupancy probabilities ${\boldsymbol{\eta}}^\beta(u)$ of the nodes $u\in V$ . We drop the superscript $\beta$ , assuming a stable rate; we then have ${\boldsymbol{\eta}} = [{\boldsymbol{\eta}}(1)~{\boldsymbol{\eta}}(2)~\cdots~{\boldsymbol{\eta}}(n-1)~0]$ . This is defined assuming that the sink collects all data it receives and has no notion of maintaining a queue. Let $\boldsymbol{{J}}$ be another n-element column vector such that $\boldsymbol{{J}}(i)>0$ if $i\in V_s$ , $\boldsymbol{{J}}(u_{{\scriptsize s}})=-\sum_{i\in V_s}\boldsymbol{{J}}(i)$ , and $\boldsymbol{{J}}(i)=0$ elsewhere, and let I be the usual $n\times n$ identity matrix. Given the transition matrix $P_w$ for the random walk defined by w on the graph G, the steady-state queue equations at the nodes can be written in matrix form as

(15) \begin{equation}{\boldsymbol{\eta}}^T(I-P_w)= \beta \boldsymbol{{J}}^T.\end{equation}

As we know the transition matrix $P_w=D^{-1}A$ , where D is the diagonal matrix of generalized degrees and A is the adjacency matrix, the matrix $(I-P_w)$ is also a Laplacian, since we can rewrite it as $(I-P_w)=D^{-1}(D-A)=D^{-1}L$ . So (15) can be rewritten as

(16) \begin{equation}\boldsymbol{{x}}^TL=\beta \boldsymbol{{J}}^T,\end{equation}

where $\boldsymbol{{x}}^T={\boldsymbol{\eta}}^TD^{-1}$ is a row vector such that $\boldsymbol{{x}}(u)={\boldsymbol{\eta}}(u)/\mbox{deg}({u})$ for all u, where ${\boldsymbol{\eta}}(u)$ is the steady-state queue occupancy probability and $\mbox{deg}({u})=\sum_{v\,:\,(u,v)\in E}w_{uv}$ is the generalized degree of the node u. Equation (16) is similar to Laplacian systems of the form $L\boldsymbol{{x}} = \boldsymbol{{b}}$ with the constraint that only one element in $\boldsymbol{{b}}$ is negative. We call such systems ‘one-sink’ Laplacian systems. In our subsequent work [Reference Gillani and Bagchi8, Reference Gillani and Bagchi9] we discuss this connection in detail.

4.2. A lower bound

Having established the steady-state equation for the Data Collection Process, we will use it to characterize the critical data rate. In particular, we will prove a lower bound on this rate.

Proof of Theorem 2. For a given graph $G=(V,E,w)$ , with source set $V_s\subseteq V\setminus\{u_{{\scriptsize s}}\}$ and transition matrix $P_w$ for a random walk defined by w on the graph G, recall that the steady-state queue equations at nodes can be written in matrix form as

(17) \begin{equation}{\boldsymbol{\eta}}^T(I-P_w)=\beta \boldsymbol{{J}}^T.\end{equation}

Now, in order to bound the maximum stable data rate $\beta$ at which the source nodes generate data in terms of the underlying graph parameters, we will consider eigendecomposition of the left-hand side of (17). For this, we will deviate from the usual inner product on the vector space $\mathbb{R}^V$ , i.e., $\langle f,g\rangle = \sum_{x\in V}f(x)g(x)$ , and define another inner product on $\mathbb{R}^V$ which is given by $\langle f,g\rangle_\mu \,:\!=\, \sum_{x\in V}f(x)g(x)\mu(x)$ , where $\mu$ is the stationary distribution of the random walk defined by w on the graph satisfying $\mu=\mu P_w$ . From Lemma 12.2 in [Reference Levin, Peres and Wilmer20], it is known that the inner product space $(\mathbb{R}^V, \langle\cdot,\cdot\rangle)_\mu$ has an orthonormal basis of real-valued eigenfunctions $\{f_j\}_{j=1}^{|V|}$ corresponding to real eigenvalues $\{\lambda_j\}$ . Using this lemma and writing the vector ${\boldsymbol{\eta}}^T$ in terms of the eigenvectors, we have ${\boldsymbol{\eta}}^T = \sum_{i=1}^{|V|} \langle{\boldsymbol{\eta}}^T,f_i\rangle_\mu f_i.$ This gives us that ${\boldsymbol{\eta}}^T(I - P_w) = \sum_{i=1}^{|V|} (1 - \lambda_i^w)\langle{\boldsymbol{\eta}}^T,f_i\rangle_\mu f_i$ , where $\lambda_i^w$ is the ith eigenvalue of the transition matrix $P_w$ . Moreover, from Lemma 12.1 in [Reference Levin, Peres and Wilmer20], we also know that the absolute value of any eignevalue of a transition matrix can be at most 1, so $\lambda_1^w = 1 > \lambda_2^w \geq \cdots \geq \lambda_n^w$ . Thus, we have

(18) \begin{align}{\boldsymbol{\eta}}^T(I - P_w) = \sum_{i=2}^{|V|}(1 - \lambda_i^w)\langle{\boldsymbol{\eta}}^T,f_i\rangle_\mu f_i \end{align}

(19) \begin{align} \qquad\qquad\qquad\quad\qquad\geq (1 - \lambda_2^w)\left(\sum_{i=2}^{|V|}\langle{\boldsymbol{\eta}}^T,f_i\rangle_\mu f_i\right).\qquad\end{align}

Note that $f_1, \ldots, f_{|V|}$ form an orthonormal basis, so $\sum_{i=1}^{|V|}\langle{\boldsymbol{\eta}}^T,f_i\rangle_\mu^2 = \lVert{\boldsymbol{\eta}}^T\rVert_\mu^2$ . Hence we have

(20) \begin{equation}\sum\limits_{i=2}^n{\langle{\boldsymbol{\eta}}^T,f_i\rangle_\mu^2} = \lVert{\boldsymbol{\eta}}^T\rVert_\mu^2 - \langle{\boldsymbol{\eta}}^T,f_1\rangle_\mu^2.\end{equation}

The eigenfunction $f_1$ corresponding to the eigenvalue 1 can be taken to be a constant vector 1, so

\begin{equation*}\langle{\boldsymbol{\eta}}^T,f_1\rangle_\mu = \sum\limits_{i=1}^n{{\boldsymbol{\eta}}(i)\mu(i)},\end{equation*}

where $\mu(i)=\sum_{v\in V} \mu(v)P_w[v,i]$ . Also,

\begin{equation*}\lVert{\boldsymbol{\eta}}^T\rVert_\mu^2 = \sum\limits_{i=1}^n{{\boldsymbol{\eta}}^2(i)\mu(i)}.\end{equation*}

Using these results in (20), we have

(21) \begin{equation}\sum\limits_{i=2}^n{\langle{\boldsymbol{\eta}}^T,f_i\rangle_\mu^2} = \sum\limits_{i=1}^n{{\boldsymbol{\eta}}^2(i)\mu(i)} - \Bigg(\sum\limits_{i=1}^n{{\boldsymbol{\eta}}(i)\mu(i)}\Bigg)^2 = \mbox{Var}_\mu({\boldsymbol{\eta}}(i)) = \sum\limits_{i=1}^n({\boldsymbol{\eta}}(i) - \bar{{\boldsymbol{\eta}}}_\mu)^2\mu(i),\end{equation}

where $\bar{{\boldsymbol{\eta}}}_\mu=\sum\limits_{i=1}^n{{\boldsymbol{\eta}}(i)\mu(i)}$ is the expected queue occupancy probability of nodes under the stationary distribution $\mu$ . Now, taking the square of the norm of (19) and using (21), we have

(22) \begin{equation}\lVert {\boldsymbol{\eta}}^T(I - P_w) \rVert_\mu^2 \geq (1 - \lambda_2^w)^2 \mbox{Var}_\mu({\boldsymbol{\eta}}(i)).\end{equation}

Using (22) in the square of the norm of (17), we have

(23) \begin{equation}\beta \geq \frac{(1 - \lambda_2^w)}{\lVert \boldsymbol{{J}}^T \rVert_\mu}~\sqrt[]{\mbox{Var}_\mu({\boldsymbol{\eta}}(i))}.\end{equation}

Moreover, as $\sum_{i\in V_s}\boldsymbol{{J}}^2(i)\leq (\sum_{i \in V_s}\boldsymbol{{J}}(i))^2$ , we have

(24) \begin{align}\lVert \boldsymbol{{J}}^T \rVert_\mu&=\sqrt{\sum_{i \in V_s}\boldsymbol{{J}}^2(i) \mu(i) + \left(\sum_{i \in V_s} \boldsymbol{{J}}(i)\right)^2\mu(u_{{\scriptsize s}}) }\leq \sum_{i \in V_s} \boldsymbol{{J}}(i)\sqrt{ \mu_m + \mu(u_{{\scriptsize s}})},\end{align}

where $\mu_m=\max_{i \in V_s} \mu(i)$ .

To get a bound on $\mbox{Var}_\mu({\boldsymbol{\eta}}(i)) = \sum\limits_{i=1}^n({\boldsymbol{\eta}}(i) - \bar{{\boldsymbol{\eta}}}_\mu)^2\mu(i)$ , we consider two nodes whose queue occupancy probability we know precisely: (i) the sink, $u_{{\scriptsize s}}$ , which has ${\boldsymbol{\eta}}(u_{{\scriptsize s}}) = 0$ (as it has no notion of maintaining a queue and it sinks data packets as soon as it receives them), and (ii) a node $u_{\max}$ with maximum queue occupancy probability for a given $\beta$ ; let it be ${\boldsymbol{\eta}}_{\max}^\beta=\max_{u\in V \setminus \{u_{{\scriptsize s}}\}}{\boldsymbol{\eta}}^\beta(u)$ . Now, let $\beta=(1-\delta)\beta^*$ where $\beta^*$ is the critical data rate and $\delta \in (0,1)$ . From (15) we know ${\boldsymbol{\eta}}$ is linear in $\beta$ and ${\boldsymbol{\eta}}_{\max}^{\beta*}=1$ , so ${\boldsymbol{\eta}}_{\max}^\beta=\frac{\beta}{\beta^*}$ , and hence we have ${\boldsymbol{\eta}}_{\max}^\beta=1-\delta$ .

Let $\bar{{\boldsymbol{\eta}}}_\mu=\sum_{i=1}^n {\boldsymbol{\eta}}(i)\mu(i)$ be the expected queue occupancy probability of nodes under the stationary distribution $\mu$ . We can bound the variance $\mbox{Var}_\mu({\boldsymbol{\eta}}(i))$ using the contributions of the nodes $u_{{\scriptsize s}}$ and $u_{\max}$ as follows:

(25) \begin{equation}\mbox{Var}_\mu({\boldsymbol{\eta}}(i)) \geq \left(1-\delta- \bar{{\boldsymbol{\eta}}}_\mu)^2\mu(u_{\max}) + (\bar{{\boldsymbol{\eta}}}_\mu - 0)^2\right)\mu(u_{{\scriptsize s}}) \geq \frac{(1-\delta)^2\mu(u_{\max})\mu(u_{{\scriptsize s}})}{\mu(u_{\max})+\mu(u_{{\scriptsize s}})},\end{equation}

where the last inequality holds as $(1-\delta- \bar{{\boldsymbol{\eta}}}_\mu)^2\mu_{u_{\max}} + (\bar{{\boldsymbol{\eta}}}_\mu - 0)^2\mu_{u_{{\scriptsize s}}}$ achieves its optimum at

\begin{equation*}\bar{{\boldsymbol{\eta}}}_\mu=\frac{(1-\delta)\mu_{u_{\max}}}{\mu_{u_{\max}}+\mu_{u_{{\scriptsize s}}}}.\end{equation*}

Now, using the fact that when $\beta \rightarrow \beta^*$ , $\delta\rightarrow 0$ in (25), and then using the resultant bound on $\mbox{Var}_\mu({\boldsymbol{\eta}}_i)$ and the value of $\lVert \boldsymbol{{J}}^T \rVert_\mu$ (cf. Equation (24)) in (23), we have

(26) \begin{equation}\beta^* \geq \frac{(1 - \lambda_2^w)}{\sum_{i\in V_s} \boldsymbol{{J}}(i)}~\sqrt{\frac{\mu(u_{\max})\mu(u_{{\scriptsize s}})}{(\mu(u_{\max})+\mu(u_{{\scriptsize s}}))(\mu_m+\mu(u_{{\scriptsize s}}))}}.\end{equation}

Now, we know

\begin{equation*}\mu(i)=\frac{\mbox{deg}({i})}{\sum_{u\in V}\mbox{deg}({u})},\end{equation*}

and

\begin{equation*}\frac{d_{\min}}{\sum_{u\in V}\mbox{deg}({u})} \leq \mu(i) \leq \frac{d_{\max}}{\sum_{u\in V}\mbox{deg}({u})},\end{equation*}

where $d_{\min}$ and $d_{\max}$ are the generalized minimum and maximum degrees of the graph, respectively. Using the appropriate bounds on $\mu(i)$ in (26), we have

(27) \begin{equation}\beta^* \geq \frac{(1 - \lambda_2^w)}{\sum_{i\in V_s} \boldsymbol{{J}}(i)}~\frac{\sqrt{d_{\min}\mbox{deg}({u_{{\scriptsize s}}})}}{\left(d_{\max}+\mbox{deg}({u_{{\scriptsize s}}}) \right)},\end{equation}

where $\lambda_2^w$ is the second smallest eigenvalue of the transition matrix of the random walk defined by the weight function w, and $\mbox{deg}({u_{{\scriptsize s}}})$ is the generalized degree of the sink node.

4.3. An upper bound

We also prove an upper bound on $\beta^*$ for the case where $V_s=V \setminus \{u_{{\scriptsize s}}\}$ . Here is the upper bound result.

Proof of Proposition 1. Given any vertex $u \in V$ , recall that its measure is defined as $\rho(u)\,:\!=\,\sum\limits_{v\in V}P_w[ {u,v} ]$ , and for any $U \subset V$ we have $\rho(U)=\sum\limits_{u\in U}\rho(u)$ . Similarly, for the edge boundary $\partial U\,:\!=\,\{(u,v)\,:\, u \in U ,v \notin U\}$ , we have

\begin{equation*}\rho(\partial U)= \sum\limits_{u \in U ,v \notin U}P_w[ {u,v} ].\end{equation*}

Now, let us define constants

\begin{equation*}h(U)\,:\!=\, \frac{\rho(\partial U)}{\rho(U)}, \qquad \hat{h}(G)\,:\!=\,\min\limits_{U \subset V,u_{{\scriptsize s}}\notin U}h(U) \leq h(G),\end{equation*}

where h(G) is the edge expansion of the graph G.

We know that for any given set $U \subset V$ , where $u_{{\scriptsize s}}\notin U$ , the maximum data flow that can move out of this set is the flow across the boundary $\partial U$ , so

(28) \begin{align}\beta \rho(U) &\leq \rho(\partial U)\end{align}

(29) \begin{align}\beta &\leq \min\limits_U h(U) = \hat{h}(G) \leq h(G).\end{align}

Now, for the set $U =V_s=V\setminus \{u_{{\scriptsize s}}\}$ , we have

\begin{equation*}\hat{h}(G))\leq \sum\limits_{u\,:\,u\sim u_{{\scriptsize s}}}\frac{P_w[ {u,u_{{\scriptsize s}}} ]}{n - 1}.\end{equation*}

So from (28),

\begin{equation*}\beta \leq \sum\limits_{u\,:\,u\sim u_{{\scriptsize s}}}\frac{P_w[ {u,u_{{\scriptsize s}}} ]}{n - 1}.\end{equation*}

Hence the upper bound on the critical data rate is given by

(30) \begin{equation}\beta \leq \min\Big\{\hat{h}(G), \sum\limits_{u\,:\,u\sim u_{{\scriptsize s}}}\frac{P_w[ {u,u_{{\scriptsize s}}} ]}{n-1}\Big\}.\end{equation}

Note that our derived upper and lower bounds on the critical data rate relate directly to the two sides of Cheeger’s inequality [Reference Cheeger and Gunning4].

5. Geometric rate of convergence

Next we characterize the rate of convergence of the Markov chain $\big\{ Q_t^{\boldsymbol{{J}}, \beta}\big\}_{t\geq 0}$ for the stable regime, i.e., $\beta< \beta^*$ . In particular, we first prove a general result about the total variation distance between the probability distributions of two Markov chains and their rate of convergence. Then, as a special case of this result, we show that the convergence of Markov chain $\big\{ Q_t^{\boldsymbol{{J}}, \beta}\big\}_{t\geq 0}$ is geometric; i.e., starting from any initial state, the distance from the stationarity reduces exponentially. Note that we drop the superscripts $\boldsymbol{{J}},\beta$ from the Markov chain representation, as we assume a stable data rate value to prove the convergence rate.

Proof of Theorem 3. We first note that our Markov chain $Q_t$ is stochastically ordered (cf. [Reference Lund and Tweedie23]). To understand what this means we define a natural partial order on $(\mathbb{N} \cup \{0\})^{|V \setminus \{u_{{\scriptsize s}}\}|}$ as follows: $\boldsymbol{{x}} \preceq \boldsymbol{{y}}$ if $\boldsymbol{{x}}_v \leq \boldsymbol{{y}}_v$ for all $v \in V \setminus \{u_{{\scriptsize s}}\}$ . A function

\begin{equation*}f \,:\, (\mathbb{N} \cup \{0\})^{|V \setminus \{u_{{\scriptsize s}}\}|} \rightarrow \mathbb{R}\end{equation*}

is said to be increasing if $\boldsymbol{{x}} \preceq \boldsymbol{{y}}$ implies that $f(\boldsymbol{{x}}) \leq f(\boldsymbol{{y}})$ . Given two random processes X and Y supported on $(\mathbb{N} \cup \{0\})^{|V \setminus \{u_{{\scriptsize s}}\}|}$ or $(\mathbb{N} \cup \{0\})^{|V|-1}$ , we say X is stochastically dominated by Y if ${\mathbb{E}\left[{f(X)}\right]}\leq {\mathbb{E}\left[{f(Y)}\right]}$ for every increasing function f. For our Data Collection chain we state the stochastic orderedness property as follows.

We prove this claim by constructing a coupling between the two chains such that each of them performs exactly the same transmission actions. In the case that one of the chains is empty, the transmission action is a dummy action. It is easy to see that stochastic ordering follows naturally for the Data Collection chain.

To use this claim for our irreducible and aperiodic Markov chain $Q_t$ described by the Data Collection Process defined on $(\mathbb{N} \cup \{0\})^{|V|-1}$ having transition matrix $\mathcal{P}$ and a stationary distribution $\pi$ , let us define two other irreducible and aperiodic Markov chains $Q^1_t$ and $Q^2_t$ , each with state space $(\mathbb{N} \cup \{0\})^{|V|-1}$ . Initially, suppose the data is generated in the two chains in a coupled way such that one of them dominates the other; i.e., either $Q^1_0(v) \leq Q^2_0(v)$ for all $v \in V \setminus \{u_{{\scriptsize s}}\}$ or vice versa.

Now consider the coupling $(Q^1_t,Q^2_t)$ on $(\mathbb{N} \cup \{0\})^{|V|-1} \times (\mathbb{N} \cup \{0\})^{|V|-1}$ defined over random sequences

\begin{equation*}\{0,1\} \times \left\{\prod_{v \in V \setminus \{u_{{\scriptsize s}}\}} \Gamma(v)\right\},\end{equation*}

where $\Gamma(v)$ is the set of one-step destinations from the node v, such that both the chains $Q^1_t$ and $Q^2_t$ are populated in a coupled way. Such Markov chains are said to be stochastically ordered chains in queueing theory; they have the property that the Markov chain which dominates the other chain will always maintain dominance over it.

Under this coupling we allow the two chains to run in such a way that any data generation or data transmission decision made by any queue in one chain is followed by the corresponding queue in the other chain as well. To distinguish the newly generated packets in the two chains from the existing ones, we assign colors to the data packets: the existing packets in $Q^1_t$ are colored red and those in $Q^2_t$ are colored blue, while the newly generated packets in both chains are colored green. Moreover, in both chains, green (newly generated) packets have preference in the transmission. Now, let $Q_t^{1,green}(u)$ represent the number of green packets in the queue of a given node u in $Q^1_t$ , and let ${\boldsymbol{\eta}}_u$ be the steady-state queue occupancy probability of the Markov chain $Q_t$ . Since the number of green packets in both chains starts at zero, and the chains are stochastically ordered, the green-packet queue occupancy is always bounded by that of the chain with stationary distribution; i.e.,

\begin{equation*}\mathbb{P}\left[ {Q_t^{1,green}(u)\geq 1} \right]\leq {\boldsymbol{\eta}}_u.\end{equation*}

The same holds for the other chain, $Q^2_t$ .

To ensure that the two chains get coupled, all the red and blue (old) packets in $Q^1_t$ and $Q^2_t$ respectively need to be sunk. We consider the chain $Q^1_t$ ; the same will hold for $Q^2_t$ as well. By our preference in transmission, we know that the probability that red packets move out of the queue in one time step in $Q^1_t$ is equal to the probability that there are no green packets in the given queue, i.e.,

\begin{equation*}1-\mathbb{P}\left[ {Q_t^{1,green}(u)\geq 1} \right].\end{equation*}

Also, we have

\begin{equation*}1-\mathbb{P}\left[ {Q_t^{1,green}(u)\geq 1} \right]\geq 1-{\boldsymbol{\eta}}_u\geq \min_u 1-{\boldsymbol{\eta}}_u\geq 1-{\boldsymbol{\eta}}_{max},\end{equation*}

where ${\boldsymbol{\eta}}_{max}=\max_{u\in V \setminus \{u_{{\scriptsize s}}\}}{\boldsymbol{\eta}}_u$ . Now, let $N^{(red)}$ and $N^{(blue)}$ be the total numbers of red and blue data packets in the chains $Q^1_t$ and $Q^2_t$ , respectively, at the beginning; these are assumed to be finite. Also, let $T_{N^{(red)}}$ and $T_{N^{(blue)}}$ be the times taken by the respective number of packets to get sunk. We have the following lemma bounding this time.

Lemma 4. Given a Data Collection Process on the graph G with $N^{(*)}<\infty$ as the total number of data packets present in the queues of all nodes initially, the time taken by all such packets to reach the sink—call it $T_{N^{(*)}}$ —is bounded as follows:

(31) \begin{equation}\mathbb{P}\left[ {T_{N^{(*)}}\geq \frac{2t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}} (\log 1/\epsilon+1)+N^{(*)} -1} \right]\leq \frac{\epsilon}{2},\end{equation}

where $t_{{\scriptsize hit}}$ is the worst-case hitting time of a random walk on G, and ${\boldsymbol{\eta}}_{\max}$ is the maximum queue occupancy probability at stationarity.

The proof of the lemma proceeds by coupling the Data Collection Process to a random walk with the property that the time taken by this random walk to hit $u_{{\scriptsize s}}$ is at most $N^{(*)}$ steps less than the time for the Data Collection Process to sink all $N^{(*)}$ packets. The result then follows from bounding the hitting time of this random walk.

Proof of Lemma 4. Let us say that the $N^{(*)}$ initial packets are red in color and the new packets generated thereafter are green. Also, let us say that the Markov chain $Q^*_t$ describes the Data Collection Process that began with the set of initial packets at some initial locations.

We now define three $N^{(*)}$ -dimensional processes based on $Q_t^*$ :

• $V^1_t$ : $V^1_t(i)\in V$ is the position of the red packet $p_i$ at step t in $Q^*_t$ .

• $V^2_t$ : Here there are no green packets delaying the red packets, but at each time step each vertex transmits no packet with probability ${\boldsymbol{\eta}}_{\max}$ , the maximum queue occupancy probability of $Q_t^*$ at stationarity. $V^2_t(i)$ again gives the position of the ith red packet at time t.

• $V^3_t$ : In this process, we have only red packets, but all of them have been assigned distinct deterministically chosen ranks, say $1, \ldots, N^{(*)}$ . Under this process, at any queue the choice of packet to send is deterministic: the packet with the lowest rank is chosen for transmission. Other than the choice of packet, all other transmission decisions are similar to $V^2_t$ . $V^3_t(i)$ again gives the position of the ith red packet at time t.

Note that all three processes are absorbed by the state $(u_{{\scriptsize s}}, \ldots, u_{{\scriptsize s}})$ , i.e., when all red data packets get sunk. Let $\tau_i$ be the time to absorption of the process $V^i_t$ , $1 \leq i \leq 3$ . Then for every $k\geq 0$ , using a simple coupling argument we can prove

(32) \begin{equation}\mathbb{P}\left[ {\tau_1 \geq k} \right]\leq \mathbb{P}\left[ {\tau_2 \geq k} \right] = \mathbb{P}\left[ {\tau_3 \geq k} \right].\end{equation}

Now for $V_t^3$ , let us define a collection of random variables $\{Y_t\}_{t\geq 0}$ by constructing what is refered to as a delay sequence in [Reference Leighton, Maggs, Ranade and Rao18]. We set $Y_0 = u_{{\scriptsize s}}$ . Let the packet $p_1$ be the last packet to be absorbed in the sink in $V^3_t$ . If $p_1$ came to the sink from the node u, then $Y_1 = u$ . In this way, we move back $\ell_1\geq 1$ steps till we reach the first queue where $p_1$ was delayed because a lower-ranked packet, say $p_2$ , was preferred for transmission. Let us say this node is $v_1$ , i.e., $Y_{\ell_1} = v_1$ . After this, we set $Y_{\ell_1 + 1}$ to the node from which the preferred packet $p_2$ came to $v_1$ . Now we trace $p_2$ back till we reach the node $v_2$ where it was delayed by another packet $p_3$ . Let $\ell_2$ represent the number of hops encountered during this trace. We continue this process similarly till we reach a packet $p_k$ which was never delayed and can be traced back to its initial position. At this point, we have defined $Y_0, \ldots, Y_{D}$ , with $D = \sum_{i=1}^{k-1} \ell_i+\ell_k$ , where $\ell_i$ is the number of hops traveled by the packet $p_{i}$ till it reached a node where it was delayed by the packet $p_{i+1}$ , and $\ell_k$ is the number of hops traveled by the packet $p_k$ till it reached its initial position $v_k$ .

Now consider the collection of random variables $\{X_t\}_{t = 0}^D$ with $X_t = Y_{D-t}$ for $0 \leq t \leq D$ . From the way the $Y_t$ are constructed, it is clear that $\{X_t\}_{t = 0}^D$ is a random walk beginning at $X_0 = Y_D$ and followed till it hits $u_{{\scriptsize s}}$ . This is a lazy walk that stays at the same vertex with transition matrix ${\boldsymbol{\eta}}_{\max}I + (1 - {\boldsymbol{\eta}}_{\max})\mathcal{P}$ . Let $\tau$ be the time taken for a random walk starting at any node to hit $u_{{\scriptsize s}}$ under the Data Collection Process. We have the following claim relating this hitting time to the absorption time of the process $V^3_t$ .

Proof of Claim 2. Consider a trace of $V_t^3$ and the corresponding random walk $\{X_t\}$ . We will synchronize the progress of a single packet in $V_t^3$ to the progress of $\{X_t\}$ ; i.e., at every time t we will identify a packet $p_i$ and an $0 \leq s \leq k$ such that $X_t = V^3_{t+s}(i)$ . The particular packet chosen for synchronization will change as we move along. The first candidate will be $p_k$ , the last packet in the delay sequence. Note that the last packet $p_k$ in the delay sequence makes its first move at the same time for both $V_t^3$ and $\{X_t\}$ ; i.e., $V^3_0(k)=X_0=v_k$ , where $v_k$ is the initial position of the packet $p_k$ . So both the process and the random walk are synchronized with $s = 0$ in the beginning and will remain synchronized through $\ell_k$ hops; i.e., $V^3_{\ell_{k}}(k)=X_{\ell_{k}}=v_{k-1}$ , where the packet $p_k$ delays the packet $p_{k-1}$ by one unit. After this, our choice of packet to follow will switch to $p_{k-1}$ . Since the random walk follows the progress of the packet $p_{k-1}$ , it is delayed by one unit while the process $V^3_t$ keeps on moving; i.e., the two are synchronized with $s = 1$ . Continuing in this way we eventually synchronize $\{X_t\}$ with $p_1$ with $s = k-1$ . Thus, by the coupling of $V^3_t$ and $X_t$ , we have that

(33) \begin{equation}\mathbb{P}\left[ {\tau_3 \geq L + k-1} \right] \leq \mathbb{P}\left[ {\tau \geq L } \right]. \end{equation}

Since k, the number of packets encountered in the delay sequence, is a random variable bounded above by $N^{(*)}$ , the claim follows.

Since $\{X_t\}$ is a lazy walk, the time taken to hit $u_{{\scriptsize s}}$ is at most

\begin{equation*}\frac{t_{{\scriptsize hit}}}{1 - {\boldsymbol{\eta}}_{\max}},\end{equation*}

where $t_{{\scriptsize hit}}$ is the hitting time for the random walk associated with $\mathcal{P}$ . Thus, by Markov’s inequality,

\begin{equation*}\mathbb{P}\left[ {\tau\geq \frac{2t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}}} \right] \leq\frac{1}{2}.\end{equation*}

Now we consider the probability of a random walk not hitting the sink $u_{{\scriptsize s}}$ in $2(\log 1/\epsilon+1)$ times

\begin{equation*}\frac{t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}};\end{equation*}

i.e., we consider the time

\begin{equation*}\frac{2t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}}(\log 1/\epsilon+1)\end{equation*}

and divide it into $(\log 1/\epsilon+1)$ slots of

\begin{equation*}\frac{2t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}}\end{equation*}

each. By the Markov property of random walks, we know that the random walks in each of these slots are independent. We therefore have the following result:

(34) \begin{equation}\mathbb{P}\left[ {\tau\geq \frac{2t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}}(\log 1/\epsilon+1)} \right] \leq\frac{\epsilon}{2}.\end{equation}

Finally, using (32) in Claim 2 we get the result.

Now, since the chains $Q^1_t$ and $Q^2_t$ operate in parallel, the expected time for the two chains to couple, i.e., for all red and blue packets to get sunk, is the maximum of the time taken by each to get its respective packets sunk. Using Lemma 4 for both the chains, we have the expected time for $Q_t^1$ , $Q_t^2$ to couple, which we denote by $\tau_{couple}^{1,2}=\max\{T_{N^{(red)}},T_{N^{(blue)}}\}$ , as

(35) \begin{equation}\mathbb{P}\left[ {\tau_{couple}^{1,2}\geq \frac{2t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}} \left(\log \frac{1}{\epsilon}+1\right)+\max\big\{N^{(red)},N^{(blue)}\big\}-1} \right]\leq \epsilon.\end{equation}

Note that this expected coupling time result is similar to the delay result of Leighton et al. [Reference Leighton, Maggs, Ranade and Rao18, Reference Leighton, Maggs and Rao19] depicting the pipelining behavior of the Data Collection Process.

Now, to bound the distance between the two chains $Q_t^1$ and $Q_t^2$ we use the following result from Levin et al. [Reference Levin, Peres and Wilmer20].

Lemma 5. (Theorem 5.2, Levin et al. [Reference Levin, Peres and Wilmer20].) Let $\{(X_t,Y_t)\}$ be a coupling with initial states $\boldsymbol{{x}},\boldsymbol{{y}} \in \mathcal{X}$ such that $X_0=\boldsymbol{{x}}$ and $Y_0=\boldsymbol{{y}}$ and coupling time defined as $\tau_{couple}\,:\!=\,\min \{t\,:\,X_s=Y_s \text{ for all } s\geq t\}$ . Then

\begin{equation*}||\mathcal{P}^t[\boldsymbol{{x}},\cdot]-\mathcal{P}^t[\boldsymbol{{y}},\cdot]||_{TV}\leq P_{\boldsymbol{{x}},\boldsymbol{{y}}}\{\tau_{couple}>t\}. \end{equation*}

Let $\boldsymbol{{x}},\boldsymbol{{y}} \in (\mathbb{N} \cup \{0\})^{|V|-1}$ be the initial states of the chains $Q_t^1$ and $Q_t^2$ . Then for $||\mathcal{P}^t[ {\boldsymbol{{x}},\cdot} ]-\mathcal{P}^t[ {\boldsymbol{{y}},\cdot} ]||_{TV}\leq \epsilon$ , using Lemma 5 and the expected coupling time from (35), we have

(36) \begin{equation}||\mathcal{P}^t[ {\boldsymbol{{x}},\cdot} ]-\mathcal{P}^t[ {\boldsymbol{{y}},\cdot} ]||_{TV}\leq 2^{\left(1+\frac{\max\{N^{(red)},N^{(blue)}\}-1}{\frac{2t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}}}\right)}\cdot \left(\frac{1}{2}\right)^{\frac{t}{\frac{2t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}}}}.\end{equation}

Now, assume the stable data rate at which we are running these stochastic processes is $\beta=(1-\delta)\beta^*$ , where $\beta^*$ is the critical data rate and $\delta \in (0,1)$ . From (15) we know ${\boldsymbol{\eta}}$ is linear in $\beta$ . Also, for unstable data rates there exists a node whose steady-state queue occupancy is 1 (see [Reference Luo and Ephremides24] and Lemma 5 of [Reference Georgiadis and Szpankowski7]), i.e., ${\boldsymbol{\eta}}_{\max}^{\beta^*}=1$ , so we have ${\boldsymbol{\eta}}_{\max}^\beta=\frac{\beta}{\beta^*}$ ; hence, $1-{\boldsymbol{\eta}}_{\max}^\beta=\delta$ . Using this in (36) we obtain the desired result.

To use Theorem 3 to prove the geometric ergodicity result (Corollary 1), we pick $\boldsymbol{{y}}$ according to the stationary distribution $\pi$ of the Data Collection Process Markov chain.

Proof of Corollary 1. Let us consider two instances of the Data Collection Process, $Q_t^1$ and $Q_t^2$ , such that the former starts from some finite state $\boldsymbol{{x}}\in (\mathbb{N} \cup \{0\})^{|V|-1}$ and the latter starts from stationarity; i.e., initially all queues in $Q_t^1$ are occupied by some finite number of packets, and those of $Q_t^2$ are filled according to the stationary distribution $\pi$ . Then from Theorem 3 we have

(37) \begin{equation}||\mathcal{P}^t[ {\boldsymbol{{x}},\cdot} ]-\pi||_{TV}\leq 2^{\left(1+\frac{\left(\max\{N^{(\boldsymbol{{x}})},N^{(\pi)}\}-1\right)\delta}{2t_{{\scriptsize hit}}}\right)}\cdot \left(\frac{1}{2}\right)^{\frac{\delta}{2t_{{\scriptsize hit}}}\cdot t },\end{equation}

where $t_{{\scriptsize hit}}$ is the worst-case hitting time of a random walk on the graph, $N^{(\boldsymbol{{x}})}$ and $N^{(\pi)}$ are the total numbers of data packets in state $\boldsymbol{{x}}$ and at stationarity, respectively, and $\delta$ is the relative distance from the critical data rate. If we compare (37) with Definition 2 (Equation (5)), we obtain the geometric ergodicity property for the Markov chain $Q^{\boldsymbol{{J}},\beta}_t$ .

Now, for the random variable $N^{(\pi)}$ , let ${\mathbb{E}\left[{N^{(\pi)}}\right]}$ be its expectation, i.e., the expected number of data packets in $Q^{\boldsymbol{{J}},\beta}_t$ at stationarity, which by Little’s law [Reference Little21] is equal to the product of the data generation rate and the expected latency of a data packet to reach the sink at the stationarity:

\begin{equation*}{\mathbb{E}\big[{N^{(\pi)}}\big]}=\frac{\beta t_{{\scriptsize hit}}}{1-{\boldsymbol{\eta}}_{\max}^\beta}=\frac{(1-\delta)\beta^*t_{{\scriptsize hit}}}{\delta}\end{equation*}

(from linearity of ${\boldsymbol{\eta}}$ and $\beta=(1-\delta)\beta^*$ ), where $\beta^*$ is the critical data rate and $\delta \in (0,1)$ . Now, let

\begin{equation*}\epsilon_{\boldsymbol{{x}}} = \max \left\{\alpha \in [0,1] \,:\, N^{(\boldsymbol{{x}})} \leq \frac{(1-\delta)\beta^*t_{{\scriptsize hit}}}{\delta} \cdot \left(\log \frac{1}{\alpha} + 1\right) \right\}.\end{equation*}

By the definition of $\epsilon_{\boldsymbol{{x}}}$ , we have two regimes: $\epsilon\leq\epsilon_{\boldsymbol{{x}}}$ , where the ${\mathbb{E}\left[{N^{(\pi)}}\right]}$ term is dominant, and $\epsilon>\epsilon_{\boldsymbol{{x}}}$ , where $N^{(\boldsymbol{{x}})}$ is dominant.

For the simple case of $\epsilon>\epsilon_{\boldsymbol{{x}}}$ , using (37) we have

(38) \begin{equation}||\mathcal{P}^t[ {\boldsymbol{{x}},\cdot} ]-\pi||_{TV}\leq 2^{\left(1+\frac{N^{(\boldsymbol{{x}})}\delta}{2t_{{\scriptsize hit}}}\right)}\cdot \left(\frac{1}{2}\right)^{\frac{\delta}{2t_{{\scriptsize hit}}}\cdot t }.\end{equation}

Similarly for $\epsilon\leq\epsilon_{\boldsymbol{{x}}}$ we have

(39) \begin{equation}||\mathcal{P}^t[ {\boldsymbol{{x}},\cdot} ]-\pi||_{TV}\leq 2^{\left(1+\frac{(1 - \delta)\beta^*}{2} (\log 1/\epsilon + 1)\right)} \cdot \left(\frac{1}{2}\right)^{\frac{\delta}{2t_{{\scriptsize hit}}}\cdot t }.\end{equation}

Setting the right-hand side of (39) to $\epsilon$ and solving for t, we get that

(40) \begin{equation}||\mathcal{P}^t[ {x,\cdot} ]-\pi||_{TV}\leq 2 \cdot \left(\frac{1}{2}\right)^{\frac{\delta}{t_{{\scriptsize hit}}((1 - \delta)\beta^* + 2)}\cdot t}.\end{equation}

Combining (38) and (40) gives us the result.

We observe that if we set $\boldsymbol{{x}}$ to $\textbf{0}$ (all zeros), i.e., if all queues are initially empty, then $\epsilon_{\textbf{0}}$ is 1, so only (40) applies, and we determine the mixing time by setting the right-hand side to $1/M$ for a given value of $M > 0$ .

6. Some future directions

The fact that the Data Collection Process mixes fast to its stationary distribution when started from the all-empty setting can be exploited to solve systems of equations such as (16) simply by allowing the process to get close enough to stationarity and then estimating the ${\boldsymbol{\eta}}$ by keeping track of the number of time slots for which each queue is occupied. This opens up the possibilities of distributed algorithms for effective resistance and other problems, some of which we have explored in [Reference Gillani and Bagchi8–Reference Gillani, Bagchi and Ranu10]. Even if we consider graph problems on very large graphs, Laplacian systems of equations become tractable via this method, since random walks can be simulated very fast in modern computing systems for graphs with nodes in the millions (see, e.g., [Reference Sengupta, Bagchi, Ramanath and Bedathur28]).

The key shortcoming of our work is that the Data Collection Process in the subcritical region models only one-sink Laplacian systems of equations. A model that captures the full generality of Laplacian systems of equations will open a more general class of problems that can be attacked algorithmically using this method.