Is there a Kemeny’s constant for second-order random walks?

by Prof. Dario Fasino (Università di Udine)

Tuesday 6 Feb 2024, 10:00 → 11:00 Europe/Rome

Aula Magna (Dipartimento di Matematica)

Kemeny's constant is a measure of the navigability of a network by ordinary random walks, which appears in a famous result on Markov chains known as the Random Target Lemma.
A second-order random walk is a random walk where the transition probabilities depend on two past states. It can be turned into a Markov chain by lifting the state space from the nodes to the directed edges of the graph. The corresponding Kemeny constant is well known but says very little about the second-order walk on the original network. 

We extend certain definitions and results on standard random walk's mean hitting and return times to the second-order case and provide simple formulas that allow us to compute these numbers by solving suitable systems of linear equations. 
New results show that there is an infinite family of graphs for which certain second-order random walks, including the best-known non-backtracking random walk, satisfy a precise second-order counterpart of the Random Target Lemma. 
So, in summary, the answer to the question in the title is: Yes, sometimes.