Differential Privacy of the Laplace mechanism with non-deterministic function
The Laplace mechanism only works for deterministic $f$, because the notion of &quot;sensitivity&quot; (the $\Delta f$ in the formulas above) isn't well-defined for random functions. $\Delta f$ is the maximum difference between $f(x)$ and $f(y)$, for neighboring $x$ and $f$. If $f$ is a random function, then that notion of &quot;difference&quot; becomes much more complicated to capture, so in general, you simply assume that $f$ is deterministic.
To extend this to the case where $f$ is random, you could define $\Delta f$ to be the maximum difference between a possible output of $f(x)$ and a possible output of $f(y)$, for all possible values of the random bits used by $f$. That would still allow you to say $\frac{||f(x)-f(y)||}{\Delta f}\le1$. But that doesn't work if that value is unbounded (for example, if $f$ implicitly adds Gaussian noise to the result of the computation), and that's a loose approximation in general; so it's pretty much never done.