## Approximating Large Powers of Stochastic Matrices in Small Space

by Gil Cohen, Dean Doron, and Ori Sberlo

We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS95), that requires $O(\log^{3/2}n + \sqrt{\log n} \cdot \log w)$ space, in the regime $n \gg w$.