PIMS lectures
Title: Kemeny's Constant for Markov Chains
Speaker: Stephen Kirkland, University of Manitoba
Date and time:
18 Oct 2018,
3:30pm -
4:20pm
Location: Clearihue A308
Read full description
There will be refreshments at a 3:00 pm reception prior to the talk.
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 to 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.
Download poster (PDF)
Title: PIMS Undergraduate Event - Twist and Turn: the Story of the Game of Hex
Speaker: Ryan Hayward, University of Alberta
Date and time:
06 Apr 2018,
3:00pm -
4:00pm
Location: David Strong Building, room C116
Read full description
(pre-lecture refreshments in DTB A514 @ 2:30 pm)
In 1942, the Danish engineer, poet, and designer Piet Hein invented a new board game and --- with a little help from his friends --- introduced it to readers of the Danish newspaper Politiken. The game became popular: within a year, 50,000 game pads sold.
In 1949 John Nash introduced the game to the Princeton math community, and in 1957 Martin Gardner passed it on to readers of Scientific American.
In this talk for a general audience, I will sketch some big moments in Hex history, ending with an outline of the ideas that make a nearly-superhuman computer Hex program tick.
---
Ryan Hayward received his B.Sc. and M.Sc. in mathematics from Queen's University (Kingston) in 1981 and 1982 and his Ph.D. in computer science from McGill University in 1987. His doctoral thesis, Two Classes of Perfect Graphs, was supervised by Vaclav Chvatal. From 1986 through 1989 he was assistant professor in the Department of Computer Science at Rutgers University, after which he held an Alexander von Humboldt fellowship at the Institute for Discrete Mathematics in Bonn for 1989-90.
From 1990 through 1992 he was assistant professor in the Department of Computing Science at Queen's University. From 1992 he was assistant and then associate professor in the Department of Mathematics and Computer Science at the University of Lethbridge, until in 1999 joining the Department of Computing Science at the University of Alberta, where he was promoted to professor in 2004.
He has supervised 13 graduate and 29 undergraduate students, some of whom later became university professors. His current research interests include algorithms for two-player games. His group (including at times Yngvi Bjornsson, Michael Johanson, Broderick Arneson, Philip Henderson, Jakub Pawlewicz, Chao Gao and Aja Huang --- later lead programmer of AlphaGo) has built the world's strongest computer Hex player, and has solved two 1-move 10x10 Hex openings and all smaller-board openings. With Bjarne Toft, he is writing a book on the history of Hex, to be published in 2018.
Many years ago, Ryan rode his bicycle from Vancouver to Lethbridge.
Download poster (PDF)
Title: Mallow Permutations, Stable Matchings and Scaling Limits
Speaker: Omer Angel, University of British Columbia
Date and time:
26 Mar 2018,
3:30pm -
4:20pm
Location: MacLaurin Building, room D110
Read full description
We present a new representation of the Mallows permutations to stable matchings on a random bi-partite graph. We also derive new results for the scaling limits of the cycles in the Mallows permutations in terms of the Ethier-Kurtz diffusion.
Joint with Ander Holroyd, Tom Hutchcroft and Avi Levy.
(pre-lecture refreshments @2:45pm in DTB A514)
Download poster (PDF)
