Student Probability and Related Fields Seminar

A well-known result of Diaconis and Stroock says that the mixing time of a finite state space reversible Markov chain can be bounded using its absolute spectral gap. Their bound carries a factor of log(1/pi_min), where pi_min is the minimum value of the stationary distribution over the entire state space. In this talk, I prove a more general bound which applies in all cases, even when pi_min = 0 or the chain is not reversible. When the chain is reversible and the stationary distribution is close to uniform, the Diaconis-Stroock bound is much better; but in the more general setting, the new bound is almost sharp. The proof is mainly combinatorial: in one key step, we show that for any polynomial f(x), the entries of powers of the companion matrix for f are given by Schur functions in the roots of f.

In this talk I will introduce random fields, briefly give a few examples, and then prove an entropy bound for the expected supremum of Gaussian fields. This will motivate us to consider chaining arguments and, time permitting, Talagrand's majorizing measures theorem. I will draw pictures when possible and focus on conceptual understanding in order to make the talk accessible to anyone with basic knowledge of measure theory.

Starting at the identity, walk on S_n by at each step appending a random transposition. At even times, a simple argument shows the identity is always the most likely element. The least likely element is harder to pin down. Using representation theory of the symmetric group and Fourier inversion, a total order on group elements in likelihood can be found after sufficient time. From this, depending on parity of time, the n-cycle and one other surprising conjugacy class are eventually the least likely. The motivation for this question is the separation distance of the walk: the difference between the least likely element and the walk's eventual uniform stationary distribution. Very little familiarity with representation theory or random walks will be assumed and the key proofs will be combinatorial in nature.

In studying real-world graphs, one is often faced with the problem of uniformly sampling graphs with given degree sequence. There are two main approaches to this problem---direct sampling, which works well for sparse graphs but can experience exponentially bad behaviour for dense graphs, and Markov Chain Monte Carlo (MCMC), which always has polynomial runtime, but carries the usual MCMC drawback of being difficult to decide when to stop. In this talk, I will present a hybrid algorithm that attempts to achieve the best of both worlds. The underlying idea---directly sample from a superset for which this is easy, then run MCMC until the desired subset is reached---can be extended to many combinatorial structures other than graphs.