The term "probabilistic encryption" is typically used in reference to public key encryption algorithms; however various symmetric key encryption algorithms achieve a similar property (e.g., block ciphers when used in a chaining mode such as CBC), and stream ciphers such as Freestyle[1] which are inherently random.
To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.
The first provably-secure probabilistic public-key encryption scheme was proposed by Shafi Goldwasser and Silvio Micali, based on the hardness of the quadratic residuosity problem and had a message expansion factor equal to the public key size.
To combat this attack, public key encryption schemes must incorporate an element of randomness, ensuring that each plaintext maps into one of a large number of possible ciphertexts.
An intuitive approach to converting a deterministic encryption scheme into a probabilistic one is to simply pad the plaintext with a random string before encrypting with the deterministic algorithm.
Conversely, decryption involves applying a deterministic algorithm and ignoring the random padding.
In other words, the message expansion factor is equal to the public key size.