Modern work by Jarzynski, Crooks, and others shows that a more accurate statement of the second law is $\langle e^{-\beta\Delta S}\rangle = 0$.
If we use Jensen's inequality, and expand this to first order, we find
$\begin{align}
\langle e^{-\beta\Delta S}\rangle &\geq e^{-\langle \beta \Delta S \rangle}\\
1 &= 1-\langle\beta\Delta S\rangle + O(\beta^2 \Delta S^2)
\end{align}$
which shows $\langle \Delta S \rangle \geq 0$
In the thermodynamic limit (where $\Delta S$ is big), the classic version of the second law becomes true (we can drop the expectation brackets), but for small systems, you need to consider the modern form.
This comes from a more fundamental result that relates the probability of positive changes in entropy along a trajectory and negative entropy changes in the time reversed trajectory
$\frac{\mathbf{P}_+(+\Delta S)}{\mathbf{P}_-(-\Delta S)} = e^{+\beta\Delta S }$
Things can occur that generate negative entropy, and things can occur that generate positive entropy, but on average we expect them to have positive change in entropy.