Random walk on the hypercube with deleted edges

Question

Let $G$ be the $n$-dimensional boolean hypercube, i.e. the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph $G'$ obtained by deleting a $p$ fraction of edges from $G$ arbitrarily. What is a lower bound on the probability that a $t$ step random walk on $G$ (with uniformly random starting vertex and transition at each step) is entirely contained in $G'$? I am most interested in the regime where $t$ is order $n$ and $p$ is order $\log n /n$ and I suspect one should be able to prove a lower bound of the form $2^{-pt}$.

I can show using small-set expansion on the hypercube that $G'$ has a connected component of size at least $2^{n(1-p)}$, but do not know how to argue about the random walk not leaving the component.

Answer 1

In 1959, Mulholland and Smith [1] proved that for any symmetric nonnegative matrix $A$, any integer $k \ge 1$ and any nonnegative vector $z$, $$(z^T A^k z) (z^Tz)^{k-1} \ge (z^T A z)^k \; \; \; (*) $$ This was rediscovered by Blakley-Roy (1965). More on the history below.

Let $m=n2^{n-1}(1-p)$ denote the number of edges in $G'$. If $A$ is the $2^n$ by $2^n$ adjacency matrix of $G'$ and $z$ is an all ones vector of length $2^n$, then $z^T A Z=2m $ so (*) implies that the number $W_k$ of walks of length $k$ in $G'$ is at least $(2m)^k/(2^n)^{k-1}$. Therefore the probability $P_k$ that a $k$ step random walk on $G$ (with uniformly random starting vertex and transition at each step) is entirely contained in $G′$ satisfies $$P_k=2^{-n}W_k n^{-k} \ge \Bigl(\frac{2m}{n2^n}\Bigr)^k =(1-p)^k . $$ This lower bound is sharp in many cases, e.g., if $p=b/n$ and all edges of the hypercube where one of the the first $b$ coordinates differs across the edge are erased to form $G'$. The argument above extends to any graph $G$, it need not be the hypercube. Upper bounds are discussed in [7] and the references therein.

The inequality (*) is a (proved) special case of the (still open} Sidorenko conjecture ([3],[4]) which is equivalent to a conjecture of Erdos-Simonovitz. For updates on the conjecture see [5], [6].

[1] H. P. Mulholland and C. A. B. Smith. An inequality arising in genetical theory. Amer. Math. Monthly, 66(8):673–683, 1959.

[2] G. R. Blakley and P. Roy. H¨older type inequality for symmetric matrices with nonnegative entries. Proc. Amer. Math. Soc., 16(6):1244–1245, 1965.

[3] A. Sidorenko. Inequalities for functionals generated by bipartite graphs. Discrete Math. Appl., 2(5):489–504, 1992.

[4] A. Sidorenko. A correlation inequality for bipartite graphs. Graphs and Combinatorics, 9(2):201–204, 1993.

[5] B. Szegedy. An information theoretic approach to Sidorenko’s conjecture. arXiv:1406.6738, 2014.

[6] Alexander Sidorenko , Inequalities for doubly nonnegative functions https://arxiv.org/pdf/1905.08210.pdf

[7] Levin, David A., and Yuval Peres. "Counting walks and graph homomorphisms via Markov chains and importance sampling." The American Mathematical Monthly 124, no. 7 (2017): 637-641.