We examine the possibility of using a Metropolis algorithm for computing the exchange energy in a large molecular system. Following ideas set forth in a recent publication (Baer, Neuhauser, and Rabani, Phys. Rev. Lett. 111, 106402 (2013)) we focus on obtaining the exchange energy per particle (ExPE, as opposed to the total exchange energy) to a predefined statistical error and on determining the numerical scaling of the calculation achieving this. For this we assume that the occupied molecular orbitals (MOs) are known and given in terms of a standard Gaussian atomic basis set. The Metropolis random walk produces a sequence of pairs of three-dimensional points (x,x'), which are distributed in proportion to ρ(x,x')(2), where ρ(x,x') is the density matrix. The exchange energy per particle is then simply the average of the Coulomb repulsion energy υC(|x-x'|) over these pairs. To reduce the statistical error we separate the exchange energy into a short-range term that can be calculated deterministically in a linear scaling fashion and a long-range term that is treated by the Metropolis method. We demonstrate the method on water clusters and silicon nanocrystals showing the magnitude of the ExPE standard deviation is independent of system size. In the water clusters a longer random walk was necessary to obtain full ergodicity as Metropolis walkers tended to get stuck for a while in localized regions. We developed a diagnostic tool that can alert a user when such a situation occurs. The calculation effort scales linearly with system size if one uses an atom screening procedure that can be made numerically exact. In systems where the MOs can be localized efficiently the ExPE can even be computed with "sublinear scaling" as the MOs themselves can be screened.