Some Properties of Stochastic Matrices and Non-Homogeneous Markov Chains Generated by Nonlinearities in the Resource Network Model

Abstract

The resource network is a non-linear threshold model where vertices exchange resource in infinite discrete time. The model is represented by a directed weighted graph. At each time step, all vertices send their resources along all output edges following one of two rules. For each vertex, the threshold value for changing the operation rule is equal to the total weight of its outgoing edges. If all vertices have resources less than their thresholds, the network is completely described by a homogeneous Markov chain. If at least one of the vertices has a resource above the threshold, the network is described by a non-homogeneous Markov chain. The purpose of this article is to describe and investigate non-homogeneous Markov chains generated by the resource network model. It is proven that they are strongly ergodic. In addition, stochastic matrices of a special form were studied. A number of new properties were revealed for them. The results obtained were generalized to arbitrary stochastic matrices.

1. Introduction

Many problems from different subject areas are formulated and solved using network models. The study of various dynamic processes in networks, both stochastic and deterministic, often requires the tools of homogeneous and non-homogeneous Markov chains, as well as operating with stochastic matrices. This article is devoted to the investigation of the resource network model with a special kind of graph topology. The problem of studying resource networks belongs to the intersection of several classes of diffusion models. The first one contains various random walk models [1]. This is a large field comprising random walks on lattices [2], on finite connected undirected graphs [3], random walks with local biases [4], etc. In [5], the problems of optimizing flows and finding the shortest paths were solved using an analysis of the large-deviation functions of random walks. Non-linear diffusion was considered in [6]. The non-linearity is of our particular interest because the model presented in this article is also, in general, non-linear. This feature is achieved by threshold switching between the operation rules of vertices. Some vertex, under certain conditions, switches to a non-linear rule and starts functioning similarly to the vertices in the chip-firing game model. This model was proposed quite a long time ago [7]; however, it had not lost its relevance at the present time [8,9,10]. The chip-firing game is often used to describe the sand pile or avalanche model [11] and the similar processes of self-organized criticality [12,13,14,15,16].

In addition to describing physical diffusion processes in networks, similar models appear when simulating information processes, in particular the dynamics of opinions and reaching a consensus in multi-agent systems. At the present time, the classic DeGroot model [17] has many different modifications [18,19,20,21]. Homogeneous and non-homogeneous Markov chains are one of the main tools for describing multi-state systems, processes, and devices [22,23].

Studying such models, researchers are faced with the need to investigate some non-trivial properties of stochastic matrices [24,25,26]. In this paper, we study a resource network model of a special topology based on a non-ergodic graph. Some of its properties are also proven using stochastic matrices of a special form.

The resource network model is a non-linear diffusion model, where the vertices of a directed weighted graph distribute some dimensionless infinitely divisible resource according two rules depending on the resource amount at every time step. The time in the model is discrete; all vertices operate in parallel. The weights of the edges denote their throughput abilities. The vertices can store an unlimited amount of resource. If, at time t, the resource amount in a vertex exceeds the total throughput of its outgoing arcs, this vertex sends the full throughput to each arc; otherwise, it gives out all its resource, dividing it in proportion to the throughput of the arcs. Non-linearity occurs in the model when the total resource exceeds the threshold value, which is why different vertices of the network begin to function according to different rules.

The resource network was first proposed in [27]. Since that time, the theory of resource networks has arisen, and a brief description can be found in [28]. This article also describes two two-threshold modifications of the standard model. Some other models based on the standard resource network were developed by other research teams [29,30].

2. Preliminaries

2.1. Resource Network: Basic Definitions

The resource network is a non-linear flow model operating in discrete time. Vertices of a network synchronously redistribute some infinitely divisible resource. At each time step, every vertex sends the resource to all its neighbors according to one of two rules with threshold switching. The choice of the rule depends on the amount of the resource in the vertex. If the resource at the vertex is greater than the total throughput of its outgoing edges, it sends the full throughput to each edge; otherwise, the vertex gives away the entire resource, distributing it in proportion to the throughput of outgoing edges. A formal description of the operation rules is presented in Section 2.2. Vertices have unlimited capacities.

The structure of the network is given by a directed weighted graph $G=(V,E)$. The edges $e_{ij}=(v_i,v_j)\in E$ have time-constant non-negative weights $r_{ij}$ that determine the throughputs of the corresponding edges.

Matrix $R={\left(r_{ij}\right)}_{n\times n}$ is the throughput matrix, $r_{ij}\in {\mathbb{R}}_{+}$. If edge $e_{ij}$ exists, then $r_{ij}>0$, otherwise $r_{ij}=0$.

The dynamic properties of the network are determined by the rules of resource redistribution, as well as the amount of the total resource and its distribution over the vertices.

Definition 1.

Resources$q_i\left(t\right)$ are nonnegative numbers assigned to vertices $v_i,i=\overline{1,n},$ and changing in discrete time t. The state $Q\left(t\right)$ of a network at time step t is a vector of resource values at each vertex:

$$Q\left(t\right)=(q_1\left(t\right),\dots ,q_n\left(t\right)).$$

Let W be the total resource in a network. The network operation fulfills the conservation law: the resource neither flows in nor flows out:

$$\forall t\sum _{i=1}^n{q}_i\left(t\right)=W.$$

Definition 2.

The flow $f_{ij}\left(t\right)$ is the resource leaving vertex $v_i$ along the edge $e_{ij}$ at time t.

$F\left(t\right)={\left(f_{ij}\left(t\right)\right)}_{n\times n}$ is a flow matrix at time t (between t and $t+1$). Since the throughputs of the edges are limited, $\forall t{f}_{ij}\left(t\right)\le r_{ij}$. Unlike the total resource, the total flow in the network is always limited by the throughputs of the edges.

2.2. Rules of Resource Distribution

First, we introduce two characteristics of the network vertices.

Definition 3.

The values:

$$r_i^{in}=\sum _{j=1}^n{r}_{ji}and{r}_i^{out}=\sum _{j=1}^n{r}_{ij}$$

are the total in- and out-throughputs of vertex $v_i$, respectively. A loop’s throughput, if it exists, is included in both sums.

At time step t, vertex $v_i$ sends to adjacent vertex $v_j$ through edge $e_{ij}$ a resource amount $f_{ij}\left(t\right)$ equal to:

