To clear your doubt, consider a random key of length $l(n)$ where l in a polynomial in the size of message bits $n$. This is the source of stochastic/probabilistic/randomization to the polynomial encryption algorithm.
As an example, consider a one-time pad with $l(n) = 3*n$ key length and a message of 2 bits ($n = 2$).
Let the random bits of the $k = 110100$ and $m$ = 01
then $Enc_k(m)$ = 01 XOR 11 = 10 at first.
If you choose to encrypt m again,
then $Enc_k(m)$ = 01 XOR 01 = 00
Thus, the cipher-text has changed. This is a probabilistic polynomial time encryption algorithm.
If you use this 6 bit key repeatedly on a message of size 6 bits and you use it every time to encrypt $m$ using the one time pad. Then you will get a deterministic polynomial time encryption algorithm. Note how the key has become non random and hence the probabilistic becomes deterministic.