Statistics and Probability Seminar
Speaker: Raghavendra Tripathi, NYU Abu Dhabi
Host: Parthanil Roy
Title: Efficient sampling from almost all monotone sets
Time, day and date: 11:00:00 AM – 12:00:00 PM, Thursday, August 06
Venue: Conference Room
Abstract: Sampling from the uniform measure on a monotone subset of Boolean hypercube arises in several contexts. For example, sampling a configuration in bond percolation with left to right crossing, or sampling a Knapsack. One popular and oft used method to sample from such sets is to restrict the random walk on the full hypercube to the monotone set. The random walk on the full hypercube mixes in $O(nlogn)$ time.Ding and Mossel (2014) conjectured that restricted chain on any monotone set with fixed positive measure also mixes in $O(nlogn)$ time and proved an upper bound $O(n^3)$. This was recently improved to $O(n^2)$ by proving a sharp Poincare inequality. We prove that for almost all monotone subsets, the log-Sobolev constant is order $n$ which in turn implies the Ding and Mossel’s conjecture for almost all monotone sets. This talk is based on joint work with Patrick O. Santos and Pierre Youssef.