Quantum dynamical simulations of statistical ensembles pose a significant computational
challenge due to the fact that mixed states need to be represented. If the underlying
dynamics is fully unitary, for example, in ultrafast coherent control at finite temperatures,
then one approach to approximate time-dependent observables is to sample the density
operator by solving the Schrödinger equation for a set of wave functions with randomized
phases. We show that, on average, random-phase wave functions perform well for
ensembles with high mixedness, whereas at higher purities a deterministic sampling of the
energetically lowest-lying eigenstates becomes superior. We prove that minimization of the
worst-case error for computing arbitrary observables is uniquely attained by eigenstate-
based sampling. We show that this error can be used to form a qualitative estimate of the
set of ensemble purities for which the sampling performance of the eigenstate-based
approach is superior to random-phase wave functions. Furthermore, we present refinements
to both schemes which remove redundant information from the sampling procedure to
accelerate their convergence. Finally, we point out how the structure of low-rank
observables can be exploited to further improve eigenstate-based sampling schemes.