The characterization of ℓp-compressible random sequences is revisited and extended to the case of stationary and ergodic processes. The main result of this work offers a simple-to-check necessary and sufficient condition for a stationary and ergodic sequence to be ℓp-compressible in the sense proposed by Amini, Unser and Marvasti [1, Def. 6]. Furthermore, for non ℓp-compressible random sequences, we provide a closed-form expression for the best k-term relative approximation error given a rate of coefficients as the block-length tends to infinity. © 2014 IEEE.