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.



Random walk on the hypercube with deleted edges
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.


