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.

  • 2
    $\begingroup$ Thanks for the pointer to this question. I also had automata as the motivation for my question (cstheory.stackexchange.com/questions/1257/…). Unfortunately, I am not aware of any new results here. $\endgroup$
    – Lev Reyzin
    Commented Jan 20, 2014 at 3:42


Your Answer

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