1
$\begingroup$

I got stuck on this interesting question from one the probability app.

Alice would like to send Bob a secret four-digit binary message, e.g. 0000 or 0011, via the post office, but she's worried that her letter will be intercepted by a third party. Fortunately, Alice and Bob have a way of encrypting their messages: last time they met, they generated a secret one-time pad, which is a four-character sequence of Xs and underscores, e.g. XX_X. They'll use the pad to encrypt their message.

There are 2^4 possible pads: Alice chose one of them uniformly at random and shared it with Bob before they parted ways. They agreed on the following protocol: when Alice needs to send Bob a four-digit binary message, she'll encrypt it using the pad. Wherever the pad says X, she will flip the corresponding bit in the message (i.e. 1 is flipped to 0 and 0 is flipped to 1); she leaves the remainder of the message unchanged (i.e. in the places where the pad says _). She'll send the scrambled message in the mail, and Bob will use his copy of the pad to decipher it.

Eve is the spy reading Alice and Bob's mail. She knows the methodology behind the one-time pad, and she knows that Alice chose a pad uniformly at random. Furthermore, Eve believes there's a 30% chance that Alice's true (unscrambled) message will be 0000, a 60% chance that it will be 1111, and a 10% chance it'll be 0011.

Eve intercepts Alice's letter to Bob and finds the (scrambled) message 1110. Given what Eve has observed, what's the probability that Alice's true message to Bob is 1111?

$\endgroup$

1 Answer 1

3
$\begingroup$

If the X and the _ have the same probablity, and alice picks a pad at random, the probablity after Eve observed the message remain unchanged, so it is 60%.

Let $P(u1111|s1110)$ be the probabilty that the unscrambled message is 1111 when Eve sees 1110 so:

$P(u1111|s1110) = \frac{P(s1110|u1111).P(u1111)}{P(s1110|u1111).P(u1111)+P(s1110|u0000).P(u0000)+P(s1110|u0011).P(u0011)}$

$P(u1111) = 0.6 $

$P(u0000) = 0.3 $

$P(u0011) = 0.1 $

$P(s1110|u1111)$ is that alices chose the pad _ _ _ X so is $1/2^4$

$P(s1110|u0000)$ is that alices chose the pad X X X _ so is $1/2^4$

$P(s1110|u0011)$ is that alices chose the pad X X _ X so is $1/2^4$

$P(u1111|s1110) = \frac{1/2^4.P(u1111)}{1/2^4.P(u1111)+1/2^4.P(u0000)+1/2^4.P(u0011)}$

$P(u1111|s1110) = \frac{P(u1111)}{P(u1111)+P(u0000)+P(u0011)} = P(u1111) = 0.6$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .