A general-order stochastic perturbation algorithm is obtained from the order-by-order expansion of the imaginary-time evolution of a configuration interaction wave function. A truncation of configuration space that is required for the practical treatment of the perturbative corrections, however, does not preserve size-consistency as is the case for a truncated configuration interaction. To circumvent this problem, we formulate a linked variant of stochastic perturbation theory based on the coupled-cluster ansatz. The implementation based on the linearized coupled-cluster is compared with several full configuration interaction results. We also compare the results with those obtained from deterministic coupled-cluster and many-body perturbation theories.