Functional inequalities and random walks on increasing subsets of the hypercube

Abstract

Motivated by random walks on subsets of the hypercube, we prove two discrete functional inequalities on the hypercube by the technique of induction-by-restrictions. First, we give a short, elementary proof of the Poincaré inequality on increasing subsets of the cube recently established by Fei and Ferreira Pinto Jr, which yields an $O(n^2)$ upper bound on the mixing time of censored random walks, improving upon previous bounds. Second, adapting Samorodnitsky's induction method to the $p$-biased setting, we establish a sharp $p$-biased edge-isoperimetric inequality for real-valued functions supported on increasing sets, which recovers the classic biased edge-isoperimetric inequality for increasing sets and identifies increasing subcubes as the extremizers. This result also admits a probabilistic interpretation in terms of maximizing the mean first exit time of biased random walks known as Glauber dynamics.

24 pages, accepted for publication in SIAM Journal on Discrete Mathematics; the final version includes a more natural probabilistic interpretation in terms of Glauber dynamics on the biased hypercube