We consider random perturbations of general non-uniformly expanding maps, possibly having a non-degenerate critical set, and discuss their mixing rates along random orbits. In particular, we prove that, if the Lebesgue measure of the set of points failing the non-uniform expansion or the slow recurrence to the critical set at a certain time decays in a (stretched) exponential fashion for almost all random orbits, then the decay of correlations along random orbits is stretched exponential, up to some waiting time.  As corollary, we obtain almost sure stretched exponential random decay of correlations for Viana maps, as for a class of non-uniformly expanding local diffeomorphisms and a quadratic family of interval maps. In this talk we are going to state the main results, sketch the strategy for the proof and see some applications. This is a joint work with Xin Li.