On the other hand, this paper does prove that it is unlikely that the Perceptron Algorithm will run for too long on a perturbation of any given input instance. However, when one quantifies the tradeoff between "unlikely" and "run too long", one obtains an infinite expectation. The expectation of the square root of the running time is also infinite, but for all lower powers it is polynomial.