Why are Hinton's multilayer deep-learning networks stochastic?

First I'll sum up my intuitive (beginner) understanding of his deep-learning architecture. A short summary can be listened to on Coursera in the 5 minute video.

We start with several layers of autoencoder networks in an unsupervised fashion, to arrive to a good representation/compression of the problem itself. (Mind, compression is almost equivalent to intelligence, see for example the Hutter Prize).

Then we add the actual labels to the data, i.e. we start a gradient algorithm to tune the weights of our pre-trained network to arrive to a good prediction, in a supervised fashion. This is helpful because we started gradient training from a network which is already good at representing the problem, so we have less chance to get stuck in a simplistic local optima as simple multilayer networks do.

Why does using stochastic activation functions help in the whole process? We could do the same (with the same intuition above, at least) with deterministic autoencoder networks too, then applying gradient.