Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Part I: We introduce a probabilistic technique that yields the sharpest bounds obtained on mixing times for Markov chains in terms of isoperimetric properties of the state space. We show that the bounds for mixing time in total variation obtained by Lovasz and Kannan can be refined to apply to the maximum relative deviation $|p^n(x,y)/\pi(y) -1|$ of the distribution at time $n$ from the stationary distribution $\pi$. This is joint work with Yuval Peres. Part II: We show that the mixing time for random walk on the $n$-dimensional cube truncated by a hyperplane is polynomial in $n$. As a consequence, we obtain a fully-polynomial randomized approximation scheme for counting the feasible solutions of a 0-1 knapsack problem. This is joint work with Alistair Sinclair.

3:45 Refreshments will be served before the talk in 551 Kerr Hall