We address the problem of achieving an optical random laser with a cloud of cold atoms, in which gain and scattering are provided by the same atoms. The lasing threshold can be defined using the on-resonance optical thickness b0 as a single critical parameter. We predict the threshold quantitatively, as well as power and frequency of the emitted light, using two different light transport models and the atomic polarizability of a strongly pumped two-level atom. We find a critical b0 on the order of 300, which is within reach of state-of-the-art cold-atom experiments. Interestingly, we find that random lasing can already occur in a regime of relatively low scattering.