How does this trick for estimating bit error rate break down?

Question

Imagine you are receiving a message over and over via a lossy data path. The path causes bit errors but does not affect the length of the message (or shift any bits). You don't know the actual message but you will get many copies of it so you can reconstruct it (e.g. with a median filter). You want to estimate the error rate of the channel by observing the sequence of messages.

I solved this problem a while ago by "learning" the expected message and counting errors as $\text{population}(\text{learned} \oplus \text{current})$. Today it struck me that the learning component may be unnecessary: For low error rates you could approximate the rate as $\frac{\text{population}(\text{previous} \oplus \text{current})}{2}$. That is effectively measuring the previous frame against the current and vice versa simultaneously. At low error rates half of the errors can be expected to be due to $\text{previous}$ and half due to $\text{current}$.

My assumption about the independence of the errors in $\text{previous}$ and $\text{current}$ breaks down as the error rate increases and repeated errors become more likely. How does the actual error rate impact the rate given by my estimation?

Answer 1

I believe I now follow enough to understand that your alternative estimate is wrong, because if the two messages are independent (in the probability sense), then the expected number of observed differences in two messages won't be twice the expected difference between the learned message and the current one.

It won't even be twice the expected difference between the actual message and the current one.

That's because both the current and previous message can flip the same bit. You have to subtract that off the sum.

If we assume that the probability that a bit gets flipped is always $p$ (here $p$ is a population - in the statistical sense - parameter) and all flips are mutually independent, then the expected probability two corresponding bits differ between two messages is

\begin{eqnarray} P(\text{two messages disagree on a given bit}) &=& 1-P(\text{two messages agree there}) \\ &=& 1- P(\text{both unflipped or both flipped}) \\ &=& 1-[(1-p)^2 + p^2] \\ &=& 1-[1 - 2p +2p^2]\\ &=& 2p-2p^2 \end{eqnarray}

So you have to solve a quadratic: $2p^2 - 2p +q = 0$

which implies that $p = \frac{1}{2} \pm \sqrt{\frac{1}{4}-\frac{q}{2}}$.

Your question implies the error rate is low. If you know it's below 0.5, you take the smaller answer:

$p = \frac{1}{2} - \sqrt{\frac{1}{4}-\frac{q}{2}}$

That in turn suggests the MLE

$\hat p = \frac{1}{2} - \sqrt{\frac{1}{4}-\frac{\hat q}{2}}$

Let me see if I can translate that into your terms:

$\frac{1}{2}-\sqrt{\frac{1}{4}-\frac{\text{population}(\text{previous} \oplus \text{current})}{2\text{size}(\text{current})}}$

is the estimate of the per bit error rate. You'd then multiply the whole expression by $\text{size}(\text{current})$ to estimate $\text{population}(\text{actual} \oplus \text{current})$.

Incidentally, it should be possible to put standard errors on/give confidence intervals for the various estimates of quantities if you need them. (As $q$ gets anywhere twoard 0.5, the uncertainty in $p$ grows rapidly.)