If a probabilistic encryption algorithm is used, how does decryption return the correct message? Given a key $k$ and a plaintext $p$, a deterministic encryption algorithm will return a ciphertext $c_1$. In a second trial, I run the same key and plaintext $p$ through the encryption algorithm and get ciphertext $c_2$ from the first trial. $c_1$ and $c_2$ are equivalent, so running the decryption algorithm on $c_1$ and $c_2$ both return $p$.

However, if a probabilistic encryption is used instead to encrypt $p$, the algorithm will run twice and return two different ciphertexts $c_1$ and $c_2$.

How does $Dec(c_1) = p$ and $Dec(c_2) = p$?? If $c_1$ and $c_2$ are different, should decryption return different results?
In a probabilistic encryption scheme, for every plaintext there is more than one possible ciphertext.

Here's an example—with lots of details not related to your question omitted, so don't take these scissors and try running with this at home!

The recipient knows the secret ~256-bit number $r$ of times that a base point $B$ must be added to itself to yield a public point $R = B + B + \cdots + B = [r]B$ on some standard elliptic curve, say Curve25519.  (There's a shortcut to computing $[r]B$ so you only have to do a few thousand arithmetic operations and not a mindbogglingly unimaginable number.)

To conceal a message $m$ using the public point $R$, the sender:


picks a secret ~256-bit number $s$ uniformly at random;
adds $B$ to itself $s$ times to obtain $S = [s]B$;
adds $R$ to itself $s$ times to obtain $[s]R$;
computes $k = H([s]R)$, a secret key;
computes $c = \operatorname{crypto\_secretbox\_xsalsa20poly1305}(k, 0, m)$, the authenticated ciphertext under the symmetric key $k$ and nonce 0; and
transmits $(S, c)$ to the recipient.


The recipient, on receipt of $(S, c)$, then:


computes $[r]S = [r\cdot s]B = [s\cdot r]B = [s]R$;
computes $k = H([r]S) = H([s]R)$, the same secret key as the sender derived;
computes $m = \operatorname{crypto\_secretbox\_xsalsa20poly1305\_open}(k, 0, c)$, or rejects if forged.


There are roughly $2^{256}$ possible sender secrets $s$ that could be used to encrypt the message, and they all work for any message $m$, so in this cryptosystem, for any message $m$ there are about $2^{256}$ distinct ciphertexts that have $m$ as the corresponding plaintext.

This is not simply an artificial example.  To meet the standard notion of security for public-key encryption, indistinguishability under adaptive chosen-ciphertext attack, there must be many ciphertexts for any given plaintext, randomly chosen by the sender.  Otherwise, an adversary without knowledge of the private decryption key can easily tell whether a challenge ciphertext conceals one of two (or three, or $n$) possible plaintexts by encrypting the candidate plaintexts and comparing the resulting ciphertexts to the challenge.  This implies that the minimum number of distinct ciphertexts for each plaintext must be around $2^{192}$ to give confidence in security against multi-target attacks.

There are also probabilistic symmetric ciphers, like AES-CBC with randomly chosen IVs affixed to the ciphertext, or crypto_secretbox_xsalsa20poly1305 with randomly chosen nonces affixed to the ciphertext.  In this case, the randomization serves to prevent the same message content at different times from leading to the same ciphertext and enabling an adversary to recognize repeated messages.

Randomization per se is not always necessary in the symmetric setting: it is sufficient to deterministically keep state for crypto_secretbox_xsalsa20poly1305 and transmit each successive message with a count of the number of messages sent so far, for instance.  But in some cases like AES-CBC it is obligatory—though of course you could use a secret pseudorandom function of the message sequence number, such as $\operatorname{AES}_k(\mathit{seqno})$, to choose the AES-CBC IV.