Abstract: A square matrix that is entrywise nonnegative and has all row sums equal to 1 is called a stochastic matrix, and such matrices play a central role in the study of Markov chains. Given a stochastic matrix \(A\), Kemeny's constant \(K(A)\) measures the expected number of steps required for the Markov chain to transition from a given initial state to a randomly chosen final state.

 

In this talk, we will begin by giving an introduction to Kemeny's constant.  We will then go on to explore an analogue of Braess' paradox (wherein adding a road to a network can have the counter-intuitive effect of increasing travel times). Specifically, we will discuss how adding an edge into an undirected graph can increase the value of Kemeny's constant for a certain Markov chain that is naturally associated with the graph.