In recent generalized Kohn-Sham (GKS) schemes for density functional theory (DFT) Hartree-Fock type exchange is important. In plane waves and grid approaches the high cost of exchange energy calculations makes these GKS considerably more expensive than Kohn-Sham DFT calculations. We develop a stochastic approach for speeding up the calculation of exchange for large systems. We show that stochastic error per particle does not grow and can even decrease with system size (at a given number of iterations). We discuss several alternative approaches and explain how these ideas can be included in the GKS framework.