$$f_{ij}\left(t\right)=\left\{\begin{array}{c}{r}_{ij},\mathrm{if}{q}_i\left(t\right)>r_i^{out}\left(\mathrm{rule}\mathbf{1}\right);\hfill \\ \frac{r_{ij}}{r_i^{out}}{q}_i\left(t\right),\mathrm{if}{q}_i\left(t\right)\le r_i^{out}\left(\mathrm{rule}\mathbf{2}\right).\hfill \end{array}\right.$$

(1)

In other words, if the resource amount of a vertex exceeds the total throughput of outgoing edges, then it operates according to Rule 1. In this case, the flow in each edge is equal to its throughput: $f_{ij}\left(t\right)=r_{ij}$; in total, the vertex sends out its total output throughput:

$$\sum _{j=1}^n{f}_{ij}\left(t\right)=\sum _{j=1}^n{r}_{ij}=r_i^{out}.$$

If a vertex has an insufficient amount of resource, then, in accordance with Rule 2, it gives out its entire resource, distributing it to all outgoing edges in proportion to their throughputs. Then,

$$\sum _{j=1}^n{f}_{ij}\left(t\right)=q_i\left(t\right).$$

In accordance with Definition 3, we introduce similar concepts for the total input and output flows:

$$f_i^{out}\left(t\right)=\sum _{j=1}^n{f}_{ij}\left(t\right);$$

$$f_i^{in}(t+1)=\sum _{j=1}^n{f}_{ji}\left(t\right);(f_i^{in}\left(0\right)=0).$$

It follows from Formula (1) that the output flow of vertex $v_i$ at time t is

$$f_i^{out}\left(t\right)=min\{q_i\left(t\right),r_i^{out}\}.$$

(2)

Remark 1.

Note that, if $q_i\left(t\right)=r_i^{out}$, then applying both rules will lead to the same result: $f_i^{out}\left(t\right)=r_i^{out}$. This property is used in Section 3.

The input and output flows of all vertices form the corresponding vectors:

$$F^{out}\left(t\right)=(f_1^{out}\left(t\right),\dots ,f_n^{out}\left(t\right)),F^{in}\left(t\right)=(f_1^{in}\left(t\right),\dots ,f_n^{in}\left(t\right)).$$

The operation of an arbitrary network with n vertices is specified only by its initial state $Q\left(0\right)=(q_1\left(0\right),\dots ,q_n\left(0\right))$ and is given by the formula:

$$Q(t+1)=Q\left(t\right)-F^{out}\left(t\right)+F^{in}(t+1).$$

(3)

Definition 4.

Vector $Q^{*}=(q_1^{*},\dots ,q_n^{*}),$ where

$$\underset{t\to \infty }{lim}{q}_i\left(t\right)=q_i^{*},i=\overline{1,n},$$

(if it exists) is called a limit state of the network.

If the limit state exists, it can be reached in finite time or asymptotically; it depends on the network topology and the initial resource distribution. The limit state is always steady. This means that, if $Q\left(t\right)=Q^{*}$, then $Q\left(t\right)=Q(t+1)=\dots$

If the state of a network $Q^{*}$ is steady, then the flow is also steady.

$F^{*}={\left(f_{ij}^{*}\right)}_{n\times n}$ is a limit flow matrix.

It was proven in [28] that the limit state exists for all topologies of resource networks, excluding cyclic networks (networks in which the GCD of the lengths of all cycles is greater than 1).

Let us consider some properties of resource networks in more detail.

2.3. Basic Properties of Resource Networks

Here, we briefly summarize the results from [28] used in the current research.

We considered resource networks represented by strongly connected graphs with GCD of lengths of all cycles equal to 1.

A random walk on such a graph is described by a regular Markov chain. A regular Markov chain is one that has no transient sets and has a single ergodic set with only one cyclic class [31].

Resource networks based on such graphs are also called regular.

Definition 5.

A resource network is called non-symmetric if it contains at least one vertex $v_i$ for which $r_i^{out}\ne r_i^{in}$.

In fact, of course, in a connected non-symmetric network, there is at least a pair of vertices $v_i,v_j$ that meet this condition. Moreover, they satisfy the inequalities of different signs: $r_i^{out}>r_i^{in},r_j^{out}<r_j^{in}$, or vice versa.

In this section, we consider regular non-symmetric networks.

Let the total network resource W be so small that all vertices at each time step operate according to Rule 2. In this case, at every time step, each vertex gives out the entire resource (see Equation (1)). Then, the vertex resource consists only of the incoming flow, and Equation (3) can be reduced to the formula:

$$Q(t+1)=F^{in}(t+1).$$

(4)

Combining Formulas (1) (for Rule 2) and (4), we obtain

$$q_j(t+1)=\sum _{i=1}^n\frac{r_{ij}}{r_i^{out}}{q}_i\left(t\right).$$

Thus, in matrix form, the network operation is described by the formula:

$$Q(t+1)=Q\left(t\right)R^{\prime },$$

(5)

where $R^{\prime }$ is a stochastic matrix corresponding to the throughput matrix R:

$$R^{\prime }=\left(\begin{array}{ccc}\frac{r_{11}}{r_1^{out}}& \cdots & \frac{r_{1n}}{r_1^{out}}\\ \cdots & \cdots & \cdots \\ \frac{r_{n1}}{r_n^{out}}& \cdots & \frac{r_{nn}}{r_n^{out}}\end{array}\right),$$

(6)

or $R^{\prime }=D^{-1}R$, where $D=\mathrm{diag}(r_1^{out},\dots ,r_n^{out})$.

Let matrix R be such that, for any allocation of the total resource $W=1$, the whole network operates according to Rule 2 (e.g., a sufficient condition for this is the fulfillment of the inequality $r_{ij}\ge 1$ for all nonzero elements of matrix R).

Denote the vectors of the state at time step t and of the limit state for $W=1$ as $Q^1\left(t\right)$ and $Q^{1*}$, respectively.

In this case, the vector $Q^1\left(0\right)$ can be considered as a vector of the initial probability distribution. The network operation is described by Formula (5):

$$Q^1(t+1)=Q^1\left(t\right)R^{\prime }.$$

Hence, the resource distribution process is described by a regular homogeneous Markov chain. Therefore, all the results valid for regular homogeneous Markov chains [31] and stochastic matrices [31,32] can be transferred to the resource network with $W=1$:

Proposition 1.

Let a regular network be given by matrix R and $R^{\prime }$ be the corresponding stochastic matrix obtained by Formula (6), then:

1. 

The limit of the degrees of matrix $R^{\prime }$ exists:

$$\underset{t\to \infty }{lim}{\left(R^{\prime }\right)}^t=R^{\prime }{}^{*};$$

2. 

The limit state $Q^{1*}$ exists and is unique for any initial state.

For an arbitrary state $Q^1\left(t\right)$, the equality holds:

$$Q^1\left(t\right)R^{\prime }{}^{*}=Q^{1*};$$

3. 

The limit matrix $R^{\prime }$ consists of n identical rows equal to vector $Q^{1*}$:

$$R^{\prime }{}^{*}=\mathbf{1}·Q^{1*},$$

where $\mathbf{1}={(1,\dots ,1)}^{\mathrm{T}}$.

4. 

Vector $Q^{1*}$ is a unique left eigenvector of matrices $R^{\prime }$ and $R^{\prime }{}^{*}$ corresponding to eigenvalue $\lambda =1$:

$$Q^{1*}{R}^{\prime }=Q^{1*};Q^{1*}{R}^{\prime }{}^{*}=Q^{1*}.$$

Corollary 1.

The limit flow exists and is unique for any initial state: $F^{in1*}={\left(F^{out1*}\right)}^{\mathrm{T}}=Q^{1*};f_{su{m}^{*}}=1$.

Proposition 2.

Regular resource networks have a global characteristic: the threshold value of the total resource $W=T$:

• If $W<T$, there exists a finite time $t^{\prime }$ such that, for $t>t^{\prime }$, all vertices will operate according to Rule 2;
• If $W=T$, all vertices will operate according to Rule 2—in finite time or asymptotically, depending on the initial resource allocation;
• If $W>T$, there exists a finite time $t^{″}$ such that, for $t>t^{″}$, at least one vertex will operate according to Rule 1.

The resource $W\le T$ is called small; the resource $W>T$ is called large.

Proposition 3.

In a regular resource network, the threshold value T is unique and expressed by the formula:

$$T=\underset{i=\overline{1,n}}{min}\frac{r_i^{out}}{q_i^{1*}}.$$

(7)

Corollary 2.

If $W<T$, then, since some time step $t^{\prime }$, all the vertices give out their resource according to Rule 2, and all of the above results obtained for $W=1$ will also be correct.

The limit state and flow vectors are unique for any initial state and can be found by the formulae:

$$Q^{*}=W·Q^{1*};F^{in*}={\left(F^{out*}\right)}^{\mathrm{T}}=W·Q^{1*};f_{sum}^{*}=W.$$

Let $W=T$. Denote the limit state and flow vectors as $\tilde{Q}$, ${\tilde{F}}^{in}$, and ${\tilde{F}}^{out}$, respectively. Vector $\tilde{Q}$ exists and is unique for any regular network. The flow vectors ${\tilde{F}}^{in}$ and ${\tilde{F}}^{out}$ also exist.

$$\tilde{Q}={\tilde{F}}^{in}={\left({\tilde{F}}^{out}\right)}^{\mathrm{T}}=T{Q}^{1*}.$$

If $W>T$, then starting from the moment $t^{″}$, some vertices will switch to Rule 1.

It was proven that the ability of a vertex to function stably according to Rule 1 depends on the topology and weights of the edges of the graph and does not depend on the initial resource allocation.

Definition 6.

Vertices capable of accumulating resource surpluses (resources in excess of T) are called attractors.

A criterion for the attractiveness of vertices was formulated and proven [28]:

Proposition 4.

The vertex $v_k$ of a regular resource network is an attractor iff

$$k=arg\underset{i=\overline{1,n}}{min}\frac{r_i^{out}}{q_i^{1*}}.$$

Let the non-symmetric network have l attractors, $1\le l<n$, and let these attractors have numbers from 1 to l. Then, the limit vectors for $W=T$ are:

$$\tilde{Q}={\tilde{F}}^{in}={\left({\tilde{F}}^{out}\right)}^{\mathrm{T}}=(r_1^{out},\dots ,r_l^{out},{\tilde{q}}_{l+1},\dots ,{\tilde{q}}_n);{\tilde{q}}_k<r_k^{out},k=\overline{l+1,n}.$$

(8)

For any $W>T$, the $n-l$ last coordinates of a limit state vector ${\tilde{q}}_k$ do not change. The surplus $\Delta W=W-T$ is distributed among attractors:

$$Q^{*}=(r_1^{out}+\Delta w_1,\dots ,r_l^{out}+\Delta w_l,{\tilde{q}}_{l+1},\dots ,{\tilde{q}}_n);\Delta w_1+\dots +\Delta w_l=\Delta W.$$

(9)

The vectors of the limit flow remain the same as for $W=T$ (8):

$${\tilde{F}}^{in}={\left({\tilde{F}}^{out}\right)}^{\mathrm{T}}=(r_1^{out},\dots ,r_l^{out},{\tilde{q}}_{l+1},\dots ,{\tilde{q}}_n).$$

3. Resource Networks with Large Resource and Non-Homogeneous Markov Chains

When $W>T$, due to the operation of some vertices according to Rule 1, the change in the state vector ceases to be described by a homogeneous Markov chain. However, the change in flows still remains within the framework of a homogeneous Markov model. Therefore, for the sake of simplicity, in previous works, for a large resource, not states, but flows were investigated.

Here, we propose a method for studying the functioning of resource networks with a large resource using non-homogeneous Markov chains, i.e., Markov chains with dynamically changing stochastic matrices, and obtain new results.

Let us consider an example of the functioning of a network with a large resource.

Example 1.

Let the resource network be determined by the weighted graph with two vertices shown in Figure 1 with the throughput matrix R:

$$R=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right).$$

