Probability of loss using a binary symmetric channel

Question

Today we talked about Information Theory and the binary symetric channel.

For newbies here is a little explanation :

For instance if I want to send a binary to someone :

The bit will be "flipped" with a "crossover probability" of p, and otherwise is received correctly.

Example :

Note that in order to reduce the probability of the "flip" we repeat the bit 2,3,4... times. Here we use a R3 encoding cause the bit is repeated 3 times. Then to decide the transmitted bit we choose the most popular in this packet of 3 bits (in this case).

Up to here it's ok but i'm struggling with a question of my homework :

Let's suppose we use a R3 encoding, what's the probability a bit will be flipped ?

Thanks !

Answer 1

R3 encoding is a pair of algorithms:

• Encoding: a bit $b \in \{0,1\}$ is encoded as the packet $bbb$.
• Decoding: a packet $xyz \in \{0,1\}^3$ is decoded as the majority bit (the bit occurring most often).

Since the situation is symmetric, in order to understand the transmission error, it suffices to consider the case $b = 0$. Suppose we encode the bit $0$. So we transmit the packet $000$. Every bit is flipped with probability $p$, and this gives us a distribution on the received packet $xyz$. Finally, a transmission error occurs if $xyz$ is decoded as $1$, that is, if the majority of $xyz$ is $1$.

Therefore, the transmission error is the probability of the following event:

If $x,y,z \in \{0,1\}$ are independent identically distributed bits such that $\Pr[x=1] = p$, what is the probability that the majority of bits in $x,y,z$ is $1$?

You can compute this probability by brute force.