The Random-Walk Markov Matrix

Walks can be generated from powers of the vertex-adjacency matrix A (see Section 2.1), and this may be viewed as an identification of the distribution for equipoise random walks. Similarly, the distribution for simple random walks can be generated by powers of a Markov matrix. The random-walk Markov matrix, denoted by MM, of a vertex-labeled connected graph G is a real unsymmetrical V x V matrix whose elements are probabilities for the associated individual steps (Klein etal.,2004)  

Then [MM j j is the probability for a X.-step random walk beginning at vertex j and ending at vertex i. 

The Markov matrix MM may be also expressed in terms of the vertex-adjacency matrix A and the inverse diagonal matrix A  

Several unsymmetrical graph-theoretical matrices such as the Cluj matrices (see Section 5.10) and the layer matrices (Diudea and Ursu, 2003) have also been proposed. However, the Markov matrix has a much wider field of application (e.g., Ross, 1977). It should be noted that the (simple) random walks have been extensively studied in mathematics and physics (Doyle and Snell, 1984), but only occasionally in chemistry, as has already been noted. 

Algebraic manipulations with the Markov matrix appear to be rewarding in chemical graph theory. For example, the combination of the Markov matrix MM and the diagonal matrix with elements 

---

The distribution of simple random walks can be generated by powers of the random walk Markov matrix, which is a weighted adjacency matrix belonging to the class of stochastic matrices, defined as [Klein, Palacios et al, 2004]... 

The row sum of the kth power of the random walk Markov matrix MM, called random walk count, is a local vertex invariant based on simple random walks defined by analogy with the atomic walk count ... 

Other important weighted vertex adjacency matrices are the extended adjacency matrices, the edge-Wiener matrix, —> edge-Cluj matrices, —> edge-Szeged matrices, and the random walk Markov matrix. 

Most of the graph-theoretical matrices are symmetrical, whereas some of them are un-symmetrical. Examples of unsymmetrical matrices are —> Szeged matrices, —> Cluj matrices, random walk Markov matrix, —> combined matrices such as the topological distance-detour distance combined matrix, and some weighted adjacency and distance matrices. 

Random walk Markov matrix MM and its power matrices (order 2,3,4,5) for2,3-dimethylhexane. VSj and CSj are the matrix row and column sums, respectively they give the random walk counts. 

Exercise. The transition matrix (5.5) for the random walk with persistence acts in too large a space, because only the states with m = n + 1 have a meaning. Find a simpler reduction of the random walk with persistence to a Markov chain by adding a second variable Y2 which takes only two values. 

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 ... 

Each off-diagonal element [MMq,j of the feth power of the Markov matrix is interpreted as the probability for a simple random walk of length k beginning at vertex j to end at vertex i each diagonal element [MM ] is the probability for a simple random walk starting at vertex i to return to vertex i, after k steps. 

So far we have considered a single mesoscopic equation for the particle density and a corresponding random walk model, a Markov process with continuous states in discrete time. It is natural to extend this analysis to a system of mesoscopic equations for the densities of particles Pi(x,n), i = 1,2,..., m. To describe the microscopic movement of particles we need a vector process (X , S ), where X is the position of the particle at time n and S its state at time n. S is a sequence of random variables taking one of m possible values at time n. One can introduce the probability density Pj(jc, n) = 9P(X < x,S = i)/dx and an imbedded Markov chain with the m x m transition matrix H = (/i ), so that the matrix entry corresponds to the conditional probability of a transition from state i to state j. 

The feature matrix, F, found by Diffusion Maps contains the diffusion distances between data points after t time steps. The diffusion distance can be found by computing a Markov random walk on a weighted graph G = V, E), with the vertex set... 

---