# Random walk on the hypercube with deleted edges

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.

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.