# Entropy of endpoints of a random walk in a dense graph

Let $$p\in[0,1]$$ be a constant and let $$G$$ be a graph with $$n$$ vertices and $$\approx p\binom{n}{2}$$ edges. If you'd like, consider $$p=1/2$$.

Let $$X$$ be a random vertex of $$G$$ chosen proportional to its degree (i.e. the probability that $$X=v$$ is $$d(v)/2|E(G)|$$). That is, $$X$$ is chosen according to the stationary distribution of a random walk. Now, generate two standard random walks starting at $$X$$ denoted $$A_0,A_1,\dots$$ and $$B_0,B_1,\dots$$ where $$A_0=B_0=X$$.

For $$k\geq1$$, define $$\alpha_k$$ so that $$H(A_k,B_k) =\log_2(\alpha_kn^2)$$ where $$H$$ denotes the binary entropy. That is, $$\alpha_k:=2^{H(A_k,B_k)}/n^2$$. If I understand correctly, the way that entropy works is that $$\alpha_k\approx1$$ if and only if the distribution on $$(A_k,B_k)$$ is roughly uniformly on $$V(G)^2$$.

Question: Given the value of $$\alpha_i$$, what kind of lower bound can one prove on $$\alpha_j$$ for $$j>i$$?

I am mainly interested in constant values of $$i,j$$. For example, I would be quite interested to know whether all such graphs satisfy any (non-trivial) bound of the form $$\alpha_2\geq f(\alpha_1)$$ or, if parity matters, then perhaps, $$\alpha_3\geq f(\alpha_1)$$ for some function $$f$$. I'd be very happy to know if there are any existing results related to this; please excuse my lack of knowledge on random walks...

• By the way, an extreme example is if $G$ is a complete bipartite graph. For instance, if $G$ is complete bipartite with both parts of size $n/2$, then $p\approx 1/2$ and $\alpha_1=\alpha_2=\cdots\approx 1/2$. However, what happens if $G$ is graph with $\approx n^2/4$ edges such that $\alpha_1$ is something higher, like $2/3$? Or $(1-\varepsilon)$? – Jon Noel May 4 '19 at 21:21
• 1. When computing the entropy, do you condition on X or not? 2. It would be more natural to consider relative entropy to the product of two copies if the stationary distribution, in other words the mutual information of A_k and B_k. – Yuval Peres Jun 4 '19 at 0:46
• For your first question, I would be interested in any variant (conditioned or not). But I was originally thinking about unconditioned. Could you clarify the second question a bit? I'm not sure that I get what you mean. (Apologies, I am not very experienced with ideas related to random walks) – Jon Noel Jun 15 '19 at 20:08