Computing the Stationary Distribution, Locally
Computing the stationary distribution of a large finite or countably infinite state space Markov Chain (MC) has become central in many problems such as statistical inference and network analysis. Standard methods involve large matrix multiplications as in power iteration, or simulations of long random walks, as in Markov Chain Monte Carlo (MCMC). Power iteration is costly, as it involves computation at every state. For MCMC, it is difficult to determine whether the random walks are long enough to guarantee convergence. In this paper, we provide a novel algorithm that answers whether a chosen state in a MC has stationary probability larger than some ∆ ∈ (0, 1), and outputs an estimate of the stationary probability. Our algorithm is constant time, using information from a local neighborhood of the state on the graph induced by the MC, which has constant size relative to the state space. The multiplicative error of the estimate is upper bounded by a function of the mixing properties of the MC. Simulation results show MCs for which this method gives tight estimates.
The authors present an algorithm to estimate (with 
      potentially arbitrary accuracy) whether the stationary distribution of a 
      specific state of a Markov chain is greater than or less than a 
      pre-specified parameter, \delta. The algorithm uses truncated Monte Carlo 
      rollouts to estimate the expected first return time from the specified 
      state and then inverts this to get the state's stationary distribution. 
      The paper also provides a novel theoretical contribution in the form of a 
      proof that return times have exponentially decaying tails for 
      countable-space MCs (not just finite-space MCs, which was what was known 
      previously). A minimal empirical evaluation is provided as well, to 
      demonstrate that this algorithm can be run. Overall, the paper is 
      quite well-written and clear with good explanations and intuitions given 
      behind specific choices or aspects of the work. The authors address 
      potential questions in good fashion and try to give an honest presentation 
      of their work. That being said, I have a number of questions regarding the 
      work. Regarding the abstract, the authors state that power 
      iteration and MCMC run in linear time, but they also give the stationary 
      distribution over all states, so if you did that with this algorithm it 
      would be at least linear in the state space size as well, no? 
      Regarding practicality, could the author's give some intuition 
      about what someone would use this procedure for as well as how to set the 
      parameters for different types of use cases? The authors indicate that 
      there is wide applicability of this algorithm, which is true, but I am 
      having a difficult time coming up with useful purposes of this algorithm 
      (unless one runs it on every state in the space, which is somewhat 
      unreasonable). Could you comment on potential future extensions 
      (potentially to improve practicality, e.g., if there was smoothness in the 
      space)? Finally, the Borgs et al. [17] algorithm cited in the paper seems 
      more practically relevant -- could this algorithm be extended in that 
      direction somehow? Why doesn't the algorithm return the estimated 
      stationary probability of i, instead of just returning 0/1 based on 
      \delta? It seems that that would be more useful. Specifics: - 
      it would be helpful if the description of the algorithm was a bit clearer, 
      specifically - specify the inputs as the parameters and the state i 
      - clearly state that s_k is the length of a sampled trajectory 
      - the statement of theorem 3.1 is strangely asymmetrical. Why 
      don't the authors just use "With probability greater than (1-\alpha): If 
      \pi_i < \delta, the algorithm outputs 0 and if \pi_i > \delta the 
      algorithm outputs 1." - on line 261, P^(t)_{ii} is introduced 
      without being defined (as far as I can find) -- P in all other instances 
      is not time-dependent (and thus Z_ii should tend to +/- \infty, no?) -- 
      what is this quantity? - furthermore, on line 280, the authors 
      state that, in PageRank, Z_ii \approxeq 1, but give no intuition about 
      whether this is good/bad or high/low -- what is the range of Z_ii? 
      - there is a duplicated sentence on life 653 of the supplementary 
      material Results section: - change colors and data markers to 
      be distinguishable in black and white - does the x-axis of (a) refer 
      to the # of nodes or the node IDs? - is bias correction just working 
      better because it is taking more steps (based on (b)) than the biased 
      estimate? can you control for this? - please show the actual # steps 
      and \delta (not the log of them) but plot these values on a log scale (so 
      the reader has a better understanding of the numbers being shown -- figure 
      (b) seems to indicate that 8 million steps were taken for some of the data 
      points?) - a log scale on the y-axis of (c) would give a better 
      indication of the differences between the data points - the figures 
      are numbers from a single run on a single graph? why aren't they averaged 
      over many random graphs? - a real data example would help highlight 
      the efficacy of this algorithm in domains with strange distributions and 
      hot spots in the state space - (b) and (d) are said to show the 
      results from three different nodes, but what are the results for each and 
      how are they combined for the graph? could all three be shown separately? 
      - it's not clear that the computation time is upper-bounded by O(1 / 
      \delta) because it's a log-log scale -- could the authors draw this line 
      on the graph?