The Setting
The tail in Lemma 5.2 consists of steps of a finite Markov chain whose reverse transition probability is small relative to a prescribed weight at the starting state.
Let be a finite state set. A real matrix kernel on is a real matrix with rows and columns indexed by .✦ A probability vector on is a real function satisfying (1)✦ A stochastic kernel on is a real matrix kernel whose every row is a probability vector in the sense of (1).
A real matrix kernel is reversible with respect to weights on if it satisfies detailed balance: (2)✦ The weights in (2) will be a probability vector, while will provide strictly positive reference weights.
Weighted Entropy and Reverse Tails
For real functions on , the weighted row entropy is the quantity (3)✦ All logarithms are natural, and entropy summands use the convention . For real reference weights and real averaging weights on , and a real matrix kernel on , the mean weighted row entropy is the weighted sum (4)✦ where the row entropy is given by (3).
For a real matrix kernel on , reference weights , a state and a real threshold parameter , the reverse tail set is the subset of given by (5) Its probability in row is , using the set in (5).
The Claim
Theorem 1 (Lemma 5.2). Let be finite, let be a probability vector on , and let for every . Suppose that is a stochastic kernel reversible with respect to , and that satisfies for every . For every real , the reverse tail sets of (5) and the mean entropy of (4) satisfy (6)✦
In the paper, the result reads: let be a finite simple graph with positive weights , cross-mass constant and associated constant , let , let edge parameters satisfy and vertex parameters satisfy , and suppose the unordered triangle mass is positive; for the kernels at the common time of Lemma 4.1 and random labels with those row laws, the -averaged probability that is inadmissible is at most .
What Is Checked
The claim (6) is stated over stochastic real matrix kernels on finite state sets, with detailed balance relative to a probability vector and an entrywise bound relative to strictly positive reference weights.