Functional Inequalities and Random Walks on Increasing Subsets of the Hypercube
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911255125557248 |
|---|---|
| author | Chang, Fan Sun, Guowei Yu, Lei |
| author_facet | Chang, Fan Sun, Guowei Yu, Lei |
| contents | 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^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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_09852 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Functional Inequalities and Random Walks on Increasing Subsets of the Hypercube Chang, Fan Sun, Guowei Yu, Lei Combinatorics Probability 06E30, 05C81, 60C05, 60G50 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^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 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. |
| title | Functional Inequalities and Random Walks on Increasing Subsets of the Hypercube |
| topic | Combinatorics Probability 06E30, 05C81, 60C05, 60G50 |
| url | https://arxiv.org/abs/2506.09852 |