University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Algebraic Graph Theory Seminar - Steve KirklandExport this event to calendar

Thursday, July 25, 2019 — 2:30 PM EDT

Title: Kemeny's Constant for Markov Chains

Speaker: Steve Kirkland
Affiliation: University of Manitoba
Room: MC 5479

Abstract:

Markov chains are a much-studied class of stochastic processes, and it is well-known that if the transition matrix A associated with a Markov chain possesses a certain property (called primitivity), then the long-term behaviour of the Markov chain is described by a particular eigenvector of A, known as the stationary distribution vector. Rather less well-known is Kemeny’s constant for a Markov chain, which can be interpreted in terms of the expected number of time steps taken to arrive at a randomly chosen state, starting from initial state i. In particular, if Kemeny’s constant is small, then we can think of the Markov chain as possessing good mixing properties.

In this talk, we will give a short overview of Kemeny’s constant, and discuss some results dealing with the problem of minimising Kemeny’s constant over transition matrices that are subject various constraints. We will also describe some results showing that Kemeny’s constant can exhibit surprising behaviour when the transition matrix is perturbed. Throughout,  the techniques used rely on matrix theory and graph theory.

Location 
MC - Mathematics & Computer Building
5479
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2020 (76)
    1. August (9)
    2. July (17)
    3. June (11)
    4. May (6)
    5. March (11)
    6. February (11)
    7. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)