  We study the algorithmic complexity of computing persistent homology of a
randomly generated filtration. Specifically, we prove upper bounds for the
average fill-in (number of non-zero entries) of the boundary matrix on
\v{C}ech, Vietoris--Rips and Erd\H{o}s--R\'enyi filtrations after matrix
reduction. Our bounds show that the reduced matrix is expected to be
significantly sparser than what the general worst-case predicts. Our method is
based on previous results on the expected Betti numbers of the corresponding
complexes. We establish a link between these results and the fill-in of the
boundary matrix. In the $1$-dimensional case, our bound for \v{C}ech and
Vietoris--Rips complexes is asymptotically tight up to a logarithmic factor. We
also provide an Erd\H{o}s--R\'enyi filtration realising the worst-case.