The initial state vector is $Q\left(0\right)=(10,0)$.

The functioning of this network is the following:

$t=0:Q\left(0\right)=(10,0);$

$t=1:Q\left(1\right)=(9,1);$

$t=2:Q\left(2\right)=(9,1).$

…

Thus, the stable state of the network is $Q^{*}=(9,1)$.

Let us analyze the law of changing states at the first steps and create the sequence of stochastic matrices defining a non-homogeneous Markov chain for its description. Consider the first vertex at the initial state: $q_1\left(0\right)=10>2=r_1^{out}$. This means that the vertex $v_1$ at time step $t=0$ sends some resource equal to 1 to each of two outgoing edges (one of them is a loop), according to Rule 1, and stores the rest of the resource, equal to 8, in itself. The vertex $v_2$ does not transfer anything, since $q_2\left(0\right)=0$. As a result, we have the state $Q\left(1\right)$, but the same state $Q\left(1\right)$ would be obtained if the loop of the vertex $v_1$ had an arbitrary throughput in segment $[0,9]$. If $r_{11}\in [0,9]$, then $Q\left(1\right)=(9,1)$ remains the same. If $r_{11}>9$, then $Q\left(1\right)$ will change because the vertex $v_1$ will switch from Rule 1 to Rule 2 and will distribute its resource in the other way. Therefore, the value $r_{11}\left(0\right)=9$ is a threshold value of the first vertex for the resource amount $q_1\left(0\right)=10$ with a network topology determined by R.

