Hayden and Preskill's paper “Black holes as mirrors” - Classical model of black hole

If someone's read the "black holes as mirrors" paper by Hayden and Preskill which can be found here , Can you please explain to me how the probability of failure in the classical model of the black hole is upper bounded by $2^k2^{-s}$, $k$ is the length of Alice's message. $s$ is the number of bits Bob needs in order to decode the message after Alice has thrown it into the black hole.

I understand the random encoding of the n-bit strings gives rise to a probability of an accidental match (to an encoded message other than the right one) of an emitted bit as $2^{-s}$ in each position. However, how could you multiply this by $2^k$, when one of the messages is actually the right one. Shouldn't it be $2^k-1$? Even then it doesn't check out.

For example, say Alice sends a 2-bit message and the black hole is initially 8 bits long (before mixing). Say Bob has a mapping code book corresponding to the black hole internal dynamics. It so happens that the first 5 bits in all the four encoded 10-bit messages (corresponding to 4 possible messages that Alice can have) are zeros. If Bob collects the first 5 bits, it doesn't really tell him anything. Is the probability of failure 1? Or if he takes a random guess, is the probability of failure 0.75? However, $2^k2^{-s}$ evaluates to 0.125. So, it does not upper bound the probability of failure. Can you please find what's wrong in this interpretation?

On another note, $2^k2^{-s}$ isn't even lesser than $1$ if $s<k$ : it can't be a valid probability. However, nothing changes in the above analysis corresponding to $s<k$. How can this be?