If $E_{k_1}(p_1) = c_1$, what is the probability that there exists key $k_2$ such that $E_{k_2}(p_1) = c_1$? Let $k_1$ be a 56 bit DES key that performs $E_{k_1}(p_1) = c_1$. What is the probability that there exists another key $k_2$ such that $E_{k_2}(p_1) = c_1$?
DES is a block cipher with $b=64$-bit block width, and $w=56$-bit key width (ignoring key parity bits). An ideal model of a block cipher is that each key defines an independent, random-like permutation of the blocks. Under that model, if $E_{k_1}(p_1)=c_1$, then


For each key $k\ne k_1$ there is independent probability $u_1=2^{-b}=2^{-64}$ that $E_k(p_1)=c_1$
Hence for each key $k\ne k_1$ there is independent probability $v_1=1-u_1=1-2^{-b}=1-2^{-64}$ that $E_k(p_1)\ne c_1$
There are $n=2^b-1=2^{56}-1$ keys $k\ne k_1$, hence the probability $v$ that for each of these keys $E_k(p_1)\ne c_1$ is: $v={v_1}^n={(1-u_1)}^n=(1-2^{-64})^{(2^{56}-1)}$
Hence the desired probability $u$ that there exist any key $k\ne k_1$ such that $E_k(p_1)=c_1$ is: $u=1-v=1-{(1-u_1)}^n=1-(1-2^{-b})^{(2^w-1)}=1-(1-2^{-64})^{(2^{56}-1)}$
For integer $n&gt;0$ and real $\epsilon$, it holds that $(1-\epsilon)^n=1-n\,\epsilon+O((n\,\epsilon)^2)$
Therefore, for $m\gg1$ and $m\,|\epsilon|\ll1$, it holds that $1-(1-\epsilon)^{(m-1)}\approx m\,\epsilon$
Applying the approximation in (6) to the expression in (4), with $\epsilon=u_1=2^{-b}=2^{-64}$ and $m=2^w=2^{56}$, it comes
$$u\approx2^{w-b}=2^{-8}\approx0.39\%$$




Note per Ilmari Karonen's comment: the approximations made after step (4) fail when the key width $w$ approaches or exceeds the block size $b$, as would be the case for 3DES ($b=64$ and $w\in\{112,168\}$) or AES ($b=128$ and $w\in\{128,192,256\}$). We then want a better approximation. We can use ${v_1}^n=\exp(n\log(v_1))$ and $\log(1-\epsilon)=-\epsilon+O(\epsilon^2)$, giving at step (7) $u\approx1-\exp(-2^{w-b})$, valid for $b\ge20$ and $w\ge20$. That's mathematically more accurate, but numerical accuracy requires extended precision when $b-w$ is positive and sizable, which is dangerously close to hold for $b-w=8$ in the question.

Note: Our model of DES is imperfect, in particular when we consider many plaintexts $p$ : DES has additional properties that our model misses. In particular the complementation property $E_\overline k(\overline p)=\overline{E_k(p)}$; that the permutation of blocks for any particular key is even; existence of weak keys. More generally, DES is a particular block cipher (a Feistel cipher within a few cryptographically neutral bit permutations). But given that in the context there is as single plaintext $p_1$ considered, and that DES is a fair cipher (except for its last-century key and block size), it is reasonable to believe that our model is good enough for an excellent approximation of $u$ for random choice of $k_1$ and $c_1$.

Note: with DES a fixed cipher, we can no longer talk of the desired probability $u$ when the whole of both $k_1$ and $c_1$ is fixed. I conjecture that the approximation still holds when $c_1$ and all but say 16 bits of $k_1$ is fixed, but wonder what happens when $k_1$ is fixed to some particular values (like all-zero, which is a weak key).