We consider a random directed graph with fixed out-degree $d$. Each vertex chooses $d$ neighbors with replacement, uniformly and independently. Self-loops and multiple arcs are allowed in this model. This corresponds to a model of random automata over an alphabet of size $d$.

Denote by $n$ the number of vertices in the graph, which is finite. Thus there must exist a stationary distribution $\pi$ of the random walk on the graph, regardless of whether it converges. For symmetry, the expectation of $\pi(i)$ is $1/n$ for all $i$.

I want to show that with high probability, $\min_i\{\pi(i)\}$ is not too small, i.e., at least polynomially large w.r.t. $n$. Since the graph is not necessarily strongly connected, we only consider the strongly connected component. More strictly, I want to show that with high probability, $\min_i\{\pi(i) \mid \pi(i)>0\}$ won't be too small. Any literature on this?

By "high probability", I mean the probability goes to $1$ when $n \to +\infty $.

A most recent related work could be [Kenter 2013]. However, their model is different from mine and more like the Erdős–Rényi model.

Thank you.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.