We design, analyze, and implement a randomized Greedy algorithm that builds certified reduced order models for parametric partial differential equations (PDEs). We show how drawing sample parameters from a clever probability distribution provides certification with high probability over not just the samples, but the entire parameter set, a powerful result that holds even for classes of nonlinear PDEs. Moreover, we demonstrate favorable properties of the algorithm?s sampling complexity to break the curse of dimensionality encountered by e.g. the deterministic Greedy algorithm when choosing a suitable training set. We present preliminary numerical results and discuss the remaining questions in algorithm analysis and implementation. Finally, we discuss the potential of the algorithm to construct localized reduced models for nonlinear multiscale PDEs in a fully local fashion, without relying on simulations of the global computational domain.