0
$\begingroup$

We are sending a one bit message to someone. There is a 60% chance the message bit will be a 0. When transmitting the message there is a 3% chance a 1 will become a 0. There is a 5% chance a 0 will become 1 when transmitting.

Lets say we take our original message duplicate the bit 3times ie 1 -> [1,1,1] we then transmit that message to someone. What is the probability they will receive the incorrect message using majority rule to decide what the correct bit in the message was?

Now I am very bad at statistics but I created an experiment to try to determine this value with the following python code Library:

import random as r
import numpy as np
import matplotlib
import matplotlib.pyplot as plt


#p0 is the probability a bit will be 0 and size is the size of the message you wish to create
def createmessage(p0,size):
    rands = np.random.rand(size)
    msg = []
    #we parse through a big numpy array of the rands to ammortize costs in efficent c-code
    for rand in rands:
        if rand <= p0:
            msg.append(0)
        else:
            msg.append(1)
    return msg
#e0 probability that a 0 will be recieved as 1. e1 is the probability a 1 will be recieved as a 0
def transmitmessage(e0,e1,source):
    received = source.copy()
    rands = np.random.random(len(source))
    msg = []
    index = 0
    #we ammortize costs again and modify a copied version of our source
    for bit in source:
        if bool(bit):
            if rands[index] <= e1:
                received[index] = 0
        else:
            if rands[index] <= e0:
                received[index] = 1
        index+=1
    return received

The experiment:

import random as r
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from lab2lib import createmessage,transmitmessage

samplesize = 100000
p0 = 0.6
e0 = 0.05
e1 = 0.03
message = createmessage(p0,samplesize)
redundancy = []
for bit in message:
    for x in range(3):
        redundancy.append(bit)

received = transmitmessage(e0,e1,redundancy)

failures = 0
index = 0
#for every bit in our message we had an error if the bit in the source message is not equal to the bit in the recieved message
for index in range(0,len(message),3):
    majoritybit = -1
    if received[index]+received[index+1]+received[index+2] >= 2:
        majoritybit = 1
    else:
        majoritybit = 0
    if majoritybit != message[index//3]:
        failures+=1
        print(f"Bits in dispute,  Source at index {index}: {message[index//3]} 3 bits that disagree [{received[index]},{received[index+1]},{received[index+2]}]")


print(f"failures:{failures}")
print(f"failure rate: {failures/samplesize}")

My answers im getting is like this

These answers are not lining up with someone else in my class who is doing the same experiment but we can't find fault in either person code. So I am here beseeching the stat gods.

$\endgroup$
2
  • $\begingroup$ would it be related to the Shannon Limit? $\endgroup$
    – user78229
    Commented Oct 1, 2020 at 1:09
  • $\begingroup$ Our method is briefly mentioned in the wikipedia article but it seems the shannon limit has more to do with a more advanced and better technique then just doing best 2 out of 3:!see $\endgroup$ Commented Oct 1, 2020 at 1:15

1 Answer 1

0
$\begingroup$

There is a tiny mistake in this line of code:

for index in range(0,len(message),3):

You don't want to look every 3 bits of the original message, you want to look every 3 bits of the redundant version. So, to get the correct answer we replace this line by:

for index in range(0,len(redundancy), 3):

The failure rate becomes 0.00532. Now, is this the correct result? We can use the info you provided in the first paragraph to calculate the expected error rate:

$$\epsilon = 0.60\cdot0.05+0.40\cdot0.03\approx4.2\%$$

Now, what is the chance that a bit is flipped and is not corrected (that is, the actual failure rate)?

$$p=P(\text{2 errors})+P(\text{3 errors})=\binom32\epsilon^2+\epsilon^3\approx0.00537$$

That is pretty close to the simulation answer, so we can be confident that now the simulation works correctly.

$\endgroup$
1
  • $\begingroup$ Thank you so much! It's always the small mistakes. I was so worried with the random number generation and decision making for mistakes I completely overlooked such a silly mistake. $\endgroup$ Commented Oct 1, 2020 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.