  For "large" class $\mathcal{C}$ of continuous probability density functions
(p.d.f.), we demonstrate that for every $w\in\mathcal{C}$ there is mixture of
discrete Binomial distributions (MDBD) with $T\geq N\sqrt{\phi_{w}/\delta}$
distinct Binomial distributions $B(\cdot,N)$ that $\delta$-approximates a
discretized p.d.f. $\widehat{w}(i/N)\triangleq
w(i/N)/[\sum_{\ell=0}^{N}w(\ell/N)]$ for all $i\in[3:N-3]$, where
$\phi_{w}\geq\max_{x\in[0,1]}|w(x)|$. Also, we give two efficient parallel
algorithms to find such MDBD.
  Moreover, we propose a sequential algorithm that on input MDBD with $N=2^k$
for $k\in\mathbb{N}_{+}$ that induces a discretized p.d.f. $\beta$, $B=D-M$
that is either Laplacian or SDDM matrix and parameter $\epsilon\in(0,1)$,
outputs in $\widehat{O}(\epsilon^{-2}m + \epsilon^{-4}nT)$ time a spectral
sparsifier $D-\widehat{M}_{N} \approx_{\epsilon}
D-D\sum_{i=0}^{N}\beta_{i}(D^{-1} M)^i$ of a matrix-polynomial, where
$\widehat{O}(\cdot)$ notation hides $\mathrm{poly}(\log n,\log N)$ factors.
This improves the Cheng et al.'s [CCLPT15] algorithm whose run time is
$\widehat{O}(\epsilon^{-2} m N^2 + NT)$.
  Furthermore, our algorithm is parallelizable and runs in work
$\widehat{O}(\epsilon^{-2}m + \epsilon^{-4}nT)$ and depth $O(\log
N\cdot\mathrm{poly}(\log n)+\log T)$. Our main algorithmic contribution is to
propose the first efficient parallel algorithm that on input continuous p.d.f.
$w\in\mathcal{C}$, matrix $B=D-M$ as above, outputs a spectral sparsifier of
matrix-polynomial whose coefficients approximate component-wise the discretized
p.d.f. $\widehat{w}$.
  Our results yield the first efficient and parallel algorithm that runs in
nearly linear work and poly-logarithmic depth and analyzes the long term
behaviour of Markov chains in non-trivial settings. In addition, we strengthen
the Spielman and Peng's [PS14] parallel SDD solver.
