3
$\begingroup$

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.

$\endgroup$

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.