Consider the new throughput matrix $R\left(0\right)$:

$$R\left(0\right)=\left(\begin{array}{cc}9& 1\\ 1& 0\end{array}\right).$$

As $r_{11}\left(0\right)=9$, then $r_1^{out}\left(0\right)=10$ and $q_1\left(0\right)=r_1^{out}\left(0\right)$, so the vertex $v_1$ uses Rule 2 and sends out its entire resource. The vertex $v_2$ also uses Rule 2, which means that the next state $Q\left(1\right)$ is obtained using Formula (5) with the stochastic throughput matrix $R^{\prime }\left(0\right)$:

$$Q\left(1\right)=Q\left(0\right)R^{\prime }\left(0\right)=(10,0)\left(\begin{array}{cc}\frac{9}{10}& \frac{1}{10}\\ 1& 0\end{array}\right)=(9,1).$$

At the next time step, to save the operation according Rule 2 (i.e., the equality $q_1\left(1\right)=r_1^{out}\left(1\right)$), the loop throughput of vertex $v_1$ needs to be decreased by 1:

$$R\left(1\right)=\left(\begin{array}{cc}8& 1\\ 1& 0\end{array}\right).$$

Then, the next state $Q\left(2\right)$ can be calculated using the same formula with the new stochastic throughput matrix $R^{\prime }\left(1\right)$:

$$Q\left(2\right)=Q\left(1\right)R^{\prime }\left(1\right)=(9,1)\left(\begin{array}{cc}\frac{8}{9}& \frac{1}{9}\\ 1& 0\end{array}\right)=(9,1).$$

As previously, the stable state of the resource network is $Q^{*}=(9,1)$.

We have that

$$Q^{*}=Q\left(0\right)R^{*},$$

where

$$R^{*}=R^{\prime }\left(0\right)R^{\prime }\left(1\right)=\left(\begin{array}{cc}\frac{9}{10}& \frac{1}{10}\\ 1& 0\end{array}\right)\left(\begin{array}{cc}\frac{8}{9}& \frac{1}{9}\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}\frac{9}{10}& \frac{1}{10}\\ \frac{8}{9}& \frac{1}{9}\end{array}\right).$$

$Q^{*}$ is an equilibrium vector. However, the matrix $R^{*}$ itself is not a limit matrix of the (corresponding homogeneous) Markov chain. It is easy to verify this by considering its degrees.

However, $\forall t>1R^{\prime }\left(t\right)=R^{\prime }\left(1\right)$, then $Q(t+1)=Q\left(t\right)R^{\prime }\left(1\right)$ and $Q^{*}=Q^{*}{R}^{\prime }\left(1\right)$.

On the other hand,

$$Q^{*}=Q\left(0\right)R^{\prime }\left(0\right)R^{\prime }\left(1\right)R^{\prime }\left(1\right)R^{\prime }\left(1\right)\dots =Q\left(0\right)R^{\prime }\left(0\right){\left(R^{\prime }\left(1\right)\right)}^{\infty }.$$

Matrix ${\left(R^{\prime }\left(1\right)\right)}^{\infty }$ is a limit of the degrees of a regular stochastic matrix. By definition, it consists of identical rows equal to the limit vector of the probability distribution. This vector, in turn, is a normalized equilibrium vector $Q^{*}$, i.e., it is equal to $(\frac{9}{10},\frac{1}{10})$, and

$${\left(R^{\prime }\left(1\right)\right)}^{\infty }=\left(\begin{array}{cc}\frac{9}{10}& \frac{1}{10}\\ \frac{9}{10}& \frac{1}{10}\end{array}\right).$$

By the property of the limit matrix of a homogeneous Markov chain:

$$R\left(0\right){\left(R^{\prime }\left(1\right)\right)}^{\infty }={\left(R^{\prime }\left(1\right)\right)}^{\infty }$$

and

$$Q^{*}=Q\left(0\right){\left(R^{\prime }\left(1\right)\right)}^{\infty }.$$

Remark 2.

The network operation in the example is very simple. The limit state is reached in one step. However, the behavior of resource networks with a large resource, in the general case, is rather complicated. The corresponding statements can be read in [28]; examples of the operation of networks with different topologies can be found in [33].

This example shows that the functioning of the resource network with the vertices having a large resource amount can be considered as the non-homogeneous Markov chain [34].

In the general case, this transformation for the resource network with the initial state vector $Q\left(0\right)$ and the throughput matrix R can be written as follows:

$$R\to R\left(t\right)={\left\{r_{ij}\left(t\right)\right\}}_{i,j=\overline{1,n}},$$

