Probability that one machine converted a code to 0

Question

There are four machines. M1, M2, M3 and M4. M1 produces a binary code with probability $\frac{1}{2}$ and code 1 with probability $\frac{1}{2}$ and passes it to machine 2. M2 either leaves the code alone or changes it to its complIment before passing it onto M3. M3 and M4 do the same procedure before producing the final output. It is known that M2, M3, and M4 changes the binary code with probability $\frac{1}{3}$. If the final output is given as 0, what is the probability that it was produced by M1?

I am really confused about how to do this problem because, from my understanding of this problem, it seems like we are being told to find the probability of A|B, where A is the probability that M1 converted the code to 0, given the final output is all 0(the condition B), right?

Now the probability of B happening can happen in multiple ways right? So if I enumerate it, it could be:

either M1 did not convert to 0, but M2,M3,M4 did either M1 did convert to 0, and M2,M3,M4 kept it as was .... ....

Right? But how do I move on from here?

Answer 1

You are correct, this is indeed a question of finding $A|B$ as you describe.

There are some shortcuts we could take for this problem specifically, but in the interest of being able to solve other problems like it, we can set it up using Bayes Theorem:

$$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$

Where A is the probability that the original output from M1 was 0, and B is the probability that the final output (after M1, M2, M3 and M4) is 0.

The probability of $A$ is clearly just $\frac{1}{2}$, but what about $P(B)$ and $P(B|A)$ ?

As you say, there are many ways for $B$ to occur. To find $P(B|A)$, let us consider all the possibilities when $A$ is true (that is, when M1 emits a 0). Let's break these possibilities up based on the number of flips performed collectively by M2, M3, and M4:

We could have zero flips, and the outcome would be zero:

$$P(\text{zero flips}) = \left(\frac{2}{3}\right)^3$$

One flip, and the outcome is one:

$$P(\text{one flip}) = {3 \choose 1}\left( \frac{2}{3}\right)^2\left(\frac{1}{3}\right)$$

Two flips, and the outcome is back to zero:

$$P(\text{two flips}) = {3 \choose 2}\left( \frac{2}{3}\right)\left(\frac{1}{3}\right)^2$$

And lastly three flips, in which case you're back to one:

$$P(\text{three flips}) = \left( \frac{1}{3}\right)^3$$

These are mutually exclusive events, and so we can add them to find the probability of either one happening. In this case we're after $P(B|A)$, which is the probability that the final output is zero, given that the M1 value is zero. All of the cases above are for when the M1 value is zero, so we just sum the cases that result in a zero:

$$P(B|A) = P(\text{zero flips and M1=0}) + P(\text{two flips and M1=0})$$

$$=\left(\frac{2}{3}\right)^3 + {3 \choose 2}\left( \frac{2}{3}\right)\left(\frac{1}{3}\right)^2$$

$$= \frac{14}{27}$$

A little more than half. Note that this is also the probability that the final output is the same as the value of M1, a fact we will use in a moment.

For $P(B)$, the total probability that the final output is zero, we have to consider the possibilities where M1=1. With the same process I used above, we would find that the $P(B)$ is:

$$P(B) =P(B|A) + P(B|\neg A) = \text{Probability of B when M1=0, plus the probability of B when M1=1}$$

Using the fact that we know the probability of M1 being the same as the final output is $\frac{14}{27}$:

$$P(B)=\frac{1}{2}\frac{14}{27} + \frac{1}{2}\frac{13}{27}$$ $$= \frac{1}{2}$$

Intuitively this makes perfect sense, and honestly, we could probably just have guessed that it was true - the M2,M3,M4 sequence has some probability to flip the bit, and since there's an even chance at 0 or 1 to go into it, there is an even chance of 0 or 1 coming out.

We now have everything we need for Bayes Theorem. Because it's sort of "symmetric" as we described above, it comes out pretty clean:

$$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ $$=\frac{\frac{14}{27}\frac{1}{2}}{\frac{1}{2}} = \frac{14}{27}$$

In case you're also a programmer, here's some python code which simulates this process, and might help you see it more clearly (if you're not a programmer, just ignore this bit):

import numpy as np
from numpy import logical_xor as xor
from numpy import logical_and as AND

n = 1000000

M1 = np.random.rand(n) < 1/2

M2 = xor(np.random.rand(n) < 1/3, M1)
M3 = xor(np.random.rand(n) < 1/3, M2)
M4 = xor(np.random.rand(n) < 1/3, M3)

print("Proportion of zeros in M1:", (n - M1.sum()) / n)
print("Proportion of zeros in M4:", (n - M4.sum()) / n)
print("Proportion of zeros in M4 which were also zero in M1:", AND(M1==False,M4==False).sum()/(n-M4.sum()))
print("14/27, just for clarity:", 14/27)

The output should look like (depending on some randomness):

Proportion of zeros in M1: 0.499809
Proportion of zeros in M4: 0.500528
Proportion of zeros in M4 which were also zero in M1: 0.5179350605760317
14/27, just for clarity: 0.5185185185185185