We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the
complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined from $\mathsf{PTIME}$.

Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in $\mathsf{BPFO}$, the probabilistic version of first-order logic, but not in $\mathsf{C}^\omega_{\infty,\omega}$, finite variable infinitary logic with counting. This implies that many of the standard logics of finite model theory, like transitive closure logic and fixed-point logic, both with and without counting, cannot be derandomised. We prove similar results for ordered structures and structures with an addition relation, showing that
certain uniform variants of $\mathsf{AC}^0$ bounded-depth polynomial sized circuits) cannot be derandomised. These results are in contrast to the general belief that most standard complexity classes
can be derandomised.

Finally, we note that $\mathsf{BPIFP+C}$, the probabilistic version of fixed-point logic with counting, captures the complexity class $\mathsf{BPP}$, even on unordered structures.

Journal version including additional proofs.

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the
complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined from $\mathsf{PTIME}$.

Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in $\mathsf{BPFO}$, the probabilistic version of first-order logic, but not in $\mathsf{C}^\omega_{\infty,\omega}$, finite variable infinitary logic with counting. This implies that many of the standard logics of finite model theory, like transitive closure logic and fixed-point logic, both with and without counting, cannot be derandomised. We prove similar results for ordered structures and structures with an addition relation, showing that
certain uniform variants of $\mathsf{AC}^0$ bounded-depth polynomial sized circuits) cannot be derandomised. These results are in contrast to the general belief that most standard complexity classes
can be derandomised.

Finally, we note that $\mathsf{BPIFP+C}$, the probabilistic version of fixed-point logic with counting, captures the complexity class $\mathsf{BPP}$, even on unordered structures.