$$r_{ij}\left(t\right)=\left\{\begin{array}{c}{r}_{ii}+(q_i\left(t\right)-r_i^{out}),\mathrm{if}\{q_i\left(t\right)>r_i^{out}\&i=j\},\hfill \\ r_{ij},\mathrm{otherwise}.\hfill \end{array}\right.$$

(10)

Here, $\forall t\ge 0Q(t+1)=Q\left(t\right)R^{\prime }\left(t\right)$, or

$$Q(t+1)=Q\left(0\right)\prod _{i=0}^t{R}^{\prime }\left(i\right).$$

In the example above, the non-homogeneous Markov chain was strongly ergodic (see [34,35]):

Definition 7.

A non-homogeneous Markov chain with stochastic matrices $P\left(i\right)$ is called strongly ergodic if

$$\underset{t\to \infty }{lim}\prod _{i=1}^{t}P\left(i\right)=\mathbf{1}·{\pi }^{\mathrm{T}},$$

where 1 is a column vector of n units and π is some probability vector.

In general, if the limit state and the limit matrix exist, they can be found as

$$Q^{*}=Q\left(0\right)\underset{t\to \infty }{lim}\prod _{i=0}^t{R}^{\prime }\left(i\right)=Q\left(0\right)R^{\prime }{}^{\infty },$$

where $R^{\prime \infty }=\mathbf{1}·Q^{1**}$ ($Q^{1**}$ is some vector of the distribution of the resource $W=1$).

This equality holds for all strongly ergodic non-homogeneous Markov chains.

Let us turn to the study of strong ergodicity and the description of the limit characteristics of resource networks with the transient and regular components.

4. Study of Processes in Transient Components of Two-Component Resource Networks

Consider a resource network with two strongly connected components, such that there are only edges from the first one (called the transient component, with $n_1$ vertices) to the second one (called final, with $n_2$ vertices). Let n be the total number of vertices in the network (Figure 2).

Theorem 1.

There exists a finite time moment $t^{\prime }$ such that, for $t>t^{\prime }$, all vertices of the transient component operate according to Rule 2.

Proof. 

We assumed there should always exist at least one vertex (say, $v_s$) in the transient component that has an edge to the final component. Otherwise the network graph is not even weakly connected. If so, we can analyze weakly connected components independently.

Suppose there is an excessive amount of resource in an arbitrary vertex $v_k$ of the transient component at time step t. Since the transient component is strongly connected, there exists a simple path $v_k=v_{i_0}\to v_{i_1}\to \cdots \to v_{i_p}=v_s$. In that case, the resource equal to $c_1^k=r_{i_0{i}_1}$ will be transferred from $v_{i_0}$ to $v_{i_1}$ at the time moment $t+1$. This means vertex $v_{i_1}$ will contain at least $c_1^k$ resource. Next, at the moment $t+2$, vertex $v_{i_1}$ will transfer at least $c_2^k=min\{r_{i_1{i}_2},r_{i_1{i}_2}^{\prime }·c_1^k\}$ resource to the vertex $v_{i_2}$. In that case, at the moment $t+2$, vertex $v_{i_2}$ will contain at least $c_2^k$ resource. If we continue this process, we will obtain that vertex $v_{i_p}$ will contain at least $c_p^k$ resource at the moment of time $t+p$. Finally, at least $c_{\mathrm{fin}}^k=min\{r_{s\mathrm{fin}},r_{s\mathrm{fin}}^{\prime }·c_p^k\}$ resource will go to the final component at the moment $t+p+1$ (where $r_{s\mathrm{fin}}$ is some edge from $v_s$ to some vertex in the final component). Therefore, if there was excessive resource in vertex $v_k$ at moment t, then, during time period $[t,t+n_1]$ (more precisely, $[t,t+p+1]$), at least $c_{\mathrm{fin}}^k$ resource will be transferred to the final component. It is important to note that $c_{fin}^k$ depends on nothing but the fact that there was an excessive amount of resource in vertex $v_k$.

Similar reasoning can be applied to any other vertex with excessive resource $v_l$. Let us define $\epsilon =\underset{l\in \overline{1,n_1}}{min}{c}_{\mathrm{fin}}^l>0$. Then, the following holds: if, at some time moment t, an arbitrary vertex contained an excessive amount of resource, then by the time moment $t+n_1$, at least $\epsilon$ resource will be transferred to the final component.

The proof now goes by contradiction: Suppose there is no moment $t^{\prime }$ from which the transient component operates according to Rule 2 all the time. In other words, suppose there exists an infinite sequence of time moments $\{t_1^{\prime },t_2^{\prime },\dots \}$ such that at least one vertex in the transient component contains excessive resource at each of these moments. Without loss of generality, assume that $\forall i>0t_{i+1}^{\prime }-t_i^{\prime }>n_1$. Hence, at least $\epsilon$ resource will be transferred to the final component at each of the time intervals $\{[t_1^{\prime },t_1^{\prime }+n_1],[t_2^{\prime },t_2^{\prime }+n_1],\dots \}$. The total amount of transferred resource is at least ${\displaystyle \sum _{i=1}^{\infty }}\epsilon =\infty$. The contradiction is now obvious since the resource network contains only a finite amount of resource by definition. □

Theorem 1 states that every possible resource distribution in the transient component sooner or later reduces to the linear case. The following theorem shows how the network behaves in the linear case.

Theorem 2.

If the entire two-component network operates according to Rule 2, then the total amount of resource in the transient component tends to zero as time goes to infinity.

Proof. 

Let the network be defined by the matrix:

$$R=\left[\begin{array}{cc}{R}_1& R_2\\ 0& R_3\end{array}\right],$$

where $R_1\in {\mathbb{R}}^{n_1\times n_1}$ and $R_3\in {\mathbb{R}}^{n_2\times n_2}$ are nonzero square blocks corresponding to the edges of the transient and the final components, respectively; $R_2\in {\mathbb{R}}^{n_1\times n_2}$ is a rectangle block corresponding to the edges from the transient to the final component. The corresponding stochastic matrix is of the following form:

$$R^{\prime }=\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ 0& R_3^{\prime }\end{array}\right].$$

Whenever the network operates according to Rule 2, its next state is obtained according to Formula (5).

If the network is operated according to Rule 2 for every $t\ge 0$, then the following holds:

$$Q(t+1)=Q\left(0\right){\left(R^{\prime }\right)}^t.$$

(11)

Passing to the limit as $t\to \infty$ (this limit always exists since the final component is regular):

$$Q^{*}=Q\left(0\right){R^{\prime }}^{\infty }.$$

(12)

Consider powers of matrix $R^{\prime }$:

$${\left(R^{\prime }\right)}^2=\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ 0& R_3^{\prime }\end{array}\right]\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ 0& R_3^{\prime }\end{array}\right]=\left[\begin{array}{cc}{\left(R_1^{\prime }\right)}^2& R_1^{\prime }{R}_2^{\prime }+R_2^{\prime }{R}_3^{\prime }\\ 0& {\left(R_3^{\prime }\right)}^2\end{array}\right],$$

(13)

