# Probability of loss using a binary symmetric channel

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 !

• If you are stuck, try writing out all the cases, the probability that each one occurs, and then calculate the probability of incorrect decoding by summing things up. There are not that many for $R_3$! You can be systematic and treat things like $000 \to 100, 000 \to 010, 000 \to 001$ together. – Lorenzo Najt Sep 22 '20 at 20:18

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.

• Ho thanks I was working with binomial theoreme but I'll try your solution thanks ! – Théo Exagon Sep 24 '20 at 19:18