The clustering of galaxies in ongoing and upcoming galaxy surveys contains a wealth of cosmological information, but extracting this information is a nontrivial task since galaxies and their host haloes are stochastic tracers of the nonlinear matter density field. This stochasticity is usually modeled as the Poisson shot noise, which is constant as a function of wave number with amplitude given by 1=n, where n is the number density of galaxies. Here we use dark matter haloes in N-body simulations to show evidence for deviations from this simple behavior and develop models that explain the behavior of the stochasticity on large scales. First, haloes are extended, nonoverlapping objects, i.e., their correlation function needs to go to -1 on small scales. This leads to a negative correction to the stochasticity relative to the Poisson value at low wave number k, decreasing to zero for wave numbers large compared to the inverse exclusion scale. Second, haloes show a nonlinear enhancement of clustering outside the exclusion scale, leading to a positive stochasticity correction. Both of these effects go to zero for high k, making the stochasticity scale dependent even for k < 0:1h Mpc-1. We show that the corrections in the low-k regime are the same in Eulerian and Lagrangian space, but that the transition scale is pushed to smaller scales for haloes observed at present time (Eulerian space), relative to the initial conditions (Lagrangian space). These corrections vary with halo mass, and we present approximate scalings with halo mass and redshift. We also discuss simple applications of these effects to galaxy samples with nonvanishing satellite fraction, where the stochasticity can again deviate strongly from the fiducial Poisson expectation. Overall, these effects affect the clustering of galaxies at a level of a few percent even on very large scales and need to be modeled properly if we want to extract high precision cosmological information from the upcoming galaxy redshift surveys.