$$\begin{array}{c}{\left(R^{\prime }\right)}^3=\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ 0& R_3^{\prime }\end{array}\right]\left[\begin{array}{cc}{\left(R_1^{\prime }\right)}^2& R_1^{\prime }{R}_2^{\prime }+R_2^{\prime }{R}_3^{\prime }\\ 0& {\left(R_3^{\prime }\right)}^2\end{array}\right]=\hfill \\ \hfill =\left[\begin{array}{cc}{\left(R_1^{\prime }\right)}^3& {\left(R_1^{\prime }\right)}^2{R}_2^{\prime }+R_1^{\prime }{R}_2^{\prime }{R}_3^{\prime }+R_2^{\prime }{\left(R_3^{\prime }\right)}^2\\ 0& {\left(R_3^{\prime }\right)}^3\end{array}\right],\end{array}$$

(14)

and so on.

It follows from (12) that the first $n_1$ components of $Q^{*}$ are defined entirely by the first $n_1$ columns of ${R^{\prime }}^{\infty }$. Therefore, only the left-side blocks of powers of $R^{\prime }$ are of our interest. Since we can interpret $R_1^{\prime }$ as part of the stochastic matrix corresponding to the transient component of a Markov chain, it is easy to prove then (using Theorem 3.1.1 of [31]) that

$$\underset{t\to \infty }{lim}{\left(R_1^{\prime }\right)}^t=0.$$

It follows that, for each possible initial state $Q\left(0\right)$, such that the network operates according to Rule 2 forever, the limiting state will contain only zeros in the first $n_1$ components (see (12)). The statement of the theorem thus follows. □

The following theorem generalizes the two previous ones to the case of an arbitrary total resource amount in the network.

Theorem 3.

In the two-component resource network, for any value and initial distribution of the network total resource, the total amount of resource in the transient component tends to zero as time goes to infinity.

Proof. 

Let the network be defined by the matrix:

$$R=\left[\begin{array}{cc}{R}_1& R_2\\ 0& R_3\end{array}\right],$$

(15)

and the resource is greater than the threshold value. Then, the resource distribution is described by a non-homogeneous Markov chain with a stochastic matrix:

$$R^{\prime }\left(t\right)=\left[\begin{array}{cc}{R}_1^{\prime }\left(t\right)& R_2^{\prime }\left(t\right)\\ 0& R_3^{\prime }\left(t\right)\end{array}\right].$$

(16)

The network operates according to the formula:

$$Q(t+1)=Q\left(t\right)R^{\prime }\left(t\right),\mathrm{or}$$

$$Q(t+1)=Q\left(0\right)\prod _{i=1}^t{R}^{\prime }\left(i\right).$$

(17)

By Theorem 1, there is such a moment $t^{\prime }$, starting from which the transition component begins to function according to Rule 2. Then, for all $t>t^{\prime }$, the matrix $R^{\prime }\left(t\right)$ can be presented as matrix $R^{″}\left(t\right)$, where

$$R^{″}\left(t\right)=\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ 0& R_3^{\prime }\left(t\right)\end{array}\right].$$

Thus, Formula (17) can be written as follows:

$$Q(t+1)=Q\left(0\right)\prod _{i=1}^{t^{\prime }}{R}^{\prime }\left(i\right)\prod _{j=t^{\prime }+1}^t{R}^{″}\left(j\right).$$

In the second product, the block $R_1^{\prime }$ is constant; therefore, the first m columns tend to zero. Then, in the entire product, the first m columns tend to zero as time goes to infinity. □

Thus, for any total resource and any of its initial distribution in a two-component resource network, the entire resource will pass into the final component.

5. Some Properties of Stochastic Matrices

The above results can be generalized to arbitrary stochastic matrices, and some new properties can be derived. Theorem 2 implies the validity of the following theorem.

Theorem 4.

For any rectangular stochastic matrix $R^{\prime }=[R_1^{\prime },R_2^{\prime }]\in {\mathbb{R}}^{m\times n}$, $m<n,$ where $R_1^{\prime }\in {\mathbb{R}}^{m\times m}$ is a square block, $R_2^{\prime }\in {\mathbb{R}}^{m\times (n-m)}$ is a rectangular block; if $R_2\ne 0$, the rectangular matrix ${(I-R_1^{\prime })}^{-1}{R}_2^{\prime }\in {\mathbb{R}}^{m\times (n-m)}$ is stochastic.

Proof. 

Let us relatea rectangular matrix to a square one as follows:

$$R^{″}=\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ 0& I\end{array}\right],$$

Consider the powers of the matrix $R^{″}$:

$$R^{″}{}^2=\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ 0& I\end{array}\right]\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ 0& I\end{array}\right]=\left[\begin{array}{cc}{R}_1^{{}^{\prime }2}& R_1^{\prime }{R}_2^{\prime }+R_2^{\prime }\\ 0& I\end{array}\right],$$

$$\begin{gathered} R^{″}{}^3=\left[\begin{array}{cc}{R}_1^{{}^{\prime }2}& R_1^{\prime }{R}_2^{\prime }+R_2^{\prime }\\ 0& I\end{array}\right]\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ 0& I\end{array}\right]=\left[\begin{array}{cc}{R}_1^{{}^{\prime }3}& R_1^{{}^{\prime }2}{R}_2^{\prime }+R_1^{\prime }{R}_2^{\prime }+R_2^{\prime }\\ 0& I\end{array}\right], \\ ⋮ \\ {R}^{″}{}^t=\left[\begin{array}{cc}{R}_1^{{}^{\prime }t}& R_1^{{}^{\prime }t-1}{R}_2^{\prime }+R_1^{{}^{\prime }t-2}{R}_2^{\prime }+\dots +R_1^{\prime }{R}_2^{\prime }+R_2^{\prime }\\ 0& I\end{array}\right]. \end{gathered}$$

For $t\to \infty$, there is $R_1^{{}^{\prime }\infty }=0$ in the upper left block, as $R_1^{\prime }$ is the block of stochastic matrix $R^{\prime }$. Furthermore, there is the sum of a infinite decreasing geometric progression with the denominator $R_1^{\prime }$ in the upper right block:

$$R^{″}{}^{\infty }=\left[\begin{array}{cc}0& {(I-R_1^{\prime })}^{-1}{R}_2^{\prime }\\ 0& I\end{array}\right].$$

Here, mentioning that $R_2^{\prime }\ne 0$ and $R_1^{{}^{\prime }\infty }=0$, the inverse matrix ${(I-R_1^{\prime })}^{-1}$ exists always according to Theorem 1.11.1 in [31]. The matrix $R^{″}$ is stochastic; therefore, the matrix $R^{″}{}^{\infty }$ is stochastic. Thus, if $R_2^{\prime }\ne 0$, the matrix ${(I-R_1^{\prime })}^{-1}{R}_2^{\prime }$ is stochastic. □

