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...

  • $\begingroup$ 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)$? $\endgroup$ – Jon Noel May 4 '19 at 21:21
  • $\begingroup$ 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. $\endgroup$ – Yuval Peres Jun 4 '19 at 0:46
  • $\begingroup$ 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) $\endgroup$ – Jon Noel Jun 15 '19 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.