Random (Over) Sampling signal and perfect Reconstruction in Nyquist form?
For the moment restrict the discussion to 1D signals. Sampling operation can be performed as uniformly or non-uniformly. The uniform sampling is the most obvious, simplest and the preferred form, unless otherwise stated.

Nonuniform sampling can be performed in a number of ways, periodically or aperiodically, sampling instant given by a formula or being completely random.

Depending on the nonuniform sampling form, the reconstruction criterions may change. For example when you have a formula based nonuniform sampling instant $t_n$, you can (if possible) find a kernel $\phi_n(t)$ for the reconstruction integral that provides exact (perfect) recovery of a continuous time signal $x(t)$ from its nonuniform samples $x_n$. In this context the $sinc()$ kernel is a special case of the generalized sampling theorem WKS (Whittaker-Kotelnikov-Shannon) with sampling instants given by $t = n T_s$. This was historically called as the Nyquist sampling, who most successfully emplyed it into the earliest digital pulse communication systems.

The primary requirement that Nyquist (uniform) sampling theorem would provide exact reconstruction of a bandlimited baseband signal $x(t)$ from its uniform samples is that the sampling rate satisfy the Nyquist criterion; $F_s \geq 2 F_c$ where $F_c$ is the signal's bandwidth.

Now for the non-uniform sampling strategies, the most common restriction for perfect signal recovery is that on the average the Nyquist rate associated with the bandlimited signal is maintained. So when there is a deficiency of samples at some short interval $I_1$ then there must be an excess of samples at another closeby short interval $I_2$ so that the average Nyquist rate preserved. 

The above condition can be stated as the local Nyquist rate criterion.

Note that unlike uniform sampling case, for nonuniform sampling strategies and exlcusively true for the random sampling strategy, the sampling times $t_n$ in addition to the samples $x_n$ should be known in order to reconstruct the signal perfectly.

You can look for Whittaker's, Yen's, Shannon's papers for classical view on the nonuniform sampling of signals.