The simple example demonstrates how Theorem 4 works.

Example 2.

Consider the stochastic vector:

$$R^{\prime }=(r_1,r_2,r_3,r_4),r_1+r_2+r_3+r_4=1.$$

Let us split it into two blocks, so that the first block $R_1^{\prime }=\left(r_1\right)$ is square dimensioned $1\times 1$, $R_2^{\prime }=(r_2,r_3,r_4).$

Thus, according to the proven Theorem 4, the vector ${(1-R_1)}^{-1}{R}_2$ is also stochastic. Actually:

$${(1-r_1)}^{-1}(r_2,r_3,r_4)=\left({\displaystyle \frac{1}{r_2+r_3+r_4}}\right)(r_2,r_3,r_4).$$

An important generalization follows directly from Theorem 4.

Theorem 5.

For any square stochastic matrix $R^{\prime }$ and for any arbitrary partition into blocks:

$$R^{\prime }=\left[\begin{array}{cc}{R}_1^{\prime }& R_2^{\prime }\\ R_3^{\prime }& R_4^{\prime }\end{array}\right],$$

where $R_1^{\prime }$ and $R_4^{\prime }$ are square blocks; if $R_2^{\prime }\ne 0$, the rectangular matrix ${(I-R_1^{\prime })}^{-1}{R}_2^{\prime }$ is stochastic.

6. Limit States in Two-Component Resource Networks and the Strong Ergodicity of Non-Homogeneous Markov Chains

In Section 4, it was established that, whatever the initial resource distribution is, all of the resource will be transferred to the final component in infinite time.

According to Proposition 2 and Corollary 2, if a resource network is regular, then in the case of a small resource, there exists a unique limit state that does not depend on the initial distribution.

In the case of a large resource, there also always exists a limit state, but if there are several attractor vertices (Definition 6), then the limit state might not be unique for every initial state. However, the limit state is always of the form (9). What interests us is whether an analogy can be drawn with our case of a two-component network. The following theorems answer this question.

Suppose that the final component of the resource network is regular. Let T (Formula (7)) be the threshold value of the total resource for the final component.

Theorem 6.

If $W\le T$, then there exists a unique limit state that depends neither on the initial distribution of the total resource $Q\left(0\right)$ nor on blocks $R_1$ and $R_2$ of capacity matrix R.

Proof. 

The statement of the theorem means that there is no difference what the topology of the transient component is and what edges lead from the transient to the final component, if the resource amount is small.

If $W<T$, it is assumed that there is a point of time from which the entire network operates according to Rule 2. Without loss of generality, suppose that the entire network operates according to Rule 2 from the first moment.

One can deduce from Equations (13) and (14) that an arbitrary power of $R^{\prime }$ has the form:

$${\left(R^{\prime }\right)}^N=\left[\begin{array}{cc}{\left(R_1^{\prime }\right)}^N& {R^{\prime }}_{2\left(N\right)}\\ 0& {\left(R_3^{\prime }\right)}^N\end{array}\right],$$

(18)

where

$${R^{\prime }}_{2\left(N\right)}=\sum _{t=1}^N{\left(R_1^{\prime }\right)}^{N-t}{R}_2^{\prime }{\left(R_3^{\prime }\right)}^{t-1}.$$

(19)

For instance,

$$\begin{array}{c}{R^{\prime }}_{2\left(1\right)}={\left(R_1^{\prime }\right)}^0{R}_2^{\prime }{\left(R_3^{\prime }\right)}^0=R_2^{\prime },\\ {R^{\prime }}_{2\left(2\right)}=R_1^{\prime }{R}_2^{\prime }+R_2^{\prime }{R}_3^{\prime },\\ {R^{\prime }}_{2\left(3\right)}={\left(R_1^{\prime }\right)}^2{R}_2^{\prime }+R_1^{\prime }{R}_2^{\prime }{R}_3^{\prime }+R_2^{\prime }{\left(R_3^{\prime }\right)}^2,\end{array}$$

and so on.

According to Theorem 11.1 of [32], there exists a limit $\underset{N\to \infty }{lim}{\left(R^{\prime }\right)}^N={R^{\prime }}^{*}$. Combining this fact with the statement of Theorem 2, we obtain that the limit must have the form

$${R^{\prime }}^{*}=\left[\begin{array}{cc}0& R_{2*}^{\prime }\\ 0& {R^{\prime }}_3^{*}\end{array}\right],$$

where

$$R_{2*}^{\prime }=\underset{N\to \infty }{lim}{R}_{2\left(N\right)}^{\prime };{R^{\prime }}_3^{*}=\underset{N\to \infty }{lim}{R^{\prime }}_3^N.$$

Multiplying the limit stochastic matrix by itself is idempotent (i.e., ${R^{\prime }}^{*}{R^{\prime }}^{*}={R^{\prime }}^{*}$). That means the following:

$${R^{\prime }}^{*}{R^{\prime }}^{*}=\left[\begin{array}{cc}0& R_{2*}^{\prime }\\ 0& {R^{\prime }}_3^{*}\end{array}\right]\left[\begin{array}{cc}0& R_{2*}^{\prime }\\ 0& {R^{\prime }}_3^{*}\end{array}\right]=\left[\begin{array}{cc}0& R_{2*}^{\prime }{R^{\prime }}_3^{*}\\ 0& {\left({R^{\prime }}_3^{*}\right)}^2\end{array}\right]=\left[\begin{array}{cc}0& R_{2*}^{\prime }\\ 0& {R^{\prime }}_3^{*}\end{array}\right]={R^{\prime }}^{*}.$$

The latter equation implies

$$R_{2*}^{\prime }{R^{\prime }}_3^{*}=R_{2*}^{\prime }.$$

(20)

Being a limit of the power of a regular stochastic matrix, ${R^{\prime }}_3^{*}$ consists of equal rows. Its rank is 1. Moreover, whenever any stochastic matrix is right-multiplied by ${R^{\prime }}_3^{*}$, the result will also consist of the same rows. That being said, the matrix $R_{2*}^{\prime }$ consists of the same rows as ${R^{\prime }}_3^{*}$.

Suppose that ${R^{\prime }}_3^{*}$ consists of rows $\left({r^{\prime }}_3^{*}\right)$. Then, ${R^{\prime }}^{*}$ has the form

