We present stochastic solutions to the cellular automata parity problem. The model is an interacting particles system where cells are updated by pairs, randomly chosen at each time step. We analyse the convergence properties of two rules and show that they possess the required properties to classify the parity of the initial configurations. We present a formal analysis of the classification time, as well as numerical simulations, to establish that the classification time scales quadratically with the number of cells.