The Setting
Fixing a vertex , the local walk moves between adjacent vertices of its neighborhood . Its successive distributions can be compared when their starting vertices complete a triangle with . Lemma 4.1 concerns these comparisons after adding holding steps, with weighted entropy controlling the choice of a common time.
Let be a finite simple graph with positive vertex weights . The neighborhood of a vertex in is the set of vertices adjacent to .✦ For a vertex set and vertices , the vertex mass , neighborhood mass and common neighborhood mass are, respectively, (1) The cross mass of two vertex sets , which may overlap, is the sum of the products of endpoint weights over ordered adjacent pairs with first vertex in and second vertex in : (2)✦ For a real parameter , the growth function is the function on nonnegative real arguments given by (3)✦ The cross mass bound with constant is the condition that, for every and every with , (4)✦
The oriented edge state set is ; is the tail and the head of . The local walk normalizer and edge law are (5) The neighborhood transition kernel is the real matrix on given by (6)✦ The reference weight on the oriented edge set is the function assigning to each edge the weight of its head vertex: (7)✦ For the law (5), assume that has an edge and on every edge.
Kernels and Entropy
A real kernel on a finite state set is a real matrix indexed by .✦ A probability vector on a finite state set is a real vector with nonnegative entries summing to one.✦ A real kernel on is stochastic when each row is a probability vector.✦ A real weight vector on a finite state set is stationary for a real kernel on when the incoming mass at each state equals its weight; the kernel is reversible for when detailed balance holds: (8) For a real kernel on a finite state set , the lazy kernel and the smoothed kernels are the matrices given by (9) Write for the smoothing (9) of the local kernel (6).
For positive reference weights and probability vectors on a finite state set , the weighted row entropy and the total variation distance are the real quantities given by (10) All logarithms are natural, and zero entries contribute zero to the entropy in (10). The mean weighted row entropy of a kernel on a finite state set , with averaging weights and positive reference weights , is the weighted sum of its row entropies given by (11)✦
For the local walk, the average entropy and the mean neighboring row distance are the weighted averages given below, with edge law (5), reference weights (7) and mean entropy (11): (12)
For the cross mass constant , the exceptional mass constant , entropy bound constant and smoothing bound constant are the real numbers given by (13)
The Claim
Theorem 1. Let be a finite simple graph with positive vertex weights. If has an edge and on every edge, then the local transition is reversible for its edge law: (14)✦ For any real kernel on a finite state set and real weights for which is reversible, every nonnegative integer satisfies (15)✦ If and on every edge of , then, for every nonnegative integer , (16)✦ If, in addition, has an edge and for every vertex , then every nonnegative integer satisfies (17)✦ For any finite state set, a stationary probability vector for a stochastic kernel , and positive reference weights , smoothing has monotone mean weighted row entropy: (18)✦ Suppose that has an edge, , the cross mass bound (4) holds, , on every edge, and for every vertex. For every nonnegative integer , (19)✦ Under these hypotheses with , there is a nonnegative integer such that (20)✦
In the paper, the result reads: under positive vertex weights, , the cross mass bound, the presence of an edge, , and on edges, with the constants of (13) and , the local kernels on are reversible with stationary measures and satisfy for every , their averaged weighted row entropies satisfy , and there is a single for which the ordered-triangle average of is at most .
What Is Checked
The local assertions (14), (16), (17), (19) and (20) are stated over the oriented edges of a finite simple graph with positive vertex weights; their edge law, transition and reference weights are (5), (6) and (7). The hypotheses use the masses (1), the cross mass (2), and the growth function (3) in (4).
The general kernel assertions (15) and (18) concern the matrix powers (9) on any finite state set. Detailed balance in (8) alone is assumed in (15); (18) concerns the mean entropy (11) of a stochastic kernel with a stationary probability vector and positive reference weights. The local entropy and variation estimates concern the finite sums (12).