  In this paper we show how to generalize the quantum approximate counting
technique developed by Brassard, H{\o}yer and Tapp [ICALP 1998] to a more
general setting: estimating the number of marked states of a Markov chain (a
Markov chain can be seen as a random walk over a graph with weighted edges).
This makes it possible to construct quantum approximate counting algorithms
from quantum search algorithms based on the powerful "quantum walk based
search" framework established by Magniez, Nayak, Roland and Santha [SIAM
Journal on Computing 2011]. As an application, we apply this approach to the
quantum element distinctness algorithm by Ambainis [SIAM Journal on Computing
2007]: for two injective functions over a set of $N$ elements, we obtain a
quantum algorithm that estimates the number $m$ of collisions of the two
functions within relative error $\epsilon$ by making
$\tilde{O}\left(\frac{1}{\epsilon^{25/24}}\big(\frac{N}{\sqrt{m}}\big)^{2/3}\right)$
queries, which gives an improvement over the
$\Theta\big(\frac{1}{\epsilon}\frac{N}{\sqrt{m}}\big)$-query classical
algorithm based on random sampling when $m\ll N$.
