Restricted Random-Walk Matrix

The restricted random-walk matrix, denoted by RRW, has been introduced by Randic (1995). The RRW matrix is defined as 

Randic (1995) used selected invariants (paths of different lengths) of the restricted random-walk matrices for successfully deriving the structure-entropy model of octanes. 

---

A restricted random walk matrix RRW was also proposed [Randic, 1995c] as an AxA dimensional square unsymmetric matrix that enumerates restricted (i.e. selected) random walks over a molecular graph (7. The i-j entry of the matrix is the probability of a random walk starting at vertex v, and ending at vertex v,- of length equal to the topological distance dij between the considered vertices ... 

For acyclic graphs, the restricted random walk matrix is simply the reciprocal walk matrix where Mi = A, M2 = D, and M3 = 1 ... 

Matrices associated with molecular graphs need not necessarily be symmetric even though the underlying molecular graph is described by a symmetric (adjacency) matrix. When one considers restricted random walks on a graph, one arrives at a non-symmetric matrix. If we restrict the number of steps in a walk by the distance between the vertices considered then in general the probability of a successful random walk from i to j is different from the probability of a successful random walk from j to /. In Table 7 we illustrate the restricted random walk matrix for graph Gi. 

The matrix Q can now be transformed into a stochastic matrix, which will be descriptive of the restricted random walks rather than of their generation employing probabilities based on unrestricted walk models. The transformation is performed as follows Let Xt be the largest eigenvalue of the matrix Q, and let Sj be the corresponding left-hand side eigenvector (defined by SjQ = X ). Let A be a diagonal matrix with elements a(i,j) = (/) 8st = [ 1(1),. v,(2),..., (v)] and 8(i,j) is the... 

It should be emphasized that the transition matrix, Eq.(2-91), applies to the time interval between two consecutive service completion where the process between the two completions is of a Markov-chain type discrete in time. The transition matrix is of a random walk type, since apart from the first row, the elements on any one diagonal are the same. The matrix indicates also that there is no restriction on the size of the queue which leads to a denumerable infinite chain. If, however, the size of the queue is limited, say N - 1 customers (including the one being served), in such a way that arriving customers who find the queue full are turned away, then the resulting Markov chain is finite with N states. Immediately after a service completion there can be at most N -1 customers in the queue, so that the imbedded Markov chain has the state space SS = [0, 1,2,. .., N - 1 customers] and the transition matrix ... 

---