Fast algorithms that work on some large percentage of possible inputs
Not quite what you're looking for but the concept of a randomized approximation scheme (RAS) is closely related and very widely studied.  This is an algorithm for computing a (numerical) quantity $f(x)$ given an input&nbsp;$x$ and an error tolerance&nbsp;$\varepsilon$. With probability at least&nbsp;$\tfrac23$, the algorithm returns a value&nbsp;$\hat{f}$ such that $(1-\varepsilon)f(x)\leq\hat{f}\leq(1-\varepsilon)f(x)$. With probability at most&nbsp;$\tfrac13$, the algorithm either returns an answer outside that range or says, "Uh, I dunno." If the algorithm runs in time polynomial in $|x|$ (the length of the input) and&nbsp;$\varepsilon^{-1}$, it's called a fully polynomial randomized approximation scheme (FPRAS).

Only succeeding with probability at least&nbsp;$\tfrac23$ sounds pretty terrible&nbsp;&ndash; "Oh, wow, it's wrong one time out of every three!". However, it's easy to boost that to any satisfactory probability by running the algorithm repeatedly and taking the median answer (counting, "Uh, I dunno" as&nbsp;$\infty$).  By a Chernoff bound, taking the median of $O(\log |x|)$ runs gives failure probability polynomial in&nbsp;$|x|^{-1}$ and taking the median of polynomially many runs gives exponentially small failure probability.