COSAM » Events » 2016 » February » Colloquium: Stephen Kirkland

Colloquium: Stephen Kirkland
Time: Feb 12, 2016 (04:00 PM)
Location: Parker Hall 249


Speaker: Stephen Kirkland, University of Manitoba


Title: Kemeny's Constant and an Analogue of Braess' Paradox for Markov chains

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.

Faculty host: T.-Y. Tam

Last updated: 02/12/2016