Frank den Hollander, Dana Randall, and I recently posted a new version of our paper on random Markov matrices. We significantly improved the main result and newly answered a question of Bordenave, Caputo, and Chafaï (2012).
Approximation of Markov chain stationary distributions
The setting is a random Markov transition rate matrix $Q$ on $n$ states. For simplicity, assume that $Q$ is irreducible (this holds eventually a.s. for the model we study), so that there is a unique stationary distribution $\pi_Q$ which solves the matrix equation $\pi_Q Q = 0$. The main result of the paper identifies conditions under which $\pi_Q$ is close in total variation distance to the distribution $\nu_q$ that is proportional to $1/q_i$, where $q_i = \sum_{j \ne i} Q_{i,j}$ is the exit rate of $i$. This is interesting because $\pi_Q$ is generally a complicated function of all the transition rates. To get a sense of how complicated, see the Markov chain tree theorem.
A basic fact is that the probabilities $\pi_Q(i)$ are proportional to $\pi_{\widehat{Q}}(i) / q_i$, where $\widehat{Q}$ is the transition probability matrix obtained by normalizing the entries of $Q$ by the corresponding exit rates. So the closeness of $\pi_Q$ and $\nu_q$ in total variation distance naturally relates to a measure of how uniform $\pi_{\widehat{Q}}$ is. There are multiple ways to show that $\pi_{\widehat{Q}}$ is roughly uniform.
In the first draft of our paper, we showed that $\pi_{\widehat{Q}}$ was asymptotically uniform (a.s. as $n \to \infty$) by showing that $\widehat{Q}$ is a small perturbation of a rapidly mixing, doubly stochastic matrix. (This required some assumptions on the upper and lower tails of the common distribution of the entries of $Q$.) A result from Mitrophanov (2003) explains that small perturbations of rapidly mixing Markov chains do not change the stationary distribution much. Because doubly stochastic Markov chains have uniform stationary distributions, this implies that $\pi_{\widehat{Q}}$ is nearly uniform. We later realized that a different argument, which involves applying Bernstein’s inequality to the rows of the two-step transition probability matrix $\widehat{Q}^2$, ultimately gives better control on the uniformity of $\pi_{\widehat{Q}}$.
In the updated paper, we also expand the class of random transition rate matrices that we consider. We do so by separately assigning vertex and edge weights to the complete digraph, and forming $Q_{i,j}$ as the product of the vertex weight $\theta_i$ at $i$ and the weight $X_{i,j}$ of edge $(i,j)$. The edge weights are drawn i.i.d. from a non-negative distribution that can have an atom at zero, so the resulting Markov chain need not have transitions between every pair of states. Our main result merely requires that the law of edge weights has a finite $p$-th moment, for some $p > 4$. In this case, regardless of what the positive vertex weights $\theta_i$ are, we find that
$$ \| \pi_Q - \nu_q \|_{\mathrm{TV}} = o(1) \quad \mathrm{a.s.} $$In fact, because the inhomogeneity in the exit rates comes primarily from differences in the vertex weights, the same conclusion applies with $\nu_\theta$ in the place of $\nu_q$, where
$$ \nu_\theta (i) = \frac{1/\theta_i}{\sum_{k=1}^n 1/\theta_k}. $$Since $\pi_Q$ is close in total variation distance to $\nu_\theta$, and because we can make $\nu_\theta$ into any positive distribution by choosing the vertex parameters accordingly, the same is true of $\pi_Q$.
Answering a question of Bordenave, Caputo, and Chafaï
Now, instead of the random transition rate matrix $Q$, consider the random transition probability matrix $P$ that results from drawing i.i.d. edge weights $X_{i,j}$ for every edge $(i,j)$ of the complete digraph and normalizing the rows of the resulting matrix. In a 2012 PTRF paper, Bordenave, Caputo, and Chafaï asked: If the $X_{i,j}$ have a finite second moment, is
$$ \| \pi_P - u \|_{\mathrm{TV}} = o(1) \quad \mathrm{a.s.}, $$where $u$ is the uniform distribution? In fact, special cases of this question have been raised several times in the random matrix theory, physics, and computer science literatures.
We answer this question in the affirmative by showing that the entries of the two-step transition matrix $P^2$ are uniformly bounded below by $(1-o(1))/n$. The reason for studying $P^2$ instead of $P$ itself is that the entries of $P^2$ have “numerators” that are sums of edge weights. These sums have exponential lower tails—meaning that even the smallest of these $n^2$ numerators cannot be much smaller than its mean. We convert the lower bound on the entries of $P^2$ into a lower bound on the entries of $\pi_P$ using the fact that $\pi_P$ is also the stationary distribution of $P^2$.