Testing whether the uniform distribution is a stationary distribution

• We studied the Markov chain obtained by a random walk on a regular directed graph.
• For such chain, uniformity of stationary distribution depends on a local property.
• We gave a testing algorithm with sublinear query bounds to test the above property.

A random walk on a directed graph generates a Markov chain on the vertices of the graph. An important question that often arises in the context of Markov chains is, whether the uniform distribution on the vertices of the graph is a stationary distribution. A stationary distribution of a Markov chain is a global property of the graph. This leads to the belief that whether a particular distribution is a stationary distribution of a Markov chain depends on the global property of that Markov chain. In this paper for a directed graph whose underlying undirected graph is regular, we prove that whether the uniform distribution on the vertices of the graph is a stationary distribution, depends on a local property of the graph, namely if (u,v)(u,v) is a directed edge, then out-degree(u) is equal to in-degree(v).This result also has an application to the problem of testing whether a given distribution is uniform or “far” from being uniform. If the distribution is the stationary distribution of the lazy random walk on a directed graph and the graph is given as an input, then how many bits (orientations) of the input graph does one need to query in order to decide whether the distribution is uniform or “far”2 from it? This is a problem of graph property testing, and we consider this problem in the orientation model. We reduce this problem to testing Eulerianity in the orientation model.