Functional Inequalities and Random Walks on Increasing Subsets of the Hypercube

2025/06/11 by F.-R. Chang, Chang, Fan, Guowei Sun +3
Mathematics · #05C81 #06E30 #60C05 #60G50 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2506.09852

openalex publication_date 2025/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

Motivated by random walks on subsets of the hypercube, we prove two discrete functional inequalities on the hypercube. 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²) 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 increasing functions, 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.

Citations

• Optimal Young's convolutions inequality and its reverse form on the hypercube
• Inequalities in Fourier analysis on binary cubes
• On the Spectral Expansion of Monotone Subsets of the Hypercube
• On Average Distance, Level-1 Fourier Weight, and Chang's Lemma
• Lower Bounds for Dyadic Square Functions of indicator functions of sets
• Sharp isoperimetric inequalities on the Hamming cube near the critical exponent
• On sharp isoperimetric inequalities on the hypercube
• Isoperimetric Inequalities Made Simpler
• The KKL inequality and Rademacher type 2
• Hypercontractivity for global functions and sharp thresholds
• On a biased edge isoperimetric inequality for the discrete cube
• Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)
• Mixing under monotone censoring
• An inequality for functions on the Hamming cube
• Analysis of Boolean Functions
• Thresholds and expectation thresholds
• Edge-isoperimetric inequalities and influences
• Logarithmic Sobolev inequalities for finite Markov chains

Related

• An inequality for functions on the Hamming cube
• On the Spectral Expansion of Monotone Subsets of the Hypercube
• Probabilistic and Geometrical Applications to Graph Theory
• Three steps mixing for general random walks on the hypercube at criticality
• Vector-valued concentration inequalities on the biased discrete cube