$${R^{\prime }}^{*}=\left[\begin{array}{cc}0& {r^{\prime }}_3^{*}\\ \cdots & \cdots \\ 0& {r^{\prime }}_3^{*}\end{array}\right].$$

It is obvious that ${R^{\prime }}^{*}$ is of rank 1. It follows that the image of this linear operator (see Equation (12)) is determined solely by the initial amount of resource W.

The resource $W=T$ is a limit case for a small resource. By Proposition 2, for some initial states, two limit transitions are required to prove the theorem: the first one is for the transition of all vertices to Rule 2; then, the above reasoning is applied. □

Theorem 7.

If $W>T$, then for every initial state $Q\left(0\right)$, there exists a limit state $Q^{*}$. If, additionally, the final component contains only one attractor vertex, then this limit state depends only on W, i.e., it depends neither on the initial distribution of the total resource and on blocks $R_1$ and $R_2$ of capacity matrix R.

Proof. 

In this case, it is assumed that there is a point of time from which at least one vertex of the network contains an excessive amount of resource.

It follows from Theorem 1 that there is a moment from which the entire transient component operates according to Rule 2. That means that all of the excessive resource is located in the final component (at least for sufficiently large moments of time). After this fact is established, the proof in the case $W>T$ is made in analogy with the case $W\le T$. The main difference is that ${R^{\prime }}_3^{*}$ is not a limit of the powers of a single matrix, but a limit of the products of different matrices. However, it is known from the previous works [28] that this limit of the products of matrices exists for every initial condition. In the case where there is only one attractor vertex in the final component, this limit of products depends only on W. Thus, the statement of the theorem follows. □

Example 3.

Let us consider the two-component resource network shown in Figure 2. The edge weights are given by the matrix:

$$R=\left(\begin{array}{ccccccccc}1& 1& 0& 1& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0& 1\\ 0& 1& 1& 0& 0& 0& 0& 0& 1\\ ine0& 0& 0& 0& 0& 2& 1& 0& 1\\ 0& 0& 0& 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 0& 0& 1& 0& 1\\ 0& 0& 0& 0& 3& 0& 0& 0& 0\end{array}\right).$$

(21)

Let $W=14$ and the initial state be given by vector $Q\left(0\right)=(5,4,3,2,0,0,0,0,0)$. In this case, the entire resource is concentrated in the transient component.

The limit state is $Q^{*}=(0,0,0,0,2.4,1.2,6.4,1.6,2.4)$.

The functioning of the network is shown in Figure 3.

On the graph, it can be seen how the resource flows from the transient component to the vertices of the final component.

If $W>T$, then matrix sequences $R^{\prime }\left(t\right),t=0,1,\dots ,$ differ for different initial resource distributions $Q\left(0\right)$. The infinite products of these matrices tend to the limit matrices $R^{{}^{\prime }\infty }\left(Q\left(0\right)\right)$ (further, we omit the argument $\left(Q\right(0\left)\right)$).

Example 1 shows that, for at least some regular resource networks with $W>T$, there exist two stochastic matrices transforming the initial vector into the limit one:

$$Q^{*}=Q\left(0\right){R^{\prime }}^{*};Q^{*}=Q\left(0\right){R^{\prime }}^{\infty }.$$

(22)

It is easy to see that such matrices exist for any regular, as well as two-component networks and for any initial state $Q\left(0\right)(W>T)$.

The first matrix ${R^{\prime }}^{*}$ is obtained from matrix R defined by Formula (10), where $q_i\left(t\right)=q_i^{*}$; here, $q_i^{*}$ are the components of a limit vector $Q^{*}$. This matrix has different rows and is not a limit matrix. However, the limit matrix ${R^{\prime }}^{\infty }$ is a limit of the powers of the stochastic matrix ${R^{\prime }}^{*}$.

$${R^{\prime }}^{\infty }=\underset{t\to \infty }{lim}{\left({R^{\prime }}^{*}\right)}^t.$$

(23)

Matrix ${R^{\prime }}^{\infty }$ is unique for every $Q\left(0\right)$ and consists of n normalized vectors $Q^{*}$.

Therefore, the following theorem is true.

Theorem 8.

For a two-component resource network, if $W>T$, then, for every initial state, the non-homogeneous Markov chain with stochastic matrices $R^{\prime }\left(t\right)$ is strongly ergodic.

7. Discussion

The results presented in the article can be divided into three areas: two-component resource networks, stochastic matrices, and non-homogeneous Markov chains.

The main results concerning two-component resource networks were stated in the Theorems 6 and 7. It was proven that the two-component resource network with a regular final component is globally asymptotically stable, if $W\le T$ or $W>T$ and there is a single attractor vertex. If there are several attractor vertices in a final component, the resource surplus is distributed among attractors (Formula (9)) in a unique way described by Formula (22).

The study of the behavior of two-component networks made it possible to prove a number of non-trivial statements about stochastic matrices, as well as about non-homogeneous Markov chains.

In our opinion, Theorems 4–6 deserve special attention, since they formulate the interesting properties of stochastic matrices. These properties are universal and applicable to any stochastic matrices, without reference to the resource network model.

Theorem 8 states that the non-homogeneous Markov chain describing the operation of the two-component resource network with a regular final component for $W>T$ is strongly ergodic. This implies that the non-homogeneous Markov chain describing the regular resource network with $W>T$ is definitely strongly ergodic.

The non-homogeneous Markov chain corresponding to the given network and given initial distribution of resource $W>T$ is defined by Formula (10). Two matrices that transform the initial distribution into the limit distribution are presented in Formula (22), and their relationship is in Formula (23).

In the future, we plan to obtain an analytical formula for resource allocation among attractors in the limit state for a network with several attractors and $W>T$. This problem still remains open.

8. Conclusions

The resource network model is described by very simple operation rules; however, it is capable of generating complex behavior. Moreover, the network turned out to be a good tool for studying the properties of stochastic matrices and Markov chains.

In our team, two extensions of resource networks were proposed and studied: a network with the capacity limitations of attractor vertices and a network with greedy vertices [28].

Based on the resource network defined by a regular grid, a model of the distribution of pollutants on the surface of a reservoir was developed [36].

In our future research, we plan to study new modifications of resource networks, such as networks with dynamic throughputs. Using such a model, it will be possible to search for bottlenecks in the distribution of traffic in networks of various kinds—from transport to telecommunications.