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 at 21:21

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.